# Counting Kernels in Directed Graphs
with Arbitrary Orientations

Bruno Jartoux Ben-Gurion University of the Negev, Israel,
<EMAIL_ADDRESS>
###### Abstract

A kernel of a directed graph is a subset of vertices that is both independent
and absorbing (every vertex not in the kernel has an out-neighbour in the
kernel).

Not all directed graphs contain kernels, and computing a kernel or deciding
that none exist is $\mathbf{NP}$-complete even on low-degree planar digraphs.
The existing polynomial-time algorithms for this problem all restrict both the
undirected structure and the edge orientations of the input: for example, to
chordal graphs without bidirectional edges (Pass-Lanneau, Igarashi and
Meunier, Discrete Appl Math 2020) or to permutation graphs where each clique
has a sink (Abbas and Saoula, 4OR 2005).

By contrast, we count the kernels of a fuzzy circular interval graph in
polynomial time, regardless of its edge orientations, and return a kernel when
one exists. (Fuzzy circular graphs were introduced by Chudnovsky and Seymour
in their structure theorem for claw-free graphs.)

We also consider kernels on cographs, where we establish
$\mathbf{NP}$-hardness in general but linear running times on the subclass of
threshold graphs.

##  1 Introduction

A digraph is a simple, loopless, finite graph plus a choice of orientation for
each edge, which may be in either direction or in both. A kernel111No relation
to the homonymous concept in parametrised complexity. of a digraph is a subset
of vertices that is independent and absorbing, that is, $k$ is a kernel iff
the vertices with at least one outgoing edge to $k$ are exactly those not in
$k$.

#### Background.

Kernels are commonly attributed to [[, §4.5.3 in]]vonNeumann–Morgenstern (as
solutions of certain multi-player games), despite similar ideas in early 20th
century proto-game theory (Bouton on Nim [Bou01] and Zermelo on chess
[Zer13]). Besides cooperative and combinatorial games [vNM44, BG06, Fra97,
DM93], kernels make various appearances in logic (paradoxes, argumentation,
default logic [Dyr12, DMP97, BR77]) and combinatorics (the proof of the Dinitz
conjecture [Gal95]). Most of these applications deal with complexity arising
from cyclic, self-referential behaviour.

Kernels are inclusion-maximal independent sets, but not all digraphs have
kernels: for example directed odd cycles do not. Given a digraph $D$ and the
set $\ker D$ of its kernels, deciding whether $\ker D$ is nonempty, computing
$\lvert\ker D\rvert$, or building some $k\in\ker D$ are natural computational
problems. However, the decision problem is already $\mathbf{NP}$-complete,
even when $D$ is planar with maximum degree 3 [Chv73, Fra81], or when $D$ is
the line graph of a bipartite graph (with arbitrary edge orientations)
[Azi+22]. Therefore the counting and search problems are at least as hard
($\mathbf{\\#P}$\- and $\mathbf{FNP}$-complete). The literature on the
existence and computation of kernels and related structures is too vast to
relate here; recent summaries are found in Boros–Gurvich-coresPass-
LanneauIM[§3.8 in][]bang-jensenDigraphs2009. The main insight is that
interleaved directed cycles are the source of computational hardness. In fact,
a simple inductive argument shows that every acyclic digraph admits one unique
kernel.

#### Kernels in specific digraph classes.

Stable marriages à la Gale–Shapley are in bijection with the kernels of a
certain (suitably oriented) perfect line graph [GS62, GI89]. The remarkable
lattice structure of the set of kernels in that setting has led to interest in
other classes of claw-free or perfect graphs. In some, various conditions on
edge orientations lead to polynomial-time search [[, e.g.]]Maffray-
line,Abbas–Saoula,Walicki–Sjur-paperA,Pass-LanneauIM. Forbidding bidirectional
edges and forcing every clique to have a sink are the most common examples.

In contrast, we would like to solve kernel problems with restrictions on the
undirected structure only—not on the edge orientations. To my knowledge, the
sole results in this vein are tractability parametrised by tree-width (see
Section 3.1) and an exponential-time decision algorithm for general
digraphs222The running time is $\mathcal{O}(1.427^{n})$. A ‘naive’ approach
would generate and test all $\mathcal{O}(3^{n/3})$ maximal independent sets
[MM65]: $3^{1/3}\simeq 1.44$. [WD12].

For fuzzy circular interval graphs—a claw-free class which includes the proper
interval graphs, see Fig. 1 and the definition in Section 2.1—we go beyond the
decision problem:

######  Theorem 1.

Given a fuzzy circular interval graph $D$ with arbitrary edge orientations,
two subsets $S,T\subset\operatorname{\mathsf{V}}(D)$, vertex weights
$w\colon\operatorname{\mathsf{V}}(D)\to\mathbf{R}$, and $t\in\mathbf{R}$,
consider the set

$\left\\{k\in\ker D\colon S\subset k\subset T\,\land\,\sum_{x\in
k}w(x)=t\right\\}.$

In time polynomial in $\lvert D\rvert$, we can compute its number of elements
and, if nonempty, return one of them333See Appendix A for a discussion of our
running times. They are $\mathcal{O}(\lvert D\rvert^{3}\cdot\lvert\lvert
D\rvert\rvert)$ on fuzzy circular interval graphs, $\mathcal{O}(\lvert
D\rvert^{2}\cdot\lvert\lvert D\rvert\rvert)$ on fuzzy linear interval graphs
and $\mathcal{O}(\lvert D\rvert\cdot\lvert\lvert D\rvert\rvert)$ on proper
interval graphs..

######  Corollary 1.

The existence of kernels in fuzzy circular interval graphs with arbitrary edge
orientations (including bidirectional edges) is in $\mathbf{P}$.

######  Corollary 2.

Counting the maximal independent sets of a fuzzy circular interval graph, or
its maximum independent sets, takes polynomial time.

Corollary 2 contrasts with the situation in various other graph classes,
including the (equally claw-free) line graphs, where maximum independent sets
are $\mathbf{\\#P}$-complete (Section 3.2).

We devote Section 2 to proving Theorem 1 and Section 3 to remarks on
approaches parametrised by graph complexity measures, on maximal independent
sets and $\mathbf{\\#P}$-hardness, and on kernels in cographs and threshold
graphs.

A natural question which we leave open is the complexity of the search problem
on circular arc graphs, or even only on interval graphs: the case without
bidirectional edges is polynomial [PIM20].

#### Notation and terminology.

We use standard (di)graph vocabulary (‘independent set’, ‘clique’, ‘chordal’,
etc.) which any recent textbook will cover.

The vertex set and edge set of a digraph $D$ are
$\operatorname{\mathsf{V}}(D)$ and $\operatorname{\mathsf{E}}(D)$. We write
$\lvert D\rvert\coloneqq\lvert\operatorname{\mathsf{V}}(D)\rvert$ and
$\lvert\lvert
D\rvert\rvert\coloneqq\lvert\operatorname{\mathsf{V}}(D)\rvert+\lvert\operatorname{\mathsf{E}}(D)\rvert$.

The in- and out-neighbours of a vertex $x$ form the sets
$\operatorname{N}^{-}(x)$ and $\operatorname{N}^{+}(x)$. Also let
$\operatorname{N}(x)\coloneqq\operatorname{N}^{-}(x)\cup\operatorname{N}^{+}(x)$.
Bidirectional edges may lead to
$\operatorname{N}^{-}(x)\cap\operatorname{N}^{+}(x)\neq\varnothing$. The
underlying digraph will always be clear from the context. For a set of
vertices we also write $\operatorname{N}^{-}(S)\coloneqq\cup_{x\in
S}\operatorname{N}^{-}(x)$, and so on. Thus a subset of vertices $k$ is a
kernel iff $\operatorname{N}^{-}(k)=\operatorname{\mathsf{V}}(D)\setminus k$.

We say that a set of vertices $A$ absorbs a set of vertices $B$ if
$B\subset(A\cup\operatorname{N}^{-}(A))$.

If $S$ is a subset of vertices, $D[S]$ is the sub-digraph induced by $S$.

Finally, we use $\sqcup$ in lieu of $\cup$ to denote a union of pairwise
disjoint sets.

##  2 Counting kernels in fuzzy circular interval graphs

In (undirected) claw-free graphs, the independent sets have remarkable
properties allowing efficient algorithms for _maximum independent set_ and
related problems [FOS14]. This makes them a popular graph class for
algorithmic applications.

In a series of seven papers and a survey, [CS05] gave a structure theorem for
claw-free graphs. Disregarding subclasses with bounded independence number
(amenable to brute force as far as kernels are concerned), the quasi-line
graphs are an important stepping stone in this decomposition. They are the
graphs in which the neighbourhood of every vertex is the union of two cliques.
In turn, connected quasi-line graphs are either _fuzzy circular interval
graphs_ (see below), or generalised line graphs. Since the existence of
kernels is $\mathbf{NP}$-complete on arbitrarily-oriented line graphs
[Azi+22], we focus on the first class. See Fig. 1 for a diagram depicting the
inclusions between all these classes.

Figure 1: Proper inclusions among some graph classes. Inclusions without a
reference are well-known or obvious. Figure 2 shows a fuzzy linear interval
graph which is not circular arc, and the claw $K_{1,3}$ itself is an interval
graph that is not claw-free. The Information System on Graph Classes and their
Inclusions is a helpful resource [Rid].

###  2.1 Fuzzy circular interval graphs and subclasses

For every two points $a$ and $b$ of the unit circle
$\mathbf{S}^{1}\subset\mathbf{R}^{2}$, define $[a;b]$ as the closed interval
of $\mathbf{S}^{1}$ joining $a$ to $b$ anticlockwise, with
$[a;a]\coloneqq\\{a\\}$. Also let $[a;b)\coloneqq[a;b]\setminus\\{b\\}$, and
so on.

Following [CS05], a graph $G$ is a fuzzy circular interval graph (FCIG) if it
has a model consisting of a function
$f\colon\operatorname{\mathsf{V}}(G)\to\mathbf{S}^{1}$ and a set $\mathcal{I}$
of intervals of $\mathbf{S}^{1}$ of the form $[a;b]$ with $a\neq b$ such that:

  1. 1.

no two intervals in $\mathcal{I}$ share an endpoint;

  2. 2.

there are no proper inclusions among members of $\mathcal{I}$;

  3. 3.

for every two adjacent vertices $x$ and $y$ there is some interval
$I\in\mathcal{I}$ such that $f(x),f(y)\in I$;

  4. 4.

for every two non-adjacent vertices $x$ and $y$ and interval
$I\in\mathcal{I}$, if $f(x),f(y)\in I$ then the endpoints of $I$ are $f(x)$
and $f(y)$.

######  Remark 1.

The model does not fully specify the adjacency relation between vertices it
sends to distinct endpoints of the same interval (hence ‘fuzzy’). Two FCIGs
may admit the same model. For example, consider the vertex set
$\\{1,2,3,4\\}$, and a model having $f(1)=f(2)=a$ and $f(3)=f(4)=b$ with
$a,b\in\mathbf{S}^{1}$ distinct and $\mathcal{I}=\\{[a;b]\\}$. This model
describes several graphs: a cycle, a path, a clique, and the union of two
edges.

The graph is a fuzzy linear interval graph (FLIG), resp. circular interval
graph (CIG), if it has an FCIG model with $\cup_{J\in\mathcal{I}}J\neq C$,
resp. $f$ injective, and a linear interval graph (LIG) when it has a model
where both hold. In other contexts, CIGs are also known as proper circular arc
graphs and LIGs as indifference graphs, unit interval graphs or proper
interval graphs. See Fig. 1 for some proper inclusions between these and other
graph classes. Note that we could equally well define FLIGs by the same
conditions as above, except that the codomain of $f$ is the real interval
$[0;1]$.

Those four graph classes are each closed under taking induced subgraphs: if
$S\subset\operatorname{\mathsf{V}}(G)$, the pair $(f|_{S}:x\in S\mapsto
f(x),\mathcal{I})$ is a model of the subgraph induced by $S$.

######  Remark 2.

It is already known that kernel search takes polynomial time on LIGs in which
every clique has a sink because LIGs are (strongly) chordal and on FLIGs
without bidirectional edges because FLIGs are circular-arc [PIM20].

#### Nice models.

Let $D$ be an FCIG (resp. FLIG). An FCIG (FLIG) model
$(f\colon\operatorname{\mathsf{V}}(G)\to\mathbf{S}^{1},\mathcal{I})$ for $D$
(resp. $f\colon\operatorname{\mathsf{V}}(G)\to[0;1])$ is nice when
$\lvert\mathcal{I}\rvert\leq\lvert G\rvert$ and, for any two distinct vertices
$x$ and $y$, the equality $f(x)=f(y)$ implies that $x$ and $y$ are adjacent. A
nice model can always be computed in time $\mathcal{O}(\lvert
G\rvert^{2}\cdot\lvert\lvert G\rvert\rvert)$. Furthermore, every model in
which $f$ already has this fibres-are-cliques property can be made nice by
deleting some intervals while keeping the same $f$ [OPS12].

$a$$b$$c$$d$$e$$f$

Figure 2: A graph and a nice FLIG model. The reader can check that this graph
is not an LIG, nor more generally a circular arc graph. Hint: the disjoint
union of a 4-cycle and a vertex is not a circular arc graph.

#### Roadmap.

In the remainder of this section, we prove Theorem 1 in three steps: we obtain
a pared-down version for FLIGs via dynamic programming, we extend it to FCIGs,
then we discuss how some additional kernel features may be tracked.

###  2.2 The structure of kernels in fuzzy linear interval graphs

We start with some results about the structure of FLIGs and their kernels. In
all that follows, fix an FLIG $D$ and a nice model
$(f\colon\operatorname{\mathsf{V}}(D)\to[0;1],\mathcal{I})$. We will build a
weak ordering of $\operatorname{\mathsf{V}}(D)$ whose restriction to each
independent set (in particular, to each kernel) is a total order. Intuitively,
we will then construct kernels of $D$ by ‘guessing’ their vertices one after
the other ‘from right to left’.

#### Weak vertex ordering.

The model gives $\operatorname{\mathsf{V}}(D)$ a weak ordering (a ‘total order
with ties’): for every two vertices $x$ and $y$ put $x\prec y$ iff
$f(x)<f(y)$. Since the model is nice, if $x$ and $y$ are non-adjacent then
$f(x)\neq f(y)$, so either $x\prec y$ or $y\prec x$. Thus every independent
set (in particular every kernel) is totally ordered by $\prec$, even though
$\prec$ is in general not total on $\operatorname{\mathsf{V}}(D)$.

Further write $x\preceq y$ iff $y\not\prec x$ (equivalently, iff $f(x)\leq
f(y)$). Now we may talk about the vertex intervals

$\displaystyle[x;y]\coloneqq\\{z\in\operatorname{\mathsf{V}}(D)\colon x\preceq
z\preceq y\\},$
$\displaystyle[x;y)\coloneqq\\{z\in\operatorname{\mathsf{V}}(D)\colon x\preceq
z\prec y\\},$

and so forth. In particular $[x]\coloneqq[x;x]$ is a clique containing not
only $x$ but all vertices mapped to $f(x)$.

For every vertex $x$, the uniqueness of interval endpoints means that there is
at most one interval $[a;f(x)]\in\mathcal{I}$. We set $\delta(x)\coloneqq
f^{-1}(a)$ if it exists and $\delta(x)\coloneqq\varnothing$ otherwise. When
nonempty, $\delta(x)$ is a clique that may contain both neighbours and non-
neighbours of $x$. Since two intervals in $\mathcal{I}$ may not share an
endpoint,

$\forall x\in\operatorname{\mathsf{V}}(D),\quad\forall
y\in\delta(x),\quad\delta(y)=\varnothing.$ (1)

For every two vertices $x$ and $y$ let the set $K(x,y)$ comprise those kernels
of the induced subgraph $D[[x;y]]$ that contain $x$ and $y$:

$K(x,y)\coloneqq\\{k\in\ker D[[x;y]]\colon x,y\in k\\}.$

In this section we focus on the sets $K(x,y)$, for which we give a recursive
description. We motivate this choice by observing that, while in general
$K(x,y)\not\subset\ker D$, we do have

$\ker D\subset\bigsqcup_{x,y\in\operatorname{\mathsf{V}}(D)}K(x,y),$

since a kernel with leftmost and rightmost vertices $x$ and $y$ belongs to
$K(x,y)$.

#### Preliminary facts.

Let us establish three properties of $\prec$. These will also hold for induced
subgraphs of $D$ when equipped with the same weak order.

######  Lemma 1.

If $a,b\in\operatorname{\mathsf{V}}(D)$ are not adjacent, $a\prec b$ and
$c\in\operatorname{N}(a)$ then $c\preceq b$ (resp. $c\in\operatorname{N}(b)$
and $a\preceq c$).

###### Proof.

Let $c\in\operatorname{N}(a)$: there exists an interval $I\in\mathcal{I}$ with
$f(a),f(c)\in I$. But then $f(b)$ is not in the interior of $I$, as this would
cause $a$ and $b$ to be adjacent. Hence $c\preceq b$. The other inclusion is
similar. ∎

######  Lemma 2.

If $k\in\ker D$ and $a,b\in k$ with $a\prec b$, then $k\cap[a;b]$ absorbs
$(a;b)$.

###### Proof.

Since $k$ is a kernel, every vertex $c\in(a;b)\setminus k$ must have an out-
neighbour $d\in k$. If $d\prec a$ or $b\prec d$ then Lemma 1 yields
$\operatorname{N}(d)\cap(a;b)=\varnothing$, which contradicts
$c\in\operatorname{N}(d)$. Hence $d\in[a;b]$. ∎

Intuitively, Lemma 2 describes the local structure of kernels in $D$:
consecutive kernel vertices are non-adjacent and absorb the open vertex
interval which they delimit.

######  Lemma 3.

If $x$ and $y$ are distinct vertices, $k\in K(x,y)$ and $m\in
k\setminus\\{x,y\\}$, then $k\cap[m;y]$ absorbs $(m;y]$, resp. $k\cap[x;m]$
and $[x;m)$.

###### Proof.

From Lemma 2 applied to $D[[x;y]]$, $k\cap[m;y]$ absorbs $(m;y)$. The sole
remaining case is that of a vertex $z\in[y]\setminus k$. Since $k$ is a
kernel, $z$ has an out-neighbour $w\in k$. If $w\in[m;y]$ we are done.
Otherwise, it must be that $w\prec m$, but then Lemma 1 gives
$\operatorname{N}(w)\subset[x;m]$, which contradicts $z\in[y]$. The second
result is symmetrical. ∎

#### Recursive description of the kernels.

Now we may describe the sets of the form $K(x,y)$ with $x\prec y$. Such sets
are obtained by ‘guessing’ their members in decreasing $\prec$-order, ensuring
at each step that the newly selected vertex satisfies some compatibility
conditions. The main source of complications is the possibility of choosing
the next vertex from the set $\delta(y)$ after selecting
$y\in\operatorname{\mathsf{V}}(D)$.

To address this issue, we sort the kernels in $K(x,y)$ into
$\lvert\delta(y)\rvert+1$ disjoint subsets depending on their intersection
with $\delta(y)$:

$\displaystyle K_{0}(x,\varnothing,y)$ $\displaystyle\coloneqq\\{k\in
K(x,y)\colon k\cap\delta(y)=\varnothing\\},$ (2) and, for every
$m\in\delta(y)$, $\displaystyle K_{0}(x,m,y)$ $\displaystyle\coloneqq\\{k\in
K(x,y)\colon m\in k\\}.$ (3)

Next, we introduce the sets from which kernel vertices will be selected at
each step. For every two vertices $x\prec y$, let

$\displaystyle\Lambda(x,y)$
$\displaystyle\coloneqq\\{m\in(x;y)\setminus(\operatorname{N}(\\{x,y\\})\cup\delta(y))\colon\text{$\\{m,y\\}$
absorbs $(m;y]$}\\},$ (4) and, for every
$m\in\delta(y)\setminus\operatorname{N}(\\{x,y\\})$,
$\displaystyle\Lambda^{\prime}(x,m,y)$
$\displaystyle\coloneqq\\{w\in(x;m)\setminus\operatorname{N}(\\{x,m\\})\colon\text{$\\{w,m,y\\}$
absorbs $(w;y]$}\\}.$ (5)

######  Remark 3.

The functions $\Lambda$ and $\Lambda^{\prime}$ take $\mathcal{O}(\lvert
D\rvert^{3})$ values, which we may compute in polynomial time.

Recall that $\sqcup$ indicates disjoint unions.

######  Lemma 4.

If $x\prec y$ are non-adjacent vertices and $\\{x,y\\}$ does not absorb
$[x;y]$ then

$\displaystyle K(x,y)$
$\displaystyle=\bigsqcup_{m\in(\delta(y)\setminus\operatorname{N}(\\{x,y\\})\sqcup\\{\varnothing\\}}K_{0}(x,m,y),$
(6) $\displaystyle K_{0}(x,\varnothing,y)$ $\displaystyle=\hskip
25.6073pt\bigsqcup_{w\in\Lambda(x,y)}\\{k\sqcup\\{y\\}\colon k\in K(x,w)\\},$
(7) and for every $m\in\delta(y)\setminus\operatorname{N}(\\{x,y\\})$,
$\displaystyle K_{0}(x,m,y)$ $\displaystyle=\begin{dcases*}\hskip
28.45274pt\left\\{\\{x,m,y\\}\right\\}&if $\\{x,m,y\\}$ absorbs $[x;y]$,\\\
\hskip
9.95863pt\bigsqcup_{w\in\Lambda^{\prime}(x,m,y)}\\{k\sqcup\\{m,y\\}\colon k\in
K(x,w)\\}&otherwise.\end{dcases*}$ (8)

Finally if $x\prec y$ and $\\{x,y\\}$ does absorb $[x;y]$ then
$K(x,y)=\\{\\{x,y\\}\\}$.

###### Proof.

Equation 6 expresses the fact that a kernel in $K(x,y)$ has at least three
vertices, since by hypothesis $\\{x,y\\}$ is not itself a kernel. The
disjunction is on whether the second-rightmost kernel vertex belongs to the
clique $\delta(y)$, and in the affirmative on the unique kernel vertex in
$\delta(y)$.

Let us prove Eq. 7. It is a disjunction with respect to the second-rightmost
vertex in the kernel.

For the direct inclusion, let $k\in K_{0}(x,\varnothing,y)$ and let $w$ be the
second-rightmost vertex of $k$.

  * •

Observe that $w\notin\operatorname{N}(\\{x,y\\})$ since $k$ is an independent
set, that $w\notin\delta(y)$ (by hypothesis), and that $\\{w,y\\}$ absorbs
$(w;y]$ by Lemma 3. Hence $w\in\Lambda(x,y)$.

  * •

It remains to argue that $k\setminus\\{y\\}\in K(x,w)$. Its independence and
the inclusions $\\{x,w\\}\subset k\setminus\\{y\\}\subset[x;w]$ are clear. By
Lemma 3, $k\setminus\\{y\\}$ absorbs $[x;w)$. We have only to show that every
$z\in[w]\setminus\\{w\\}$ has an out-neighbour in $k\setminus\\{y\\}$. We do
know that $z$ has an out-neighbour in $k$, which suffices unless this out-
neighbour is $y$. But then some interval $I\in\mathcal{I}$ would contain both
$f(w)=f(z)$ and $f(y)$. Because $w$ and $y$ are not adjacent, the endpoints of
$I$ would be $f(w)=f(z)$ and $f(y)$, which contradicts $w\notin\delta(y)$.

For the reverse inclusion, fix $w\in\Lambda(x,y)$ and $k\in K(x,w)$ and let us
show that $k\sqcup\\{y\\}\in K_{0}(x,\varnothing,y)$. The set $k\sqcup\\{y\\}$
is independent: by Lemma 1 the only possible exception would be an edge
joining $w$ and $y$, but $w\in\Lambda(x,y)$ rules out such an edge. It absorbs
$(w;y]$ by definition of $\Lambda(x,y)$ and $[x;w]$ by definition of $K(x,w)$,
hence it absorbs $[x;y]$. That it contains $w$ and $y$ is clear.

Equation 8 is a disjunction with respect to the third rightmost vertex in the
kernel. In the edge case where this vertex is $x$, the whole kernel is
$\\{x,m,y\\}$. Consider the other case.

For the direct inclusion, let $k\in K_{0}(x,m,y)$ and let $w$ be the third
rightmost vertex of $k$. Then $w\notin\operatorname{N}(\\{x,m\\})$ since $k$
is independent. By Lemma 3, $\\{w,m,y\\}$ absorbs $(w,y]$. Hence
$w\in\Lambda^{\prime}(x,m,y)$.

It remains to show that $k\setminus\\{m,y\\}\in K(x,w)$. Its independence is
clear. It does absorb $[x;w)$ by Lemma 3. The remaining case is that of
$z\in[w]\setminus\\{w\\}$. This $z$ must have an out-neighbour in $k\cap[x;m]$
by Lemma 2. If this out-neighbour were $m$, there would be some
$I\in\mathcal{I}$ containing $f(w)$ and $f(y)$. Then the independence of $k$
would force $I=[f(w);f(y)]$, in turn leading to the contradiction
$w\in\delta(m)=\varnothing$.

For the reverse inclusion, let $w\in\Lambda^{\prime}(x,m,y)$ and $k\in
K(x,w)$. From the definition of $\Lambda^{\prime}$ it is easy to see that the
set $k\sqcup\\{m,y\\}$ is independent and absorbs $[x;y]$.

Finally, the case when $x\prec y$ and $\\{x,y\\}$ does absorb $[x;y]$ is
clear. ∎

#### The recursive description as a labelled acyclic digraph.

Together, Eqs. 6, 7 and 8 let us express $K(x,y)$ as a function of at most
$\lvert\Lambda(x,y)\rvert+\sum_{m\in\delta(y)}\lvert\Lambda^{\prime}(x,m,y)\rvert$
sets of the form $K(x,y_{i})$. We view these results as defining a _subproblem
digraph_ $\mathcal{G}(D,\prec)$ whose nodes are pairs
$(x,y)\in{\operatorname{\mathsf{V}}(D)}^{2}$ with $x\prec y$, plus a terminal
node $F_{x}$ for each $x\in\operatorname{\mathsf{V}}(D)$. If $x$ and $y$ are
non-adjacent and $\\{x;y\\}$ does not absorb $[x;y]$, the node $(x,y)$ of
$\mathcal{G}(D,\prec)$ has the following outgoing edges:

  * •

for each $w\in\Lambda(x,y)$, an edge labelled with the symbol $w$ to the node
$(x,m)$,

  * •

for each $m\in\delta(y)\setminus\operatorname{N}(\\{x,y\\})$ and
$w\in\Lambda^{\prime}(x,m,y)$, an edge labelled with the concatenation $mw$ to
the node $(x,w)$, unless $\\{x,m,y\\}$ absorbs $[x;y]$, in which case the sole
outgoing edge is labelled $mx$ and goes to $F_{x}$.

Whereas if $\\{x,y\\}$ does absorb $[x;y]$ the node $(x,y)$ has an edge
labelled $x$ to $F_{x}$.

Our description of the sets $K(x,y)$ is summarised by the following lemma.

######  Lemma 5.

Given an FLIG $D$ and the weak order $\prec$ on its vertex set
$\operatorname{\mathsf{V}}(D)$ coming from a nice FLIG model, we build a
digraph $\mathcal{G}(D,\prec)$ on the vertex set

$\\{(x,y)\in(\operatorname{\mathsf{V}}(D))^{2}\colon x\prec
y\\}\sqcup\\{F_{x}\colon x\in\operatorname{\mathsf{V}}(D)\\}$

in time polynomial in $\lvert D\rvert$. This digraph is acyclic; it has
$\mathcal{O}(\lvert D\rvert^{2})$ nodes and maximum out-degree
$\mathcal{O}(\lvert D\rvert)$. Each edge is labelled with one or two vertices
of $\operatorname{\mathsf{V}}(D)$.

For every pair of vertices $(x,y)$ with $x\prec y$, the set $K(x,y)$ is in
bijection with the set of directed paths from the node $(x,y)$ to the node
$F_{x}$. Given one such path, the vertices of the corresponding kernel are
read off in decreasing $\prec$-order from the edge labels, omitting $y$.

This translates properties of the set $K(x,y)$ such as its cardinality or its
smallest elements into well-trodden algorithmic problems on acyclic digraphs
(the number of directed paths joining two nodes, the shortest directed paths
with edge lengths in $\\{1,2\\}$).

###  2.3 Reducing the circular case to the linear case

Now we show how the set of all kernels in an FCIG $D$ is expressed in term of
the sets $K(x,y)$ in some FLIGs that are all induced subgraphs of $D$. Before
we consider FCIGs however, let us mention a simple fact about kernels in
general digraphs (proof omitted).

######  Lemma 6.

If $D$ is a digraph and $a\in\operatorname{\mathsf{V}}(D)$ then

$\\{k\in\ker D\colon a\in k\\}=\\{k\in\ker
D[\operatorname{\mathsf{V}}(D)\setminus\operatorname{N}^{-}(a)]\colon a\in
k\\}.$

Now let $D$ be an FCIG and let $\alpha$ be an arbitrary vertex of $D$. In
polynomial time, we compute and fix a nice FCIG model of $D$ [OPS12]. We may
use the same interval notation as for FLIGs, with the caveat that for every
two vertices $a$ and $b$ the vertex intervals $[a;b]$ and $[b;a]$ are
generally distinct and intersect in $[a]\cup[b]$.

For each kernel $k\in\ker D$, either $\lvert k\rvert=1$, or there exists a
unique pair $a,b\in k$ such that $\alpha\in[a;b)$ and $[a;b]\cap k=\\{a,b\\}$.
That is, setting $K_{a,b}\coloneqq\\{k\in\ker D\colon[a;b]\cap
k=\\{a,b\\}\\}$,

$\ker D=\\{k\in\ker D\colon\lvert
k\rvert=1\\}\bigsqcup\left(\bigsqcup_{\alpha\in[a;b)}K_{a,b}\right).$

Single-vertex kernels can be enumerated by brute force in time
$\mathcal{O}(\lvert\lvert D\rvert\rvert)$. Hence we are left to deal with the
set $K_{a,b}$ for every two distinct vertices $a$ and $b$. It is not hard to
see that:

######  Lemma 7.

If $a$ and $b$ are not adjacent and $\\{a,b\\}$ absorbs $[a;b]$, then
$K_{a,b}$ is the set of kernels of $D[[b;a]]$ containing $a$ and $b$. If
either condition fails, $K_{a,b}=\varnothing$.

###### Proof.

The first part is easy: there can be no other kernel vertex in $(a;b)$ as
$[a;b]\subset\operatorname{N}(\\{a,b\\})$. The second part involves an FCIG
analogue of Lemma 2, proven similarly. ∎

$a$$b$$\alpha$

$a$$b$

Figure 3: Left: the FCIG $D$ with a nice model. The vertices $a$ and $b$ are
not adjacent and absorb $[a;b]$. Right: the subgraph $D^{\prime}$ obtained by
deleting $\operatorname{N}^{-}(\\{a,b\\})$ has a nice FLIG model in which $a$
and $b$ are extremal, deduced from the original model by shrinking or deleting
intervals without perturbing adjacencies.

Given $a$ and $b$ non-adjacent and such that $\\{a,b\\}$ absorbs $[a;b]$,
consider the subgraph $D[[b;a]]$ as well as the FCIG interval model
$(f,\mathcal{I})$ it inherits from $D$. We will show that $D[[b;a]]$ is almost
an FLIG.

By Lemma 6, we can delete vertices in $\operatorname{N}^{-}(\\{a,b\\})$
without modifying the set of kernels containing $a$ and $b$, so we delete
$[a;b]\setminus\\{a;b\\}$. We now have $[a;b]=\\{a,b\\}$. If the interval
$[f(a);f(b)]$ is in $\mathcal{I}$, we delete it and retain a valid model,
since there is no adjacency it could contribute. Now there are no intervals in
$\mathcal{I}$ containing both $a$ and $b$. Without removing any edge, we may
shrink the intervals in $\mathcal{I}$ until some sub-interval of $(f(a);f(b))$
is not covered by $\cup_{I\in\mathcal{I}}I$.

This shows that the resulting induced subgraph $D^{\prime}$ is an FLIG with
the same set of kernels containing both $a$ and $b$ as $D[[b;a]]$, and
$D^{\prime}$ has an FLIG model where $a$ and $b$ are the leftmost and
rightmost vertices. This model might not be nice (if we deleted more vertices
than intervals), but can be made nice again by deleting unnecessary intervals
[OPS12]. See Figure 3 for an illustration.

Thus, computing the cardinality (or an element, or the number of elements of a
certain size) of $K_{a,b}$ amounts to computing $K(a,b)$ in the FLIG
$D^{\prime}$ as in Section 2.2.

Combining the present results with those in Section 2.2, we obtain the
following theorem.

######  Theorem 2.

Given an $n$-vertex fuzzy circular interval graph $D$ with arbitrary edge
orientations, we can compute the size of $\ker D$ and, if nonempty, return one
of its elements in time polynomial in $n$.

###  2.4 Extensions of the algorithm

To get from Theorem 2 to Theorem 1, we modify the graph $\mathcal{G(D,\prec)}$
from Section 2.2 by refining the definitions of $\Lambda$ and
$\Lambda^{\prime}$ as needed, to ensure that kernel vertices respect the newly
introduced constraints.

If there are two subsets $S,T\subset\operatorname{\mathsf{V}}(D)$ and we want
$\mathcal{G(D,\prec)}$ to encode only kernels that include $S$ and are
included in $T$, then we may replace Eq. 4 with

$\Lambda(x,y)\coloneqq\left\\{m\in(T\cap(x;y))\setminus(\operatorname{N}(\\{x,y\\})\cup\delta(y))\colon\begin{aligned}
&\text{$\\{m,y\\}$ absorbs $(m;y]$}\\\ &[m;y]\cap
S\subset\\{m;y\\}\end{aligned}\right\\},$

and Eq. 5 similarly. This amounts to deleting some of the edges in
$\mathcal{G(D,\prec)}$: the edges with a label not in $T$ and the out-edges
from a node $(x,y)$ with at least one label $\ell$ such that
$S\cap[\ell;y]\neq\\{\ell,y\\}$.

If $w\colon\operatorname{\mathsf{V}}(D)\to\mathbf{R}$ is a weight function,
then we define the weight of each edge in $\mathcal{G(D,\prec)}$ as the sum of
the weights of its labels. For each node $(x,y)$ and terminal $F_{x}$ of
$\mathcal{G(D,\prec)}$, we can list the weights of all directed paths from
$(x,y)$ to $F_{x}$ with multiplicity in a bottom-up fashion, since
$\mathcal{G(D,\prec)}$ is acyclic. This still takes time polynomial in $\lvert
D\rvert$, independent of $\max_{\operatorname{\mathsf{V}}(D)}|w|$.

##  3 Further remarks

###  3.1 Tree-width, clique-width

The tree-width of a digraph $D$ is an integer
$\operatorname{tw}(D)\in\mathbf{N}$ measuring its complexity relative to a
scale on which trees are simplest. Note that $\operatorname{tw}(D)$ does not
depend on edge orientations.

A set of vertices $k$ being a kernel is expressible in the _monadic second-
order logic of directed graphs_ (see e.g. [ALS91]), for example by the
formula:

$\forall v\quad(v\notin k\iff\exists u\quad u\in k\land Evu),$

where the relation symbol $E$ encodes directed edges, so the counting version
of Courcelle’s theorem [CE12, Th. 6.56] gives

######  Theorem 3.

For some computable function $f$ there exist algorithms that, given a digraph
$D$, compute $\lvert\ker D\rvert$, and, if $\ker D\neq\varnothing$, build a
largest and a smallest kernel, all of it in time
$\mathcal{O}(f(\operatorname{tw}(D))\cdot\lvert\lvert D\rvert\rvert)$.

The proofs, constructive but quite involved, yield fast growing functions $f$,
making said algorithms impractical. Still, this approach has interesting
consequences, such as a polynomial-time algorithm for deciding the existence
of kernels of size $\mathcal{O}(\log^{2}\lvert\lvert D\rvert\rvert)$ in planar
digraphs [Gut+05].

As for our Theorem 1, there is little overlap with these results since even
LIGs have arbitrarily large cliques, hence unbounded tree-width.

_Clique-width_ , the other most common complexity measure, is as coarse as
tree-width in our orientation-agnostic setting. Indeed, unlike tree-width,
clique-width strongly depends on edge orientations: if a class $\mathcal{C}$
of undirected graphs has unbounded tree-width (say, if $\mathcal{C}$ contains
all complete graphs) then the digraph class obtained by taking all possible
edge orientations on members of $\mathcal{C}$ has unbounded clique-width
[CE12, Prop. 2.117]. In fact, we show that the existence of kernels is
$\mathbf{NP}$-complete on cographs (which, when undirected, are the graphs of
clique-width at most $2$): see Theorem 4 below. This contrasts with our
Theorem 1, and with the positive results on adequately oriented cographs
[AS05].

###  3.2 Counting maximal and maximum independent sets

An independent set of a graph is maximal when it has no independent superset,
and maximum when its cardinality is largest among independent sets. Clearly,
the latter entails the former.

The kernels of a digraph with all edges bidirectional are exactly its maximal
independent sets. Hence Theorem 1 translates into polynomial-time algorithms
for counting maximal independent sets, maximal independent sets of a certain
size, and thus also maximum independent sets in FCIGs. Compare with chordal
graphs and other quasi-line graphs:

######  Lemma 8 ([OUU08]).

Counting maximal independent sets is $\mathbf{\\#P}$-complete on chordal
graphs.

######  Lemma 9.

Counting maximum independent sets is $\mathbf{\\#P}$-complete on line graphs
of bipartite graphs.

###### Proof.

Let $G$ be a bipartite graph. In polynomial time, we decide whether $G$ has
perfect matchings by building a largest matching (e.g. by the Ford–Fulkerson
algorithm) and checking whether it is perfect. In the affirmative, the perfect
matchings of $G$ are the maximum independent sets of its line graph. Now an
algorithm that counts the latter also counts the former, but counting the
perfect matchings of bipartite graphs is $\mathbf{\\#P}$-complete [Val79]. ∎

###  3.3 Cographs and threshold graphs

One may define cographs inductively as being either a single-vertex graph, or
the union of $G_{1}$ and $G_{2}$, or the join444One obtains the join of two
undirected graphs by adding every possible edge between them. of $G_{1}$ and
$G_{2}$, where $G_{1}$ and $G_{2}$ are smaller (disjoint) cographs. In
particular, cliques, independent sets, and matchings are easily identified as
cographs.

######  Theorem 4.

The existence of kernels is $\mathbf{NP}$-complete on cographs with
bidirectional edges.

###### Proof of Theorem 4.

The problem is clearly in $\mathbf{NP}$.

Fix an instance of the Boolean satisfiability problem (SAT) in conjunctive
normal form: a set of variables $\mathcal{V}$ which defines a set of literals
$L=\\{v,\bar{v}\colon v\in\mathcal{V}\\}\simeq\mathcal{V}\times\\{0,1\\}$, and
a set of disjunctive clauses $\mathcal{C}\subset\mathcal{P}(L)$. A solution of
the SAT instance is a subset $S\subset L$ such that $v\in S\iff\bar{v}\notin
S$ for each variable $v$ and $S$ intersects every clause in $\mathcal{C}$.

Build a digraph on $\mathcal{C}\sqcup L$ by putting a bidirectional edge
between every pair of clauses in $\mathcal{C}$, and between every variable
$v\in\mathcal{V}$ and its negation $\bar{v}$. Also add two special vertices
$\alpha$ and $\omega$ with an edge from $\alpha$ to $\omega$. Finally, for
each clause $c\in\mathcal{C}$ put a directed edge from $c$ to the literals
that appear in $c$ and to $\alpha$, as well as directed edges to $c$ from the
literals that do not appear in $c$ and from $\omega$. The resulting digraph on
$\mathcal{C}\sqcup L\sqcup\\{\alpha,\omega\\}$, which we will call $D$, has
the following properties:

  * •

$D$ has $\lvert\mathcal{V}\rvert+\lvert\mathcal{C}\rvert+2$ vertices;

  * •

(the undirected graph underlying) $D$ is a cograph, as the join of a complete
graph on $\mathcal{C}$ and a perfect matching on $L\sqcup\\{\alpha,\omega\\}$;

  * •

If $k$ is a kernel of $D$ then $\omega\in k$ and $k\subset
L\sqcup\\{\omega\\}$. Indeed, since
$\operatorname{N}^{+}(\alpha)=\\{\omega\\}$, either $\alpha\in k$ or
$\omega\in k$, but in the first case
$\operatorname{N}^{+}(\omega)=\mathcal{C}\subset\operatorname{N}(\alpha)\subset\operatorname{N}(k)$
contradicts the independence of $k$, since $\omega$ must have an out-neighbour
in $k$. Hence $\omega\in k$, which implies
$(\mathcal{C}\sqcup\\{\alpha\\})\cap k=\operatorname{N}(\omega)\cap
k=\varnothing$;

  * •

In view of the previous fact, kernels are subsets of literals (plus $\omega$)
containing exactly one of $v$ and $\bar{v}$ for each variable
$v\in\mathcal{V}$, and such that each $c\in\mathcal{C}$ has at least one out-
neighbour in the kernel. Thus the kernels of $D$ are in bijection with the
solutions of the SAT instance.

Hence this construction is a polynomial-time parsimonious reduction of SAT to
the existence of kernels in cographs. ∎

We conclude by noting that the counting problem is not only polynomial but
linear on a particular subclass of cographs, even though said subclass, having
unbounded tree-width, does not fall under the purview of Theorem 3.

A cograph is a threshold graph if it has a cograph construction sequence as
above where $G_{1}$ is a single vertex at each step.

######  Theorem 5.

Counting the kernels of an arbitrarily oriented threshold graph $T$ and, when
applicable, building one, takes linear time $\mathcal{O}(\lvert\lvert
T\rvert\rvert)$. If $\omega(T)$ is the clique number, enumerating its kernels
takes time $\mathcal{O}(\omega(T)\cdot\lvert T\rvert+\lvert\lvert
T\rvert\rvert)$.

These results are already known for the maximal independent sets in undirected
threshold graphs [GR20].

###### Proof of Theorem 5.

For every set $\mathcal{F}\subset\operatorname{\mathsf{V}}(T)$, let
$\ker_{\mathcal{F}}T\coloneqq\\{k\in\ker T\colon
k\cap\mathcal{F}=\varnothing\\}$. A threshold graph construction sequence for
$T$ is found in linear time [MP95, §1.4.2], so we give a recursive description
of $\ker_{\mathcal{F}}T$.

  * •

If $T$ is a single vertex $v$, then

$\ker_{\mathcal{F}}T=\begin{dcases*}\varnothing&if $v\in\mathcal{F}$,\\\
\\{\\{v\\}\\}&otherwise.\end{dcases*}$

  * •

If $T$ is the disjoint union of a vertex $v$ and a subgraph $T^{\prime}$, then

$\ker_{\mathcal{F}}T=\begin{dcases*}\varnothing&if $v\in\mathcal{F}$,\\\
\\{\\{v\\}\sqcup k\colon
k\in\ker_{\mathcal{F}}T^{\prime}\\}&otherwise.\end{dcases*}$

  * •

If $T$ is the join of a vertex $v$ and a subgraph $T^{\prime}$, then
$\\{v\\}\in\ker_{\mathcal{F}}T$ iff $v$ absorbs $T^{\prime}$ and
$v\notin\mathcal{F}$ (and we can check these conditions in time
$\mathcal{O}(\deg v+n)$) and regardless

$\ker_{\mathcal{F}}T\setminus\\{\\{v\\}\\}=\ker_{\mathcal{F}\setminus\\{v\\}}T^{\prime}.$

This lets us compute $\lvert\ker_{\mathcal{F}}T\rvert$ in time $R(\lvert
T\rvert,\lvert\operatorname{\mathsf{E}}(T)\rvert)$ where (for some absolute
constant $C$) the three cases above give

$\displaystyle R(n,m)$ $\displaystyle\leq
C+R(n-1,m)+\max_{v\in\operatorname{\mathsf{V}}(T)}(C\cdot(\deg
v+n)+R(n-1,m-\deg v))$ $\displaystyle=\mathcal{O}(m+n).$

For enumerating $\ker_{\mathcal{F}}T$ the same reasoning applies, except that
each ‘disjoint union’ step spends constant time appending a vertex to each set
in $\ker_{\mathcal{F}}T^{\prime}$. As a threshold graph, $T$ has $\omega(T)$
maximal independent sets [GR20], so
$\lvert\ker_{\mathcal{F}}T^{\prime}\rvert\leq\lvert\ker_{\mathcal{F}}T\rvert\leq\omega(T)$
and we obtain

$\displaystyle R^{\prime}(n,m)$ $\displaystyle\leq
C+(R^{\prime}(n-1,m)+C\cdot\omega(T))$
$\displaystyle\quad+\max_{v\in\operatorname{\mathsf{V}}(T)}(C\cdot(\deg
v+n)+R^{\prime}(n-1,m-\deg v))$ $\displaystyle=\mathcal{O}(\omega(T)\cdot
n+m).\qed$

######  Remark 4.

The maximal independent sets of a graph are enumerable with polynomial delay,
hence, if there are $\mu$ such sets, enumerable in total time $\mu\cdot
n^{\mathcal{O}(1)}$. This is unlikely to extend to kernels. Even if only on
cographs, a polynomial-delay algorithm for kernels would solve SAT and
(because of the parsimonious reduction) an enumeration algorithm polynomial in
the total size of its output would solve unambiguous-SAT. This would
respectively establish $\mathbf{P}=\mathbf{NP}$ and, by the Valiant–Vazirani
theorem, $\mathbf{RP}=\mathbf{NP}$ [VV86].

###  3.4 Other graph classes

#### Concave-round graphs.

A graph is concave-round if its vertices have a circular ordering in which
every _closed_ neighbourhood (that is, $\\{x\\}\sqcup\operatorname{N}(x)$) is
an interval [BHY00]. Concave-round graphs are quasi-line. They form a subclass
of normal circular-arc graphs [Saf20] and a proper superclass of CIGs.
Unknowingly, we have already solved the problem for this class, because of the
following easy but unpublished inclusion.

######  Remark 5.

Concave-round graphs form a proper subclass of the fuzzy circular interval
graphs. More precisely, they are either fuzzy linear interval graphs or
circular interval graphs (proper circular arc graphs).

###### Proof.

A concave-round graph is (at least) one of circular interval and co-bipartite
[Tuc71, Saf20]. In turn, co-bipartite graphs (i.e. graphs with a partition
into two cliques) are clearly FLIGs. ∎

#### Interval graphs and interval digraphs.

There are some results on kernel problems in _interval digraphs_ [FHJ21].
However, said interval digraphs are quite different from arbitrarily-directed
interval graphs: interval graphs are chordal, whereas every directed cycle is
an interval digraph in the sense of [FHJ21]. Hence there is little overlap
with our results.

## Acknowledgements

Thanks to F. Meunier for drawing my interest to kernels a few years ago and to
Y. Yudistky for her comments on an earlier draft.

Research supported by the European Research Council (ERC) under the European
Union’s Horizon 2020 research and innovation programme (Grant agreement No.
678765) and by the Israel Science Foundation under Grants 1065/20 and 2891/21.

## References

  * [ALS91] Stefan Arnborg, Jens Lagergren and Detlef Seese  “Easy Problems for Tree-Decomposable Graphs”  In _Journal of Algorithms_ 12.2, 1991, pp. 308–340  DOI: 10.1016/0196-6774(91)90006-K
  * [AS05] Moncef Abbas and Youcef Saoula  “Polynomial algorithms for kernels in comparability, permutation and $P_{4}$-free graphs”  In _4OR_ , 2005, pp. 217–225  DOI: 10.1007/s10288-005-0067-9
  * [Azi+22] Haris Aziz et al.  “Stable Matching with Uncertain Pairwise Preferences”  In _Theoretical Computer Science_ , 2022  DOI: 10.1016/j.tcs.2022.01.028
  * [BG06] E. Boros and V. Gurvich  “Perfect graphs, kernels, and cores of cooperative games”  In _Discrete Mathematics_ 306.19, 2006, pp. 2336–2354  DOI: 10.1016/j.disc.2005.12.031
  * [BG09] Jørgen Bang-Jensen and Gregory Z. Gutin  “Digraphs”, Springer Monographs in Mathematics  London: Springer London, 2009  DOI: 10.1007/978-1-84800-998-1
  * [BHY00] Jørgen Bang-Jensen, Jing Huang and Anders Yeo  “Convex-Round and Concave-Round Graphs”  In _SIAM Journal on Discrete Mathematics_ 13.2, 2000, pp. 179–193  DOI: 10.1137/S0895480197322154
  * [Bou01] Charles L. Bouton  “Nim, A Game with a Complete Mathematical Theory”  In _Annals of Mathematics_ 3.1/4 Annals of Mathematics, 1901, pp. 35–39  DOI: 10.2307/1967631
  * [BR77] C. Berge and A. Rao  “A combinatorial problem in logic”  In _Discrete Mathematics_ 17.1, 1977, pp. 23–26  DOI: https://doi.org/10.1016/0012-365X(77)90018-8
  * [CE12] Bruno Courcelle and Joost Engelfriet  “Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach”, Encyclopedia of Mathematics and Its Applications  Cambridge University Press, 2012  DOI: 10.1017/CBO9780511977619
  * [Chv73] Václav Chvátal  “On the computational complexity of finding a kernel” Out of print, but see author’s website: https://users.encs.concordia.ca/~chvatal/kernel.html, 1973
  * [CS05] Maria Chudnovsky and Paul Seymour  “The structure of claw-free graphs”  In _Surveys in Combinatorics 2005_ 327, London Mathematical Society Lecture Note Series  Cambridge University Press, 2005, pp. 153–172  DOI: 10.1017/CBO9780511734885.008
  * [DM93] P. Duchet and H. Meyniel  “Kernels in directed graphs: a poison game”  In _Discrete Mathematics_ 115.1, 1993, pp. 273–276  DOI: 10.1016/0012-365X(93)90496-G
  * [DMP97] Yannis Dimopoulos, Vangelis Magirou and Christos H. Papadimitriou  “On Kernels, Defaults and Even Graphs”  In _Annals of Mathematics and Artificial Intelligence_ 20.1, 1997, pp. 1–12  DOI: 10.1023/A:1018972125742
  * [Dyr12] Sjur Dyrkolbotn  “Argumentation, paradox and kernels in directed graphs”, 2012  URL: http://www.ii.uib.no/~michal/Sjur-tese.pdf
  * [FHJ21] Mathew C. Francis, Pavol Hell and Dalu Jacob  “On the Kernel and Related Problems in Interval Digraphs”  In _32nd International Symposium on Algorithms and Computation (ISAAC 2021)_ 212, Leibniz International Proceedings in Informatics (LIPIcs)  Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021, pp. 17:1–17:17  DOI: 10.4230/LIPIcs.ISAAC.2021.17
  * [FOS14] Yuri Faenza, Gianpaolo Oriolo and Gautier Stauffer  “Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition”  In _Journal of the ACM_ 61.4 New York, NY, USA: Association for Computing Machinery, 2014  DOI: 10.1145/2629600
  * [Fra81] Aviezri S. Fraenkel  “Planar kernel and Grundy with $d\leq 3$, $d_{out}\leq 2$, $d_{in}\leq 2$ are NP-complete”  In _Discrete Applied Mathematics_ 3.4, 1981, pp. 257–262  DOI: 10.1016/0166-218X(81)90003-2
  * [Fra97] Aviezri S. Fraenkel  “Combinatorial Game Theory Foundations Applied to Digraph Kernels”  In _Electronic Journal of Combinatorics_ 4.2, 1997  DOI: 10.37236/1325
  * [Gal95] Fred Galvin  “The List Chromatic Index of a Bipartite Multigraph”  In _Journal of Combinatorial Theory, Series B_ 63.1, 1995, pp. 153–158  DOI: 10.1006/jctb.1995.1011
  * [GI89] Dan Gusfield and Robert W. Irving  “The Stable Marriage Problem. Structure and Algorithms”, Foundations of Computing  MIT Press, 1989
  * [GR20] Frank Gurski and Carolin Rehs  “Counting and Enumerating Independent Sets with Applications to Combinatorial Optimization Problems”  In _Mathematical Methods of Operations Research_ 91.3, 2020, pp. 439–463  DOI: 10.1007/s00186-019-00696-4
  * [GS62] D. Gale and L.. Shapley  “College Admissions and the Stability of Marriage”  In _The American Mathematical Monthly_ 69.1 Mathematical Association of America, 1962, pp. 9–15  DOI: 10.2307/2312726
  * [Gut+05] Gregory Gutin, Ton Kloks, Chuan Min Lee and Anders Yeo  “Kernels in Planar Digraphs”  In _Journal of Computer and System Sciences_ 71.2, 2005, pp. 174–184  DOI: 10.1016/j.jcss.2005.02.003
  * [Maf92] Frédéric Maffray  “Kernels in perfect line-graphs”  In _Journal of Combinatorial Theory, Series B_ 55.1, 1992, pp. 1–8  DOI: 10.1016/0095-8956(92)90028-V
  * [MM65] J.. Moon and L. Moser  “On Cliques in Graphs”  In _Israel Journal of Mathematics_ 3.1, 1965, pp. 23–28  DOI: 10.1007/BF02760024
  * [MP95] “Threshold Graphs and Related Topics” 56, Annals of Discrete Mathematics  Amsterdam New York: Elsevier, 1995  DOI: 10.1016/S0167-5060(13)71062-8
  * [OPS12] Gianpaolo Oriolo, Ugo Pietropaoli and Gautier Stauffer  “On the recognition of fuzzy circular interval graphs”  In _Discrete Mathematics_ 312.8, 2012, pp. 1426–1435  DOI: 10.1016/j.disc.2011.12.029
  * [OUU08] Yoshio Okamoto, Takeaki Uno and Ryuhei Uehara  “Counting the Number of Independent Sets in Chordal Graphs”  In _Journal of Discrete Algorithms_ 6.2, 2008, pp. 229–242  DOI: 10.1016/j.jda.2006.07.006
  * [PIM20] Adèle Pass-Lanneau, Ayumi Igarashi and Frédéric Meunier  “Perfect graphs with polynomially computable kernels”  In _Discrete Applied Mathematics_ 272, 2020, pp. 69–74  DOI: 10.1016/j.dam.2018.09.027
  * [Rid] H.N. Ridder et al.  “Information System on Graph Classes and Their Inclusions”  URL: https://www.graphclasses.org/
  * [Saf20] Martín D. Safe  “Characterization and Linear-Time Detection of Minimal Obstructions to Concave-Round Graphs and the Circular-Ones Property”  In _Journal of Graph Theory_ 93.2, 2020, pp. 268–298  DOI: 10.1002/jgt.22486
  * [Tuc71] Alan Tucker  “Matrix Characterizations of Circular-Arc Graphs.”  In _Pacific Journal of Mathematics_ 39.2 Pacific Journal of Mathematics, A Non-profit Corporation, 1971, pp. 535–545  DOI: 10.2140/pjm.1971.39.535
  * [Val79] L.. Valiant  “The Complexity of Computing the Permanent”  In _Theoretical Computer Science_ 8.2, 1979, pp. 189–201  DOI: 10.1016/0304-3975(79)90044-6
  * [vNM44] John Neumann and Oskar Morgenstern  “Theory of Games and Economic Behavior”  Princeton University Press, 1944
  * [VV86] L.G. Valiant and V.V. Vazirani  “NP Is as Easy as Detecting Unique Solutions”  In _Theoretical Computer Science_ 47, 1986, pp. 85–93  DOI: 10.1016/0304-3975(86)90135-0
  * [WD12] Michał Walicki and Sjur Dyrkolbotn  “Finding kernels or solving SAT”  In _Journal of Discrete Algorithms_ 10, 2012, pp. 146–164  DOI: 10.1016/j.jda.2011.11.004
  * [Zer13] Ernst Zermelo  “Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels”  In _Proceedings of the Fifth International Congress of Mathematicians_ 2, 1913, pp. 501–504

##  Appendix A Running times

Let us argue that the running times of our algorithms for counting kernels are

  * •

$\mathcal{O}(\lvert D\rvert^{3}\cdot\lvert\lvert D\rvert\rvert)$ on FCIGs,

  * •

$\mathcal{O}(\lvert D\rvert^{2}\cdot\lvert\lvert D\rvert\rvert)$ on FLIGs and
CIGs,

  * •

$\mathcal{O}(\lvert D\rvert\cdot\lvert\lvert D\rvert\rvert)$ on LIGs (proper
interval graphs).

#### General setting.

The subproblem digraph $\mathcal{G}(D,\prec)$ from Section 2.2 can be
partitioned into $\lvert D\rvert$ parts, each induced by the vertex set
$\\{(x,y)\colon y\in\operatorname{\mathsf{V}}(D)\land x\prec
y\\}\sqcup\\{F_{x}\\}$ for some $x\in\operatorname{\mathsf{V}}(D)$.
Equivalently, each part correspond to kernels with a same leftmost vertex.
There are no edges between parts (and parts need not be connected). Each part
has $\mathcal{O}(\lvert D\rvert)$ vertices. Hence, for every fixed vertex
$x_{0}$, computing all values of $y\mapsto\lvert K(x_{0},y)\rvert$ takes time
$\mathcal{O}(\lvert D\rvert^{2})$ once the part containing $F_{x_{0}}$ has
been constructed. Said construction is usually the bottleneck.

For a fixed $y_{0}\in\operatorname{\mathsf{V}}(D)$, let

$\displaystyle I$ $\displaystyle\coloneqq\\{m\prec y_{0}\colon
m\notin(N(y_{0})\cup\delta(y_{0}))\land\\{m,y_{0}\\}\text{ absorbs
}(m;y_{0}]\\}.$ For each $x\prec y_{0}$ the set $\Lambda(x,y_{0})$ defined by
Eq. 4 is obtained from $I$ by $\displaystyle\Lambda(x,y_{0})$
$\displaystyle=(I\cap(x;y_{0}))\setminus\operatorname{N}(x).$

Based on this observation, here is a possible algorithm that computes
$\Lambda(x,y_{0})$ for a fixed $y_{0}$ and all values $x\in X$, with the
vertex $y_{0}$ and the subset $X\subset\operatorname{\mathsf{V}}(D)$ as
inputs. Note that, since $\prec$ is not quite a total order but a weak order,
it partitions $\operatorname{\mathsf{V}}(D)$ into classes ($[x]=\\{y\colon
y\preceq x\land x\preceq y\\}$) and (through quotienting) induces a total
order on the set of these classes.

Algorithm 1 An algorithm that computes $\Lambda(x,y_{0})$ for a fixed $y_{0}$
and all values $x\in X$.

1:candidates
$\leftarrow\\{m\in\operatorname{\mathsf{V}}(D)\setminus(\operatorname{N}(y)_{0}\cup\delta(y_{0}))\colon
m\prec y_{0}\\}$ $\triangleright$ as an array of $\lvert D\rvert$ bits

2:$I\leftarrow\varnothing$

3:for each class $C$ in decreasing $\prec$-order starting at $[y_{0}]$ do

4: for $x\in C\cap X$ do

5: $\Lambda[x,y_{0}]\leftarrow I\setminus\operatorname{N}(x)$ $\triangleright$
$\mathcal{O}(\lvert D\rvert)$

6: end for

7: $I\leftarrow I\cup(C\cap\text{candidates})$ $\triangleright$
$\mathcal{O}(\lvert C\rvert)$

8: for $m\in C\setminus(\\{y_{0}\\}\cup\operatorname{N}^{-}(y)_{0})$ do

9: candidates $\leftarrow\text{candidates}\cap\operatorname{N}^{+}(m)$
$\triangleright$ $\mathcal{O}(\deg m)$

10: end for

11:end for

It runs in time $\mathcal{O}(\lvert D\rvert\cdot\lvert X\rvert+\lvert\lvert
D\rvert\rvert)$. Similarly, if for every $y$ and
$m\in\delta(y)\setminus\operatorname{N}(y)$ we set

$\displaystyle J(m,y)$ $\displaystyle\coloneqq\\{w\prec m\colon
w\notin\operatorname{N}(m)\land\text{$\\{w,m,y\\}$ absorbs $(w;y]$}\\},$ then,
for $x\prec m$, $x\notin\operatorname{N}(m)$,
$\displaystyle\Lambda^{\prime}(x,m,y)$
$\displaystyle=(J(m,y)\cap(x;m))\setminus\operatorname{N}(x),$

and a similar algorithm computes the values of $\Lambda^{\prime}(x,m,y_{0})$
for every $x\in X$ and every $m\in\delta(y_{0})$ in time
$\mathcal{O}(\lvert\delta(y_{0})\rvert\cdot(\lvert D\rvert\cdot\lvert
X\rvert+\lvert\lvert D\rvert\rvert))$. Hence, for any fixed $x_{0}$ it takes
time $\mathcal{O}(\lvert D\rvert^{2}\cdot\lvert\lvert D\rvert\rvert)$ to build
only the part of $\mathcal{G}(D,\prec)$ containing $F_{x_{0}}$, or
$\mathcal{O}(\lvert D\rvert^{3}\cdot\lvert\lvert D\rvert\rvert)$ to build all
parts.

As for FCIGs, each set $K_{a,b}$ from Section 2.3 reduces to a set $K(a,b)$
_in an FLIG that potentially depends on both $a$ and $b$_, but careful
consideration of the deleted vertices lets us argue that said FLIG only
depends on $a$. Thus we have to build $\mathcal{O}(\lvert D\rvert)$ parts, for
a total running time of $\mathcal{O}(\lvert D\rvert^{3}\cdot\lvert\lvert
D\rvert\rvert)$.

#### In circular interval graphs.

In circular interval graphs, we can ensure the additional model property that
$\delta(y)=\varnothing$ for every vertex $y$. This leads to an empty domain
for $\Lambda^{\prime}$, and therefore to a running time of $\mathcal{O}(\lvert
D\rvert^{2}\cdot\lvert\lvert D\rvert\rvert)$.

#### In fuzzy linear interval graphs.

We can simplify the analysis by tracking only the rightmost kernel vertex. For
example, add an isolated dummy vertex $x_{0}$ at the left end of the
$\prec$-ordering. Because $x_{0}$ is isolated, it belongs to all kernels. Thus
we only need to compute the sets $K(x_{0},y)$ where
$y\in\operatorname{\mathsf{V}}(D)$, that is, we only have to build the part of
$\mathcal{G}(D,\prec)$ that contains $F_{x_{0}}$. This takes time
$\mathcal{O}(\lvert D\rvert^{2}\cdot\lvert\lvert D\rvert\rvert)$, which is
essentially optimal in the sense that it is also the running time of the FLIG
recognition algorithm.

#### In linear interval graphs.

In linear interval graphs, we combine the insights for FLIGs and CIGs: we
build a single part of the subproblem digraph and do not compute
$\Lambda^{\prime}$. This leads to a running time $\mathcal{O}(\lvert
D\rvert\cdot\lvert\lvert D\rvert\rvert)$. We leave the matter of getting to
e.g. $\mathcal{O}(\lvert\lvert D\rvert\rvert)$ open.