Algorithmic aspects of small quasi-kernels

DOI10.1007/978-3-031-15914-5_27MaRDI QIDQ6043190zbMATH OpenFDO

Authors Hélène Langlois, Frédéric Meunier, Romeo Rizzi, Stéphane Vialette

Publication date 5 May 2023

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2107.03793

zbMATH Keywords

computational complexitydigraphquasi-kernel

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Abstract: In a digraph, a quasi-kernel is a subset of vertices that is independent and such that every vertex can reach some vertex in that set via a directed path of length at most two. Whereas Chv'atal and Lov'asz proved in 1974 that every digraph has a quasi-kernel, very little is known so far about the complexity of finding small quasi-kernels. In 1976 ErdH{o}s and Sz'ekely conjectured that every sink-free digraph $D=(V,A)$ has a quasi-kernel of size at most $|V|/2$. Obviously, if $D$ has two disjoint quasi-kernels then it has a quasi-kernel of size at most $|V|/2$, and in 2001 Gutin, Koh, Tay and Yeo conjectured that every sink-free digraph has two disjoint quasi-kernels. Yet, they constructed in 2004 a counterexample, thereby disproving this stronger conjecture. We shall show that, not only sink-free digraphs occasionally fail to contain two disjoint quasi-kernels, but it is computationally hard to distinguish those that do from those that do not. We also prove that the problem of computing a small quasi-kernel is polynomial time solvable for orientations of trees but is computationally hard in most other cases (and in particular for restricted acyclic digraphs).

Cites work

• scientific article; zbMATH DE number 3465337 (Why is no real title available?)
• scientific article; zbMATH DE number 1764950 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• Analytical approach to parallel repetition
• Disjoint quasi-kernels in digraphs
• Finding kernels or solving SAT
• Fundamentals of parameterized complexity
• On the number of quasi-kernels in digraphs
• Optimization, approximation, and complexity classes
• Perfect graphs, kernels, and cores of cooperative games
• Planar kernel and Grundy with d 3, dout 2, din 2 are NP- complete
• Reducibility among combinatorial problems
• Short proofs of classical theorems
• The list chromatic index of a bipartite multigraph
• Theory of games and economic behavior.
• Towards the small quasi-kernel conjecture

Cited in

(4)

• On the small quasi-kernel conjecture -- a survey
• Results on the small quasi-kernel conjecture
• Generalized quasikernels in digraphs
• Quasi-kernels in split graphs

This page was built for publication: Algorithmic aspects of small quasi-kernels

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6043190)