# LP Constraints for Connected Subgraphs of Fixed Size

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.

• 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?! – Moritz Firsching Sep 29 '17 at 8:25
• @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. – Manfred Weis Sep 29 '17 at 8:53