3
$\begingroup$

Question:

how can the connectedness-constraint for a subgraph, that is induced by a proper subset $W\subset V$ of the vertices of $G(V,E),\ |V|=n,\ |W|=m$, be formulated in a $LP$ or $ILP$?

Fixing the size of the subgraph is trivial; also some upper bounds on the number of edges between the elements of $W$ may be devised quite easily. I can't however come up with a provably necessary and sufficient condition.

$\endgroup$
2
  • $\begingroup$ Here's a naive idea, which might not work: could you model this as a flow problem? Choose one vertex to be the sink and all the other ones to be the source. (Make sure that if the input on each source is $1$, then on the sink you have $n-1$, if n is the number of vertices in $W$.) Then add constraints that make sure that everything flows. Such a flow should exists if and only if everything is connected to the sink vertex?! $\endgroup$ Sep 29 '17 at 8:25
  • $\begingroup$ @MoritzFirsching I don't think it will work in a one shot setting; it may however work by solving a whole set of programs; a different one for each different source. $\endgroup$ Sep 29 '17 at 8:53
2
$\begingroup$

It looks like Section 3 in Algorithms for the Maximum Weight Connected k -Induced Subgraph Problem (Ernst Althaus, Markus Blumenstock, Alexej Disterhoft, Andreas Hildebrandt and Markus Krupp; COCOA 2014) contains several possible ILP models.

$\endgroup$
0

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.