On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2014-02-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1727 |
| _version_ | 1797704420149952512 |
|---|---|
| author | Hell Pavol Hernández-Cruz César |
| author_facet | Hell Pavol Hernández-Cruz César |
| author_sort | Hell Pavol |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T05:20:09Z |
| format | Article |
| id | doaj.art-cc19f68ae6ec4cd08435cb08a2f87e59 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T05:20:09Z |
| publishDate | 2014-02-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-cc19f68ae6ec4cd08435cb08a2f87e592023-09-03T07:47:24ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922014-02-0134116718510.7151/dmgt.1727dmgt.1727On the Complexity of the 3-Kernel Problem in Some Classes of DigraphsHell Pavol0Hernández-Cruz César1School of Computing Science Simon Fraser University Burnaby, B.C., Canada V5A 1S6School of Computing Science Simon Fraser University Burnaby, B.C., Canada V5A 1S6Let 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.https://doi.org/10.7151/dmgt.1727kernel3-kernelnp-completenessmultipartite tournamentcyclically 3-partite digraphsk-quasi-transitive digraph |
| spellingShingle | Hell Pavol Hernández-Cruz César On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs Discussiones Mathematicae Graph Theory kernel 3-kernel np-completeness multipartite tournament cyclically 3-partite digraphs k-quasi-transitive digraph |
| title | On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs |
| title_full | On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs |
| title_fullStr | On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs |
| title_full_unstemmed | On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs |
| title_short | On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs |
| title_sort | on the complexity of the 3 kernel problem in some classes of digraphs |
| topic | kernel 3-kernel np-completeness multipartite tournament cyclically 3-partite digraphs k-quasi-transitive digraph |
| url | https://doi.org/10.7151/dmgt.1727 |
| work_keys_str_mv | AT hellpavol onthecomplexityofthe3kernelprobleminsomeclassesofdigraphs AT hernandezcruzcesar onthecomplexityofthe3kernelprobleminsomeclassesofdigraphs |