<p>Note that if you relax the problem by allowing $f$ to be arbitrary (not necessarily bijective), then it becomes polynomial. The algorithm proceeds similarly to topological sorting: you number the vertices one by one, maintaining the set $U$ of unnumbered vertices whose in-neighbors have been numbered. Whenever possible, you choose a vertex $x \in U$ and number it with the <em>smallest</em> element of $S(x)$ greater than the numbers of its in-neighbors. It is not hard to see that an instance $(G,S)$ has a solution iff the previous algorithm run on $(G,S)$ ends with all vertices numbered.</p>

CC BY-SA 3.0
2013-09-19T14:01:55.373Z
Fair point, this relaxation means that a greedy heuristic works, and that's even in the case where $n$ is not the number of vertices but an arbitrary value. Do we agree that in the latter case, where injectivity and surjectivity are not equivalent anymore, you would need to relax both (and not just one) for the greedy heuristic to work?
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2013-09-19T13:56:37.073Z
2013-09-19T16:50:16.307Z
2013-09-19T16:50:16.307Z
Super0
<p>A trivial observation is that if $|S(x)| \le 2$ for all $x$, then this problem is solvable in polynomial time, by reduction to 2SAT.</p>

<p>Here's how.  Introduce a variable $v_{x,i}$ for each vertex $x$ and each $i$ such that $i \in S(x)$.  For each pair $x,y$ of vertices, if there is a path from $x$ to $y$, we get some constraints: if $i\in S(x)$, $j\in S(y)$, and $i&gt;j$, then we get the constraint $\neg v_{x,i} \lor \neg v_{y,j}$.  Bijectivity gives us another set of constraints: for each pair $x,y$ of vertices with $x\ne y$, if $i \in S(x)$ and $i \in S(y)$, we add $\neg v_{x,i} \lor \neg v_{y,i}$.  Finally, the requirement that each vertex must be assigned a label gives us yet another set of constraints: for each $x$, if $S(x)=\{i,j\}$, we get the constraint $v_{x,i} \lor v_{x,j}$.  (Note that only the last set of constraints exploit the promise that $|S(x)|\le 2$ for each $x$.)</p>

<p>I realize this observation won't help you in your particular situation.  Sorry about that.</p>

CC BY-SA 3.0
2013-09-19T19:42:14.067Z
2013-09-19T19:42:14.067Z
D.W.
<p>I think this problem is NP-hard. I try to sketch a reduction from MinSAT. In the MinSAT problem we are given a CNF and our goal is to minimize the number of satisfied clauses. This problem is NP-hard, see e.g., <a href="http://epubs.siam.org/doi/abs/10.1137/S0895480191220836?journalCode=sjdmec">http://epubs.siam.org/doi/abs/10.1137/S0895480191220836?journalCode=sjdmec</a></p>

<p>Divide the vertices into two groups - some will represent literals, the others clauses, so $n=2v+c$ where $v$ is the number of variables of the CNF (usualy denoted by $n$) and $c$ is the number of clauses. Direct an edge from each literal-vertex to the clause-vertex where it occurs. Define $S$ for a literal-vertex that represents $x_i$ as $\{i,i+v+k\}$ (where $k$ is an arbitrary parameter), so either $f(x_i)=i$ and $f(\bar x_i)=i+v+k$ or $f(\bar x_i)=i$ and $f(x_i)=i+v+k$. For each clause-vertix, let $S=\{v+1,\ldots,v+k,2v+k+1,\ldots,n\}$, so $k$ of the clause-vertices are ``small''.</p>

<p>Now the CNF has an assignment where at least $k$ clauses are false if and only if your problem can be solved for the above instance.  The MinSAT problem is exactly to test whether a CNF formula $\varphi$ has an assignment that makes at least $k$ clauses false, so this shows that your problem is NP-hard.</p>

<p>To help you understand this reduction, here's the intuition: small labels ($1,2,\dots,v+k$) correspond to the truth value False, and large labels ($v+k+1,\dots,2v+k$) correspond to True.  The constraints for literal-vertices ensure that each $x_i$ is either True or False and that $\overline{x_i}$ has the opposite truth value.  The edges ensure that if any literal is True, then all clause-vertices containing it are assigned True as well.  (In contrast, if all literals in a clause are assigned False, then this graph structure allows the clause-vertex to be assigned either False or True.)  Finally, the choice of $k$ ensures that $k$ of the clause-vertices are assigned False and $c-k$ of them are assigned True.  So, if there is a valid topological sort of this graph, then there is an assignment to the variables that makes at least $k$ of the clauses of $\varphi$ false (all of the clause-vertices that were assigned False, plus possibly some of the ones that were assigned True).  Conversely, if there is an assignment to the variables that makes at least $k$ of the clauses of $\varphi$ false, then there is a valid topological sort of this graph (we fill in the labels for the literal-vertices in the obvious way; and for each clause of $\varphi$ that is true, we give its corresponding clause-vertex a label that corresponds to True; the other clause-vertices can receive labels corresponding to an arbitrary truth value).</p>

CC BY-SA 3.0
2013-09-19T14:03:34.317Z
Thanks for your answer! I'm trying to understand your sketch. Would you mind explaining what $k$ is?
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2013-09-19T18:00:19.350Z
@a3nm: k is a parameter that is given for the MinSAT input.
domotorp
CC BY-SA 3.0
2013-09-19T18:02:32.703Z
@Marzio: SAT is not equivalent to MinSAT with $k=|c|$, as in the latter problem we would require all clauses to be false. Your $\phi$ does not have an all clauses false assignment. Of course this does not prove my reduction is correct...
domotorp
CC BY-SA 3.0
2013-09-19T20:22:25.517Z
This is a gorgeous reduction!  @a3nm, I've suggested an edit to the answer to explain domotorp's elegant reduction in more detail; if it is approved, hopefully it will help you understand the ideas more clearly.
D.W.
CC BY-SA 3.0
2013-09-19T22:25:26.227Z
@domotorp: you are right, I completely missed what MinSAT is. Nice reduction!!!
Marzio De Biasi
CC BY-SA 3.0
2013-09-19T22:47:55.170Z
@MarzioDeBiasi, Are you sure?  It looks right to me.  $1,2,\dots,v$ correspond to False (for literals), $v+1,\dots,v+k$ corresponds to False (for clauses), and $v+k+1,\dots,2v+k$ correspond to True (for literals).  $2v+k+1,\dots,2v+c$ is slightly tricky: I said that it corresponds to True (for clauses), but maybe a better way to say it is that could correspond to the clause being either true or false.  All true clauses (i.e., clauses where at least one literal is true) will get a label from $2v+k+1,\dots,2v+c$, but some false clauses (where all literals are false) might get those labels too.
D.W.
CC BY-SA 3.0
2013-09-19T23:57:21.027Z
@D.W.: ok (I only meant small labels for literals). A clause can take the value of false (v+1,...,v+k) iif all its literals are false (1..v). If a clause contains a true literal (v+k+1,..,2v+k) then it must take a large value (2v+k+1,...,2v+c). Very nice reduction!!
Marzio De Biasi
CC BY-SA 3.0
2013-09-23T09:07:23.337Z
Yes, I understand the argument now. That's a beautiful reduction. Thanks a lot!
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2013-09-19T13:31:54.497Z
2013-09-19T20:43:48.693Z
2013-09-19T20:43:48.693Z
domotorp
<p>I am given as input a DAG $G$ of $n$ vertices where each vertex $x$ is additionally labeled with some $S(x) \subseteq \{1, \ldots, n\}$.</p>

<p>A topological sort of $G$ is a bijection $f$ from the vertices of $G$ to $\{1, \ldots, n\}$ such that for all $x$, $y$, if there is a path from $x$ to $y$ in $G$ then $f(x) \leq f(y)$. I wish to decide whether there exists a topological sort of $G$ such that for all $x$, $f(x) \in S(x)$.</p>

<p>What is the complexity of this decision problem?</p>

<p>[Notes: Clearly this is in NP. If you look at the graph of allowed vertex/position pairs, with undirected edges between pairings that conflict because they violate the order, you get a graph of disjoint cliques where you want to pick at most one pair per clique, at most one pair per position and at most one pair per vertex -- it seems related to 3-dimensional matching but I can't see if it is still hard with the additional structure of this specific problem.]</p>

<sorting><directed-acyclic-graph><partial-order><order-theory><topological-sorting>
Complexity of topological sort with constrained positions
Antoine Amarilli 'a3nm'
# Complexity of topological sort with constrained positions

(Asked by: username_0 on 2013-09-18)

I am given as input a DAG $G$ of $n$ vertices where each vertex $x$ is additionally labeled with some $S(x) \subseteq \{1, \ldots, n\}$.

A topological sort of $G$ is a bijection $f$ from the vertices of $G$ to $\{1, \ldots, n\}$ such that for all $x$, $y$, if there is a path from $x$ to $y$ in $G$ then $f(x) \leq f(y)$. I wish to decide whether there exists a topological sort of $G$ such that for all $x$, $f(x) \in S(x)$.

What is the complexity of this decision problem?

[Notes: Clearly this is in NP. If you look at the graph of allowed vertex/position pairs, with undirected edges between pairings that conflict because they violate the order, you get a graph of disjoint cliques where you want to pick at most one pair per clique, at most one pair per position and at most one pair per vertex -- it seems related to 3-dimensional matching but I can't see if it is still hard with the additional structure of this specific problem.]

**Tags:** sorting, directed-acyclic-graph, partial-order, order-theory, topological-sorting

---

## 3 answers

### Answer by username_3 on 2013-09-19. Score: 9 | Accepted answer

I think this problem is NP-hard. I try to sketch a reduction from MinSAT. In the MinSAT problem we are given a CNF and our goal is to minimize the number of satisfied clauses. This problem is NP-hard, see e.g., <http://epubs.siam.org/doi/abs/10.1137/S0895480191220836?journalCode=sjdmec>

Divide the vertices into two groups - some will represent literals, the others clauses, so $n=2v+c$ where $v$ is the number of variables of the CNF (usualy denoted by $n$) and $c$ is the number of clauses. Direct an edge from each literal-vertex to the clause-vertex where it occurs. Define $S$ for a literal-vertex that represents $x\_i$ as $\{i,i+v+k\}$ (where $k$ is an arbitrary parameter), so either $f(x\_i)=i$ and $f(\bar x\_i)=i+v+k$ or $f(\bar x\_i)=i$ and $f(x\_i)=i+v+k$. For each clause-vertix, let $S=\{v+1,\ldots,v+k,2v+k+1,\ldots,n\}$, so $k$ of the clause-vertices are ``small''.

Now the CNF has an assignment where at least $k$ clauses are false if and only if your problem can be solved for the above instance. The MinSAT problem is exactly to test whether a CNF formula $\varphi$ has an assignment that makes at least $k$ clauses false, so this shows that your problem is NP-hard.

To help you understand this reduction, here's the intuition: small labels ($1,2,\dots,v+k$) correspond to the truth value False, and large labels ($v+k+1,\dots,2v+k$) correspond to True. The constraints for literal-vertices ensure that each $x\_i$ is either True or False and that $\overline{x\_i}$ has the opposite truth value. The edges ensure that if any literal is True, then all clause-vertices containing it are assigned True as well. (In contrast, if all literals in a clause are assigned False, then this graph structure allows the clause-vertex to be assigned either False or True.) Finally, the choice of $k$ ensures that $k$ of the clause-vertices are assigned False and $c-k$ of them are assigned True. So, if there is a valid topological sort of this graph, then there is an assignment to the variables that makes at least $k$ of the clauses of $\varphi$ false (all of the clause-vertices that were assigned False, plus possibly some of the ones that were assigned True). Conversely, if there is an assignment to the variables that makes at least $k$ of the clauses of $\varphi$ false, then there is a valid topological sort of this graph (we fill in the labels for the literal-vertices in the obvious way; and for each clause of $\varphi$ that is true, we give its corresponding clause-vertex a label that corresponds to True; the other clause-vertices can receive labels corresponding to an arbitrary truth value).

> **Comments:**
> **username_0**: Thanks for your answer! I'm trying to understand your sketch. Would you mind explaining what $k$ is?  
> **username_3**: @a3nm: k is a parameter that is given for the MinSAT input.  
> **username_3**: @Marzio: SAT is not equivalent to MinSAT with $k=|c|$, as in the latter problem we would require all clauses to be false. Your $\phi$ does not have an all clauses false assignment. Of course this does not prove my reduction is correct...  
> **username_2**: This is a gorgeous reduction!  @a3nm, I've suggested an edit to the answer to explain domotorp's elegant reduction in more detail; if it is approved, hopefully it will help you understand the ideas more clearly.  
> **username_4**: @domotorp: you are right, I completely missed what MinSAT is. Nice reduction!!!  
> **username_2**: @MarzioDeBiasi, Are you sure?  It looks right to me.  $1,2,\dots,v$ correspond to False (for literals), $v+1,\dots,v+k$ corresponds to False (for clauses), and $v+k+1,\dots,2v+k$ correspond to True (for literals).  $2v+k+1,\dots,2v+c$ is slightly tricky: I said that it corresponds to True (for clauses), but maybe a better way to say it is that could correspond to the clause being either true or false.  All true clauses (i.e., clauses where at least one literal is true) will get a label from $2v+k+1,\dots,2v+c$, but some false clauses (where all literals are false) might get those labels too.  
> **username_4**: @D.W.: ok (I only meant small labels for literals). A clause can take the value of false (v+1,...,v+k) iif all its literals are false (1..v). If a clause contains a true literal (v+k+1,..,2v+k) then it must take a large value (2v+k+1,...,2v+c). Very nice reduction!!  
> **username_0**: Yes, I understand the argument now. That's a beautiful reduction. Thanks a lot!  

---

### Answer by username_1 on 2013-09-19. Score: 2

Note that if you relax the problem by allowing $f$ to be arbitrary (not necessarily bijective), then it becomes polynomial. The algorithm proceeds similarly to topological sorting: you number the vertices one by one, maintaining the set $U$ of unnumbered vertices whose in-neighbors have been numbered. Whenever possible, you choose a vertex $x \in U$ and number it with the *smallest* element of $S(x)$ greater than the numbers of its in-neighbors. It is not hard to see that an instance $(G,S)$ has a solution iff the previous algorithm run on $(G,S)$ ends with all vertices numbered.

> **Comments:**
> **username_0**: Fair point, this relaxation means that a greedy heuristic works, and that's even in the case where $n$ is not the number of vertices but an arbitrary value. Do we agree that in the latter case, where injectivity and surjectivity are not equivalent anymore, you would need to relax both (and not just one) for the greedy heuristic to work?  

---

### Answer by username_2 on 2013-09-19. Score: 2

A trivial observation is that if $|S(x)| \le 2$ for all $x$, then this problem is solvable in polynomial time, by reduction to 2SAT.

Here's how. Introduce a variable $v\_{x,i}$ for each vertex $x$ and each $i$ such that $i \in S(x)$. For each pair $x,y$ of vertices, if there is a path from $x$ to $y$, we get some constraints: if $i\in S(x)$, $j\in S(y)$, and $i>j$, then we get the constraint $\neg v\_{x,i} \lor \neg v\_{y,j}$. Bijectivity gives us another set of constraints: for each pair $x,y$ of vertices with $x\ne y$, if $i \in S(x)$ and $i \in S(y)$, we add $\neg v\_{x,i} \lor \neg v\_{y,i}$. Finally, the requirement that each vertex must be assigned a label gives us yet another set of constraints: for each $x$, if $S(x)=\{i,j\}$, we get the constraint $v\_{x,i} \lor v\_{x,j}$. (Note that only the last set of constraints exploit the promise that $|S(x)|\le 2$ for each $x$.)

I realize this observation won't help you in your particular situation. Sorry about that.


---

