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 Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-10 Page: https://delphi.science/r/arxiv/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$…