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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.