Minimum graph cut with constraints

Question

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.

Answer 1

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.