# Maximum subset of connected edges

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.
• Even your first solution does not guarantee the optimal solution. – Vince Jan 28 at 15:51
• @Vince, yeah figured as much. The more I think about this the more I think that this is not solvable in some nice way. – Nick Chapman Jan 28 at 16:16
• 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. – Vince Jan 30 at 13:19