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.

Improve this question
$\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$
    – Moritz Firsching
    Commented Sep 29, 2017 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$
    – Manfred Weis
    Commented Sep 29, 2017 at 8:53

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .