The Complexity of $(P_k,P_{\ell })$-Arrowing

Abstract

For fixed nonnegative integers $k$ and $\ell$, the $(P_k,P_{\ell })$-Arrowing problem asks whether a given graph, $G$, has a red/blue coloring of $E(G)$ such that there are no red copies of $P_k$ and no blue copies of $P_{\ell }$. The problem is trivial when $\max (k,\ell )\le 3$, but has been shown to be coNP-complete when $k=\ell =4$. In this work, we show that the problem remains coNP-complete for all pairs of $k$ and $\ell$, except $(3,4)$, and when $\max (k,\ell )\le 3$. Our result is only the second hardness result for $(F,H)$-Arrowing for an infinite family of graphs and the first for 1-connected graphs. Previous hardness results for $(F,H)$-Arrowing depended on constructing graphs that avoided the creation of too many copies of $F$ and $H$, allowing easier analysis of the reduction. This is clearly unavoidable with paths and thus requires a more careful approach. We define and prove the existence of special graphs that we refer to as ``transmitters.'' Using transmitters, we construct gadgets for three distinct cases: 1) $k=3$ and $\ell \ge 5$, 2) $\ell >k\ge 4$, and 3) $\ell =k\ge 4$. For $(P_3,P_4)$-Arrowing we show a polynomial-time algorithm by reducing the problem to 2SAT, thus successfully categorizing the complexity of all $(P_k,P_{\ell })$-Arrowing problems.

Accepted to FCT 2023