×

On the complexity of the 3-kernel problem in some classes of digraphs. (English) Zbl 1292.05124

Summary: 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\in N\), we have \(d(u,v), d(v,u)\geq k\); it is \(l\)-absorbent if for every \(u\in V(D)-N\) there exists \(v\in N\) such that \(d(u,v)\leq 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.

MSC:

05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI

References:

[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; · Zbl 0832.05048
[3] C. Berge, Graphs (North-Holland, Amsterdam, 1985).; · Zbl 0565.05030
[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; · Zbl 0721.05027
[5] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer-Verlag, Berlin Heidelberg New York, 2008).; · Zbl 1134.05001
[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; · 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.; · Zbl 1241.05042
[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; · 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; · Zbl 1234.05113
[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.; · 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; · Zbl 1246.05067
[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.; · Zbl 0794.05039
[16] M. Richardson, On weakly ordered systems, Bull. Amer. Math. Soc. 52(2) (1946) 113-116. doi:10.1090/S0002-9904-1946-08518-3; · 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;
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.