Réunion d'été SMC 2026
Saint John, 5 - 8 juin 2026
Théorie structurelle et algorithmique des graphes
Org: Ben Cameron (University of Prince Edward Island), Alexander Clow (Simon Fraser University) et Margaret-Ellen Messinger (Mount Allison University)
Org: Ben Cameron (University of Prince Edward Island), Alexander Clow (Simon Fraser University) et Margaret-Ellen Messinger (Mount Allison University)
- IAIN BEATON, Acadia University
- BEN CAMERON, University of Prince Edward Island
- MACKENZIE CARR, Toronto Metropolitan University
- NANCY CLARKE, Acadia University
- ALEXANDER CLOW, Simon Fraser University
An Algorithm for the Small Quasi-Kernels Conjecture [PDF]
- BEN CAMERON, University of Prince Edward Island
-
In a digraph $D$,
a quasi-kernel is an independent set $Q$ such that for every vertex $u$, there is a vertex $v \in Q$ satisfying $\text{dist}(v,u)\leq 2$.
In 1974 Chvátal and Lovász showed every digraph contains a quasi-kernel.
In 1976, P. L. Erdős and Szákely conjectured that every sourceless digraph has a quasi-kernel of order at most $\frac{n}{2}$.
Despite significant recent attention by the community the problem remains far from solved, with no bound of the form $(1-\epsilon)n$ known.
We introduce a polynomial time algorithm which greedily constructs a small quasi-kernel.
Using this algorithm we prove that
for any sourceless digraph $D$ with maximum out-degree $3$
contains a
quasi-kernel of order at most ${4n}/{7}$.
- JULIEN CODSI, Princeton University
- KAREN COLLINS, Wesleyan University
- GENA HAHN, Université de Montréal
- SEAN KIM, Simon Fraser University
- TAITE LAGRANGE, Waterloo University
- MARGARET-ELLEN MESSINGER, Mount Allison University
- BEN SEAMONE, Dawson College
- AGNES TOTSCHNIG, Massachusetts Institute of Technology
- ANN TRENK, Wellesley College
- KAREN COLLINS, Wesleyan University