3
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Typing "NP-complete poset" on google seems to give many examples of such problems. $\endgroup$
    – Denis
    Feb 27 at 9:59
  • $\begingroup$ 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$. $\endgroup$
    – Max Flow
    Feb 28 at 7:24
  • 1
    $\begingroup$ 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. $\endgroup$
    – Vinicius dos Santos
    Mar 1 at 4:47

1 Answer 1

Reset to default
5
$\begingroup$

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:

Bouchitte, Vincent; Habib, Michel, NP-completeness properties about linear extensions, Order 4, No. 1-3, 143-154 (1987). ZBL0627.06005.

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:

da Silva, Rodrigo Ferreira; Urrutia, Sebastián; dos Santos, Vinícius Fernandes, One-sided weak dominance drawing, Theor. Comput. Sci. 757, 36-43 (2019). ZBL1422.68186.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.