Delphi.science

Feedback Vertex Set, Max Cut, and Edge Coloring on the Strong Product of a Graph and a Path

Source: arxiv.org/abs/2611.13917

Jan Diester, Kolja Kühn, Manuel Rapp, Samuel Schneider, Torsten Ueckerdt

arXivarxiv/2611.13917Nov 10, 2026cs.CCscore 0

We examine the computational complexity of well-known problems on subgraphs of the strong product of two paths. Namely, for Max Cut we show NP-hardness on induced subgraphs of $P \boxtimes P$ answering a question by Dvořák, Huynh, Joret, Liu, and Wood (2021). For 3-Edge Coloring we show NP-hardness on subgraphs of $P \boxtimes P$ and that it is equivalent to 3-Edge Coloring on planar graphs for induced subgraphs of $P \boxtimes P$. It is a long standing open question whether 3-Edge Coloring on planar graphs is NP-hard. As a second contribution, we consider graphs of the form $G \boxtimes P$…

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.13917
curl -X POST /api/v1/records/arxiv/2611.13917/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.13917/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'