<p>I am trying to solve a linear programming problem that deals with finding an optimal subgraph as a function of several parameters. The case is I am trying to model a constraint that ensures that the selected subgraph is connected without success.</p>
<p>I know that there is a theorem that assures that if you have a number of edges less than the number of vertices minus one the graph is not connected, but the fulfillment of this restriction does not prove that the graph is connected.</p>
<p>Could someone tell me a constraint that ensures the connectivity of the selected network?</p>

CC BY-SA 4.0
2023-02-27T15:20:38.497Z
Is it really linear programming or (mixed) integer linear programming, i.e. are you working with integer variables?
Christian Komusiewicz
CC BY-SA 4.0
2023-02-27T15:34:20.177Z
Yes, assume this is an integer programming problem.
AdCerros
CC BY-SA 4.0
2023-02-27T15:46:41.790Z
Take a look at, say, the LP for minimum spanning tree.  You just need to ensure that every cut is crossed.  A-priori this gives exponentially many constraints, so you can either use a separation oracle (e.g. for Ellipsoid) or you can do it with polynomially many constraints (e.g. by adding, for every pair of vertices $u, v$, constraints that there is a $u-v$ flow of value 1 in the graph where the LP edge weights are the capacities).  This "spanning tree polytope" has optimal integer solutions, so you don't need to use integer linear programming.
Neal Young
CC BY-SA 4.0
2023-02-27T15:47:35.190Z
p.s. this is probably not a research-level question so may be better suited to cs.se (and so the question may be closed).
Neal Young
CC BY-SA 4.0
2023-02-27T15:58:01.753Z
Note that the selected tree may or may not include all vertices of the tree, so I don't know if this can be related to the minimum expasion tree.
AdCerros
CC BY-SA 4.0
2023-02-27T17:10:22.163Z
So you want a Steiner tree.  The techniques I mentioned work for that as well, just take $u$ and $v$ to be all pairs of vertices that you want to be connected (i.e., forced into the tree).
Neal Young
CC BY-SA 4.0
2023-02-27T22:12:35.010Z
(although in that case the polytope does not generally have only integer vertices...) E.g. search for poly-time approximation algorithms for "network design" problems. e.g. https://scholar.google.com/scholar?cluster=5863538968633157232&hl=en&as_sdt=0,30&as_vis=1
Neal Young
CC BY-SA 4.0
2023-02-28T07:03:32.907Z
The connected subgraph polytope is studied e.g. in Section 2 of https://doi.org/10.1137/090752614 . Theorem 2.6 characterizes the integral vertices in terms of linear inequalities. If we consider a linear objective function (whose coefficients need not be non-positive or non-negative), the minimum cost connected subgraph need not be a tree.
Max Flow
CC BY-SA 4.0
2023-02-28T20:07:04.480Z
I think I don't quite understand the similarity between this problem and a Steiner tree, could someone give me some insight on the subject?
AdCerros
CC BY-SA 4.0
2023-03-01T10:47:41.077Z
This is not really a research question, and runs the risk to be seen as a homework question. Maybe you could explain the context in which you fell on this question to convince people that you are not just a student asking on stackexchange for the solution to their homework (no offense meant if you are, but then checkout cstheory.stackexchange.com/tour, and maybe consider asking on cs.stackexchange.com ?)
J.y B.y
<graph-theory><linear-programming>
Ensuring the connectivity of an undirected graph through linear programming
AdCerros
# Ensuring the connectivity of an undirected graph through linear programming

(Asked by: username_0 on 2023-02-27)

I am trying to solve a linear programming problem that deals with finding an optimal subgraph as a function of several parameters. The case is I am trying to model a constraint that ensures that the selected subgraph is connected without success.

I know that there is a theorem that assures that if you have a number of edges less than the number of vertices minus one the graph is not connected, but the fulfillment of this restriction does not prove that the graph is connected.

Could someone tell me a constraint that ensures the connectivity of the selected network?

**Tags:** graph-theory, linear-programming
> **Comments:**
> **username_1**: Is it really linear programming or (mixed) integer linear programming, i.e. are you working with integer variables?  
> **username_0**: Yes, assume this is an integer programming problem.  
> **username_2**: Take a look at, say, the LP for minimum spanning tree.  You just need to ensure that every cut is crossed.  A-priori this gives exponentially many constraints, so you can either use a separation oracle (e.g. for Ellipsoid) or you can do it with polynomially many constraints (e.g. by adding, for every pair of vertices $u, v$, constraints that there is a $u-v$ flow of value 1 in the graph where the LP edge weights are the capacities).  This "spanning tree polytope" has optimal integer solutions, so you don't need to use integer linear programming.  
> **username_2**: p.s. this is probably not a research-level question so may be better suited to cs.se (and so the question may be closed).  
> **username_0**: Note that the selected tree may or may not include all vertices of the tree, so I don't know if this can be related to the minimum expasion tree.  
> **username_2**: So you want a Steiner tree.  The techniques I mentioned work for that as well, just take $u$ and $v$ to be all pairs of vertices that you want to be connected (i.e., forced into the tree).  
> **username_2**: (although in that case the polytope does not generally have only integer vertices...) E.g. search for poly-time approximation algorithms for "network design" problems. e.g. https://scholar.google.com/scholar?cluster=5863538968633157232&hl=en&as_sdt=0,30&as_vis=1  
> **username_3**: The connected subgraph polytope is studied e.g. in Section 2 of https://doi.org/10.1137/090752614 . Theorem 2.6 characterizes the integral vertices in terms of linear inequalities. If we consider a linear objective function (whose coefficients need not be non-positive or non-negative), the minimum cost connected subgraph need not be a tree.  
> **username_0**: I think I don't quite understand the similarity between this problem and a Steiner tree, could someone give me some insight on the subject?  
> **username_4**: This is not really a research question, and runs the risk to be seen as a homework question. Maybe you could explain the context in which you fell on this question to convince people that you are not just a student asking on stackexchange for the solution to their homework (no offense meant if you are, but then checkout cstheory.stackexchange.com/tour, and maybe consider asking on cs.stackexchange.com ?)  

---

## 0 answers

