Premium
A dichotomy for the kernel by H ‐walks problem in digraphs
Author(s) -
GaleanaSánchez Hortensia,
HernándezCruz César
Publication year - 2019
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22389
Subject(s) - digraph , vertex (graph theory) , combinatorics , mathematics , quantum walk , discrete mathematics , arc (geometry) , kernel (algebra) , graph , physics , geometry , quantum mechanics , quantum algorithm , quantum
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.