# NP-complete problems on posets?

I'm in the midst of some doctoral research and trying to figure out a particularly tricky reduction. I think my best shot is to reduce from an NP-complete problem on posets, if one exists.

I did some digging but did not find anything NP-complete; I found a couple of items that are FPT with respect to the diameter of the poset, but I don't think that's terribly helpful in my search.

I know I may not find anything here, but I figure it doesn't hurt to ask. Does anyone know of any NP-complete problems on posets?

• Typing "NP-complete poset" on google seems to give many examples of such problems. Feb 27 at 9:59
• There is the partial ordering problem: Given a finite set $A$ and $c \colon A^2 \to \mathbb{Z}$, find the characteristic vector $x \colon A^2 \to \{0,1\}$ of a partial order $x^{-1}(1)$ that minimizes $c^T x$. Feb 28 at 7:24
• Being "FPT with respect to the diameter of the poset" does not contradict the problem being NP-hard. Indeed, most parameterized algorithms are developed to tackle NP-hard problems. The most likely scenario in case you mentioned is that the problem is NP-hard in general but tractable in posets with bounded width. Mar 1 at 4:47

Let $$P$$ be a poset and $$L$$ a linear extension of $$P$$. We say $$(x,y)$$ is a jump in $$L$$ if $$x$$ and $$y$$ are uncomparable in $$P$$ and there is no $$z$$ such that $$x \leq_L z \leq_L y$$. Given a poset $$P$$ and an integer $$k$$, it is NP-hard to decide whether there is a linear extension with at most $$k$$ jumps. This is know as the Jump Number Problem. See, for example, this paper by Bouchitte and Habib:
There are other problems which ask for extensions with some properties. For instance, given posets $$P$$ and $$Q$$, one may be interested in finding a linear extension of $$P$$ that disagrees with $$Q$$ as much as possible. This problem has some interesting applications and it has been shown to be NP-hard: