Finding kernels in special digraphs

Definitions and mathematical statement

Let $D=(V,A)$ be a finite loopless digraph. Opposite arcs may both be present. A kernel is a set $K\subseteq V$ which is independent and absorbing: no arc has both endpoints in $K$, and \[ \text{for every }v\notin K\text{ there is }u\in K \text{ with }vu\in A. \] Thus absorption uses an arc from an outside vertex into the set, not the reverse direction.

Identify structurally defined classes $\mathcal D$ for which kernel existence can be decided, and a kernel constructed when one exists, in time polynomial in $|V|+|A|$. The algorithm's exponent is fixed for the class. State whether membership is promised or efficiently recognizable and whether an additional representation is required. The question does not require polynomial solvability for arbitrary digraphs, where the decision problem is NP-complete.

A specific source-highlighted target is a super-orientation of a perfect graph: replace each undirected edge by one or both directions. A graph is perfect when every induced subgraph has chromatic number equal to its largest clique size. Assume that within every clique, the one-way arcs form an acyclic digraph. Under this hypothesis existence is known; the remaining task is efficient construction for the whole class. Results for narrower classes should specify their extra restrictions. A kernel of one digraph is not a certificate that every induced subdigraph has a kernel, which is the separate kernel-perfectness question.

Short English statement

Find structural classes of digraphs in which a kernel can be found or its absence certified in polynomial time, including the stated perfect-graph class.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000036 (AMR-029-0036), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Finding kernels in special digraphs. Original source indexed by AMR-029-0036. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Finding kernels in special digraphs. Individual source statement and remarks. https://lemon.cs.elte.hu/egres/open/Finding_kernels_in_special_digraphs.