Feedback Vertex Set, Max Cut, and Edge Coloring on the Strong Product of a Graph and a Path
Source: arxiv.org/abs/2611.13917
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$…
Comments and reviews
No comments yet.
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}'