2
$\begingroup$

I have been trying to come up with an efficient algorithm for the following problem.

Let $G = (V,E)$ be an undirected acyclic weighted graph, where there is exactly one path from a vertex $u$ to any other vertex $v$.

Let $S \in V$ be a set of vertices from $G$.

$|S|$ is the size of the set.

$0 \leq |S| \leq |V|$.

Split the graph into $|S|$ connected components such that each component has exactly one vertex $v \in S$, and the sum of the weights of the edges that get removed is minimum.

I have thought of two algorithms which I will briefly describe.

Algorithm 1

enter image description here

The complexity of this algorithm is $O(2^{|E|} \ (|V|+|E|))$

Algorithm 2

enter image description here

This second approach is more feasible. If implemented naively, though, the time complexity is $O(|S| \ (|V|+|E|))$. This is the result of running a depth first search to find two vertices that belong to the same component and are in S. And it is also used to find the smallest edge in the path from $u$ to $v$. The depth first search is then executed $O(|S|)$ times.

I was wondering if this problem can be solved asymptotically better. I was thinking I could use a dynamic graph which supports queries of the form: are $u$ and $v$ in the same component? and allows deletion of edges. I think this is also known as decremental connectivity. However, this data structure would not help me find the shortest edge from $u$ to $v$.

Any help is appreciated.

Improve this question
$\endgroup$

0

Reset to default

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.