# Dually conformal hypergraphs

Endre Boros
MSIS Department and RUTCOR Rutgers University  New Jersey  USA
<EMAIL_ADDRESS>
Vladimir Gurvich
RUTCOR Rutgers University  New Jersey  USA
National Research University Higher School of Economics Moscow  Russia
<EMAIL_ADDRESS>Martin Milanič
FAMNIT and IAM University of Primorska  Koper  Slovenia
<EMAIL_ADDRESS>Yushi Uno
Graduate School of Informatics Osaka Metropolitan University Sakai Osaka
Japan
<EMAIL_ADDRESS>
###### Abstract

Given a hypergraph $\mathcal{H}$, the dual hypergraph of $\mathcal{H}$ is the
hypergraph of all minimal transversals of $\mathcal{H}$. The dual hypergraph
is always Sperner, that is, no hyperedge contains another. A special case of
Sperner hypergraphs are the conformal Sperner hypergraphs, which correspond to
the families of maximal cliques of graphs. All these notions play an important
role in many fields of mathematics and computer science, including
combinatorics, algebra, database theory, etc. In this paper we study
conformality of dual hypergraphs. While we do not settle the computational
complexity status of recognizing this property, we show that the problem is in
co-NP and can be solved in polynomial time for hypergraphs of bounded
dimension. In the special case of dimension $3$, we reduce the problem to
$2$-Satisfiability. Our approach has an implication in algorithmic graph
theory: we obtain a polynomial-time algorithm for recognizing graphs in which
all minimal transversals of maximal cliques have size at most $k$, for any
fixed $k$.

Keywords: hypergraph, conformal hypergraph, dual hypergraph, maximal clique

MSC (2020): 05C65, 05D15, 05C69 05C85, 68R10, 05-08

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Notation and definitions
    2. 2.2 Representation of hypergraphs
    3. 2.3 Subtransverals
    4. 2.4 Conformal hypergraphs
  3. 3 Dually conformal hypergraphs
    1. 3.1 Basic observations
    2. 3.2 Computing the co-occurrence graph of the dual hypergraph
    3. 3.3 The Dual Conformality problem
    4. 3.4 A polynomial case of Dual Conformality
  4. 4 Graphs with small upper clique transversal number
  5. 5 Dually conformal hypegraphs with bounded dimension
    1. 5.1 The general case
    2. 5.2 The case of dimension three
    3. 5.3 The two-uniform case
  6. 6 Discussion

##  1 Introduction

A _hypergraph_ is a finite set of finite sets called _hyperedges_. We consider
the following two properties of hypergraphs. A hypergraph is _Sperner_ [63]
(also called _simple_ [10, 11] or a _clutter_ [61]) if no hyperedge is
contained in another hyperedge. A hypergraph is _conformal_ if for each set
$U$ of vertices, if each pair of vertices in $U$ is contained in some
hyperedge, then $U$ is contained in some hyperedge (see, e.g., [61]). Both
notions play an important role in combinatorics and in many other fields of
mathematics and computer science. For example, Sperner hypergraphs and their
extensions have numerous applications in algebra, theory of monotone Boolean
functions, and databases (see, e.g., Anderson [3] and Engel [29]).
Furthermore, conformal hypergraphs are important for databases (see, e.g.,
Beeri, Fagin, Maier, and Yannakakis [9]) and arise naturally in algebraic
topology (see Berge [10, p. 412, Exercise 1]).

It is interesting to investigate the above properties in relation with the
concepts of blocking and antiblocking hypergraphs. Given a hypergraph
$\mathcal{H}=(V,E)$, the _blocking hypergraph_ (or _blocker_ ; see, e.g.,
Schrijver [61]) of $\mathcal{H}$ is the hypergraph with vertex set $V$ whose
hyperedges are exactly the minimal sets of vertices that contain at least one
vertex from each hyperedge. This concept is so natural that it was studied
under several other names in the literature, including _transversal
hypergraph_ (see Berge [10, 11]), _hitting sets_ (see Karp [43] and also Garey
and Johnson [35]), or _Menger dual_ (see Woodall [69]). Furthermore, motivated
by the equivalent concept of monotone Boolean duality (see, e.g., Crama and
Hammer [24]), the blocker of $\mathcal{H}$ is also called the _dual
hypergraph_ of $\mathcal{H}$ and denoted by $\mathcal{H}^{d}$. Indeed, in the
case of Sperner hypergraphs, the operation of mapping $\mathcal{H}$ to its
dual hypergraph is an involution, that is, $(\mathcal{H}^{d})^{d}=\mathcal{H}$
(see, e.g., Berge [10] and Schrijver [61]). Hypergraph duality has many
applications, for example to Nash-solvability of two-person game forms; see
Edmonds and Fulkerson [26] for the zero-sum case, and Gurvich and Naumova [41]
for the general two-person case. Many other applications and references can be
found in the papers by Eiter and Gottlob [28] and Makino and Kameda [54]. The
complexity of the _dualization problem_ , that is, computing the dual
hypergraph $\mathcal{H}^{d}$ given $\mathcal{H}$, is a famous open problem
(see Fredman and Khachiyan [32]).

Similarly to the blocker of a given hypergraph $\mathcal{H}=(V,E)$, one can
define the _antiblocker_ of $\mathcal{H}$ as the hypergraph $\mathcal{H}^{a}$
with vertex set $V$ whose hyperedges are exactly the maximal sets of vertices
that contain at most one vertex from each hyperedge (see Fulkerson [34]). The
antiblocker was also called _König dual_ by Woodall [69]; see also McKee [56].
Blockers and antiblockers are related to perfect graphs and polyhedral
combinatorics and were considered together in several papers [33, 40, 64, 36,
27].

It follows easily from the definitions that for every hypergraph
$\mathcal{H}$, its dual $\mathcal{H}^{d}$ is always Sperner. Furthermore, as
explained above, if $\mathcal{H}$ is also Sperner, then
$(\mathcal{H}^{d})^{d}=\mathcal{H}$. Analogously, for every hypergraph
$\mathcal{H}$, its antiblocker $\mathcal{H}^{a}$ is always conformal, and if
$\mathcal{H}$ is also conformal, then $(\mathcal{H}^{a})^{a}=\mathcal{H}$, as
shown by Woodall [69, 70] (see also Schrijver [61]). However, while the
antiblocker $\mathcal{H}^{a}$ is always Sperner, the dual $\mathcal{H}^{d}$
need not be conformal. For example, all the $2$-element subsets of a
$3$-element set form a hypergraph such that its dual is not conformal.
Moreover, even if a hypergraph is conformal, its dual may fail to be
conformal.111Consider the $2$-uniform hypergraph $\mathcal{H}$ given by the
edges of the $5$-cycle, that is, $\mathcal{H}=(V,E)$ with $V=\\{1,2,3,4,5\\}$
and $E=\\{\\{1,2\\},\\{2,3\\},\\{3,4\\},\\{4,5\\},\\{5,1\\}\\}$. Clearly,
$\mathcal{H}$ is conformal. However,
$E(\mathcal{H}^{d})=\\{\\{1,2,4\\},\\{2,3,5\\},\\{3,4,1\\},\\{4,5,2\\},\\{5,1,3\\}\\}$.
In particular, every pair of vertices belongs to a hyperedge and hence
$\mathcal{H}^{d}$ is not conformal.

Table 1: Properties of blockers and antiblockers. | Sperner | conformal
---|---|---
blocker, $\mathcal{H}^{d}$ | always | not always
antiblocker, $\mathcal{H}^{a}$ | always | always

### Our focus and motivations

The above relations summarized in Table 1 motivate our paper studying
hypergraphs whose dual is conformal. Conformal hypergraphs were characterized
independently by Gilmore [37] (see also [10, 11]) and Zykov [72]; the
characterization leads to a polynomial-time recognition algorithm. On other
other hand, the complexity of recognizing hypergraphs whose dual is conformal
is open. In this paper we focus on this problem and call such hypergraphs
_dually conformal_.

Further motivations for the study of dually conformal hypergraphs include the
following. First, variants of dual conformality are important for the
dualization problem (see Khachiyan, Boros, Elbassioni, and Gurvich [44, 46,
45]). Second, dually conformal hypergraphs have an application in algorithmic
graph theory. More precisely, a side result of our approach is a polynomial-
time algorithm for the following problem, for any fixed positive integer $k$:
given a graph $G$, does $G$ admit a minimal clique transversal (that is, an
inclusion-minimal set of vertices that intersects all maximal cliques) of size
at least $k$? This problem was studied recently by Milanič and Uno [57] and
was shown to be NP-hard in general.

### Our results

We initiate a study of the recognition problem of dually conformal
hypergraphs. As one of our main results, we develop a polynomial-time
algorithm for the case of hypergraphs of bounded dimension (maximum size of a
hyperedge). For hypergraphs of dimension at most $3$ we develop an alternative
approach based on $2$-Satisfiability. We also discuss separately the case of
$2$-uniform hypergraphs, that is, the case of graphs.

Our second main result, obtained using another polynomially solvable special
case of the recognition problem of dually conformal hypergraphs, is a
polynomial-time algorithm for recognizing graphs in which all minimal clique
transversals have size at most $k$, for any fixed $k$.

### Structure of the paper

In Section 2 we summarize the necessary preliminaries, including some basic
properties of conformal hypergraphs, both in the Sperner case and in general.
In Section 3 we present some basic results about dually conformal hypergraphs
and initiate a study of the corresponding recognition problem by identifying a
first polynomially solvable special case. Applications of this algorithm to
graphs are presented in Section 4. In Section 5, we discuss hypergraphs of
bounded dimension, both in the general case as well as in the special cases of
$3$-uniform and $2$-uniform hypergraphs. We conclude the paper in Section 6
with a discussion and several open questions.

##  2 Preliminaries

###  2.1 Notation and definitions

A _hypergraph_ is a pair $\mathcal{H}=(V,E)$ where $V$ is a finite set of
_vertices_ and $E$ is a set of subsets of $V$ called _hyperedges_ such that
every vertex belongs to a hyperedge. For a hypergraph $\mathcal{H}=(V,E)$ we
write $E(\mathcal{H})=E$ and $V(\mathcal{H})=V$, and denote by
$\dim(\mathcal{H})=\max_{e\in E}|e|$ its _dimension_. A hypergraph
$\mathcal{H}$ is said to be _$k$ -uniform_ if $|e|=k$ for all $e\in
E(\mathcal{H})$. Thus, $2$-uniform hypergraphs are precisely the (finite,
simple, and undirected) graphs without isolated vertices. We only consider
graphs and hypergraphs with nonempty vertex sets. For a vertex $v\in V$ its
degree $\deg(v)=\deg_{\mathcal{H}}(v)$ is the number of hyperedges in $E$ that
contain $v$ and $\Delta(\mathcal{H})=\max_{v\in V}\deg(v)$ is the maximum
degree of $\mathcal{H}$. The _size_ of a hypergraph $\mathcal{H}$ is the
number of hyperedges in $\mathcal{H}$. A hyperedge of $\mathcal{H}$ is said to
be _maximal_ if it is not contained in any other hyperedge. A hypergraph is
_Sperner_ if no hyperedge contains another, or, equivalently, if every
hyperedge is maximal.

A _transversal_ of a hypergraph $\mathcal{H}=(V,E)$ is a set of vertices
intersecting all hyperedges. A transversal is _minimal_ if it does not contain
any other transversal. Recall that the _dual hypergraph_ of a hypergraph
$\mathcal{H}=(V,E)$ is the hypergraph $\mathcal{H}^{d}$ with vertex set $V$,
whose hyperedges are exactly the minimal transversals of $\mathcal{H}$.

######  Fact 2.1 (Folklore, see, e.g., Berge [11]).

Let $\mathcal{H}$ be a Sperner hypergraph. Then
$(\mathcal{H}^{d})^{d}=\mathcal{H}$.

###  2.2 Representation of hypergraphs

In this subsection we describe a useful data structure for representing
hypergraphs. Let $\mathcal{H}=(V,E)$ be a hypergraph. We write $n=|V|$ and
$m=|E|$. An _incident pair_ of $\mathcal{H}$ is a pair $(v,e)$ such that $v\in
e\in E$. We assume that $\mathcal{H}$ is represented by a complete list of its
edges, as subsets of $V$, and equipped with a fixed pair of orderings of its
vertices and edges, say $V=\\{v_{1},\ldots,v_{n}\\}$ and
$E=\\{e_{1},\ldots,e_{m}\\}$.

We first perform a preprocessing step taking time $\mathcal{O}(|V||E|)$ in
order to compute the edge-vertex incidence matrix of $\mathcal{H}$, a binary
matrix $I\in\\{0,1\\}^{E\times V}$ with rows indexed by the hyperedges of
$\mathcal{H}$, columns indexed by the vertices of $\mathcal{H}$, and
$I_{e,v}=1$ if and only if $v\in e$. Having constructed the edge-vertex
incidence matrix, we can look up in constant time whether, given a vertex
$v\in V$ and hyperedge $e\in E$, the pair $(v,e)$ is an incident pair of
$\mathcal{H}$.

Next we construct a doubly-linked representation of incident pairs of
$\mathcal{H}$, that is, a collection $L$ of doubly linked lists of incident
pairs, one for each vertex and one for each hyperedge. Each incident pair
contains a pointer to its vertex, another one to its hyperedge, and having
four links – horizontal prev and next and vertical prev and next. The
horizontal links form a doubly linked circular list attached to the hyperedge,
and the vertical ones form a doubly linked circular list attached to the
vertex. See Figure 1 for an example. Due to the doubly linked nature
insertions can be done in constant time. We can thus build the structure $L$
in $\mathcal{O}(|V||E|)$ time, as follows.

  1. 1.

First, we initialize the doubly linked lists for each vertex and hyperedge to
be the doubly linked lists consisting only of the corresponding vertex, resp.
hyperedge.

  2. 2.

Then, we traverse the edge-vertex incidence matrix $I$ row by row. As we
traverse a row labeled by a hyperedge $e$, we build the doubly linked list
corresponding to this hyperedge (with horizontal prev and next links) along
with the pointers to $e$. At the same time, when a new incident pair $(v,e)$
is added to the list, the doubly linked list corresponding to the vertex $v$
is augmented with this pair (with vertical prev and next links) and the
pointer to vertex $v$.

Figure 1: A hypergraph $\mathcal{H}$, its edge-vertex incidence matrix, and
the doubly-linked representation of its incident pairs.

The usefulness of the above data structures is summarized in the following.

######  Proposition 2.2.

Given a hypergraph $\mathcal{H}=(V,E)$, with $V=\\{v_{1},\ldots,v_{n}\\}$ and
$E=\\{e_{1},\ldots,e_{m}\\}$, there is an algorithm running in time
$\mathcal{O}(|V||E|)$ that computes its edge-vertex incidence matrix and the
doubly-linked representation of its incident pairs.

Using the incidence matrix we can test in constant time the relation $v\in e$
for all $v\in V$ and $e\in E$. Using the doubly-linked representation of the
incident pairs we can:

  * •

list the vertices of a hyperedge $e\in E$ in time linear in
$|e|\leq\dim(\mathcal{H})$;

  * •

list the hyperedges containing a vertex $v\in V$ in time linear in
$\deg(v)\leq\Delta(\mathcal{H})$;

  * •

compute for any two hyperedges $e$ and $f$ their union, intersection, and the
two set differences $e\setminus f$ and $f\setminus e$ in time
$\mathcal{O}(|e|+|f|)=\mathcal{O}(\dim(\mathcal{H}))$; in particular, we can
test in time $\mathcal{O}(\dim(\mathcal{H}))$ if $e\subseteq f$.

Let us also remark that, when discussing the running times of algorithms on
graphs (in Section 4), we assume that the adjacency lists are sorted. If they
are initially not sorted, we first sort them in time $\mathcal{O}(|V|+|E|)$
(see [38]).

###  2.3 Subtransverals

Given a hypergraph $\mathcal{H}=(V,E)$, a set $S\subseteq V$ is a
_subtransversal_ of $\mathcal{H}$ if $S$ is subset of a minimal transversal.
The following characterization of subtransversals due to Boros, Gurvich, and
Hammer [15, Theorem 1] was formulated first in terms of prime implicants of
monotone Boolean functions and their duals, and reproved in terms of
hypergraphs in [14]. Given a set $S\subseteq V$ and a vertex $v\in S$, we
denote by $E_{v}(S)$ the set of hyperedges $e\in E$ such that $e\cap
S=\\{v\\}$.

######  Theorem 2.3 (Boros, Gurvich, Elbassioni, and Khachiyan [14]).

Let $\mathcal{H}=(V,E)$ be a hypergraph and let $S\subseteq V$. Then $S$ is a
subtransversal of $\mathcal{H}$ if and only if there exists a collection of
hyperedges $\\{e_{v}\in E_{v}(S):v\in S\\}$ such that the set $(\bigcup_{v\in
S}e_{v})\setminus S$ does not contain any hyperedge of $\mathcal{H}$.

Note that edges that intersect $S$ in more than one vertex do not influence
the fact whether $S$ is a subtransversal or not. The problem of determining if
a given set $S$ is a subtransversal is NP-complete even for $2$-uniform
hypergraphs, see [15, 14]. For sets of bounded cardinality, however, Theorem
2.3 leads to a polynomial-time algorithm.

######  Corollary 2.4.

Let $\mathcal{H}=(V,E)$ be a hypergraph with dimension $k$ and maximum degree
$\Delta$, given by an edge-vertex incidence matrix and a doubly-linked
representation of its incident pairs, and let $S\subseteq V$. Then, there
exists an algorithm running in time

$\mathcal{O}\left(k|E|\cdot\min\left\\{\Delta^{|S|}\,,\left(\frac{|E|}{|S|}\right)^{|S|}\right\\}\right)$

that determines if $S$ is a subtransversal of $\mathcal{H}$. In particular, if
$|S|=\mathcal{O}(1)$, the complexity is $\mathcal{O}(k|E|\Delta^{|S|})$.

###### Proof.

Note that any minimal transversal has at most as many vertices as the number
of hyperedges. Thus, if $|S|>|E|$, then we can determine in time
$\mathcal{O}(|S|+|E|)=\mathcal{O}(k|E|)$ that $S$ is not a subtransversal.
Note that $\mathcal{O}(|S|)=\mathcal{O}(|V|)=\mathcal{O}(k|E|)$, since
$V=\bigcup_{e\in E}e$.

From now on, we assume that $|S|\leq|E|$. To a subset $S\subseteq V$ we
associate the following families of edges:

$\begin{array}[]{rll}E_{v}(S)&=~{}\\{e\in E\mid e\cap S=\\{v\\}\\}&\text{ for
}~{}~{}~{}v\in S,\text{ and, }\\\ E_{\omega}(S)&=~{}\\{e\in E\mid e\cap
S=\emptyset\\}.\end{array}$

We describe the desired algorithm with the following procedure.

Procedure SubTransversal:

Input:

A hypergraph $\mathcal{H}=(V,E)$ given by an edge-vertex incidence matrix and
a doubly-linked representation $L$ of its incident pairs, a subset $S\subseteq
V$ such that $|S|\leq|E|$.

Output:

Yes if $S$ is a subset of a minimal transversal of $\mathcal{H}$, and No
otherwise.

Step 1:

Compute the families $E_{u}(S)$ for $u\in S\cup\\{\omega\\}$ in
$\mathcal{O}(|S|+k|E|)=\mathcal{O}(k|E|)$ time.

We can do this in the stated time by first traversing the set $S$ and marking
each vertex that belongs to $S$. Then for each hyperedge $e\in E$ we traverse
the corresponding list of $\mathcal{O}(k)$ vertices; if the hyperedge $e$
contains no vertex from $S$, we put it in $E_{\omega}(S)$, and if it contains
a unique vertex from $S$, say $v$, we put it in $E_{v}(S)$.

1.1

If $E_{v}(S)=\emptyset$ for some $v\in S$, then STOP and output No,
$\mathcal{O}(|S|)$ time.

1.2

otherwise if $E_{\omega}(S)=\emptyset$, then STOP and output Yes ($S$ is a
minimal transversal of $\mathcal{H}$ in this case) $\mathcal{O}(1)$ time.

Step 2:

Initialize an array $A\in\\{0,1\\}^{V}$ of length $n$ by zeros in
$\mathcal{O}(|V|)=\mathcal{O}(k|E|)$ time.

(Recall that $|V|\leq k|E|$, since $V=\bigcup_{e\in E}e$.)

For each selection $e_{v}\in E_{v}(S)$, $v\in S$ $\displaystyle\prod_{v\in
S}|E_{v}(S)|\leq\min\left\\{\Delta^{|S|},\left(\frac{|E|}{|S|}\right)^{|S|}\right\\}$
times:

2.1

Compute $\displaystyle U=\bigcup_{v\in S}e_{v}$ in $\mathcal{O}(k|S|)$ time.

To compute the set $U$ in time $\mathcal{O}(k|S|)$, we first create an object
for $U$ with a root of a doubly linked list that is initially empty (next and
prev point back to itself). As we look up the vertices of the edges $e_{v}$,
$v\in S$, one by one, in total time $O(k|S|)$ for each such vertex $u\in
e_{v}$ we first check the value of $A_{u}$. If $A_{u}=0$, we set $A_{u}=1$ and
then we add $u$, with the corresponding prev and next links, to the list of
$U$.

At the end of this procedure, the array $A$ will have $A_{u}=1$ if and only if
$u\in U$.

2.2

STOP and output Yes if $e\not\subseteq U$ for all $e\in E_{\omega}(S)$ in
$\mathcal{O}(k|E_{\omega}(S)|)=\mathcal{O}(k|E|)$ time.

For a given $e\in E_{\omega}(S)$ the test $e\not\subseteq U$ can be performed
in time $\mathcal{O}(|e|)=\mathcal{O}(k)$ by scanning the doubly linked list
of $e$ and checking the corresponding entries of the array $A$.

2.3

Restore the array $A$ to the all-zero array in $\mathcal{O}(k|S|)$ time.

This is achieved by scanning the set $U$ once, in linear time in the length of
this set, which is $\mathcal{O}(k|S|)$, and switching back the corresponding
entries in the array $A$ to zero.

Step 3:

STOP and output No in $\mathcal{O}(1)$ time.

Thus, we get two upper estimates for the running time of SubTransversal:

$\mathcal{O}\left(k|E|\Delta^{|S|}\right)~{}~{}~{}\text{ and
}~{}~{}~{}\mathcal{O}\left(k|E|\left(\frac{|E|}{|S|}\right)^{|S|}\right)\,,$

as claimed. ∎

###  2.4 Conformal hypergraphs

In this section we summarize some basic properties of conformal hypergraphs: a
characterization of conformal Sperner hypergraphs, which establishes a close
connections with graphs, a characterization of general conformal hypergraphs,
and a polynomial-time recognition algorithm of conformal hypergraphs.

All the graphs in this paper are finite, simple, and undirected. We use
standard graph theory terminology, following West [68].

Given a hypergraph $\mathcal{H}=(V,E)$, its _co-occurrence graph_ is the graph
$G(\mathcal{H})$ with vertex set $V$ that has an edge between two distinct
vertices $u$ and $v$ if there is a hyperedge $e$ of $\mathcal{H}$ that
contains both $u$ and $v$.

######  Observation 2.5.

For every hypergraph $\mathcal{H}$, every hyperedge of $\mathcal{H}$ is a
clique in the co-occurrence graph $G(\mathcal{H})$.

Note however that hyperedges of $\mathcal{H}$ are not necessarily maximal
cliques of $G(\mathcal{H})$. For example, if $\mathcal{H}$ is the complete
graph $K_{3}$, then $G(\mathcal{H})=\mathcal{H}$, but $G(\mathcal{H})$ has a
unique maximal clique of size $3$.

Recall that a hypergraph is said to be _conformal_ if for each set $U$ of
vertices, if each pair of vertices in $U$ is contained in some hyperedge, then
$U$ is contained in some hyperedge. It is not difficult to see that a
hypergraph $\mathcal{H}$ is conformal if and only if every maximal clique of
its co-occurrence graph is a hyperedge of $\mathcal{H}$ (in fact, this was the
definition of conformality given by Berge [10, 11]). Furthermore, a Sperner
hypergraph $\mathcal{H}$ is conformal if and only if every maximal clique of
its co-occurrence graph is a hyperedge of $\mathcal{H}$ (see [9]).

We now recall a characterization of Sperner conformal hypergraphs due to
Beeri, Fagin, Maier, and Yannakakis [9] (see also Berge [10, 11] for the
equivalence between properties 1 and 2). The _clique hypergraph_ of a graph
$G=(V,E)$ is the hypergraph with vertex set $V$ with hyperedges exactly the
maximal cliques in $G$.

######  Theorem 2.6 ([9], see also [10, 11]).

For every Sperner hypergraph $\mathcal{H}$, the following properties are
equivalent.

  1. 1.

$\mathcal{H}$ is conformal.

  2. 2.

$\mathcal{H}$ is the clique hypergraph of some graph.

  3. 3.

$\mathcal{H}$ is the clique hypergraph of its co-occurrence graph.

We now generalize Theorem 2.6 by characterizing the conformality property for
general (not necessarily Sperner) hypergraphs.

######  Lemma 2.7.

Let $\mathcal{H}$ be a hypergraph such that there exists a graph $G=(V,E)$ and
a collection $\mathcal{C}$ of cliques of $G$ containing all maximal cliques of
$G$ (and possibly some others) such that $\mathcal{H}=(V,\mathcal{C})$. Then
$G=G(\mathcal{H})$.

###### Proof.

We have $V(G(\mathcal{H}))=V(\mathcal{H})=V=V(G)$. Furthermore, two distinct
vertices $u$ and $v$ are adjacent in $G$ if and only if there exists a maximal
clique in $G$ containing both $u$ and $v$, and they are adjacent in the co-
occurrence graph $G(\mathcal{H})$ if and only if there exists a hyperedge of
$\mathcal{H}$ containing $u$ and $v$. The assumption on $\mathcal{C}$ implies
that there exists a maximal clique in $G$ containing both vertices if and only
if there exists a set in $\mathcal{C}$ containing both. Thus, since
$E(\mathcal{H})=\mathcal{C}$, we infer that graphs $G$ and $G(\mathcal{H})$
have the same edge sets. We conclude that $G=G(\mathcal{H})$. ∎

######  Theorem 2.8.

For every hypergraph $\mathcal{H}$, the following properties are equivalent.

  1. 1.

$\mathcal{H}$ is conformal.

  2. 2.

Every maximal clique in $G(\mathcal{H})$ is a maximal hyperedge of
$\mathcal{H}$.

  3. 3.

There exists a graph $G=(V,E)$ and a collection $\mathcal{C}$ of cliques of
$G$ containing all maximal cliques of $G$ (and possibly some others) such that
$\mathcal{H}=(V,\mathcal{C})$.

###### Proof.

We show first that property 1 implies property 2. Suppose first that
$\mathcal{H}$ is conformal, that is, every maximal clique in $G(\mathcal{H})$
is a hyperedge of $\mathcal{H}$. Let $C$ be a maximal clique in
$G(\mathcal{H})$. Since $\mathcal{H}$ is conformal, $C$ is a hyperedge of
$\mathcal{H}$. It is in fact a maximal hyperedge, since if $C$ is properly
contained in another hyperedge $e$ of $\mathcal{H}$, then by 2.5 we obtain
that $e$ is a clique in $G(\mathcal{H})$ properly containing $C$, contrary to
the assumption that $C$ is a maximal clique. Thus, property 2 holds.

Next, we show that property 2 implies property 3. To this end, suppose that
every maximal clique in $G(\mathcal{H})$ is a maximal hyperedge of
$\mathcal{H}$, and let $G=G(\mathcal{H})$ and $\mathcal{C}=E(\mathcal{H})$. We
then have $V(\mathcal{H})=V(G)$, by 2.5 every member of $\mathcal{C}$ is a
clique of $G$, and by property 2, every maximal clique in $G$ belongs to
$\mathcal{C}$. Thus, property 3 holds for $G=G(\mathcal{H})$ and
$\mathcal{C}=E(\mathcal{H})$.

We show next that property 3 implies property 1. Suppose that there exists a
graph $G=(V,E)$ and a collection $\mathcal{C}$ of cliques of $G$ containing
all maximal cliques of $G$ (and possibly some others) such that
$\mathcal{H}=(V,\mathcal{C})$. By Lemma 2.7, we have $G=G(\mathcal{H})$. This
implies that every maximal clique in $G(\mathcal{H})=G$ is a hyperedge of
$\mathcal{H}$, thus $\mathcal{H}$ is conformal and property 1 holds. ∎

Note that the proof of Theorem 2.8 shows that if $\mathcal{H}=(V,\mathcal{C})$
for some graph $G=(V,E)$ and a collection $\mathcal{C}$ of cliques of $G$
containing all maximal cliques of $G$, then not only the collection
$\mathcal{C}$ but also the graph $G$ is uniquely determined from
$\mathcal{H}$; namely, $G$ is the co-occurrence graph of $\mathcal{H}$.
Checking conformality of a given hypergraph can be done in polynomial time,
due to the following characterization.

######  Theorem 2.9 (Gilmore [37]; see also [72, 10, 11]).

A hypergraph $\mathcal{H}=(V,E)$ is conformal if and only if for every three
hyperedges $e_{1},e_{2},e_{3}\in E$ there exists a hyperedge $e\in E$ such
that

$(e_{1}\cap e_{2})\cup(e_{1}\cap e_{3})\cup(e_{2}\cap e_{3})\subseteq e\,.$

######  Proposition 2.10.

Given a hypergraph $\mathcal{H}=(V,E)$ with dimension $k$, it can be tested in
time $\mathcal{O}(|V||E|+k|E|^{4})$ if $\mathcal{H}$ is conformal.

###### Proof.

Using Proposition 2.2, we compute in time $\mathcal{O}(|V||E|)$ the edge-
vertex incidence matrix of $\mathcal{H}$ and the doubly-linked representation
of its incident pairs. We then check the conformality of $\mathcal{H}$ by
verifying the condition from Theorem 2.9. This can be done by iterating over
all $\mathcal{O}(|E|^{3})$ triples $\\{e_{1},e_{2},e_{3}\\}$ of hyperedges,
and for each such triple compute in time $\mathcal{O}(k)$ the set
$S=(e_{1}\cap e_{2})\cup(e_{1}\cap e_{3})\cup(e_{2}\cap e_{3})$, and iterate
over all edges $e\in E$ to verify the inclusion $S\subseteq e$. The overall
running time of this procedure is $\mathcal{O}(|E|^{3}\cdot(k+|E|\cdot
k))=\mathcal{O}(k|E|^{4})$. ∎

##  3 Dually conformal hypergraphs

We say that a hypergraph $\mathcal{H}$ is _dually conformal_ if its dual
hypergraph $\mathcal{H}^{d}$ is conformal. In this section we present some
basic observations about dually conformal hypergraphs and initiate a study of
the corresponding recognition problem. While we do not settle the
computational complexity status of the problem, we show that the problem is in
co-NP and develop a polynomial-time algorithm for a special case.

###  3.1 Basic observations

Since the dual hypergraph of any hypergraph $\mathcal{H}$ is the same as the
dual hypergraph of the hypergraph obtained from $\mathcal{H}$ by keeping only
the inclusion-minimal hyperedges, in order to test dual conformality of a
hypergraph we can assume without loss of generality that the hypergraph is
Sperner.

In the next proposition, we characterize the dually conformal Sperner
hypergraphs using a connection with graphs. Given a graph $G$, a set of
vertices that intersects all maximal cliques of $G$ is called a _clique
transversal_ in $G$. A clique transversal in $G$ is _minimal_ if it does not
contain any other clique transversal.

######  Proposition 3.1.

Let $\mathcal{H}$ be a hypergraph. Then the following statements are
equivalent.

  1. 1.

$\mathcal{H}$ is a dually conformal Sperner hypergraph.

  2. 2.

There exists a graph $G$ such that $\mathcal{H}$ is the hypergraph of all
minimal clique transversals of $G$.

###### Proof.

Let $\mathcal{H}$ be a dually conformal Sperner hypergraph. Let $G$ be the co-
occurrence graph of $\mathcal{H}^{d}$. Since $\mathcal{H}^{d}$ is a conformal
Sperner hypergraph, Theorem 2.6 implies that $\mathcal{H}^{d}$ is the clique
hypergraph of $G$. But then $\mathcal{H}=(\mathcal{H}^{d})^{d}$ is exactly the
hypergraph of all minimal clique transversals of $G$.

Conversely, let $G$ be a graph and let $\mathcal{H}$ be the hypergraph of all
minimal clique transversals of $G$. By construction, $\mathcal{H}$ is a
Sperner hypergraph. Then $\mathcal{H}^{d}$ is the clique hypergraph of $G$ and
thus $\mathcal{H}^{d}$ is conformal. ∎

The following characterization of dually conformal hypergraphs follows
immediately from the definition.

######  Observation 3.2.

For every hypergraph $\mathcal{H}$, the following properties are equivalent.

  1. 1.

$\mathcal{H}$ is dually conformal.

  2. 2.

Every maximal clique in $G(\mathcal{H}^{d})$ is a minimal transversal of
$\mathcal{H}$.

Fix a hypergraph $\mathcal{H}$ and let $G=G(\mathcal{H}^{d})$. By 3.2, a
necessary and sufficient condition for $\mathcal{H}$ to be dually conformal is
that every maximal clique of $G$ is a minimal transversal of $\mathcal{H}$.
Thus, in general, there are two possible reasons why $\mathcal{H}$ could fail
to be dually conformal.

######  Corollary 3.3.

Let $\mathcal{H}$ be a hypergraph and let $G=G(\mathcal{H}^{d})$. Then
$\mathcal{H}$ is not dually conformal if and only if one of the following two
conditions holds.

  1. (a)

$G$ contains a maximal clique $C$ that is not a transversal of $\mathcal{H}$,
or

  2. (b)

$G$ contains a maximal clique $C$ that is a transversal of $\mathcal{H}$ but
not a minimal one.

As shown by the following two examples, the two conditions are independent of
each other.

######  Example 3.4.

The following hypergraph satisfies property (a) but not property (b). Let
$\mathcal{H}$ be the hypergraph with vertex set $\\{1,\ldots,6\\}$ and
hyperedges $\\{1,2\\}$, $\\{1,3\\}$, $\\{2,3\\}$, $\\{1,4\\}$, $\\{2,5\\}$,
$\\{3,6\\}$, and $\\{4,5,6\\}$. Then the hyperedges of $\mathcal{H}^{d}$ are
$\\{1,2,6\\}$, $\\{1,3,5\\}$, and $\\{2,3,4\\}$. Its co-occurrence graph
$G=G(\mathcal{H}^{d})$ is shown in Fig. 2.

Figure 2: A hypergraph $\mathcal{H}$, its dual hypergraph $\mathcal{H}^{d}$,
and the co-occurrence graph of $\mathcal{H}^{d}$.

Note that $C=\\{1,2,3\\}$ is a maximal clique in $G$ that is not a transversal
of $\mathcal{H}$, since it misses the hyperedge $\\{4,5,6\\}$. Thus,
$\mathcal{H}$ satisfies property (a). On the other hand, all maximal cliques
in $G$ other than $C$ are minimal transversals of $\mathcal{H}$, and hence
$\mathcal{H}$ does not satisfy property (b).

######  Example 3.5.

The following hypergraph satisfies property (b) but not property (a). Let $G$
be the complete graph $K_{3}$ and let $\mathcal{H}=G$, that is,
$V(\mathcal{H})=\\{1,2,3\\}$ and
$E(\mathcal{H})=\\{\\{1,2\\},\\{1,3\\},\\{2,3\\}\\}$. Then
$\mathcal{H}^{d}=\mathcal{H}$ and $G(\mathcal{H}^{d})=G$. Graph $G$ is
complete and hence contains a unique maximal clique $C$, namely
$C=\\{1,2,3\\}$. This clique is a transversal of $\mathcal{H}$ but not a
minimal one. Thus, $\mathcal{H}$ satisfies property (b) but not property (a).

Furthermore, as shown by the following example, the two conditions can occur
simultaneously.

######  Example 3.6.

The following hypergraph satisfies both properties (a) and (b). Let
$\mathcal{H}$ have vertex set $\\{1,\ldots,6\\}$ and hyperedges $\\{1,4,5\\}$,
$\\{1,4,6\\}$, $\\{2,4,5\\}$, $\\{2,5,6\\}$, $\\{3,4,6\\}$, $\\{3,5,6\\}$, and
$\\{4,5,6\\}$. Then the hyperedges of $\mathcal{H}^{d}$ are $\\{1,2,6\\}$,
$\\{1,3,5\\}$, $\\{2,3,4\\}$, $\\{4,5\\}$, $\\{4,6\\}$, and $\\{5,6\\}$. Its
co-occurrence graph $G=G(\mathcal{H}^{d})$ is isomorphic to the complete
multipartite graph $K_{2,2,2}$, with parts $\\{1,4\\}$, $\\{2,5\\}$, and
$\\{3,6\\}$; two vertices in $G$ are adjacent to each other if and only if
they belong to different parts.

Note that the set $C=\\{1,2,3\\}$ is a maximal clique in $G$ that is not a
transversal of $\mathcal{H}$, since it misses the hyperedge $\\{4,5,6\\}$.
Thus, $\mathcal{H}$ satisfies property (a). Furthermore,
$C^{\prime}=\\{4,5,6\\}$ is a maximal clique in $G$ that is a transversal of
$\mathcal{H}$ but not a minimal one, since it properly contains the minimal
transversal $\\{4,5\\}$. Hence, $\mathcal{H}$ also satisfies property (b).

###  3.2 Computing the co-occurrence graph of the dual hypergraph

Immediately from 2.5 we obtain the following.

######  Corollary 3.7.

Every hyperedge of $\mathcal{H}^{d}$ is a clique in $G(\mathcal{H}^{d})$.

######  Proposition 3.8.

Given a hypergraph $\mathcal{H}=(V,E)$ with dimension $k$ and maximum degree
$\Delta$, the co-occurrence graph of the dual hypergraph $\mathcal{H}^{d}$ can
be computed in time $\mathcal{O}(k|E|\Delta^{2}|V|^{2})$.

###### Proof.

Using Proposition 2.2, we compute in time $\mathcal{O}(|V||E|)$ the edge-
vertex incidence matrix of $\mathcal{H}$ and the doubly-linked representation
of its incident pairs. Two distinct vertices $u$ and $v$ in $V$ are adjacent
in the co-occurrence graph of $(\mathcal{H})^{d}$ if and only if the set
$\\{u,v\\}$ is a subtransversal of $\mathcal{H}$. Applying Corollary 2.4 we
can test in time $\mathcal{O}(k|E|\Delta^{2})$ if any such set is a
subtransversal of $\mathcal{H}$. As the total number of pairs is
$\mathcal{O}(|V|^{2})$, the claimed time complexity follows. ∎

######  Corollary 3.9.

Given a hypergraph $\mathcal{H}=(V,E)$, the co-occurrence graph of the dual
hypergraph $\mathcal{H}^{d}$ can be computed in time
$\mathcal{O}(|V|^{3}|E|^{3})$.

###### Proof.

Immediate from Proposition 3.8 using the fact that the dimension and the
maximum degree of $\mathcal{H}$ are bounded by $k\leq|V|$ and $\Delta\leq|E|$,
respectively. ∎

###  3.3 The Dual Conformality problem

We are interested in the complexity of testing conformality for the dual
hypergraph of a given hypergraph $\mathcal{H}$. Formally, we introduce the
following problem.

Dual Conformality
Input: A hypergraph $\mathcal{H}$. Question: Is the dual hypergraph
$\mathcal{H}^{d}$ conformal?

3.2 has the following algorithmic consequence.

######  Proposition 3.10.

Given a hypergraph $\mathcal{H}=(V,E)$ with dimension $k$ and maximum degree
$\Delta$, the Dual Conformality problem is solvable in time
$\mathcal{O}(|V|^{2}(k|E|\Delta^{2}+(|V|+|E|)\cdot|E(\mathcal{H}^{d})|))$.

###### Proof.

First, we compute the co-occurrence graph $G=G(\mathcal{H}^{d})$ of
$\mathcal{H}^{d}$. By Proposition 3.8, this can be done in time
$\mathcal{O}(k|E|\Delta^{2}|V|^{2})$. By Corollary 3.7, $\mathcal{H}^{d}$ has
only hyperedges that are cliques of $G$. Now, the maximal cliques of $G$ can
be generated with polynomial delay using the algorithm by Tsukiyama et al.
[66] on the complement of $G$. More precisely, after a preprocessing step that
takes $\mathcal{O}(|V|^{2})$ time, the algorithm outputs all the maximal
cliques of $G$ one by one, spending time $\mathcal{O}(|V|^{3})$ between two
consecutive output cliques. We run the algorithm, and every time it outputs a
maximal clique of $G$ check if it belongs to $\mathcal{H}^{d}$ or not. This is
easy to check in time $\mathcal{O}(|V|^{2}|E|)$: it must be a transversal of
$\mathcal{H}$ and must be minimal. If you get a NO at any time, then stop, and
the answer is NO, otherwise, the answer is YES. The total running time of this
approach is
$\mathcal{O}(k|E|\Delta^{2}|V|^{2}+|V|^{2})+\mathcal{O}((|V|^{3}+|V|^{2}|E|)\cdot|E(\mathcal{H}^{d})|)$,
which simplifies to
$\mathcal{O}(k|E|\Delta^{2}|V|^{2}+|V|^{2}(|V|+|E|)\cdot|E(\mathcal{H}^{d})|)$.
∎

######  Remark 3.11.

The approach of the proof of Proposition 3.10 actually shows the following.
Assume that there exists an algorithm for generating all maximal cliques of an
$n$-vertex graph $G$ with preprocessing time $\mathcal{O}(T_{1}(n))$ and that
spends time $\mathcal{O}(T_{2}(n))$ between outputting any two consecutive
maximal cliques. Then, given a hypergraph $\mathcal{H}=(V,E)$, the Dual
Conformality problem is solvable in time
$\mathcal{O}(|V|^{3}|E|^{3}+T_{1}(|V|)+(|V|^{2}|E|+T_{2}(|V|))\cdot|E(\mathcal{H}^{d})|)$.
In particular, one could apply not only the algorithm by Tsukiyama et al. but
also any of the more recent faster algorithms, e.g., those in [21, 55, 20].

Of course, the size of $\mathcal{H}^{d}$ could easily be exponential in the
size of $\mathcal{H}$, so this algorithm is exponential in the size of
$\mathcal{H}$, in the worst case.222Not on average, though. On average, the
size of the dual hypergraph of a Sperner hypergraph $\mathcal{H}$ is
polynomial in the size of $\mathcal{H}$. This follows from the proof of the
main result in [47]. Accordingly, the question about computing
$\mathcal{H}^{d}$ from $\mathcal{H}$ was typically addressed from the point of
view of output-sensitive algorithms (see, e.g., [49, 60, 28]). The currently
known best algorithm for computing $\mathcal{H}^{d}$ for a general hypergraph
$\mathcal{H}$ has a running time which is linear in the output size and quasi-
polynomial in the input size [32].

######  Observation 3.12.

The Dual Conformality problem is in co-NP.

###### Proof.

Suppose that for a given hypergraph $\mathcal{H}$, its dual is not conformal.
Then there exists a maximal clique $C$ of the co-occurrence graph of
$\mathcal{H}^{d}$ that is not a minimal transversal of $\mathcal{H}$. It can
be verified in polynomial time whether a set $C\subseteq V(\mathcal{H})$
satisfies all this properties. By Corollary 3.9, the co-occurrence graph
$G(\mathcal{H}^{d})$ can be computed in polynomial time. Having computed
$G(\mathcal{H}^{d})$, we can check in polynomial time if every two distinct
vertices in $C$ are adjacent in $G(\mathcal{H}^{d})$ and whether no vertex in
$V(G(\mathcal{H}^{d}))\setminus C$ is adjacent to all vertices in $C$. Since
the hypergraph $\mathcal{H}$ is our input, we can also check in polynomial
time if $C$ is not a minimal transversal of $\mathcal{H}$. ∎

However, the complexity of Dual Conformality remains open in general.

###  3.4 A polynomial case of Dual Conformality

We develop a polynomial-time algorithm for Dual Conformality when restricted
to the hypergraphs $\mathcal{H}$ such that every maximal clique of the co-
occurrence graph of $\mathcal{H}^{d}$ is a transversal of $\mathcal{H}$. This
algorithm is then used in Section 4 to develop a polynomial-time algorithm for
recognizing graphs in which all minimal clique transversals have size at most
$k$, for every fixed $k$.

Restricted Dual Conformality
Input: A hypergraph $\mathcal{H}$ such that every maximal clique of
$G(\mathcal{H}^{d})$ is a transversal of $\mathcal{H}$. Question: Is the dual
hypergraph $\mathcal{H}^{d}$ conformal?

######  Lemma 3.13.

Let $\mathcal{H}$ be a hypergraph and let $G=G(\mathcal{H}^{d})$. Suppose that
every maximal clique of $G$ is a transversal of $\mathcal{H}$. Then
$\mathcal{H}$ is not dually conformal if and only if $G$ contains a vertex $v$
such that $N_{G}(v)$ is a transversal of $\mathcal{H}$.

###### Proof.

Assume first that there exists a vertex $v$ of $G$ such that $N_{G}(v)$ is a
transversal of $\mathcal{H}$. Let $T$ be a minimal transversal of
$\mathcal{H}$ such that $T\subseteq N_{G}(v)$. By Corollary 3.7, every minimal
transversal of $\mathcal{H}$ is a clique in $G$. Thus, $T$ is a clique and
since $T$ is contained in $N_{G}(v)$, the set $T\cup\\{v\\}$ is also a clique.
Let $C$ be a maximal clique in $G$ such that $T\cup\\{v\\}\subseteq C$. Then
$C$ is a maximal clique in $G$ that properly contains a minimal transversal of
$\mathcal{H}$ (namely $T$). Therefore, $C$ is not a minimal transversal of
$\mathcal{H}$. By 3.2, $\mathcal{H}$ is not dually conformal.

Assume now that $\mathcal{H}$ is not dually conformal. By 3.2, $G$ has a
maximal clique $C$ that is not a minimal transversal of $\mathcal{H}$. Since,
by the assumption on $\mathcal{H}$ every maximal clique of $G$ is a
transversal of $\mathcal{H}$, there exists a minimal transversal $T$ of
$\mathcal{H}$ properly contained in $C$. Let $v$ be a vertex in $C\setminus
T$. Then, since $C$ is a clique, $T$ is a subset of $N_{G}(v)$. This implies
that $N_{G}(v)$ is a transversal of $\mathcal{H}$. ∎

######  Proposition 3.14.

Given a hypergraph $\mathcal{H}=(V,E)$ with dimension $k$ and maximum degree
$\Delta$ such that every maximal clique of $G(\mathcal{H}^{d})$ is a
transversal of $\mathcal{H}$, the Restricted Dual Conformality problem is
solvable in time $\mathcal{O}(k|E|\Delta^{2}|V|^{2})$.

###### Proof.

Using Proposition 2.2, we compute in time $\mathcal{O}(|V||E|)$ the edge-
vertex incidence matrix of $\mathcal{H}$ and the doubly-linked representation
of its incident pairs. Next, we compute the co-occurrence graph
$G=G(\mathcal{H}^{d})$ of $\mathcal{H}^{d}$. By Proposition 3.8, this can be
done in time $\mathcal{O}(k|E|\Delta^{2}|V|^{2})$. Then we iterate over all
vertices $v$ of $G$ and verify in time $\mathcal{O}(k|E|)$ if the neighborhood
of $v$ in $G$ is a transversal of $\mathcal{H}$. By Lemma 3.13, if such a
vertex exists, then $G$ is not dually conformal, and otherwise it is. The
total running time of this approach is
$\mathcal{O}(k|E|\Delta^{2}|V|^{2}+k|V||E|)=\mathcal{O}(k|E|\Delta^{2}|V|^{2})$.
∎

######  Remark 3.15.

The time complexity of the algorithm given by Proposition 3.14 is dominated by
the time needed to compute the co-occurrence graph of $\mathcal{H}^{d}$. The
complexity of the remaining steps is only $\mathcal{O}(k|V||E|)$.

##  4 Graphs with small upper clique transversal number

In this section we shift the focus from hypergraphs to graphs and apply the
results from Section 3 to a problem about clique transversals in graphs.
Recall that a _clique transversal_ in a graph is a set of vertices
intersecting all maximal cliques. The problem of determining the minimum size
of a clique transversal has received considerable attention in the literature
(see, e.g., the works by Payan in 1979 [59], by Andreae, Schughart, and Tuza
in 1991 [6], by Erdős, Gallai, and Tuza in 1992 [30], as well as more recent
works [16, 5, 8, 25, 39, 50, 53, 22, 52, 13, 62, 51]). Recently, Milanič and
Uno initiated in [57] the study of the “upper” variant of this parameter. An
_upper clique transversal_ of a graph $G$ is a minimal clique transversal of
maximum size. The _upper clique transversal number_ of a graph $G$ is denoted
by $\tau_{c}^{+}(G)$ and defined as the maximum size of a minimal clique
transversal in $G$. In hypergraph terminology, the upper clique transversal
number of a graph $G$ is the maximum size of a hyperedge of the dual of the
clique hypergraph. The corresponding decision problem is as follows.

Upper Clique Transversal
Input: A graph $G$ and an integer $k$. Question: Does $G$ contain a minimal
clique transversal of size at least $k$, i.e., is $\tau_{c}^{+}(G)\geq k$?

Milanič and Uno showed in [57] that Upper Clique Transversal is NP-complete in
the classes of chordal graphs, chordal bipartite graphs, and line graphs of
bipartite graphs, but solvable in linear time in the classes of split graphs
and proper interval graphs.

We now show that for fixed $k$, the problem can be reduced in polynomial to
the Restricted Dual Conformality problem, and is thus polynomial-time
solvable. We consider the following family of problems parameterized by a
positive integer $k$, where, unlike for the Upper Clique Transversal problem,
$k$ is fixed and not part of the input.

$k$-Upper Clique Transversal
Input: A graph $G$. Question: Does $G$ contain a minimal clique transversal of
size at least $k$, i.e., is $\tau_{c}^{+}(G)\geq k$?

The problem is only interesting for $k\geq 2$, since every graph with at least
one vertex is a yes-instance to the $1$-Upper Clique Transversal problem.

Let us first note that the variant of the $k$-Upper Clique Transversal problem
in which the family of maximal cliques of the input graph $G$ is also part of
the input admits a simple polynomial-time algorithm. It suffices to verify if
there exists a set $X\subseteq V(G)$ of size $k-1$ that is not a clique
transversal of $G$ but is contained in some minimal clique transversal. The
former condition can be checked directly using the family of maximal cliques
of $G$, and the latter condition can be checked in polynomial time since $k$
is fixed, by Corollary 2.4. An alternative solution would be to verify if
there exists a set $X\subseteq V(G)$ of size $k$ that is contained in some
minimal clique transversal.

Solving the problem without knowing the family of maximal cliques (which could
be exponential in the size of $G$) requires more work, but is still doable in
polynomial time.

######  Theorem 4.1.

For every integer $k\geq 2$, given a graph $G=(V,E)$, the $k$-Upper Clique
Transversal problem is solvable in time $\mathcal{O}(|V|^{3k-3})$.

We prove Theorem 4.1 in several steps. One key ingredient is a polynomial-time
algorithm to test if a given constant-sized set of vertices in a graph is a
clique transversal.333Note that the assumption on the bound on the size of the
set is essential. In fact, as shown by Zang [71], it is co-NP-complete to
check, given a graph $G$ and an independent set $I$, whether $I$ is a clique
transversal in $G$. By definition, a set $X$ of vertices in a graph $G$ is a
clique transversal if and only if $X$ intersects all maximal cliques. In
particular, this means that for every clique $C$ in $G-X$ there exists a
vertex $x\in X$ containing $C$ in its neighborhood. As we show next, it is
sufficient to require this condition for all cliques $C$ in $G-X$ such that
$|C|\leq|X|$.

######  Lemma 4.2.

For every graph $G$ and every set $X\subseteq V(G)$, the following statements
are equivalent.

  1. 1.

$X$ is a clique transversal in $G$.

  2. 2.

For every clique $C$ in $G-X$, there exists a vertex $x\in X$ such that
$C\subseteq N_{G}(x)$.

  3. 3.

For every clique $C$ in $G-X$ such that $|C|\leq|X|$, there exists a vertex
$x\in X$ such that $C\subseteq N_{G}(x)$.

###### Proof.

Suppose $X$ is a clique transversal in $G$ and let $C$ be a clique in $G-X$.
Let $C^{\prime}$ be a maximal clique in $G$ such that $C\subseteq C^{\prime}$.
Then $C^{\prime}$ contains a vertex $x\in X$. Since $C\cup\\{x\\}\subseteq
C^{\prime}$ and $C^{\prime}$ is a clique, we must have $C\subseteq N_{G}(x)$.

Clearly, the second statement implies the third one.

We prove that the third statement implies the first one by contraposition.
Suppose that $X$ is not a clique transversal in $G$. Then there exists a
maximal clique $C^{\prime}$ in $G$ such that $C^{\prime}\cap X=\emptyset$.
Since $C^{\prime}$ is a maximal clique disjoint from $X$, every vertex in $X$
has a non-neighbor in $C^{\prime}$. Selecting one such non-neighbor for each
vertex in $X$ results in a clique $C$ in $G-X$ such that $|C|\leq|X|$ and
every vertex in $X$ has a non-neighbor in $C$. Thus, there is no vertex $x\in
X$ such that $C\subseteq N_{G}(x)$. ∎

Lemma 4.2 implies the following characterization of clique transversals of
size one. A _universal vertex_ in a graph $G$ is a vertex adjacent to all
other vertices.

######  Corollary 4.3.

Given a graph $G=(V,E)$ and a vertex $v\in V$, the set $\\{v\\}$ is a clique
transversal in $G$ if and only if $v$ is a universal vertex in $G$.

###### Proof.

By Lemma 4.2, the singleton $\\{v\\}$ is a clique transversal in $G$ if and
only if for every clique $C$ in $G-v$, it holds that $C\subseteq N_{G}(v)$. If
this latter condition is satisfied, then $v$ is universal in $G$, since
otherwise for any vertex $w$ in $G$ nonadjacent to $v$, the set $C=\\{w\\}$
would be a clique in $G-v$ violating the condition $C\subseteq N_{G}(v)$. And
conversely, if $v$ is universal in $G$, then $N_{G}(v)=V(G)\setminus\\{v\\}$
and hence the condition $C\subseteq N_{G}(v)$ is satisfied trivially for any
clique $C$ in $G-v$. ∎

As another consequence of Lemma 4.2, we obtain that when the size of a set of
vertices is bounded by a constant, testing whether the set is a clique
transversal can be done in polynomial time.

######  Proposition 4.4.

For every fixed $k\geq 1$, there is an algorithm running in time
$\mathcal{O}(|V|^{k})$ to check if, given a graph $G=(V,E)$ and a set
$X\subseteq V(G)$ with $|X|\leq k$, the set $X$ is a clique transversal of
$G$.

###### Proof.

If $k=1$, then by Corollary 4.3 $X$ is a clique transversal of $G$ if and only
if $X=\\{v\\}$ such that $v$ is a universal vertex in $G$. This condition can
be tested in time $\mathcal{O}(|V|)$.

Assuming $k\geq 2$, we first compute in time $\mathcal{O}(|V|^{2})$ the
adjacency matrix of $G$. This will allow for testing adjacency of a pair of
vertices in constant time. By Lemma 4.2, it suffices to verify if every clique
$C$ in $G$ with size at most $|X|$ either contains a vertex of $X$ or is
contained in the neighborhood of some vertex in $X$. Since $|X|\leq k$, all
such cliques can be enumerated in time $\mathcal{O}(|V|^{k})$. For each such
clique $C$, we can check in time $\mathcal{O}(|C||X|)=\mathcal{O}(1)$ if $C$
is disjoint from $X$. If it is, then we iterate over all $\mathcal{O}(1)$
vertices $x\in X$ and for each such vertex $x$ check the condition $C\subseteq
N_{G}(x)$ in time $\mathcal{O}(|C|)=\mathcal{O}(1)$. If for some clique $C$
that is disjoint from $X$ no such vertex $x\in X$ exists, we conclude that $X$
is not a clique transversal in $G$, and otherwise it is. The total running
time is $\mathcal{O}(|V|^{k})$. ∎

Furthermore, note that for every fixed $k$, if a set $X\subseteq V(G)$ with
$|X|\leq k$ is a clique transversal of $G$, then we can check in polynomial
time if $X$ is a minimal clique transversal, simply by checking, for all $x\in
X$, whether the set $X\setminus\\{x\\}$ is a clique transversal. This can be
done in time $\mathcal{O}(k|V|^{k-1})=\mathcal{O}(|V|^{k-1})$ by Proposition
4.4.

######  Corollary 4.5.

For every fixed $k$, there is an algorithm running in time
$\mathcal{O}(|V|^{k})$ to check if, given a graph $G=(V,E)$ and a set
$X\subseteq V(G)$ with $|X|\leq k$, the set $X$ is a minimal clique
transversal of $G$.

######  Lemma 4.6.

Let $k$ be a positive integer and $G$ be a graph. Let $\mathcal{H}$ be the
hypergraph defined as follows: the vertex set of $\mathcal{H}$ is $V(G)$, and
the hyperedges of $\mathcal{H}$ are precisely the minimal clique transversals
$X$ of $G$ such that $|X|\leq k$. Then the following statements are
equivalent.

  1. 1.

$\tau_{c}^{+}(G)\leq k$.

  2. 2.

$\mathcal{H}$ is the hypergraph of all minimal clique transversals of $G$.

  3. 3.

$\mathcal{H}$ is dually conformal and $G=G(\mathcal{H}^{d})$.

###### Proof.

The equivalence between items 1 and 2 follows directly from the definition of
$\tau_{c}^{+}(G)$. We thus focus on establishing the equivalence between items
2 and 3.

Assume that $\mathcal{H}$ is the hypergraph of all minimal clique transversals
of $G$, that is, $\mathcal{H}$ is the dual hypergraph of the clique hypergraph
of $G$. By 2.1, the dual hypergraph of $\mathcal{H}$ is the clique hypergraph
of $G$. By Theorem 2.6, $\mathcal{H}^{d}$ is conformal, that is, $\mathcal{H}$
is dually conformal. Furthermore, Lemma 2.7 shows that $G=G(\mathcal{H}^{d})$.

Conversely, assume now that $\mathcal{H}$ is dually conformal and
$G=G(\mathcal{H}^{d})$. Since $\mathcal{H}^{d}$ is conformal, Theorem 2.6
implies that $\mathcal{H}^{d}$ is the clique hypergraph of
$G(\mathcal{H}^{d})=G$. Thus, by 2.1, $\mathcal{H}=(\mathcal{H}^{d})^{d}$ is
the hypergraph of all minimal clique transversals of $G$. ∎

We now have everything ready to prove Theorem 4.1.

###### Proof of Theorem 4.1..

We first describe the algorithm and then justify its correctness and running
time. Let $G=(V,E)$ be the input graph.

The algorithm performs the following steps:

  1. 1.

Compute the hypergraph $\mathcal{H}$ defined as follows: the vertex set of
$\mathcal{H}$ is $V$, and the hyperedges of $\mathcal{H}$ are precisely the
minimal clique transversals $X$ of $G$ such that $|X|<k$.

  2. 2.

Compute the co-occurrence graph $G(\mathcal{H}^{d})$ of the dual hypergraph of
$\mathcal{H}$.

  3. 3.

Check if $G\neq G(\mathcal{H}^{d})$.

  4. 4.

If $G\neq G(\mathcal{H}^{d})$, then the algorithm determines that
$\tau_{c}^{+}(G)\geq k$ (that is, $G$ is a yes-instance) and halts.

  5. 5.

If $G=G(\mathcal{H}^{d})$, then apply Proposition 3.14 on $\mathcal{H}$ to
test if $\mathcal{H}^{d}$ is conformal.

     * •

If $\mathcal{H}^{d}$ is conformal, then the algorithm determines that
$\tau_{c}^{+}(G)<k$ (that is, $G$ is a no-instance) and halts.

     * •

If $\mathcal{H}^{d}$ is not conformal, then the algorithm determines that
$\tau_{c}^{+}(G)\geq k$ (that is, $G$ is a yes-instance) and halts.

To prove correctness, let us first justify that, in the case when
$G=G(\mathcal{H}^{d})$, we can indeed apply Proposition 3.14 on $\mathcal{H}$
to test if $\mathcal{H}^{d}$ is conformal. By the definition of the hypergraph
$\mathcal{H}$, every maximal clique of $G$ intersects every hyperedge of
$\mathcal{H}$. Thus, if $G=G(\mathcal{H}^{d})$, then every maximal clique of
$G(\mathcal{H}^{d})$ is a transversal of $\mathcal{H}$. This means that
$\mathcal{H}$ is indeed a valid input to the Restricted Dual Conformality
problem, and hence Proposition 3.14 applies, as claimed. Furthermore, by Lemma
4.6, we have $\tau_{c}^{+}(G)<k$ if and only if $\mathcal{H}$ is dually
conformal and $G=G(\mathcal{H}^{d})$. Equivalently, $\tau_{c}^{+}(G)\geq k$ if
and only if one of the following conditions holds: either (i) $G\neq
G(\mathcal{H}^{d})$ or (ii) $G=G(\mathcal{H}^{d})$ and $\mathcal{H}^{d}$ is
not conformal. This implies that each of the three outputs of the algorithm is
correct.

It remains to analyze the time complexity. We compute the hypergraph
$\mathcal{H}$ in time $\mathcal{O}(|V|^{2k-1})$ by enumerating all the
$\mathcal{O}(|V|^{k-1})$ subsets $X$ of $V$ with size less than $k$ and
checking, for each such set $X$, if $X$ is a minimal clique transversal of
$G$, in time $\mathcal{O}(|V|^{|X|})=\mathcal{O}(|V|^{k-1})$ using Corollary
4.5. Note that $\mathcal{H}$ has $\mathcal{O}(|V|)$ vertices and
$\mathcal{O}(|V|^{k-1})$ hyperedges. Its dimension is at most $k-1$ and
maximum degree $\Delta=\mathcal{O}(|V|^{k-2})$. By Proposition 3.8, the co-
occurrence graph of $\mathcal{H}^{d}$ can be computed in time
$\mathcal{O}(k|E(\mathcal{H})|\Delta^{2}|V(\mathcal{H})|^{2})=\mathcal{O}(k\cdot|V|^{k-1}\cdot|V|^{2(k-2)}\cdot|V|^{2})=\mathcal{O}(|V|^{3k-3})$.
The check whether the equality between the two graphs $G$ and
$G(\mathcal{H}^{d})$ holds can be performed in time $\mathcal{O}(|V|+|E|)$ by
comparing the adjacency lists of the two graphs. Finally, testing conformality
of $\mathcal{H}^{d}$ in the case when the two graphs are the same can be done
in time
$\mathcal{O}(k|E(\mathcal{H})|\Delta^{2}|V(\mathcal{H})|^{2})=\mathcal{O}(|V|^{3k-3})$
by Proposition 3.14. As each of the remaining steps takes constant time, we
conclude that the algorithm runs in time $\mathcal{O}(|V|^{3k-3})$. ∎

We close the section with a remark about the case $k=2$. Applying Theorem 4.1
to this case shows that given a graph $G=(V,E)$, the $2$-Upper Clique
Transversal problem is solvable in time $\mathcal{O}(|V|^{3})$. However, the
problem can be solved in linear time, as a consequence of the following
characterization of graphs in which all minimal clique transversals have size
one.

######  Proposition 4.7.

Let $G$ be a graph. Then $\tau_{c}^{+}(G)=1$ if and only if $G$ is complete.

###### Proof.

If $G$ is complete, then the only minimal clique transversals are the sets
consisting of a single vertex. Thus, $\tau_{c}^{+}(G)=1$ in this case.

Assume now that $G$ is not complete. Let $S$ be the set of universal vertices
of $G$. Note that by Corollary 4.3, $S$ is precisely the set of vertices $v$
such that $\\{v\\}$ is a clique transversal. We claim that $V\setminus S$ is a
clique transversal. Suppose this is not the case. Then $G$ admits a maximal
clique $C$ contained entirely in $S$. Since $S$ is a clique, we have $C=S$.
However, since every maximal clique contains $C$, it follows that $S$ is the
only maximal clique in $G$ and hence $G$ is complete, a contradiction. This
shows that $V\setminus S$ is a clique transversal, as claimed. Thus,
$V\setminus S$ contains a minimal clique transversal, and any such clique
transversal is of size at least $2$, since otherwise its only vertex would
belong to $S$. Consequently, $\tau_{c}^{+}(G)\geq 2$. ∎

##  5 Dually conformal hypegraphs with bounded dimension

In this section we study dually conformal hypergraphs of bounded dimension.
Recall that, given a hypergraph $\mathcal{H}$, the _dimension_ of
$\mathcal{H}$ is the maximum cardinality of a hyperedge in $\mathcal{H}$.

By Proposition 3.1, a Sperner hypergraph is dually conformal if and only if
there exists a graph $G$ such that $\mathcal{H}$ is the hypergraph of all
minimal clique transversals of $G$. In the case when dimension is bounded by a
positive integer $k$, we obtain a similar characterization, which in addition
takes into account the upper clique transversal number of graphs.

######  Proposition 5.1.

For every hypergraph $\mathcal{H}$ and positive integer $k$, the following
statements are equivalent.

  1. 1.

$\mathcal{H}$ is a dually conformal Sperner hypergraph with dimension at most
$k$.

  2. 2.

There exists a graph $G$ with $\tau_{c}^{+}(G)\leq k$ such that $\mathcal{H}$
is the hypergraph of all minimal clique transversals of $G$.

The proof of this proposition is very similar to the proof of Proposition 3.1,
so we omit it.

For a positive integer $k$, we are interested in the complexity of the
following problem.

Dimension-$k$ Dual Conformality
Input: A hypergraph $\mathcal{H}$ with dimension at most $k$. Question: Is the
dual hypergraph $\mathcal{H}^{d}$ conformal?

In this section we develop a polynomial-time algorithm for Dimension-$k$ Dual
Conformality for any fixed positive integer $k$. For the cases
$k\in\\{2,3\\}$, we also develop more direct algorithms.

###  5.1 The general case

We start with a technical lemma.

######  Lemma 5.2.

For every positive integer $k$, there exists an algorithm running in time
$\mathcal{O}(|E|\Delta^{2}|V|^{2}+|E||V|^{k})$ that takes as input a
hypergraph $\mathcal{H}=(V,E)$ with dimension at most $k$ and maximum degree
$\Delta$ and tests whether $G=G(\mathcal{H}^{d})$ contains a maximal clique
$C$ that is not a transversal of $\mathcal{H}$.

###### Proof.

By Proposition 3.8, the graph $G$ can be computed in time
$\mathcal{O}(k|E|\Delta^{2}|V|^{2})$, which is
$\mathcal{O}(|E|\Delta^{2}|V|^{2})$ since the dimension is constant. We show
the existence of an algorithm with the stated running time that tests the
negation of the stated condition, namely whether every maximal clique of $G$
is a transversal of $\mathcal{H}$. This condition is equivalent to the
condition that every hyperedge of $\mathcal{H}$ is a clique transversal in
$G$. Since each hyperedge $e$ of $\mathcal{H}$ has size at most $k$, by
Proposition 4.4 it can be tested in time $\mathcal{O}(|V|^{k})$ whether $e$ is
a clique transversal in $G$. Hence, the total running time of the described
algorithm is $\mathcal{O}(|E|\Delta^{2}|V|^{2}+|E||V|^{k})$. ∎

######  Theorem 5.3.

For every positive integer $k$, given a hypergraph $\mathcal{H}=(V,E)$ with
dimension at most $k$ and maximum degree $\Delta$, the Dimension-$k$ Dual
Conformality problem is solvable in time
$\mathcal{O}(|E||V|^{2}\Delta^{2}+|E||V|^{k})$.

###### Proof.

We make use of the characterization of dually conformal hypergraphs given by
Corollary 3.3. First we test condition (a) in time
$\mathcal{O}(|E||V|^{2}\Delta^{2}+|E||V|^{k})$ using Lemma 5.2. If condition
(a) holds, we conclude that $\mathcal{H}$ is not dually conformal. If the
condition does not hold, then every maximal clique of the graph
$G=G(\mathcal{H}^{d})$ is a transversal of $\mathcal{H}$, which means that
$\mathcal{H}$ is a valid input for the Restricted Dual Conformality problem.
In this case, we test dual conformality of $\mathcal{H}$ in time
$\mathcal{O}(k|E|\Delta^{2}|V|^{2})$ using Proposition 3.14. Since $k$ is
constant, the complexity simplifies to $\mathcal{O}(|E|\Delta^{2}|V|^{2})$. ∎

###  5.2 The case of dimension three

The case $k=3$ of Theorem 5.3 is as follows.

######  Theorem 5.4.

Given a hypergraph $\mathcal{H}=(V,E)$ with dimension at most $3$ and maximum
degree $\Delta$, the Dimension-$3$ Dual Conformality problem is solvable in
time $\mathcal{O}(|E||V|^{2}\Delta^{2}+|E||V|^{3})$.

We now develop an alternative approach for recognizing dually conformal
hypergraphs within the family of hypergraphs of dimension at most three, based
on a reduction to $2$-Satisfiability. The running time of this algorithm
matches that of Theorem 5.3.

Recall that Corollary 3.3 gives two possible reasons why $\mathcal{H}$ could
fail to be dually conformal. A similar characterization is as follows.

######  Lemma 5.5.

Let $\mathcal{H}$ be a hypergraph and let $G=G(\mathcal{H}^{d})$. Then
$\mathcal{H}$ is not dually conformal if and only if one of the following two
conditions holds.

  1. (a)

$G$ contains a maximal clique $C$ that is not a transversal of $\mathcal{H}$,
or

  2. (c)

$G$ contains a clique $C$ and a vertex $v\in C$ such that for each hyperedge
$e\in E(\mathcal{H})$ that contains $v$ we have $|C\cap e|\geq 2$.

###### Proof.

By Corollary 3.3, the equivalence holds if $G$ contains a maximal clique $C$
that is not a transversal of $\mathcal{H}$.

Suppose now that every maximal clique of $G$ is a transversal of
$\mathcal{H}$. In this case, by Corollary 3.3, it suffices to show that $G$
contains a maximal clique $C$ that is a transversal of $\mathcal{H}$ but not a
minimal one if and only if $G$ contains a clique $C^{\prime}$ and a vertex
$v\in C^{\prime}$ such that for all hyperedges $e\in E(\mathcal{H})$ that
contain $v$ we have $|C^{\prime}\cap e|\geq 2$. Suppose first that $G$
contains a maximal clique $C$ that is a transversal of $\mathcal{H}$ but not a
minimal one. Then there exists a vertex $v\in C$ such that $C\setminus\\{v\\}$
is a transversal of $\mathcal{H}$. In particular, this implies that for all
hyperedges $e\in E(\mathcal{H})$ that contain $v$ we have $|C\cap e|\geq 2$.

For the converse direction, suppose that $G$ contains a clique $C^{\prime}$
and a vertex $v\in C^{\prime}$ such that for each hyperedge $e\in
E(\mathcal{H})$ that contains $v$ we have $|C^{\prime}\cap e|\geq 2$. Let $C$
be a maximal clique in $G$ such that $C^{\prime}\subseteq C$. We claim that
$C$ is a transversal of $\mathcal{H}$ but not a minimal one. The fact that $C$
is a transversal of $\mathcal{H}$ follows from the assumption that every
maximal clique of $G$ is a transversal of $\mathcal{H}$. Furthermore, $C$ is
not a minimal transversal since $C\setminus\\{v\\}$ is a transversal of
$\mathcal{H}$. To see this, consider an arbitrary hyperedge $e\in
E(\mathcal{H})$.

  * •

If $v\in e$, then $|C^{\prime}\cap e|\geq 2$ and hence
$|(C\setminus\\{v\\})\cap e|\geq|(C^{\prime}\setminus\\{v\\})\cap e|\geq 1$.

  * •

If $v\not\in e$, then $(C\setminus\\{v\\})\cap e=C\cap e$, and $C\cap
e\neq\emptyset$ since $C$ is a transversal of $\mathcal{H}$.

Thus, in either case, $C\setminus\\{v\\}$ intersects $e$. It follows that
$C\setminus\\{v\\}$ is a transversal of $\mathcal{H}$, as claimed. ∎

Recall that condition (a) can be tested in polynomial time for any bounded
dimension using Lemma 5.2. Next we show that for hypergraphs with dimension at
most three, condition (c) can be tested in polynomial time using a reduction
to $2$-Satisfiability, a well-known problem solvable in linear time (see
Aspvall, Plass, and Tarjan [7]).

######  Lemma 5.6.

There exists an algorithm running in time
$\mathcal{O}(|E||V|^{2}\Delta^{2}+|V|^{3})$ that tests whether for a given
hypergraph $\mathcal{H}=(V,E)$ with dimension at most $3$ and maximum degree
$\Delta$, the graph $G=G(\mathcal{H}^{d})$ contains a clique $C$ and a vertex
$v\in C$ such that for each hyperedge $e\in E$ that contains $v$ it holds
$|C\cap e|\geq 2$.

###### Proof.

By Proposition 3.8 the co-occurrence graph $G=G(\mathcal{H}^{d})$ of
$\mathcal{H}^{d}$ can be constructed in time
$\mathcal{O}(|E|\Delta^{2}|V|^{2})$. We develop a polynomial-time algorithm to
test, given a vertex $v$ of $G$, whether $G$ contains a clique $C$ such that
$v\in C$ and for each hyperedge $e\in E$ that contains $v$ we have $|C\cap
e|\geq 2$. Let $e_{1},\ldots,e_{\ell}$ be the hyperedges of $\mathcal{H}$ that
contain $v$. We need to decide if there is a clique $K$ in $G$ such that
$K\subseteq N_{G}(v)$ and $K\cap e_{i}\neq\emptyset$ for all
$i\in\\{1,\ldots,\ell\\}$.

For each $i\in\\{1,\ldots,\ell\\}$, we compute in time $\mathcal{O}(|V|)$ the
intersection $e_{i}\cap N_{G}(v)$. If $e_{i}\cap N_{G}(v)=\emptyset$ for some
$i\in\\{1,\ldots,\ell\\}$, then the desired clique $K$ does not exist. So let
us assume that $e_{i}\cap N_{G}(v)\neq\emptyset$ for all
$i\in\\{1,\ldots,\ell\\}$. In this case we determine the existence of a
desired clique $K$ by solving the following instance of $2$-Satisfiability:

  * •

For each vertex $u\in N_{G}(v)$ there is one variable $x_{u}$ (with the
intended meaning that $x_{u}$ takes value true in a satisfying assignment if
and only if $u\in K$).

  * •

For every two distinct non-adjacent vertices $u,w\in N_{G}(v)$, we introduce
the clause $\neg x_{u}\vee\neg x_{w}$ (specifying that not both $u$ and $w$
can be selected in the clique $K$).

Furthermore, for every $i\in\\{1,\ldots,\ell\\}$, we introduce the clause
$\bigvee_{u\in e_{i}\cap N_{G}(v)}x_{u}$ (specifying that at least one of the
vertices in $e_{i}\cap N_{G}(v)$ should belong to $K$).

Note that for each $i\in\\{1,\ldots,\ell\\}$, we have $v\in e_{i}$ and
$|e_{i}|\leq 3$ since $\mathcal{H}$ has dimension at most $3$. Consequently,
$|e_{i}\cap N_{G}(v)|\leq|e_{i}\setminus\\{v\\}|\leq 2$ and hence all the
clauses have length one or two. The instance of $2$-Satisfiability is
constructed so that there is a clique $K$ in $G$ such that $K\subseteq
N_{G}(v)$ and $K\cap e_{i}\neq\emptyset$ for all $i\in\\{1,\ldots,\ell\\}$ if
and only if the conjunction of all the clauses has a satisfying assignment.
There are $\mathcal{O}(\Delta)$ intersections $e_{i}\cap N_{G}(v)$,
$i\in\\{1,\ldots,\ell\\}$, which can be computed in time
$\mathcal{O}(\Delta|V|)$. There are $\mathcal{O}(|V|)$ variables and
$\mathcal{O}(|V|^{2}+\Delta)$ clauses, hence this is a polynomial-time
reduction to the linear-time solvable $2$-Satisfiability problem. We solve an
instance of $2$-Satisfiability for each vertex $v$ of $G$, and hence the time
complexity of this part of the algorithm is
$\mathcal{O}(|V|(\Delta|V|+|V|+|V|^{2}+\Delta))=\mathcal{O}(|V|^{2}(|V|+\Delta))$,
resulting in the total running time of
$\mathcal{O}(|E||V|^{2}\Delta^{2}+|V|^{3})$, as claimed. ∎

Lemmas 5.5, 5.2, and 5.6 provide an alternative proof of Theorem 5.4.

###  5.3 The two-uniform case

In this section we analyze in some more details the case $k=2$ of Theorem 5.3,
that is, the case of $2$-uniform hypergraphs. Note that in this case we are
dealing simply with graphs without isolated vertices; in particular, we shall
also use the standard graph theory terminology and notation.

In the case $k=2$, the characterization of dually conformal hypergraphs given
by Lemma 5.5 can be simplified as follows.

######  Lemma 5.7.

Let $\mathcal{H}$ be a $2$-uniform hypergraph and let $G=G(\mathcal{H}^{d})$.
Then $\mathcal{H}$ is not dually conformal if and only if one of the following
two conditions holds.

  1. $(a)$

$G$ contains a maximal clique $C$ that is not a transversal of $\mathcal{H}$,
or

  2. $(c^{*})$

$G$ contains a vertex $v$ such that the closed neighborhood of $v$ in
$\mathcal{H}$ is a clique in $G$.

###### Proof.

By Lemma 5.5, it is sufficient to show that condition $(c^{*})$ from Lemma 5.7
is equivalent to condition $(c)$ from Lemma 5.5. Since $\mathcal{H}$ is
$2$-uniform, the inequality $|C\cap e|\geq 2$ in condition $(c)$ is equivalent
to the inclusion $e\subseteq C$. Thus, condition $(c)$ is equivalent to
following condition: $G$ contains a vertex $v$ and a clique $C$ such that $C$
contains $v$ as well as all hyperedges $e$ of $\mathcal{H}$ that contain $v$.
In graph theoretic terms, this means that $G$ contains a vertex $v$ and a
clique $C$ such that $C$ contains the closed neighborhood of $v$ in
$\mathcal{H}$. If this condition is satisfied, then $N_{\mathcal{H}}[v]$ is a
clique in $G$, too, and condition $(c^{*})$ holds. Conversely, if condition
$(c^{*})$ holds and $v$ is a vertex in $G$ such that $N_{\mathcal{H}}[v]$ is a
clique in $G$, then we can take $C=N_{\mathcal{H}}[v]$ and condition $(c)$ is
satisfied. ∎

Using Lemma 5.7 we now prove the announced result.

######  Theorem 5.8.

Given a $2$-uniform hypergraph $\mathcal{H}=(V,E)$ with maximum degree
$\Delta$, the Dimension-$2$ Dual Conformality problem is solvable in time
$\mathcal{O}(|E||V|^{2}\Delta^{2})$.

###### Proof.

Let $\mathcal{H}$ be the input $2$-uniform hypergraph and let
$G=G(\mathcal{H}^{d})$ be the co-occurrence graph of $\mathcal{H}^{d}$. By
Proposition 3.8, $G$ can be computed in time
$\mathcal{O}(|E||V|^{2}\Delta^{2})$. By Lemma 5.7, $\mathcal{H}$ is not dually
conformal if and only if one of the conditions $(a)$ and $(c^{*})$ from the
lemma holds. By Lemma 5.2, condition (a) can be tested in time
$\mathcal{O}(|E||V|^{2}\Delta^{2}$). Since we know both graphs $G$ and
$\mathcal{H}$, condition $(c^{*})$ can also be tested in polynomial time: for
each vertex $v$ of $G$, we compute the closed neighborhood of $v$ in
$\mathcal{H}$ and verify if it is a clique in $G$. For a fixed vertex $v$ of
$G$, this can be done in time $\mathcal{O}(\Delta^{2})$, resulting in the
total time complexity of $\mathcal{O}(|V|\Delta^{2})$. ∎

######  Remark 5.9.

The time complexity of the algorithm given by Theorem 5.8 is dominated by the
time needed to compute the co-occurrence graph of $\mathcal{H}^{d}$. The
complexity of the remaining steps is only
$\mathcal{O}(|E||V|^{2}+|V|\Delta^{2})$.

Recall that by Corollary 4.3, a minimal clique transversal in a graph $G$ has
size one if and only if it consists of a universal vertex. Therefore,
Proposition 5.1 and its proof imply the following.

######  Corollary 5.10.

For every $2$-uniform hypergraph $\mathcal{H}$, the following statements are
equivalent.

  1. 1.

$\mathcal{H}$ is dually conformal.

  2. 2.

There exists a graph $G$ with $\tau_{c}^{+}(G)=2$ and without universal
vertices such that $\mathcal{H}$ is the hypergraph of all minimal clique
transversals of $G$.

##  6 Discussion

We have initiated the study of dually conformal hypergraphs, that is,
hypergraphs whose dual hypergraph is conformal. As our main result, we
developed a polynomial-time algorithm for recognizing dual conformality in
hypergraphs of bounded dimension.

The main problem left open by our work is of course the problem of determining
the complexity of Dual Conformality. In particular, the following questions
are open.

######  Question 1.

Is Dual Conformality co-NP-complete? Is it in NP? Is it in P?

One could approach these questions by studying the Dual Conformality problem
in particular classes of hypergraphs, for example on hypergraphs derived from
graphs (such as matching hypergraphs [1, 67], various clique [40, 67, 58, 59,
48], independent set [40, 67], neighborhood [31, 17], separator [42, 65, 18],
and dominating set hypergraphs [17, 18], etc.). If there exists a type of
hypergraphs derived from graphs and a class of graphs $\mathcal{G}$ such that
for each graph $G\in\mathcal{G}$, the corresponding hypergraph can be computed
in polynomial time but testing dual conformality is co-NP-complete, this would
imply co-NP-completeness of Dual Conformality. In particular, given that the
conformality property of Sperner hypergraphs is closely related to clique
hypergraphs of graphs (cf. Theorem 2.6), it would be natural to investigate
the complexity of Dual Conformality when restricted to clique hypergraphs of
graphs. This leads to the following property of graphs. A graph $G$ is _clique
dually conformal (CDC)_ if its clique hypergraph is dually conformal.

######  Question 2.

What is the complexity of recognizing CDC graphs?

As explained above, the question is particularly interesting for graph classes
with polynomially many maximal cliques. As our preliminary investigations, we
were able to develop polynomial-time algorithms for testing the CDC property
in the classes of split graphs and triangle-free graphs. To keep the length of
this paper manageable, we shall present these results in a separate
publication.

Recall that our results have implications for the upper clique transversal
problem in graphs. The variant of the problem in which $k$ is part of input is
known to be NP-hard, see [57]. In terms of the parameterized complexity of the
problem (with $k$ as the parameter), Theorem 4.1 shows that the problem is in
XP. This motivates the following.

######  Question 3.

Is the $k$-Upper Clique Transversal problem with $k$ as parameter W[1]-hard?

We conclude with some structural questions.

######  Question 4.

Is there a real number $r\geq 1$ such that every conformal hypergraph
$\mathcal{H}$ satisfies
$(\dim(\mathcal{H})\cdot\dim(\mathcal{H}^{d}))^{r}\geq|V(\mathcal{H})|$?

Note that we may without loss of generality restrict our attention to Sperner
conformal hypergraphs. On the other hand, the conformality assumption in 4 is
essential, as shown by the following construction by Vladimir Gurvich and
Kazuhisa Makino (personal communication), generalizing a graph construction
due to Costa, Haeusler, Laber, and Nogueira [23]. Consider integers $d\geq 2$,
$\ell\geq 1$, and $k>d$. Define a $d$-uniform hypergraph $\mathcal{H}=(V,E)$
as follows. Consider a set $W$ of $k$ vertices. The hypergraph $\mathcal{H}$
contains, as hyperedges, all $d$-subsets of $W$ and $\ell{k\choose d-1}$ other
edges, obtained as follows. To every $(d-1)$-subset of $W$ let us assign a new
vertex and add the obtained $d$-set to $E$. Moreover, let us do this $\ell$
times for each $(d-1)$-set. Note that $\mathcal{H}$ is not conformal.
Furthermore, the number of vertices is $|V|=k+\ell{k\choose d-1}$, while
$\dim(\mathcal{H})=d$ and $\dim(\mathcal{H}^{d})=k+\ell-(d-1)$. In particular,
taking an integer $q\geq 2$ and setting $d=q+1$, $k=2q$, and $\ell=1$, we
obtain $\dim(\mathcal{H})=\dim(\mathcal{H}^{d})=q+1$, while $|V|={2q\choose
q}+2q$, which is exponential in $q$. If $d=2$, $k>d$ is arbitrary, and
$\ell=k-1$, we obtain the same example as in [23].

Since the general case of 4 is equivalent to the Sperner case, Theorem 2.6
implies that the question can be posed equivalently in graph theoretic terms.
Recall that for a graph $G$, we denote by $\omega(G)$ the maximum size of a
clique in $G$ and by $\tau_{c}^{+}(G)$ the upper clique transversal number of
$G$.

######  Question 5.

Is there a real number $r\geq 1$ such that every graph $G$ satisfies

$\left(\omega(G)\cdot\tau_{c}^{+}(G)\right)^{r}\geq|V(G)|\,?$

A strongly related question for the class of CIS graphs (that is, graphs in
which every maximal independent set is a clique transversal) was posed by
Alcón, Gutierrez, and Milanič in [2]. Denoting by $\alpha(G)$ the maximum size
of an independent set in a graph $G$, the question is as follows.

######  Question 6 (Alcón, Gutierrez, and Milanič [2]).

Is there a real number $r\geq 1$ such that every CIS graph $G$ satisfies

$(\omega(G)\cdot\alpha(G))^{r}\geq|V(G)|\,?$

Note that a positive answer to 6 question would imply a positive answer to 5
for the class of CIS graphs. For general graphs, random graphs show that the
analogue of 6 does not hold (see, e.g., [12]). On the other hand, the famous
Erdős-Hajnal conjecture (see, e.g., the survey by Chudnovsky [19]) states that
the analogue of 6 holds when restricted to any class of graphs not containing
a fixed graph $H$ as an induced subgraph (with the value of $r$ depending on
$H$). In contrast, every graph is an induced subgraph of a CIS graph (see
[4]).

### Acknowledgements

We are grateful to Kazuhisa Makino for helpful discussions related to 4. Part
of the work for this paper was done in the framework of bilateral projects
between Slovenia and the USA and between Slovenia and the Russian federation,
partially financed by the Slovenian Research and Innovation Agency (BI-
US/22–24–093, BI-US/22–24–149, BI-US/$20$–$21$–$018$, and BI-
RU/$19$–$21$–$029$). The work of the third author is supported in part by the
Slovenian Research and Innovation Agency (I0-0035, research program P1-0285
and research projects N1-0102, N1-0160, J1-3001, J1-3002, J1-3003, J1-4008,
and J1-4084). This research of the second author was included in the HSE
University Basic Research Program. The work of the fourth author is partially
supported by JSPS KAKENHI Grant Number JP17K00017, 20H05964 and 21K11757,
Japan.

## References

  * [1] R. Aharoni, E. Berger, and R. Ziv.  The edge covering number of the intersection of two matroids.  Discrete Math., 312(1):81–85, 2012.
  * [2] L. Alcón, M. Gutierrez, and M. Milanič.  A characterization of claw-free CIS graphs and new results on the order of CIS graphs.  In The proceedings of Lagos 2019, the tenth Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2019), volume 346 of Electron. Notes Theor. Comput. Sci., pages 15–27. Elsevier Sci. B. V., Amsterdam, 2019.
  * [3] I. Anderson.  Combinatorics of finite sets.  Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1987.
  * [4] D. V. Andrade, E. Boros, and V. Gurvich.  On graphs whose maximal cliques and stable sets intersect.  In Optimization problems in graph theory, volume 139 of Springer Optim. Appl., pages 3–63. Springer, Cham, 2018.
  * [5] T. Andreae and C. Flotow.  On covering all cliques of a chordal graph.  Discrete Math., 149(1-3):299–302, 1996.
  * [6] T. Andreae, M. Schughart, and Z. Tuza.  Clique-transversal sets of line graphs and complements of line graphs.  Discrete Math., 88(1):11–20, 1991.
  * [7] B. Aspvall, M. F. Plass, and R. E. Tarjan.  A linear-time algorithm for testing the truth of certain quantified Boolean formulas.  Inform. Process. Lett., 8(3):121–123, 1979.
  * [8] V. Balachandran, P. Nagavamsi, and C. P. Rangan.  Clique transversal and clique independence on comparability graphs.  Inform. Process. Lett., 58(4):181–184, 1996.
  * [9] C. Beeri, R. Fagin, D. Maier, and M. Yannakakis.  On the desirability of acyclic database schemes.  J. ACM, 30(3):479–513, 1983.
  * [10] C. Berge.  Graphs and hypergraphs. Translated by Edward Minieka, volume 6 of North-Holland Math. Libr. Elsevier (North-Holland), Amsterdam, 1973.
  * [11] C. Berge.  Hypergraphs.  North-Holland Publishing Co., Amsterdam, 1989.
  * [12] B. Bollobás.  Random graphs, volume 73 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, second edition, 2001.
  * [13] F. Bonomo, G. Durán, M. D. Safe, and A. K. Wagler.  Clique-perfectness of complements of line graphs.  Discrete Appl. Math., 186:19–44, 2015.
  * [14] E. Boros, V. Gurvich, K. Elbassioni, and L. Khachiyan.  An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension.  Parallel Process. Lett., 10(4):253–266, 2000.
  * [15] E. Boros, V. Gurvich, and P. L. Hammer.  Dual subimplicants of positive Boolean functions.  volume 10, pages 147–156. 1998.
  * [16] G. J. Chang, M. Farber, and Z. Tuza.  Algorithmic aspects of neighborhood numbers.  SIAM J. Discrete Math., 6(1):24–29, 1993.
  * [17] N. Chiarelli and M. Milanič.  Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs.  Discrete Appl. Math., 179:1–12, 2014.
  * [18] N. Chiarelli and M. Milanič.  Linear separation of connected dominating sets in graphs.  Ars Math. Contemp., 16(2):487–525, 2019.
  * [19] M. Chudnovsky.  The Erdös-Hajnal conjecture—a survey.  J. Graph Theory, 75(2):178–190, 2014.
  * [20] C. Comin and R. Rizzi.  An improved upper bound on maximal clique listing via rectangular fast matrix multiplication.  Algorithmica, 80(12):3525–3562, 2018.
  * [21] A. Conte, R. Grossi, A. Marino, and L. Versari.  Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs.  Algorithmica, 82(6):1547–1573, 2020.
  * [22] J. W. Cooper, A. Grzesik, and D. Král.  Optimal-size clique transversals in chordal graphs.  J. Graph Theory, 89(4):479–493, 2018.
  * [23] V. Costa, E. Haeusler, E. S. Laber, and L. Nogueira.  A note on the size of minimal covers.  Inform. Process. Lett., 102(2-3):124–126, 2007.
  * [24] Y. Crama and P. L. Hammer, editors.  Boolean functions. Theory, algorithms, and applications, volume 142 of Encycl. Math. Appl. Cambridge: Cambridge University Press, 2011.
  * [25] P. Eades, M. Keil, P. D. Manuel, and M. Miller.  Two minimum dominating sets with minimum intersection in chordal graphs.  Nordic J. Comput., 3(3):220–237, 1996.
  * [26] J. Edmonds and D. R. Fulkerson.  Bottleneck extrema.  J. Comb. Theory, 8:299–306, 1970.
  * [27] P. Eirinakis, D. Magos, and I. Mourtos.  Blockers and antiblockers of stable matchings.  Theor. Comput. Sci., 524:126–133, 2014.
  * [28] T. Eiter and G. Gottlob.  Identifying the minimal transversals of a hypergraph and related problems.  SIAM J. Comput., 24(6):1278–1304, 1995.
  * [29] K. Engel.  Sperner theory, volume 65 of Encyclopedia of Mathematics and its Applications.  Cambridge University Press, Cambridge, 1997.
  * [30] P. Erdős, T. Gallai, and Z. Tuza.  Covering the cliques of a graph with vertices.  volume 108, pages 279–289. 1992.
  * [31] F. Foucaud.  Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes.  J. Discrete Algorithms, 31:48–68, 2015.
  * [32] M. L. Fredman and L. Khachiyan.  On the complexity of dualization of monotone disjunctive normal forms.  J. Algorithms, 21(3):618–628, 1996.
  * [33] D. R. Fulkerson.  Blocking and anti-blocking pairs of polyhedra.  Math. Program., 1:168–194, 1971.
  * [34] D. R. Fulkerson.  Anti-blocking polyhedra.  J. Comb. Theory, Ser. B, 12:50–71, 1972.
  * [35] M. R. Garey and D. S. Johnson.  Computers and intractability.  A Series of Books in the Mathematical Sciences. W. H. Freeman and Co., San Francisco, CA, 1979.
  * [36] G. Gasparyan, M. Preissmann, and A. Sebő.  Imperfect and nonideal clutters: A common approach.  Combinatorica, 23(2):283–302, 2003.
  * [37] P. Gilmore.  Families of sets with faithful graph representation.  IBM Research Note N.C., 184, 1962.  Thomas J. Watson Research Center, Yorktown Heights, New York.
  * [38] M. C. Golumbic.  Algorithmic graph theory and perfect graphs, volume 57 of Annals of Discrete Mathematics.  Elsevier Science B.V., Amsterdam, second edition, 2004.
  * [39] V. Guruswami and C. Pandu Rangan.  Algorithmic aspects of clique-transversal and clique-independent sets.  Discrete Appl. Math., 100(3):183–202, 2000.
  * [40] V. Gurvich.  On exact blockers and anti-blockers, $\Delta$-conjecture, and related problems.  Discrete Appl. Math., 159(5):311–321, 2011.
  * [41] V. Gurvich and M. Naumova.  Lexicographically maximal edges of dual hypergraphs and nash-solvability of tight game forms.  Annals of Mathematics and Artificial Intelligence, 2022.  To appear. https://doi.org/10.1007/s10472-022-09820-3.
  * [42] P. L. Hammer, F. Maffray, and M. Queyranne.  Cut-threshold graphs.  Discrete Appl. Math., 30(2-3):163–179, 1991.
  * [43] R. M. Karp.  Reducibility among combinatorial problems.  In Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), The IBM Research Symposia Series, pages 85–103. Plenum, New York-London, 1972.
  * [44] L. Khachiyan, E. Boros, K. Elbassioni, and V. Gurvich.  A new algorithm for the hypergraph transversal problem.  In Computing and combinatorics. 11th annual international conference, COCOON 2005, Kunming, China, August 16–29, 2005. Proceedings., pages 767–776. Berlin: Springer, 2005.
  * [45] L. Khachiyan, E. Boros, K. Elbassioni, and V. Gurvich.  A global parallel algorithm for the hypergraph transversal problem.  Inform. Process. Lett., 101(4):148–155, 2007.
  * [46] L. Khachiyan, E. Boros, K. Elbassioni, and V. Gurvich.  On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs.  Theoret. Comput. Sci., 382(2):139–150, 2007.
  * [47] A. D. Korshunov.  The number of monotone Boolean functions.  Problemy Kibernet., (38):5–108, 272, 1981.
  * [48] S. L. Lauritzen, T. P. Speed, and K. Vijayan.  Decomposable graphs and hypergraphs.  J. Austral. Math. Soc. Ser. A, 36(1):12–29, 1984.
  * [49] E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan.  Generating all maximal independent sets: NP-hardness and polynomial-time algorithms.  SIAM J. Comput., 9(3):558–565, 1980.
  * [50] C.-M. Lee.  Algorithmic aspects of some variations of clique transversal and clique independent sets on graphs.  Algorithms (Basel), 14(1):Paper No. 22, 14, 2021.
  * [51] C.-M. Lee and M.-S. Chang.  Distance-hereditary graphs are clique-perfect.  Discrete Appl. Math., 154(3):525–536, 2006.
  * [52] M. C. Lin and S. Vasiliev.  Approximation algorithms for clique transversals on some graph classes.  Inform. Process. Lett., 115(9):667–670, 2015.
  * [53] K. Liu and M. Lu.  Complete-subgraph-transversal-sets problem on bounded treewidth graphs.  J. Comb. Optim., 41(4):923–933, 2021.
  * [54] K. Makino and T. Kameda.  Transformations on regular nondominated coteries and their applications.  SIAM J. Discrete Math., 14(3):381–407, 2001.
  * [55] K. Makino and T. Uno.  New algorithms for enumerating all maximal cliques.  In Algorithm theory—SWAT 2004, volume 3111 of Lecture Notes in Comput. Sci., pages 260–272. Springer, Berlin, 2004.
  * [56] T. A. McKee.  Logical aspects of combinatorial duality.  Can. Math. Bull., 27:251–256, 1984.
  * [57] M. Milanič and Y. Uno.  Upper clique transversals in graphs.  In D. Paulusma and B. Ries, editors, Graph-Theoretic Concepts in Computer Science – 49th International Workshop, WG 2023, Fribourg, Switzerland, June 28–30, 2023, Revised Selected Papers, volume 14093 of Lecture Notes in Comput. Sci., pages 432–446. Springer Nature Switzerland, 2023.  Full version available at https://arxiv.org/abs/2309.14103.
  * [58] B. Mohar and R. Škrekovski.  The Grötzsch theorem for the hypergraph of maximal cliques.  Electron. J. Combin., 6:Research Paper 26, 13, 1999.
  * [59] C. Payan.  Remarks on cliques and dominating sets in graphs.  Ars Combin., 7:181–189, 1979.
  * [60] R. C. Read and R. E. Tarjan.  Bounds on backtrack algorithms for listing cycles, paths, and spanning trees.  Networks, 5(3):237–252, 1975.
  * [61] A. Schrijver.  Combinatorial optimization. Polyhedra and efficiency (3 volumes), volume 24 of Algorithms Comb. Berlin: Springer, 2003.
  * [62] E. Shan, Z. Liang, and L. Kang.  Clique-transversal sets and clique-coloring in planar graphs.  European J. Combin., 36:367–376, 2014.
  * [63] E. Sperner.  Ein Satz über Untermengen einer endlichen Menge.  Math. Z., 27(1):544–548, 1928.
  * [64] J. Tind.  Blocking and antiblocking polyhedra.  Ann. Discrete Math. 4, 159-174 (1979)., 1979.
  * [65] M. Tkáč and H.-J. Voss.  On $k$-trestles in polyhedral graphs.  Discuss. Math. Graph Theory, 22(1):193–198, 2002.
  * [66] S. Tsukiyama, M. Ide, H. Ariyoshi, and I. Shirakawa.  A new algorithm for generating all the maximal independent sets.  SIAM J. Comput., 6(3):505–517, 1977.
  * [67] D. B. West.  Parameters of partial orders and graphs: packing, covering, and representation.  In Graphs and order (Banff, Alta., 1984), volume 147 of NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., pages 267–350. Reidel, Dordrecht, 1985.
  * [68] D. B. West.  Introduction to graph theory.  Prentice Hall, Inc., Upper Saddle River, NJ, 1996.
  * [69] D. R. Woodall.  Menger and König systems.  Theor. Appl. Graphs, Proc. Kalamazoo 1976, Lect. Notes Math. 642, 620-635 (1978)., 1978.
  * [70] D. R. Woodall.  Minimax theorems in graph theory.  Selected topics in graph theory, 237-269 (1978)., 1978.
  * [71] W. Zang.  Generalizations of Grillet’s theorem on maximal stable sets and maximal cliques in graphs.  Discrete Math., 143(1-3):259–268, 1995.
  * [72] A. A. Zykov.  Hypergraphs.  Russ. Math. Surv., 29(6):89–156, 1974.