On the generalized multiway cut in trees problem

Given a tree $T=(V,E)$ with $n$ vertices and a collection of terminal sets $D=\{S_1,S_2,\dots ,S_c\}$ , where each $S_i$ is a subset of $V$ and $c$ is a constant, the generalized multiway cut in trees problem (GMWC(T)) asks to find a minimum size edge subset $E^{\prime }\subseteq E$ such that its removal from the tree separates all terminals in $S_i$ from each other for each terminal set $S_i$ . The GMWC(T) problem is a natural generalization of the classical multiway cut in trees problem, and has an implicit relation to the Densest $k$ ‐Subgraph problem. In this paper, we show that the GMWC(T) problem is fixed‐parameter tractable by giving an $O(n^2+2^k)$ time algorithm, where $k$ is the size of an optimal solution, and the GMWC(T) problem is polynomial time solvable when the problem is restricted in paths.We also discuss some heuristics for the GMWC(T) problem