15
$\begingroup$

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

$\endgroup$
9
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – a3nm Sep 19 '13 at 14:01
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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