Ensure a graph is connected in a linear programming problem

Question

I am trying to set up a linear programming problem that induces a subgraph of a complete graph G while trying to minimize the following objective function along with a certain set of constraints:

$$\sum_{\forall j \in V(G)} \sum_{\forall i \in V(G)} w_{i,j}x_{i,j}$$

Where $w_{i,j}$ is the weight of the edge between $i$ and $j$ in G and $x_{i,j}$ is the presence of an edge between them.

Is there a constraint I can add which will make the outputted graph be a connected component? My current crude solution is to find an MST and set those edges to equal 1, but I was wondering if there was a better way of going about this.

Answer 1

Setting the edges in a spanning tree equal to $1$ is not a true solution: it eliminates some valid solutions which are connected, but don't contain the specific spanning tree you found.

A general solution is to add the following constraints: for all $S \subset V(G)$ excluding $\varnothing$ and $V(G)$ itself, require $$ \sum_{i \in S} \sum_{j \notin S} x_{ij} \ge 1. $$ This says "$S$ cannot be a connected component: there is at least one edge between $S$ and the rest of the graph", so when this constraint exists for all $S$, it makes sure that the graph cannot be split into multiple connected components.

The downside is that this is exponentially many constraints. Taking into account that $S$ and $V(G)-S$ give the same constraint, we get $2^{n-1}-1$ constraints for an $n$-vertex graph.

The way to deal with this downside is row generation. First, don't include any constraints that enforce connectivity, and solve the linear program. If the graph you get is not connected (which can be checked efficiently), find a connectivity constraint it violates, and add it to the LP. Then, use the dual simplex method to solve the LP again from the previous optimal solution. Repeat until you get a connected solution.

Answer 2

An alternative approach is to use flow of a phantom commodity. I assume you want all vertices to be retained in the subgraph. Assume the graph is undirected with $\vert V\vert=n$. Fair warning: in what follows I will assume that if $(i,j)$ is an edge, $(j,i)$ is recognized as the same edge and the variable $x_{j,i}$ exits (and is constrained to equal $x_{i,j}$).

Arbitrarily pick one vertex $v_0\in V$ as the source, with a supply of $n-1$ units of the phantom commodity. Every other vertex has demand 1. Add variables $y_{i,j} \ge 0$, representing the flow of whatever it is from $i$ to $j\neq i$ across the edge between them, together with the constraints $$y_{i,j}\le (n-1)x_{i,j}\quad \forall i,j\in V, i\neq j,$$ $$ \sum_{j\in V:(v_0,j)\in E(G)}y_{v_0,j} = n-1,$$and $$\sum_{j:(i,j)\in E(G)}y_{i,j}=\sum_{j:(j,i)\in E(G)}y_{j,i}-1\quad \forall i\in V(G)\backslash \lbrace v_0 \rbrace.$$ The first constraint essentially says that you can move the commodity across an edge that was not chosen for the subgraph. The second constraint dictates the flow out of the chosen source vertex (and serves to ensure that it is connected to the rest of the subgraph). The third constraint says that at every other node, one unit of supply gets absorbed and anything left gets passed along.

The number of added constraints and added variables are both quadratic in the vertex count.