12
$\begingroup$

Tree width measures how close a graph is to a tree. Several NP-hard problems are tractable on graphs with bounded tree width. If a problem remains NP-hard on trees then tree width cannot save us. This was the motivation behind one of my previous questions asking for NP-hard problems on trees.

There are several directed versions of tree width measuring how close a directed graph is to a directed acyclic graph (DAG). What are some directed problems that remain NP-hard on DAGs ? A directed problem makes essential use of the directions of the edges. For example, hamiltonian path is a directed problem whereas vertex cover is not. One of the answers to my previous question gave a general recipe for generating problems that are hard on trees. Is there such a recipe for DAGs ?

Improve this question
$\endgroup$

4 Answers 4

Reset to default
7
$\begingroup$

This only aims at partially answering the first question of the post:

What are some directed problems that remain NP-hard on DAGs ?

In [1], a few natural problems on directed graphs are given that remain NP-hard on DAGs. The motivation of the paper is to find a "good" treewidth-like measure for digraphs. They argue that the drawback of many measures for digraphs is that they are constant for DAGs, but many directed counterparts of natural problems remain NP-hard on DAGs. For more on this topic, see also [2] and the references of these papers.

[1] Robert Ganian, Petr Hlinený, Joachim Kneis, Alexander Langer, Jan Obdrzálek, Peter Rossmanith: On Digraph Width Measures in Parameterized Algorithmics. IWPEC 2009:185-197. Full version

[2] Robert Ganian, Petr Hlinený, Joachim Kneis, Daniel Meister, Jan Obdrzálek, Peter Rossmanith, Somnath Sikdar: Are there any good digraph width measures?. IPEC 2010, to appear. arXiv

Improve this answer
$\endgroup$
6
$\begingroup$

Several routing problems are known to be NP-hard and even hard to approximate to polynomial factors in DAGs. These include problems such as maximum edge-disjoint paths and congestion-minimization. See the papers by Andrews, Chuzhoy, Khanna, Zhang and others for more pointers.

Improve this answer
$\endgroup$
2
$\begingroup$

The famous OPEN[8] problem from list of Garey and Johnson is beyond P, but open to be proved to be NP-C. That problem is on DAG. Each round you can delete at most three vertices which do not have incoming edge. Decide whether all the vertices of the DAG could be deleted in K rounds? OPEN from 1970s.

Improve this answer
$\endgroup$
1
$\begingroup$

From the logic point of view, evaluate a MSO formula is NP-hard on DAGs. For example, $\varphi:=\exists C_1 C_2 C_3 [\forall x (C_1 x \lor C_2 x \lor C_3 x) \land \bigwedge_{i=1,2,3}\forall x,y(\neg C_i x \lor \neg C_i y\lor \neg E(x,y))]$ says graph G can be 3-colored. And for any undirected graph $G$, we can directed its edges to get a DAG $G'$, and change all $E(x,y)$ in $\varphi$ to $E(x,y)\lor E(y,x)$. Now we have $G\models\varphi\iff G'\models\varphi'$.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ It seems that this problem is not using the directions of the edges. I am looking for directed problems. $\endgroup$
    – Shiva Kintali
    Commented Oct 5, 2010 at 7:53
  • $\begingroup$ @Shiva: Why does this not meet your criteria for a directed problem? $\endgroup$
    – András Salamon
    Commented Oct 5, 2010 at 14:08
  • 1
    $\begingroup$ @András : Graph coloring cares about the presence of an edge (u,v). It does not matter if the edge is directed from u to v or from v to u. On the other hand, Hamiltonian Path uses the directions of the edges. It is possible to change the directions of some edges and convert an YES instance into a NO instance. $\endgroup$
    – Shiva Kintali
    Commented Oct 5, 2010 at 19:18
  • $\begingroup$ @Shiva: So you want a property that is expressed by a formula that isn't symmetric (invariant under permutation of variables)? $\endgroup$
    – András Salamon
    Commented Oct 6, 2010 at 5:49
  • $\begingroup$ @András : Exactly. $\endgroup$
    – Shiva Kintali
    Commented Oct 6, 2010 at 7:33

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.