Delphi.science

Conflict-Free Cuts: Exploring the Boundaries of Tractability

Source: arxiv.org/abs/2611.15846

Subrahmanyam Kalyanasundaram, Subodh Kumar

arXivarxiv/2611.15846Nov 11, 2026cs.DSscore 0

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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

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}'