A dichotomy for the kernel by $H$-walks problem in digraphs

Abstract

Let $H=(V_H,A_H)$ be a digraph which may contain loops, and let $D=(V_D,A_D)$ be a loopless digraph with a coloring of its arcs $c:A_D\to V_H$. An $H$-walk of $D$ is a walk $(v_0,\dots ,v_n)$ of $D$ such that $(c(v_{i-1},v_i),c(v_i,v_{i+1}))$ is an arc of $H$, for every $1\le i\le n-1$. For $u,v\in V_D$, we say that $u$ reaches $v$ by $H$-walks if there exists an $H$-walk from $u$ to $v$ in $D$. A subset $S\subseteq V_D$ is a kernel by $H$-walks of $D$ if every vertex in $V_D\setminus S$ reaches by $H$-walks some vertex in $S$, and no vertex in $S$ can reach another vertex in $S$ by $H$-walks. A panchromatic pattern is a digraph $H$ such that every arc-colored digraph $D$ has a kernel by $H$-walks. In this work, we prove that every digraph $H$ is either a panchromatic pattern, or the problem of determining whether an arc-colored digraph $D$ has a kernel by $H$-walks is $NP$-complete.

20 pages, 3 figures