4
$\begingroup$

I have a problem on a graph (of maximum degree $c$) which looks for a connected subset of edges fulfilling some properties.

I have problems formulating the connectedness condition in an IP/LP. The only approach I can think of is to iteratively force the solution to contain an edge in every graph-cut.

Does anyone have any ideas?

Thank you

  • 0
    Hi, thanks for your answer. I didn't have time to think about your solution in depth, but I'll get back to you later.2011-12-18

2 Answers 2

6

I believe you can view the connectedness requirement like a maximum flow problem.

Introduce a new "supersource" node and a "supersink" node. Denote your candidate for a connected subgraph by $S$. Create an arc connecting the supersource to one of the nodes $x$ in $S$. Create an arc from each node in $S$ to the supersink; each of these arcs should have capacity $1$. Give each arc attached to a node not in $S$ or the supersource or supersink a capacity of $0$.

Then there is total flow of amount $|S|$ from the supersource to the supersink if and only if $S$ is connected. If you can find a total flow of amount $|S|$, the capacities on the arcs to the supersink mean that each flow of one unit must have gone through a different node in $S$ just before reaching the supersink. Since each flow of one unit must also go through $x$, this means that $x$ must be connected to all other nodes in $S$, and so all nodes in $S$ must be connected to each other.

The constraints in the maximum flow problem are nice (just flow-balance, nonnegativity, and capacity constraints), so implementing this shouldn't be too bad. You should also make the total flow being equal to $|S|$ one of the constraints (rather than trying to maximize the flow, so that's how this differs from the maximum flow problem). If you want to include these constraints as part of your overall IP/LP formulation rather than just as a check at the end, you'll need to make sure the flow constraints are active only for the nodes you're considering for your candidate $S$ - probably through some logical (binary) constraints.

0

Since I have the same problem at hand, I look through a dozen of papers from 1980s to 2010s, finally found a method that seems efficient enough and simple enough for me.

It is a particular version of flow formulation of Steiner tree problem, which is explained here.