# Kernels and quasi-kernels in digraphs.

- Authors
- Publication Date
- Dec 20, 2023
- Source
- HAL-Descartes
- Keywords
- Language
- English
- License
- Unknown
- External links

## Abstract

An important concept in directed graph theory is that of a kernel. This notion was introduced by Morgenstern and von Neumann for studying winning strategies in combinatorial games and now has numerous applications in various fields such as graph theory, game theory, economics, and logic.In a directed graph, D=(V,A), a kernel is a subset N of vertices that is both independent—no pair of vertices in N is connected by an arc—and absorbing—every vertex outside N is the origin of an arc pointing to an element in N. Not all graphs have a kernel, as demonstrated by the example of odd-length cycles. Deciding whether a graph has a kernel is NP-complete. However, there are graphs for which this decision problem is trivial: a directed perfect graph without directed cycles of length 3 always has a kernel. This is a consequence of a theorem by Boros and Gurvich, proved by them in 1996 (and conjectured by Berge and Duchet in 1980). However, the algorithmic complexity of finding a kernel is not known for this class, posing an important open question.The first part of this thesis focuses on studying this question. The polynomial result about some special cases had already been established, such as for triangulated graphs or bipartite graphs. We extend this list, including a generalization of comparability graphs.Chvátal and Lovász showed in 1974 that a slight modification of the kernel definition ensures its systematic existence: they proved that every directed graph has an independent subset N such that every vertex outside N has a path of length at most 2 to an element of N. Such a subset is a quasi-kernel. Their proof provides a polynomial-time algorithm to find one in any directed graph. However, a thorough algorithmic study of quasi-kernels had never been conducted before and constitutes an open question. This study answered natural questions, such as the existence of distinct quasi-kernels or the minimal size of a quasi-kernel, both motivated by a conjecture by Erdős and Székely from 1976.The second part of this thesis consists of the algorithmic study of quasi-kernels and specific cases related to the Erdős-Székely conjecture.