Discussiones Mathematicae Graph Theory | |
On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs | |
Hell Pavol1  Hernández-Cruz César1  | |
[1] School of Computing Science Simon Fraser University Burnaby, B.C., Canada V5A 1S6; | |
关键词: kernel; 3-kernel; np-completeness; multipartite tournament; cyclically 3-partite digraphs; k-quasi-transitive digraph; | |
DOI : 10.7151/dmgt.1727 | |
来源: DOAJ |
【 摘 要 】
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.
【 授权许可】
Unknown