<p>Let <span class="math-container">$P$</span> be a poset and <span class="math-container">$L$</span> a linear extension of <span class="math-container">$P$</span>. We say <span class="math-container">$(x,y)$</span> is a <em>jump</em> in <span class="math-container">$L$</span> if <span class="math-container">$x$</span> and <span class="math-container">$y$</span> are uncomparable in <span class="math-container">$P$</span> and there is no <span class="math-container">$z$</span> such that <span class="math-container">$x \leq_L z \leq_L y$</span>. Given a poset <span class="math-container">$P$</span> and an integer <span class="math-container">$k$</span>, it is NP-hard to decide whether there is a linear extension with at most <span class="math-container">$k$</span> jumps. This is know as the Jump Number Problem. See, for example, this paper by Bouchitte and Habib:</p>
<p><em>Bouchitte, Vincent; Habib, Michel</em>, <a href="https://doi.org/10.1007/BF00337693" rel="noreferrer"><strong>NP-completeness properties about linear extensions</strong></a>, Order 4, No. 1-3, 143-154 (1987). <a href="https://zbmath.org/?q=an:0627.06005" rel="noreferrer">ZBL0627.06005</a>.</p>
<p>There are other problems which ask for extensions with some properties. For instance, given posets <span class="math-container">$P$</span> and <span class="math-container">$Q$</span>, one may be interested in finding a linear extension of <span class="math-container">$P$</span> that disagrees with <span class="math-container">$Q$</span> as much as possible. This problem has some interesting applications and it has been shown to be NP-hard:</p>
<p><em>da Silva, Rodrigo Ferreira; Urrutia, Sebastián; dos Santos, Vinícius Fernandes</em>, <a href="https://doi.org/10.1016/j.tcs.2018.07.012" rel="noreferrer"><strong>One-sided weak dominance drawing</strong></a>, Theor. Comput. Sci. 757, 36-43 (2019). <a href="https://zbmath.org/?q=an:1422.68186" rel="noreferrer">ZBL1422.68186</a>.</p>

CC BY-SA 4.0
2023-03-01T04:43:38.147Z
2023-03-01T04:43:38.147Z
Vinicius dos Santos
<p>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.</p>
<p>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.</p>
<p>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?</p>

CC BY-SA 4.0
2023-02-27T09:59:47.837Z
Typing "NP-complete poset" on google seems to give many examples of such problems.
Denis
CC BY-SA 4.0
2023-02-28T07:24:35.507Z
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$.
Max Flow
CC BY-SA 4.0
2023-03-01T04:47:53.907Z
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.
Vinicius dos Santos
<np-hardness><np-complete>
NP-complete problems on posets?
Ctenochaetus
# NP-complete problems on posets?

(Asked by: username_0 on 2023-02-27)

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?

**Tags:** np-hardness, np-complete
> **Comments:**
> **username_1**: Typing "NP-complete poset" on google seems to give many examples of such problems.  
> **username_2**: 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$.  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_3 on 2023-03-01. Score: 5 | Accepted answer

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**](https://doi.org/10.1007/BF00337693), Order 4, No. 1-3, 143-154 (1987). [ZBL0627.06005](https://zbmath.org/?q=an:0627.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**](https://doi.org/10.1016/j.tcs.2018.07.012), Theor. Comput. Sci. 757, 36-43 (2019). [ZBL1422.68186](https://zbmath.org/?q=an:1422.68186).


---

