3-connectivity as a set linear constraints

Question

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)?

Answer 1

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.