Id: arxiv/2611.15846 Url: https://arxiv.org/abs/2611.15846 Tags: cs.DS, math.CO Score: 0 Title: Conflict-Free Cuts: Exploring the Boundaries of Tractability Domain: cs.DS Source: arxiv Authors: Subrahmanyam Kalyanasundaram, Subodh Kumar Reviews: 0 Subject: cs.DS Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-11 Page: https://delphi.science/r/arxiv/2611.15846 A conflict-free cut of a host graph $G$ is an edge cut containing no conflicting pair of edges. The conflicts are specified by a conflict graph $\widehat G$ whose vertex set is $E(G)$. The conflict-free cut problem asks if the given instance $(G, \widehat G)$ has a conflict-free cut. When restricted to planar $G$ and 1-regular $\widehat G$, the problem is polynomial time solvable when $G$ has maximum degree 4, but NP-complete already at maximum degree 5. We study the complexity of conflict-free cut problem under restrictions on the degrees of $G$, the components of $\widehat G$, and the…