Conflict-Free Cuts: Exploring the Boundaries of Tractability
Source: arxiv.org/abs/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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.15846
curl -X POST /api/v1/records/arxiv/2611.15846/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.15846/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'