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

  • $\begingroup$ Your variables, I assume, are indicator variables $x_{ij}$ for whether edge $ij$ is present? $\endgroup$ – Misha Lavrov May 3 at 15:15
  • $\begingroup$ yes. Notice that we do not need the minimum flow, so the weights can be arbitrary. $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.