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

Pavol Hell; César Hernández-Cruz

Discussiones Mathematicae Graph Theory (2014)

- Volume: 34, Issue: 1, page 167-185
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topPavol Hell, and César Hernández-Cruz. "On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs." Discussiones Mathematicae Graph Theory 34.1 (2014): 167-185. <http://eudml.org/doc/267793>.

@article{PavolHell2014,

abstract = {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.},

author = {Pavol Hell, César Hernández-Cruz},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {kernel; 3-kernel; NP-completeness; multipartite tournament; cyclically 3-partite digraphs; k-quasi-transitive digraph},

language = {eng},

number = {1},

pages = {167-185},

title = {On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs},

url = {http://eudml.org/doc/267793},

volume = {34},

year = {2014},

}

TY - JOUR

AU - Pavol Hell

AU - César Hernández-Cruz

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

JO - Discussiones Mathematicae Graph Theory

PY - 2014

VL - 34

IS - 1

SP - 167

EP - 185

AB - 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.

LA - eng

KW - kernel; 3-kernel; NP-completeness; multipartite tournament; cyclically 3-partite digraphs; k-quasi-transitive digraph

UR - http://eudml.org/doc/267793

ER -

## References

top- [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] Zbl0832.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] Zbl0721.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] Zbl1213.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. Zbl1223.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] Zbl1284.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] Zbl1281.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] Zbl0060.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]