# Constraint that checks for an undirected graph whether it is connected?

I would like to create a constraint with AMPL that checks whether I am able to reach from one node $$v$$ to all other nodes of a set but I don't really know how to formulate it (especially in AMPL (+CPLEX)).

(I am not interested in finding the shortest paths just a path per pair of nodes $$(v,*)$$ (Floyd-Warshall))

Basically the main goal of my optimisation is to split graphs into two subgraphs even so this extends the question itself (the objective function is untested and highly experimental): For a connected graph $$G=(V,E_V)$$ I'd like to find two connected subgraphs $$SG1=(U,E_U)$$ and $$SG2=(W,E_W)$$ $$\begin{split} & \min |\text{card}(U)-\text{card}(W)|\cdot\text{card}\left(N^+_{E_V}(U)\cap N^+_{E_V}(W)\right)\\ & \exists v\in U: N^+_{E_U}(v)=U \text{ therefore the first subgraph is connected}\\ & \exists v\in W: N^+_{E_W}(v)=W \text{ the second subgraph is connected}\\ & U\cap W=\emptyset\\ & N^+_{E} \text{ is the set of nodes that is reachable for a given set of edges} \end{split}$$

• To clarify: In your model, do you have decision variables that turn edges on/off? And you're trying to write constraints that check whether the resulting network is connected? Feb 17 '20 at 16:05
• One moment will add (I think) the details you asked for. Feb 17 '20 at 16:40

I am aware of models that model such constraints using a network-flow-type approach. The basic idea is to create a source node that send "flow" of an imaginary product for which all nodes have a demand of 1. There are no costs for the flows.

In your case the problem is trickier because you would need two source nodes, and maybe two types of imaginary products, and maybe you have a constraint that each node needs one type or the other—but hopefully you can make use of this idea.

I would also suggest doing an online search for "connectivity constraints". There are other approaches in the literature.

One possible solution (not necessarily quick or efficient) is a lazy constraint approach:

• Solve your problem, ignoring the connection requirement
• Examine the solution and find the subgraph $$H$$ that is connected to $$v$$.
• If $$H=G$$, you are finished.
• Otherwise, add a constraint that at least one of the edges between $$H$$ and not-$$H$$ is connected, and repeat.

This post by Bob Fourer gives an example of the same approach as applied to a TSP.

You may have a look at this presentation about network flows implementations in AMPL. In the presentation, the authors talked about new AMPL implementations of "arc" and "node" especially on page 8 they mentioned keywords like from and to that I think will help you design your constraints in AMPL. There is also AMPL book chapter about network linear programs that you can read more about the topic. I hope it works for you.

• If I'm not mistaken, I think these AMPL features just make it easier to define models on networks. I think the OP is asking about constraints that check for connectedness, given that the structure of the network itself may be determined by decision variables. Feb 17 '20 at 16:04
• @LarrySnyder610 You are right Dr. Snyder before the question has been changed, I thought the mentioned keywords could be helpful in writing the necessary constraints in AMPL. But now, my answer is away from being a solution. I will just delete the answer if I can not find modify it. Feb 17 '20 at 17:53