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} o V_{H}

. An

H

-walk of

D

is a walk

(v_{0}, d o t s, 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 l e i l e n - 1

. For

u, v i n 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 s u b s e t e q V_{D}

is a kernel by

H

-walks of

D

if every vertex in

V_{D} s e t m i n u s 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

N P

-complete.

Recommendations

Cited in

(3)

This page was built for publication: A dichotomy for the kernel by H‐walks problem in digraphs