Answers are grounded in this paper and cite their sources.
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 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 P and that it is equivalent to 3-Edge Coloring on planar graphs for induced subgraphs of P 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 P and show that Feedback Vertex Set on these graphs is FPT in the clique-width of G. Furthermore, we show that it can be solved in polynomial time if G is chordal or co-comparable and that the computational complexity depends on the parity of P if G is bipartite. Namely, it is solvable in polynomial time if P has an even number of vertices but is NP-complete otherwise. For Max Cut, we show that it can be solved in polynomial time if G is bipartite.
No takes yet. Share an insight, caveat, or question.
Diester et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: