A dichotomy for the kernel by H ‐walks problem in digraphs

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 → V H . An H ‐walk of D is a walk ( v 0 , … , 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 ≤ i ≤ n − 1 . For u , v ∈ 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 ⊆ V D is a kernel by H ‐walks of D if every vertex in V D \ 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 H ‐arc‐colored digraph D has a kernel by H ‐walks. In this study, 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 N P ‐complete.