Minimum label k-cut complexity limits efficient graph separation methods
Minimum Label $k$-Cut on Planar Graphs: Complexity and Color Structure
Data Structures and Algorithms
Summary
This work looks at a puzzle where you have a network with colored connections, and you want to remove the fewest colors to split the network into enough pieces. The authors find that even on simple networks, deciding the best way to do this can be very hard. They also show when certain conditions allow fast solutions and when the problem becomes impossible to solve quickly. These insights help understand which network structures and color patterns make separating networks easier or harder.
What this means in practice
- •For network designers: Design algorithms for cutting colored networks knowing which structures permit efficient minimum label separations and which do not.
- •For routing protocol developers: Understand complexity barriers when color-coded link removals are used for network segmentation in planar or cactus-shaped topologies.
A theory result. No direct application yet.
Authors
Yuanhao Wang, Wei Wang
Abstract
Minimum Label $k$-Cut asks for a minimum-size set of colors such that deleting all edges of these colors leaves at least $k$ connected components. We study how the structure of the underlying graph and its color classes affects the complexity of this problem. Regarding fixed-parameter tractability with respect to $k$ on simple planar graphs, we prove that the problem is W[1]-hard, even when the underlying graph is a cactus graph and each color appears at most twice. Furthermore, for cactus graphs in which every color class is connected, we establish a complexity boundary in terms of the maximum monochromatic degree: when this degree is at most two, an optimal solution can be found in $O(Nk^2)$ time, where $N$ is the input size, with no restriction on color frequency or the number of blocks spanned by a color; allowing the maximum monochromatic degree to increase to three already makes the decision version NP-complete. Finally, we prove that the problem remains W[1]-hard parameterized by $k$ on fan graphs, even when every color class is an induced path. These results show that bounding color frequency does not suffice to eliminate parameterized hardness. They also establish a monochromatic-degree boundary for connected colors on cactus graphs and identify complexity barriers to extending this tractable case to outerplanar graphs.