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
    Commented Feb 27, 2023 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
    Commented Feb 28, 2023 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
    Commented Mar 1, 2023 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 you have read our privacy policy.

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