patternMinor
Comparing different versions of Steiner Connected Component Subgraph problem
Viewed 0 times
problemsteinercomparingdifferentconnectedversionscomponentsubgraph
Problem
Problem 1
Let $G(V,E)$ be a directed graph. Let $T \subseteq V$ be a subset of vertices called terminals. Find a subgraph $H$ of $G$, such that $T \subseteq V(H)$, $H$ is a strongly connected component and the number of edges in $H$ is minimized. Here $V(H)$ stands for the set of vertices of $H$.
Problem 2
Everything remains the same, but this time we want to minimize the number of vertices in $H$.
Let $H$ and $H^{'}$ be optimal solutions to problem $1$ and $2$ respectively, for a given $G$. Let the number of edges in $H$ and $H^{'}$ be $e$ and $e^{'}$ respectively.
I am trying to find an example of a graph $G$, such that $e |V(H^{'})|$. I am unable to do so, the example I came up with has $e=e^{'}$ (and $|V(H)| > |V(H^{'})|$). But I wanted to see a case of strict inequality.
In the example above the red vertices are the terminals. And $e=e^{'}=6$, where as $|V(H^{'})|=4$ and $V(H)=6$ (to be precise $H^{'}$ is also an optimal solution for problem $1$ in this example).
Let $G(V,E)$ be a directed graph. Let $T \subseteq V$ be a subset of vertices called terminals. Find a subgraph $H$ of $G$, such that $T \subseteq V(H)$, $H$ is a strongly connected component and the number of edges in $H$ is minimized. Here $V(H)$ stands for the set of vertices of $H$.
Problem 2
Everything remains the same, but this time we want to minimize the number of vertices in $H$.
Let $H$ and $H^{'}$ be optimal solutions to problem $1$ and $2$ respectively, for a given $G$. Let the number of edges in $H$ and $H^{'}$ be $e$ and $e^{'}$ respectively.
I am trying to find an example of a graph $G$, such that $e |V(H^{'})|$. I am unable to do so, the example I came up with has $e=e^{'}$ (and $|V(H)| > |V(H^{'})|$). But I wanted to see a case of strict inequality.
In the example above the red vertices are the terminals. And $e=e^{'}=6$, where as $|V(H^{'})|=4$ and $V(H)=6$ (to be precise $H^{'}$ is also an optimal solution for problem $1$ in this example).
Solution
In the figure, the bottom four vertices of the graph are red-colored vertices.
$H$ has $5$ edges and $5$ vertices.
$H'$ has $6$ edges and $4$ vertices.
$H$ has $5$ edges and $5$ vertices.
$H'$ has $6$ edges and $4$ vertices.
Context
StackExchange Computer Science Q#144086, answer score: 2
Revisions (0)
No revisions yet.