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/

[1] J. Bang-Jensen and G. Gutin, Digraphs (Springer-Verlag, Berlin Heidelberg New York, 2002).

[2] J. Bang-Jensen and J. Huang, Quasi-transitive digraphs, J. Graph Theory 20 (1995) 141-161. doi:10.1002/jgt.3190200205

[3] C. Berge, Graphs (North-Holland, Amsterdam, 1985).

[4] C. Berge and P. Duchet, Recent problems and results about kernels in directed graphs, Discrete Math. 86 (1990) 27-31. doi:10.1016/0012-365X(90)90346-J

[5] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer-Verlag, Berlin Heidelberg New York, 2008).

[6] V. Chvátal, On the computational complexity of finding a kernel, Technical Report Centre de Recherches Mathématiques, Université de Montréal CRM-300 (1973).

[7] A.S. Fraenkel, Planar kernel and Grundy with d ≤ 3, d+ ≤ 2, d− ≤ 2 are NP-complete, Discrete Appl. Math. 3 (1981) 257-262. doi:10.1016/0166-218X(81)90003-2

[8] H. Galeana-Sánchez, I.A. Goldfeder and I. Urrutia, On the structure of 3-quasi-transitive digraphs, Discrete Math. 310 (2010) 2495-2498. doi:10.1016/j.disc.2010.06.008

[9] H. Galeana-Sánchez and C. Hernández-Cruz, k-kernels in multipartite tournaments, AKCE Int. J. Graphs Comb. 8 (2011) 181-198.

[10] H. Galeana-Sánchez and C. Hernández-Cruz, On the existence of k-kernels digraphs and in weighted digraphs, AKCE Int. J. Graphs Comb. 7 (2010) 201-215.

[11] H. Galeana-Sánchez and C. Hernández-Cruz, Cyclically k-partite digraphs and k- kernels, Discuss. Math. Graph Theory 31 (2011) 63-78. doi:10.7151/dmgt.1530

[12] H. Galeana-Sánchez and C. Hernández-Cruz, k-kernels in generalizations of transitive digraphs, Discuss. Math. Graph Theory 31 (2011) 293-312. doi:10.7151/dmgt.1546

[13] H. Galeana-Sánchez, C. Hernández-Cruz and M.A. Juárez-Camacho, On the existence and number of (k+1)-kings in k-quasi-transitive digraphs, Discrete Math. 313 (2013) 2582-2591.

[14] C. Hernández-Cruz and H. Galeana-Sánchez, k-kernels in k-transitive and k-quasi- transitive digraphs, Discrete Math. 312 (2012) 2522-2530. doi:10.1016/j.disc.2012.05.005

[15] M. Kwaśnik, A. W loch and I. W loch, Some remarks about (k, l)-kernels in directed and undirected graphs, Discuss. Math. 13 (1993) 29-37.

[16] M. Richardson, On weakly ordered systems, Bull. Amer. Math. Soc. 52(2) (1946) 113-116. doi:10.1090/S0002-9904-1946-08518-3

[17] A. Sánchez-Flores, A counterexample to a generalization of Richardson’s theorem, Discrete Math. 65 (1987) 319-320. doi:10.1016/0012-365X(87)90064-1