32
$\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 ?

Improve this question
$\endgroup$
2
  • 4
    $\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
    Commented Dec 3, 2011 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
    Commented Dec 3, 2011 at 17:19

5 Answers 5

Reset to default
21
$\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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Dec 6, 2011 at 1:23
19
$\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).

Improve this answer
$\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.

Improve this answer
$\endgroup$
4
  • 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
    Commented Dec 3, 2011 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
    Commented Dec 3, 2011 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$
    – didest
    Commented Dec 4, 2011 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
    Commented Dec 4, 2011 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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Dec 4, 2011 at 2:36
  • 2
    $\begingroup$ That's another interesting example. And p.s congratulations on the amazing new result. $\endgroup$
    – Suresh Venkat
    Commented Dec 4, 2011 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
    Commented Dec 4, 2011 at 8:15
0
$\begingroup$

I am coming from a statistics background in my answer by problem A is harder than problem B if the statistical error of problem A is at least as much as that of problem B, given both problems are solved with algorithms of the same computational complexity.

An example of a problem being harder in the undirected graph setting is the following. Suppose you have an Erdős–Rényi model with $n$ nodes and parameter $p$ and a "small" fraction of nodes are corrupted by an adversary (adversary can add/remove any edges that are adjacent to the corrupted set of nodes). Then, estimating the parameter $p$ in the directed Erdős–Rényi model is easier than in the undirected Erdős–Rényi model. if I am not mistaken the complexity is $O(n^3)$.

Improve this answer
$\endgroup$

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.