patternMinor
Minimize edges of a directed unweighted graph
Viewed 0 times
minimizeedgesgraphunweighteddirected
Problem
I need to find an algorithm to find a sub-graph $G'=(V, E')$ of a directed unweighted graph $G = (V, E)$ where for all $(u, v)\in E$ there exists a path in $G'$ from $u$ to $v$ and the size of $E'$ is minimal.
As an example, $(1, 2) (2, 3) (1, 3)$ reduces to $(1, 2) (2, 3)$. Additionally, $(1, 2) (2, 3) (1, 3) (3, 1)$ reduces to $(1, 2) (2, 3) (3, 1)$.
This is not an MST (or arborescence) problem since we care every vertex as a root hence Edmond's algorithm does not work.
I am clueless at this point. At least a hint is highly appreciated.
As an example, $(1, 2) (2, 3) (1, 3)$ reduces to $(1, 2) (2, 3)$. Additionally, $(1, 2) (2, 3) (1, 3) (3, 1)$ reduces to $(1, 2) (2, 3) (3, 1)$.
This is not an MST (or arborescence) problem since we care every vertex as a root hence Edmond's algorithm does not work.
I am clueless at this point. At least a hint is highly appreciated.
Solution
There is no polynomial-time algorithm for your problem, unless $\mathsf{P}=\mathsf{NP}$.
Let $H$ be a connected undirected graph with at least $2$ vertices and consider the directed graph $G$ obtained by replacing each undirected edge {u,v} of $H$ with the pair of directed edges $(u,v)$ and $(v,u)$.
If there is a Hamiltonian path traversing the vertices $\langle u_0, \dots, u_{n-1}, u_n = u_0 \rangle$ of $H$, in order, then the set of $n$ edges $\{ (u_i, u_{(i+1) \bmod n}) \mid i=0,\dots,n-1\}$ of $G$ induces a subgraph $G'$ with your property.
If there is a subgraph $G'$ of $G$ with at most $n$ edges that satisfies your property, then it must have exactly $n$ edges. Moreover the in-degree and the out-degree of each vertex must be exactly $1$, and the undirected version $H'$ of $G'$ must be connected. In other words $G'$ is a cycle that that traverses each vertex of $G$ exactly once, showing that $H'$ is a Hamiltonian path of $H$.
Let $H$ be a connected undirected graph with at least $2$ vertices and consider the directed graph $G$ obtained by replacing each undirected edge {u,v} of $H$ with the pair of directed edges $(u,v)$ and $(v,u)$.
If there is a Hamiltonian path traversing the vertices $\langle u_0, \dots, u_{n-1}, u_n = u_0 \rangle$ of $H$, in order, then the set of $n$ edges $\{ (u_i, u_{(i+1) \bmod n}) \mid i=0,\dots,n-1\}$ of $G$ induces a subgraph $G'$ with your property.
If there is a subgraph $G'$ of $G$ with at most $n$ edges that satisfies your property, then it must have exactly $n$ edges. Moreover the in-degree and the out-degree of each vertex must be exactly $1$, and the undirected version $H'$ of $G'$ must be connected. In other words $G'$ is a cycle that that traverses each vertex of $G$ exactly once, showing that $H'$ is a Hamiltonian path of $H$.
Context
StackExchange Computer Science Q#125833, answer score: 6
Revisions (0)
No revisions yet.