1
$\begingroup$

I'm attempting to solve this problem:

Given an undirected connected graph $G=(V,E)$ with $\mathrm{weight}(e)>0$ for all $e \in E$, and a subset $S \subseteq V$, we define that a sub-graph $H=(V',E')$ of $G$ spans $S$ if $S \subseteq V'$ and $H$ is connected.

We define $H$ to be minimal spanning if the sum of all weights in $E'$ is smaller than the sum of all weights in every other sub-graph of $G$ which spans $S$.

The problem requires that given $G$ and $S=(v_i , v_j , v_k)$ where $i\neq j \neq k$ to describe an efficient algorithm to find a minimal spanning sub-graph.

I attempted to prove that a minimal spanning sub-graph will always contain the cheapest path between $2$ of the $3$ vertices in $S$, but found counter-examples that disproved my claim.

In a previous section of the problem, I've proved that a minimal spanning subgraph when $|S|=2$ is always the cheapest path between the $2$ vertices in $S$.

However, I was not able to incorporate this proof into my attempts in solving this problem.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
1
$\begingroup$

To my understanding, what you are looking at is a Steiner tree problem variant.

This is a $\mathsf{NP}$-hard problem, so it's no wonder you have difficulties solving it.

Maybe you can find some answers here (didn't read the paper in details, though).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Indeed, after reading about the Steiner tree problem, I've manged to understand why my problem and this are related, however, I was not able to come to a complete understanding of the solution to either problems. $\endgroup$
    – Aishgadol
    Dec 17, 2022 at 10:26
1
$\begingroup$

Since there are only three vertices in S, you can solve this problem by solving the following integer program. Let $w(e)$ be the weight of edge $e$ and $x_e$ a binary variable indicating if $e \in H$. We also define $\delta(U) = \{uv \in E: u \in U, v \notin U\}$ for some $U \subseteq V$.

$min$ $\Sigma(w(e)x_e: e \in E)$

$\Sigma(x_e: e \in \delta(U))$ $\>$ $(U \subseteq V, v_i \in U, v_j \notin U)$
$\Sigma(x_e: e \in \delta(U))$ $\>$ $(U \subseteq V, v_i \in U, v_k \notin U)$
$\Sigma(x_e: e \in \delta(U))$ $\>$ $(U \subseteq V, v_j \in U, v_k \notin U)$
$x_e \geq 0$ $\forall e \in E$
$x_e \in \mathbb{Z}$ $\forall e \in E$

Improve this answer
$\endgroup$
0
$\begingroup$

This is the Steiner tree problem in graphs with three terminals. It can be solved in polynomial time. You can use for example the Dreyfus-Wagner algorithm to solve it. In the case of three terminals it boils down to the following: Compute for each vertex (including the three terminals) the shortest path to each of the terminals and choose the vertex such that the sum of these paths is minimum. The three (possibly single-vertex) shortest paths to the terminals give you an optimal solution.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I've had a similar idea in mind, but this forces us to a time complexity of $n^2logn$ as we (in a more general way, since we dont know the limit on $|V|$) are required to apply dijkstra's algorithm on every node. $\endgroup$
    – Aishgadol
    Dec 17, 2022 at 10:29
  • $\begingroup$ You just need to compute the shortest paths from the three terminals to all other vertices. So it is O(n log n), because you only have three. Alternatively, if you are looking only for a practical solution, use this Steiner tree solver: scipjack.zib.de . It will give you an optimal solution to your problem in milliseconds, even for thousands of vertices. $\endgroup$
    – Dan
    Dec 17, 2022 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.