Cardinality constrained and multicriteria (multi)cut problems

In 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,…,BRB1,…,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 j  th criterion, is at most BjBj, for 1⩽j⩽R1⩽j⩽R. We prove this problem to be NPNP-complete in paths and cycles even if R=2R=2. When R=2R=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 NPNP-complete if k=1k=1 and that, for arbitrary k  , it remains strongly NPNP-complete in directed stars but can be solved by (polynomial) dynamic programming algorithms in paths and cycles. For k=1k=1, we also prove that R-CriMultiCut is strongly NPNP-complete in planar bipartite graphs and remains NPNP-complete in K2,dK2,d even for R=2R=2.