28
$\begingroup$

I was presenting a lecture on pancake sorting, and mentioned that:

Which got me thinking. There is a sense in which "signed" sorting is "directed" - you can view the sign as a direction (and indeed, this is the motivation from evolutionary biology). But it's an easier problem ! This is unusual because generally (at least on graphs) directed problems are harder (or at least as hard) as their undirected counterparts.

Assuming a generous definition of "directed", are there any examples of directed problems that are easier than their undirected counterparts ?

$\endgroup$
  • 2
    $\begingroup$ You may consider Horn 3SAT ( every clause can be represented as ( A AND B) $\to$ C) as a directed clauses since they may be viewed as implications. So, here the directed case is easy while the undirected 3SAT is hard. $\endgroup$ – Mohammad Al-Turkistany Dec 3 '11 at 15:40
  • 1
    $\begingroup$ I have wondered a similar question for a class I was teaching (where we used LP to approximate the IP solution): is there a class of problems where finding an integer solution was easier than finding a rationnal solution $\endgroup$ – Gopi Dec 3 '11 at 17:19
17
$\begingroup$

Counting Eulerian circuits for directed graphs is doable in polynomial time using the BEST theorem, while apparently, the same problem for undirected graphs is #P-complete.

$\endgroup$
  • $\begingroup$ All the answers are great, but if I have to accept one, this is it because the gap is large and the problem is very clean. $\endgroup$ – Suresh Venkat Dec 6 '11 at 1:23
15
$\begingroup$

An interesting and not so well-known case is the following. Suppose we have an edge-weighted graph $G$ and root node $r$. We want the minimum-cost sub-graph of $G$ such that there are $k$ edge-disjoint paths from $r$ to every node in the graph. When $k=1$ this is the min-cost arborescence problem in directed graphs and in undirected graphs it is equivalent to the MST problem. Both solvable in poly-time though the undirected case is easier. However the problem is poly-time solvable in directed graphs for any $k$ while it is NP-Hard in undirected graphs for $k=2$ (since it captures the min-cost $2$-edge-connected sub-graph problem).

$\endgroup$
13
$\begingroup$

Maybe this is not the best example, but consider (Directed) Cycle Cover, where the task is to cover all the vertices by vertex-disjoint (directed) cycles. In the directed case, this can be reduced to bipartite matching and solved in polynomial time. In the undirected case, the problem can be reduced to nonbipartite matching (and vice versa), which is a harder problem, but still polynomial-time solvable.

$\endgroup$
  • 10
    $\begingroup$ A more impressive similar example is the following: let $G$ be a directed weighted graph (weights can be negative). We can check if there is a negative cycle in $G$ using Ford-Bellman algorithm. But if $G$ is undirected then the problem becomes much-much harder (but still poly-time solvable). $\endgroup$ – ilyaraz Dec 3 '11 at 13:11
  • $\begingroup$ This is definitely a good example, and along the lines of what I was thinking about when I asked the question. $\endgroup$ – Suresh Venkat Dec 3 '11 at 18:14
  • 2
    $\begingroup$ I always had the impression that "problems involving cycles" are easier on directed graphs. Maybe there is some principle behind it, like that 2-connected componentes have "less structure" than strongly connected components ("problems involving cycles" = those that can be solved by looking separately at each component). $\endgroup$ – Diego de Estrada Dec 4 '11 at 4:50
  • 3
    $\begingroup$ Diego: if a directed closed walk goes through a vertex v, then there is a directed cycle going through v. The analogous statement is not true for undirected graphs. Thus in directed graphs, often we can reason about walks instead of cycles. Walks are more robust and less graph-theoretical than cycles, which could be an advantage. Maybe this is a formal explanation of your impression. $\endgroup$ – Daniel Marx Dec 4 '11 at 11:40
9
$\begingroup$

Here's a problem that, as I recently realized, looks actually harder in undirected graphs than directed ones.

Suppose you have a graph with positive and negative edge weights, and you are asked to detect a negative weight cycle. There is a scaling algorithm for this problem for directed graphs by Goldberg'93 (A. V. Goldberg. 1993. Scaling algorithms for the shortest paths problem. In SODA '93.) running in O($m\sqrt{n}\log C$) time where $m$ is the number of edges, $n$ the number of vertices and $C$ the largest absolute value of an edge weight. In contrast, the same problem in undirected graphs has much worse algorithms. To my knowledge, the best known is by Gabow'83 (H. N. Gabow. 1983. An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In STOC '83. ) and runs in O(min($n^3, mn\log n$)) time. There's also an approach using T-joins which gives the same runtime, I don't remember where I saw it however.

The negative cycle problem is crucial in the design of single source shortest paths (SSSP) algorithms and it is not surprising that the best running times for SSSP in directed and undirected graphs with arbitrary weights have the same runtimes-- O($m\sqrt{n}\log C$) and O(min($n^3, mn\log n$)) respectively.

$\endgroup$
  • $\begingroup$ but here 'hard' just means with respect to the (polynomial) runtimes of the algorithms that we know; it could be that we are missing some technique, of course $\endgroup$ – virgi Dec 4 '11 at 2:36
  • 2
    $\begingroup$ That's another interesting example. And p.s congratulations on the amazing new result. $\endgroup$ – Suresh Venkat Dec 4 '11 at 3:02
  • 1
    $\begingroup$ Thanks, Suresh! On another note, I just noticed that ilyaraz had my answer in a comment to Daniel Marx' answer... sorry for the duplicate. $\endgroup$ – virgi Dec 4 '11 at 8:15

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.