Multicut and multiway cut problems on graphs have received significant attention in the literature. Both of the problems are hard and have interesting applications. The authors of this paper study variants of the above problems. In particular, they study the multicut problem on trees (MCT) and a generalized version of the multiway cut problem on trees (GMWCT). Both of the above variants are parameterized versions of the original problems where instead of computing an edge set as a solution to the problem, we are asked whether an edge set of size k (given as an input parameter) exists (satisfying the required condition).

The main contributions of the authors in this paper are threefold:

First, they “present a parameterized algorithm for the MCT problem ... that improves the current best algorithm of Chen et al. [1].” Notably, to achieve this improvement, the authors have exploited a “connection between the MCT problem and the vertex cover problem, first exploited in the [same] paper [1].”

Second, the authors answer an open question in the literature by showing that the GMWCT problem is polynomially solvable “if the number of terminal sets is fixed.” Notably, the multiway cut on trees problem has already been shown in the literature to be polynomially solvable.

Third, they show that the GMWCT problem can be reduced to the MCT problem implying a polynomial-time algorithm for GMWCT. While a recent result by Dang et al. [2] also suggests a polynomial-time algorithm for GMWCT, the results presented in this paper ensure a better running time.

Finally, it is worth mentioning that the results as well as the techniques used by the authors give rise to several interesting questions, especially in the context of the connection between MCT and the vertex cover. These questions are expected to be pursued, and more intriguing results may be expected in the near future.