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

CC BY-SA 3.0
2011-12-03T20:47:54.047Z
2011-12-03T20:47:54.047Z
Chandra Chekuri
<p>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.</p>

CC BY-SA 3.0
2011-12-03T13:11:22.340Z
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).
ilyaraz
CC BY-SA 3.0
2011-12-03T18:14:08.020Z
This is definitely a good example, and along the lines of what I was thinking about when I asked the question.
Suresh Venkat
CC BY-SA 3.0
2011-12-04T04:50:10.640Z
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).
didest
CC BY-SA 3.0
2011-12-04T11:40:14.533Z
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.
Daniel Marx
CC BY-SA 3.0
2011-12-03T12:36:52.383Z
2011-12-03T12:36:52.383Z
Daniel Marx
<p>Here's a problem that, as I recently realized, looks actually harder in undirected graphs than directed ones.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-12-04T02:36:24.020Z
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
virgi
CC BY-SA 3.0
2011-12-04T03:02:47.247Z
That's another interesting example. And p.s congratulations on the amazing new result.
Suresh Venkat
CC BY-SA 3.0
2011-12-04T08:15:05.670Z
Thanks, Suresh! On another note, I just noticed that ilyaraz had my answer in a comment to Daniel Marx' answer... sorry for the duplicate.
virgi
CC BY-SA 3.0
2011-12-04T02:34:14.097Z
2011-12-04T02:34:14.097Z
virgi
<p>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.</p>
<p>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 <span class="math-container">$n$</span> nodes and parameter <span class="math-container">$p$</span> and a &quot;small&quot; 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 <span class="math-container">$p$</span> 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 <span class="math-container">$O(n^3)$</span>.</p>

CC BY-SA 4.0
2022-03-03T10:36:15.440Z
2022-03-03T10:36:15.440Z
tortue
<p>Counting Eulerian circuits for directed graphs is doable in polynomial time using the <a href="http://en.wikipedia.org/wiki/BEST_theorem">BEST theorem</a>, while apparently, <a href="http://www.cdam.lse.ac.uk/Reports/Files/cdam-2004-12.pdf">the same problem for undirected graphs is #P-complete</a>.</p>

CC BY-SA 3.0
2011-12-06T01:23:45.820Z
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.
Suresh Venkat
CC BY-SA 3.0
2011-12-04T09:54:40.400Z
2011-12-04T09:54:40.400Z
Timothy Sun
<p>I was presenting a lecture on <a href="http://en.wikipedia.org/wiki/Pancake_sorting">pancake sorting</a>, and mentioned that: </p>

<ul>
<li><a href="http://dl.acm.org/citation.cfm?id=307964">Sorting by reversals is NP-hard</a></li>
<li><a href="http://dl.acm.org/citation.cfm?id=225112">"signed" sorting by reversals is in P</a>. </li>
</ul>

<p>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. </p>

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

CC BY-SA 3.0
2011-12-03T15:40:24.257Z
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.
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-12-03T17:19:34.163Z
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
Gopi
<ds.algorithms>
"Directed" problems that are easier than their "undirected" variant.
Suresh Venkat
# "Directed" problems that are easier than their "undirected" variant.

(Asked by: username_0 on 2011-12-03)

I was presenting a lecture on [pancake sorting](http://en.wikipedia.org/wiki/Pancake_sorting), and mentioned that:

* [Sorting by reversals is NP-hard](http://dl.acm.org/citation.cfm?id=307964)
* ["signed" sorting by reversals is in P](http://dl.acm.org/citation.cfm?id=225112).

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 ?

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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  

---

## 5 answers

### Answer by username_9 on 2011-12-04. Score: 21 | Accepted answer

Counting Eulerian circuits for directed graphs is doable in polynomial time using the [BEST theorem](http://en.wikipedia.org/wiki/BEST_theorem), while apparently, [the same problem for undirected graphs is #P-complete](http://www.cdam.lse.ac.uk/Reports/Files/cdam-2004-12.pdf).

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_3 on 2011-12-03. Score: 19

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


---

### Answer by username_4 on 2011-12-03. Score: 13

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.

> **Comments:**
> **username_5**: 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).  
> **username_0**: This is definitely a good example, and along the lines of what I was thinking about when I asked the question.  
> **username_6**: 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).  
> **username_4**: 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.  

---

### Answer by username_7 on 2011-12-04. Score: 9

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.

> **Comments:**
> **username_7**: 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  
> **username_0**: That's another interesting example. And p.s congratulations on the amazing new result.  
> **username_7**: Thanks, Suresh! On another note, I just noticed that ilyaraz had my answer in a comment to Daniel Marx' answer... sorry for the duplicate.  

---

### Answer by username_8 on 2022-03-03. Score: 0

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


---

