1
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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

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