Geodesic
On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs
Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 1, pp. 167-185

Voir la notice de l'article provenant de la source Library of Science

Let D be a digraph with the vertex set V (D) and the arc set A(D). A subset N of V (D) is k-independent if for every pair of vertices u, v ∈ N, we have d(u, v), d(v, u) ≥ k; it is l-absorbent if for every u ∈ V (D) − N there exists v ∈ N such that d(u, v) ≤ l. A k-kernel of D is a k-independent and (k − 1)-absorbent subset of V (D). A 2-kernel is called a kernel. It is known that the problem of determining whether a digraph has a kernel (“the kernel problem”) is NP-complete, even in quite restricted families of digraphs. In this paper we analyze the computational complexity of the corresponding 3-kernel problem, restricted to three natural families of digraphs. As a consequence of one of our main results we prove that the kernel problem remains NP-complete when restricted to 3-colorable digraphs.
Keywords: kernel, 3-kernel, NP-completeness, multipartite tournament, cyclically 3-partite digraphs, k-quasi-transitive digraph 
@article{DMGT_2014_34_1_a13,
     author = {Hell, Pavol and Hern\'andez-Cruz, C\'esar},
     title = {On the {Complexity} of the {3-Kernel} {Problem} in {Some} {Classes} of {Digraphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {167--185},
     publisher = {mathdoc},
     volume = {34},
     number = {1},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2014_34_1_a13/}
}
TY  - JOUR
AU  - Hell, Pavol
AU  - Hernández-Cruz, César
TI  - On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2014
SP  - 167
EP  - 185
VL  - 34
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2014_34_1_a13/
LA  - en
ID  - DMGT_2014_34_1_a13
ER  - 
%0 Journal Article
%A Hell, Pavol
%A Hernández-Cruz, César
%T On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs
%J Discussiones Mathematicae. Graph Theory
%D 2014
%P 167-185
%V 34
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2014_34_1_a13/
%G en
%F DMGT_2014_34_1_a13
Hell, Pavol; Hernández-Cruz, César. On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs. Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 1, pp. 167-185. http://geodesic.mathdoc.fr/item/DMGT_2014_34_1_a13/