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

Discussiones Mathematicae Graph Theory

Hell Pavol¹  Hernández-Cruz César¹ 

[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