{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-11","reactions":{}}