2
$\begingroup$

I am trying to resolve the following problem and was wondering if there already exists consecrated algorithms to solve it.

Let $G(V,E)$ be a weighted graph with vertices $V$ connected through weighted edges $E$. Given a subset $S \subset V$, perform graph contraction such that all edges are removed until only the vertices in $S$ remain and the distance-preserving edges connecting them. If there exists more than one edges connecting two nodes from $S$, pick the smallest weight and remove the other(s).

The "Distance-preserving graph contractions" paper from Bernstein et al. was the closest I could find to my problem, but their goal is different (for one, they are not bound by a set $S$).

The min-cut class of problems seems also close-by, but not exactly what I want.

Can you please point me in the right direction?

Thank you!

Improve this question
$\endgroup$
3
  • $\begingroup$ Just some clarification: By contract a vertex $v$ [of degree greater than 2], you mean remove $v$ from $G$ and then, for every two neighbours $u_1$ and $u_2$ of $v$, put the edge $u_1u_2$ and set the length $\ell(u_1u_2)$ of the edge $u_1u_2$ to $\ell(u_1u_2) = \ell(u_1v) + \ell(vu_2)$ [and then do something to take care of duplicate edges]? $\endgroup$
    – Mike
    Aug 28, 2018 at 15:05
  • 1
    $\begingroup$ Of course you can always do something like that above--contract vertices not in $S$ and the pairwise distances between vertices in $S$ will be preserved. The main issue is that the resulting graph may in fact be different topologically, in that e.g., the original graph had a small cut that bisected $S$ but the new resulting graph does not. $\endgroup$
    – Mike
    Aug 28, 2018 at 15:10
  • $\begingroup$ @Mike's first comment: yes, that is what I want to do. The extra merge step removes all but the smallest edge connecting any given two vertices that used to be connected through $v$. $\endgroup$
    – Paul Irofti
    Aug 28, 2018 at 15:32

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.