Cardinality constrained and multicriteria (multi)cut problems

AbstractIn this paper, we consider multicriteria and cardinality constrained multicut problems. Let G be a graph where each edge is weighted by R positive costs corresponding to R criteria and consider k source–sink pairs of vertices of G and R integers B1,…,BR. The problem R-CriMultiCut consists in finding a set of edges whose removal leaves no path between the ith source and the ith sink for each i, and whose cost, with respect to the jth criterion, is at most Bj, for 1⩽j⩽R. We prove this problem to be NP-complete in paths and cycles even if R=2. When R=2 and the edge costs of the second criterion are all 1, the problem can be seen as a monocriterion multicut problem subject to a cardinality constraint. In this case, we show that the problem is strongly NP-complete if k=1 and that, for arbitrary k, it remains strongly NP-complete in directed stars but can be solved by (polynomial) dynamic programming algorithms in paths and cycles. For k=1, we also prove that R-CriMultiCut is strongly NP-complete in planar bipartite graphs and remains NP-complete in K2,d even for R=2