Theoretical Computer Science

Complexity of topological sort with constrained positions


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.]




Solution

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 (5)

  • +0 – Thanks for your answer! I'm trying to understand your sketch. Would you mind explaining what $k$ is? — Sep 19, 2013 at 14:03  
  • +1 – @a3nm: k is a parameter that is given for the MinSAT input. — Sep 19, 2013 at 18:00  
  • +1 – @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... — Sep 19, 2013 at 18:02  
  • +0 – 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. — Sep 19, 2013 at 20:22  
  • +0 – @domotorp: you are right, I completely missed what MinSAT is. Nice reduction!!! — Sep 19, 2013 at 22:25  


External Links

External links referenced by this document: