I have a graph $G$ with $m$ vertices $V$ and $n$ edges $E$. $G$ is weighted, directed, and cyclic. I want to select heaviest $k$ edges from $E$ such that all of the edges form a connected, undirected graph. Note that when selecting these edges, the graph is considered to be connected even when two vertices $v_1$ and $v_3$ are joined by otherwise directed edges through $v_2$.

N1 ----> N2 <---- N3

Note that I am not simply looking for the maximum spanning tree, because if there were edges $e_{v_1,v_2}, e_{v_2,v_1}, e_{v_1,v_3}, e_{v_3,v_1}$ with weights

$$w_{e_{v_1,v_2}} = \max(w_E)$$ $$w_{e_{v_2,v_1}} = \max(w_E)$$ $$w_{e_{v_1,v_3}} = \max(w_E)$$ $$w_{e_{v_3,v_1}} = \max(w_E)$$

Then I would want to include all of those edges in my subset (provided of course that $k >4$).

My two big questions:

  1. Is there a formal name for this problem?
  2. Is there a polynomial time solution for this problem.

My gut reaction to how to solve this (and I'm pretty sure this is $O($🗑️$)$ is:

  • Sort the edges by weight.
  • Select the top $k$ edges by weight.
  • Cluster the edges to determine whether they are connected.
  • If after clustering the edges they are not all connected and instead form $c$ clusters, then drop the bottom $c - 1$ edges from the initial set of $k$.
  • Repeat this clustering and dropping process until $c$ is not changing.
  • Find the maximally weighted paths that connect all clusters using $c - 1$ edges. If no paths exist, drop another edge and restart the clustering process.

Another possibility I have considered (which I don't think gives the right solution, but I'll throw it out there)

  • Sort the edges by weight.
  • Select the top $k$ edges by weight.
  • Cluster the edges into $c$ clusters.
  • Now without removing any edges, find the shortest paths between all clusters, or really the smallest number of additional edges that can be added to connect the clusters.
  • If we added $x$ edges, then we must now remove $x$ edges from the $k$ that were selected before, but we can only remove edges such that the graph remains connected.
  • $\begingroup$ Even your first solution does not guarantee the optimal solution. $\endgroup$ – Vince Jan 28 at 15:51
  • $\begingroup$ @Vince, yeah figured as much. The more I think about this the more I think that this is not solvable in some nice way. $\endgroup$ – Nick Chapman Jan 28 at 16:16
  • $\begingroup$ The worst is that I would be personally interested by such problem for work. But I suppose like you that there is no polynomial answer. $\endgroup$ – Vince Jan 30 at 13:19

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.