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

Abstract

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

How to cite

top

Pavol 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. [1] J. Bang-Jensen and G. Gutin, Digraphs (Springer-Verlag, Berlin Heidelberg New York, 2002). 
  2. [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. [3] C. Berge, Graphs (North-Holland, Amsterdam, 1985). 
  4. [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. [5] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer-Verlag, Berlin Heidelberg New York, 2008). 
  6. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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] 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.