<p>We have a recent preprint where we show it's polynomial-time on planar graphs: <a href="https://arxiv.org/abs/2305.01314" rel="nofollow noreferrer">https://arxiv.org/abs/2305.01314</a>. In general graphs, it remains open whether it is polynomial-time or NP-complete.</p>
<p>An FPT algorithm for general graphs can be given by using <em>flow-augmentation</em>: <a href="https://arxiv.org/abs/2111.03450" rel="nofollow noreferrer">https://arxiv.org/abs/2111.03450</a></p>

CC BY-SA 4.0
2023-07-25T14:42:11.513Z
2023-07-25T14:42:11.513Z
Laakeri
<p>In the <strong>Network Diversion</strong> problem, we are given an <em>undirected</em> graph <span class="math-container">$G$</span> on <span class="math-container">$n$</span> vertices, with specified nodes <span class="math-container">$s$</span> and <span class="math-container">$t$</span> and specified edge <span class="math-container">$e$</span>, and a positive integer <span class="math-container">$k$</span>, and are tasked with determining if it is possible to delete at most <span class="math-container">$k$</span> edges from <span class="math-container">$G$</span> to produce a graph which</p>
<ol>
<li><p>contains an <span class="math-container">$st$</span>-path, and</p>
</li>
<li><p>has the property that every <span class="math-container">$st$</span>-path in <span class="math-container">$G$</span> passes through the edge <span class="math-container">$e$</span>.</p>
</li>
</ol>
<p>In other words, we want to know if by removing a &quot;small&quot; number of edges from <span class="math-container">$G$</span>, we can force anyone walking from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> to go through a specific edge <span class="math-container">$e$</span>.</p>
<p><strong>Question:</strong> what is known about the (exact or parameterized) complexity of Network Diversion? Is this problem known to be polynomial-time solvable, NP-hard, W[1]-hard, etc.?</p>

<ds.algorithms><graph-theory><graph-algorithms><parameterized-complexity>
What is known about the complexity of Network Diversion?
Naysh
# What is known about the complexity of Network Diversion?

(Asked by: username_0 on 2023-07-25)

In the **Network Diversion** problem, we are given an *undirected* graph $G$ on $n$ vertices, with specified nodes $s$ and $t$ and specified edge $e$, and a positive integer $k$, and are tasked with determining if it is possible to delete at most $k$ edges from $G$ to produce a graph which

1. contains an $st$-path, and
2. has the property that every $st$-path in $G$ passes through the edge $e$.

In other words, we want to know if by removing a "small" number of edges from $G$, we can force anyone walking from $s$ to $t$ to go through a specific edge $e$.

**Question:** what is known about the (exact or parameterized) complexity of Network Diversion? Is this problem known to be polynomial-time solvable, NP-hard, W[1]-hard, etc.?

**Tags:** ds.algorithms, graph-theory, graph-algorithms, parameterized-complexity

---

## 1 answers

### Answer by username_1 on 2023-07-25. Score: 1 | Accepted answer

We have a recent preprint where we show it's polynomial-time on planar graphs: <https://arxiv.org/abs/2305.01314>. In general graphs, it remains open whether it is polynomial-time or NP-complete.

An FPT algorithm for general graphs can be given by using *flow-augmentation*: <https://arxiv.org/abs/2111.03450>


---

