Polyhedral description of kernels

Definitions and mathematical statement

For a finite loopless digraph $D=(V,A)$, a kernel is an independent set $K$ such that every vertex outside $K$ has an outgoing arc into $K$. Let $\chi^K\in\{0,1\}^V$ be its incidence vector and define \[ P_{\rm ker}(D)=\operatorname{conv}\{\chi^K:K\text{ is a kernel of }D\}. \] Use the empty polytope when no kernel exists. The underlying undirected graph joins two vertices whenever there is an arc in either direction.

Determine structural classes of digraphs for which this polytope has an explicit linear-inequality description. The inequalities must be described directly from the graph or a specified representation, rather than obtained by first enumerating all kernels. State whether the system has polynomially many inequalities, permits polynomial-time separation, or is only a combinatorial characterization; these are different strengths of answer.

Every kernel vector obeys \[ x\ge0,\qquad x(Q)\le1\quad(Q\text{ a clique}),\qquad x_v+\sum_{u:vu\in A}x_u\ge1\quad(v\in V). \] Singleton cliques are included. These necessary inequalities suggest a starting relaxation, but the problem does not assert that they always suffice. Integer solutions of the independence and absorption conditions are easy to describe; identifying their convex hull is the additional requirement. A fractional point satisfying the displayed constraints need not be an average of actual kernels. Merely finding one kernel also does not describe this polytope.

Short English statement

Describe the convex hull of kernel incidence vectors by explicit graph-based inequalities for suitable classes of digraphs.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000066 (AMR-029-0066), 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: Polyhedral description of kernels. Original source indexed by AMR-029-0066. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Polyhedral description of kernels. Individual source statement and remarks. https://lemon.cs.elte.hu/egres/open/Polyhedral_description_of_kernels.