Given an directed graph $G= (N,E)$, where $N$ is the set of nodes and $E$ is the set of all edges, each associated with a direction. $G$ is a connected graph but not necessarily a complete graph.

A path can start at any of the blue nodes, can contain one or more blue node depending on the graph connectivity and the edges direction, but must end at the destination in red. My graphs are relatively small, thus it is possible to enumerate all possible paths. Let $P$ be the set of all paths with no cycles. In the graph below 7 paths are possible: $P = \{p_{(n_1dst)},p_{(n_2dst)},p_{(n_3dst)},p_{(n_1n_2dst)}, p_{(n_1n_3dst)}, p_{(n_2n_3dst)}, p_{(n_1n_2n_3dst)}\}$.

I want to write a set of constraints that makes sure that in the final solution we obtain a path or a subset of paths such that there's at least one blue node in common with all other blue nodes in the selected paths or all blue nodes are in the same path.

For example, for the graph below a solution that contains $p_{(n_1dst)}$ and $p_{(n_2n_3dst)}$ is not feasible. The possible feasible solutions are if we use at least:

  1. $p_{(n_1n_2n_3dst)}$ + additional paths
  2. $p_{(n_1n_2dst)}$ and $p_{(n_1n_3dst)}$ + additional paths
  3. $p_{(n_1n_2dst)}$ and $p_{(n_2n_3dst)}$ + additional paths
  4. $p_{(n_1n_3dst)}$ and $p_{(n_2n_3dst)}$ + additional paths

If we define $x_{p} \in \{0,1\}^{|P|}$ as a binary variable that equals 1 if path $p$ is used, and 0 otherwise. The following constraints can be added:

$c_1:$ $p_{(n_1n_2dst)} + p_{(n_1n_3dst)} + p_{(n_1n_2n_3dst)} \geq 1$
$c_2:$ $p_{(n_1n_2dst)} + p_{(n_2n_3dst)} + p_{(n_1n_2n_3dst)} \geq 1$
$c_3:$ $p_{(n_1n_3dst)} + p_{(n_2n_3dst)} + p_{(n_1n_2n_3dst)} \geq 1$

if for example $p_{(n_1n_2dst)} = 1$ then $c_1$ and $c_2$ are respected, thus in $c_3$, either $p_{(n_1n_3dst)}$ or $p_{(n_2n_3dst)}$ or $p_{(n_1n_2n_3dst)}$ has to be selected.

enter image description here

While this work for graphs of size 3, I tried to generalize it in this way for larger graphs (size 4 and more): $\sum_{r~\in~\Theta_{n}} x_{p} \geq 1, \forall~ n \in N$, where $\Theta_{n} = n \cup \Bigl\{ \bigcup_{k=1}^{k=|c^{'}|}$ $c^{'} \choose k$ $\Bigr\}, \forall n \in N$, and where $c^{'} = c \setminus \{n\} $. I find for each node $n$ the combination of size 1 to $|N|-1$ of n with the remaining nodes without n. But this didn't work.

Does anyone has an idea on how to make this work, and if this problem has a name in the OR literature?

  • $\begingroup$ Do you mean that you want every pair of selected paths to intersect in at least one blue node? $\endgroup$
    – RobPratt
    Commented Jul 19, 2023 at 19:37
  • $\begingroup$ not necessarily for every pair of selected paths. Imagine you have a graph of 4 nodes where A --> B --> C --> D (A is connected only to B that is only connected to C that is only connected to D). Path $p_{AB}$ and $p_{CD}$ don't intersect in any node, but if one of the following paths $p_{BC}$ or $p_{ABC}$ or $p_{BCD}$ is used we have a feasible solution. $\endgroup$
    – CHE
    Commented Jul 19, 2023 at 20:11

1 Answer 1


It sounds like you want to enforce connectivity of an induced subhypergraph of a hypergraph with the blue nodes as the node set and a hyperedge for each path. You can do this by enforcing connectivity of an induced subgraph in the associated bipartite "incidence" graph with the blue nodes on the left, a node for each hyperedge on the right, and an edge if the blue node appears in the hyperedge.

  • $\begingroup$ I hadn't come across hypergraphs before so I had to read about it. Following your idea I think the connectivity can be enforced for some graphs with special structure by adding the following constraint: $\sum_{p~\in~\Theta_{a}} x_{p} \geq 1 , \forall~ a = (u,v) \in \mathcal{A}$. Where $\mathcal{A}$ is the set of all connected arcs in $G$, and $\Theta_{a}$ is the set of all hyperedges containing the arc $a$. However, for a complete graph of size 4 this won't work. $\endgroup$
    – CHE
    Commented Jul 20, 2023 at 14:23
  • $\begingroup$ There are several alternative formulations that enforce a connected subgraph of a general graph. See optimization-online.org/wp-content/uploads/2020/01/7582.pdf $\endgroup$
    – RobPratt
    Commented Jul 20, 2023 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.