On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs

Pavol Hell ; César Hernández-Cruz

Discussiones Mathematicae Graph Theory, Tome 34 (2014), p. 167-185 / Harvested from The Polish Digital Mathematics Library

Résumé

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.

Détail

Publié le : 2014-01-01

Zbl 1292.05124

EUDML-ID : urn:eudml:doc:267793

Bibliographie

[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[Crossref] | Zbl 0832.05048

[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[Crossref] | Zbl 0721.05027

[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[Crossref]

[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[Crossref][WoS] | Zbl 1213.05112

[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. | Zbl 1223.05097

[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[Crossref] | Zbl 1284.05114

[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[Crossref]

[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.[WoS][Crossref] | Zbl 1281.05068

[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[WoS][Crossref]

[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[Crossref] | Zbl 0060.06506

[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 [Crossref]