# 3-connectivity as a set linear constraints

It turns out connectivity of a graph can be expressed as a set of linear constraints. https://www.researchgate.net/post/How_can_I_ensure_graph_connectivity_using_LP_or_MIP_formulation

Giving a vertex a supply N and naming it source, and then every other vertex a sink with demand 1, (and every edge with N capacity) this can be expressed as a flow problem.

If a solution is found then the edges used necessarily make a connected component.

Now I tried to generalise this for 3 connectivity without success (played with capacities,sources sinks etc). Any ideas? Or any other idea maybe without passing through flow (but always only using linear constraints)?

• Your variables, I assume, are indicator variables $x_{ij}$ for whether edge $ij$ is present? – Misha Lavrov May 3 at 15:15
• yes. Notice that we do not need the minimum flow, so the weights can be arbitrary. – Paramar May 3 at 15:29

By Menger's theorem, $$G$$ is $$3$$-connected if there are $$3$$ vertex-disjoint paths between any two vertices $$s,t$$. For fixed $$s,t$$ we can encode this as a flow problem:

• For each vertex $$v$$, give the network two nodes $$v^-$$, $$v^+$$ with an edge $$v^-v^+$$ of capacity $$1$$.
• For every pair of vertices $$\{v,w\}$$ add edges $$v^+w^-$$ and $$v^-w^+$$ with capacity $$1$$.
• Give $$s^+$$ supply $$3$$ and $$t^-$$ demand $$3$$.

Unfortunately, I don't think this combines well. Still, we can just write $$\binom n2$$ separate flow problems of this form (in distinct variables). Let $$x_{vw}^{st}$$ be the flow variable from $$v^+$$ to $$w^-$$ in the $$s,t$$-flow problem, and add $$x_{vw} \ge x_{vw}^{st} + x_{wv}^{st}$$ as a constraint, for each $$s,t$$.

(I'm assuming the graph is undirected, so we have a single $$x_{vw}$$ variable for the unordered pair $$\{v,w\}$$.)

Then $$x_{vw}$$ will only need to be $$1$$ if the edge $$vw$$ is used by any of the $$3$$-connectivity flow problems, so the graph $$G$$ defined by $$E(G) = \{vw : x_{vw} = 1\}$$ is $$3$$-connected.

This definitely works as an integer program, but at least the flow subproblems have integer basic solutions, so their linear relaxations work fine as well. The variables $$x_{vw}$$ might need to be integer variables, though, I'm not sure. But their linear relaxation gives an edge-weighted graph which seems $$3$$-connected in some nontrivial sense, too.

Also, the block structure of this problem makes Benders decomposition a natural tool: for any fixed value of the $$x_{vw}$$ variables, we have $$\binom n2$$ flow problems that can be solved independently.

Another option is an integer program with exponentially many constraints. Just have a variable $$x_{vw} \in \{0,1\}$$ for each edge $$vw$$ and for every partition $$V = S \cup T \cup \{a,b\}$$ require that $$\sum_{v \in S} \sum_{w \in T} x_{vw} \ge 1.$$ This has the advantage of simplicity but not many other advantages: the previous program only had $$O(n^4)$$ variables and constraints.

• I am amazed. I am reading your first approach to get the ramifications now. – Paramar May 3 at 16:04