Deciding kernel-perfectness

Definitions and mathematical statement

Let $D=(V,A)$ be a finite loopless digraph; opposite arcs are allowed. A kernel is a subset $K\subseteq V$ that is stable and absorbing: no arc has both endpoints in $K$, and every $v\in V\setminus K$ has an arc $v\to u$ with $u\in K$. For $U\subseteq V$, let $D[U]$ be the induced subdigraph retaining exactly the arcs with both endpoints in $U$.

The digraph is kernel-perfect when \[ \text{every }D[U],\ U\subseteq V, \text{ has a kernel}. \] Determine the computational complexity of recognizing kernel-perfect digraphs, both in general and for structurally specified classes. In particular, seek efficient recognition criteria for natural classes where the universal induced-subgraph condition can be tested without enumerating every subset, and hardness classifications where it cannot.

The input is the digraph itself, rather than a supplied kernel for each induced subgraph. Having a kernel in $D$ alone is strictly less demanding than kernel-perfectness. The empty induced subgraph has the empty kernel. With the absorption convention above, reversing all arcs also reverses the direction used in the kernel condition; using out-dominating stable sets without that reversal would describe a different property of the given orientation.

Short English statement

Determine the complexity of recognizing digraphs in which every induced subdigraph has an absorbing stable set.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000025 (AMR-029-0025), 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: Deciding kernel-perfectness. Original source indexed by AMR-029-0025. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Deciding kernel-perfectness. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Deciding_kernel-perfectness.