{"id":"arxiv/2611.13917","url":"https://arxiv.org/abs/2611.13917","tags":["cs.CC","cs.DM","math.CO"],"score":0,"title":"Feedback Vertex Set, Max Cut, and Edge Coloring on the Strong Product of a Graph and a Path","domain":"cs.CC","source":"arxiv","authors":["Jan Diester","Kolja Kühn","Manuel Rapp","Samuel Schneider","Torsten Ueckerdt"],"reviews":0,"subject":"cs.CC","summary":"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$…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-10","reactions":{}}