HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Comparing different versions of Steiner Connected Component Subgraph problem

Submitted by: @import:stackexchange-cs··
0
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).

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.

Context

StackExchange Computer Science Q#144086, answer score: 2

Revisions (0)

No revisions yet.