Minimizing the maximum bump cost in linear extensions of a poset

A linear extension of a poset P=(X,?) is a permutation x ₁,x ₂,…,x _|X| of X such that i<j whenever x _i ?x _j . For a given poset P=(X,?) and a cost function c(x,y) defined on X×X, we want to find a linear extension of P such that maximum cost is as small as possible. For the general case, it is NP-complete. In this paper we consider the linear extension problem with the assumption that c(x,y)=0 whenever x and y are incomparable. First, we prove the discussed problem is polynomially solvable for a special poset. And then, we present a polynomial algorithm to obtain an approximate solution.