Maximum (edge)weight connected subgraph of an undirected graph.

Let G be a undirected graph with weighted edges. I want to find a connected subgraph which has at most L nodes(vertices) whose sum of edges is maximum. It sounds similar to MWCS or PCST but here only the edges are weighted and there is a limit on no of nodes in the subgraph. These are related papers I found for solving MWCS or PCST: http://dimacs11.cs.princeton.edu/workshop/ElKebirKlau.pdf http://dimacs11.cs.princeton.edu/workshop/AlthausBlumenstock.pdf

PS: All weights are positive unlike in MWCS.

You might want take a look at our paper that considers what we call a generalized MWCS problem (https://arxiv.org/abs/1605.02168) and corresponding solver (https://github.com/ctlab/gmwcs-solver/). There, unlike in classical MWCS, edge weights (both postitve and negative) are allowed. It works pretty well for the practical instances that we have.

• While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. – Glorfindel Apr 18 '17 at 8:36

We can do this using linear programming. Let your objective function be

x1 e1 + x2 e2 + ..... xn en

where xk is a boolean variable to show whether to select kth edge. And ek is the edge weight. Here, n is the no of edges. Then we can formulate the following constraints:

x1 + x2 + ... xn <= p, where p is the no of edges we want.

If one edge k, is guaranteed to be in the subgraph to be selected, then formulate constraints outwards from that edge. For example, if u and v are edges connected to k, then the constraints u<=k and v<=k will be present. And so on for all the edges. This will ensure connectedness of the selected graph. Feeding this to any linear programming solver like lp_solve will give boolean values of all xs.