<p>The problem that you describe is NP-hard even on stars as we can reduce Multicut in Trees to its decision version (where we have a cost bound). In Multicut in Trees the input is a tree $G=(V,E)$, a set $S\subseteq {V\choose 2}$ of vertex pairs, and an integer $k$ and one asks whether one can separate all vertex pairs of $S$ by removing at most $k$ edges. The reduction to your problem is to keep $G$ and $S$ as they are, set $N$ to $k+1$ and set the cost bound for accepting a solution to $+\infty$. Then the Multicut instance is a yes-instance if and only if the constructed instance is a yes-instance.</p>

<p>Note that this reduction does not specify how to define the edge weights. In other words, even testing whether there is a feasible solution, that is, any partition with $N$ parts is NP-hard.    </p>

CC BY-SA 4.0
2018-08-03T14:25:37.637Z
I see. Are there any approximate/heuristic based approaches that I could use or extend to solve my problem?
Ali250
CC BY-SA 4.0
2018-08-06T07:06:11.137Z
One could try different variants of a greedy heuristic: for example, one could compute the edge whose removal separates the most pairs that need to be separated and then greedily remove this edge until all the separation constraints are fulfilled.
Christian Komusiewicz
CC BY-SA 4.0
2018-08-03T13:07:39.113Z
2018-08-03T13:07:39.113Z
Christian Komusiewicz
<p>Given an undirected acyclic raph $G = \{V,E\}$, with each edge $e$ having weight $c_e$in the range $[-\infty, +\infty] $, I want to compute a partition of the graph into $N$ disjoint sets $G_i, i=1,...,N$ by removing certain edges such that the overall sum of the remaining edge weights across all $N$ sets is minimized. In addition, I would like to set constraints that would force certain pairs of vertices to be in disjoint sets.</p>

<p>Formally speaking, if each set $G_i$ has $M$ edges $e_j, \hspace{2pt}j=1,...,M$, then:</p>

<p>$$min \sum_i^N\sum_j^Me_j$$</p>

<p>and $\mathbb{P}$ is the set of constraints which disallows certain pairs of nodes $v_k$ and $v_l$ from being assigned to the same set:
$$v_k \in G_k,v_l \in G_l \hspace{2pt} \land \hspace{2pt} k \neq l, \hspace{3pt}\forall (k,l) \in \mathbb{P}$$</p>

<p>I've searched around for this, and most minimum cut algorithms only seem to offer bipartite splits. I also looked into s-t cut algorithms, but in my case rather than having a single source and sink I have multiple such pairs that I want to keep in disjoint sets.</p>

<p><strong>Additional Information</strong> I'm trying to model segments of walking trajectories as graph nodes. The edge weights denote the dissimilarity score between two trajectory segments (conversely, if I use the similarity score then I require the maximum cut). The constraints will be used to ensure that two trajectory segments that overlap in time must never be assigned to the same set.</p>

<graph-theory><optimization><max-flow-min-cut>
Minimum graph cut with constraints
Ali250
# Minimum graph cut with constraints

(Asked by: username_0 on 2018-08-03)

Given an undirected acyclic raph $G = \{V,E\}$, with each edge $e$ having weight $c\_e$in the range $[-\infty, +\infty] $, I want to compute a partition of the graph into $N$ disjoint sets $G\_i, i=1,...,N$ by removing certain edges such that the overall sum of the remaining edge weights across all $N$ sets is minimized. In addition, I would like to set constraints that would force certain pairs of vertices to be in disjoint sets.

Formally speaking, if each set $G\_i$ has $M$ edges $e\_j, \hspace{2pt}j=1,...,M$, then:

$$min \sum\_i^N\sum\_j^Me\_j$$

and $\mathbb{P}$ is the set of constraints which disallows certain pairs of nodes $v\_k$ and $v\_l$ from being assigned to the same set:
$$v\_k \in G\_k,v\_l \in G\_l \hspace{2pt} \land \hspace{2pt} k \neq l, \hspace{3pt}\forall (k,l) \in \mathbb{P}$$

I've searched around for this, and most minimum cut algorithms only seem to offer bipartite splits. I also looked into s-t cut algorithms, but in my case rather than having a single source and sink I have multiple such pairs that I want to keep in disjoint sets.

**Additional Information** I'm trying to model segments of walking trajectories as graph nodes. The edge weights denote the dissimilarity score between two trajectory segments (conversely, if I use the similarity score then I require the maximum cut). The constraints will be used to ensure that two trajectory segments that overlap in time must never be assigned to the same set.

**Tags:** graph-theory, optimization, max-flow-min-cut

---

## 1 answers

### Answer by username_1 on 2018-08-03. Score: 4

The problem that you describe is NP-hard even on stars as we can reduce Multicut in Trees to its decision version (where we have a cost bound). In Multicut in Trees the input is a tree $G=(V,E)$, a set $S\subseteq {V\choose 2}$ of vertex pairs, and an integer $k$ and one asks whether one can separate all vertex pairs of $S$ by removing at most $k$ edges. The reduction to your problem is to keep $G$ and $S$ as they are, set $N$ to $k+1$ and set the cost bound for accepting a solution to $+\infty$. Then the Multicut instance is a yes-instance if and only if the constructed instance is a yes-instance.

Note that this reduction does not specify how to define the edge weights. In other words, even testing whether there is a feasible solution, that is, any partition with $N$ parts is NP-hard.

> **Comments:**
> **username_0**: I see. Are there any approximate/heuristic based approaches that I could use or extend to solve my problem?  
> **username_1**: One could try different variants of a greedy heuristic: for example, one could compute the edge whose removal separates the most pairs that need to be separated and then greedily remove this edge until all the separation constraints are fulfilled.  

---

