Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
I'm really curious to see how my suggestion worked. Were you able to implement it? If so, how did it perform? (Or did you award me the bounty because I was the only person to offer a suggestion?) –  Mike Spivey Dec 18 '11 at 21:53
    
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. –  stefan Dec 18 '11 at 23:07
add comment

1 Answer

up vote 1 down vote accepted
+50

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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