# On well-edge-dominated graphs

1Sarah E. Anderson, 2Kirsti Kuenzel and 3Douglas F. Rall

1Department of Mathematics
University of St. Thomas
St. Paul, Minnesota USA
Email<EMAIL_ADDRESS>

2Department of Mathematics
Trinity College
Hartford, Connecticut USA
Email<EMAIL_ADDRESS>

3Department of Mathematics
Furman University
Greenville, SC, USA
Email<EMAIL_ADDRESS>
###### Abstract

A graph is said to be well-edge-dominated if all its minimal edge dominating
sets are minimum. It is known that every well-edge-dominated graph $G$ is also
equimatchable, meaning that every maximal matching in $G$ is maximum. In this
paper, we show that if $G$ is a connected, triangle-free, nonbipartite, well-
edge-dominated graph, then $G$ is one of three graphs. We also characterize
the well-edge-dominated split graphs and Cartesian products. In particular, we
show that a connected Cartesian product $G\Box H$ is well-edge-dominated,
where $G$ and $H$ have order at least $2$, if and only if $G\Box H=K_{2}\Box
K_{2}$.

Keywords: well-edge-dominated, split graph, equimatchable, Cartesian product
AMS subject classification: 05C69, 05C76, 05C75

##  1 Introduction

A set $F$ of edges in a graph $G$ is an _edge dominating set_ if every edge of
$G$ that is not in $F$ is adjacent to at least one edge in $F$. Mitchell and
Hedetniemi [14] initiated the study of edge domination by presenting a linear
algorithm that finds a smallest edge dominating set in a tree. Yannakakis and
Gavril [18] showed that it is NP hard to find an edge dominating set of
minimum size even when restricted to planar graphs or subcubic bipartite
graphs. See [3, 8, 9] for additional results on the complexity of finding a
minimum edge dominating set. The set consisting of all the vertices that are
incident with at least one edge in a minimum edge dominating set is a vertex
dominating set in a nontrivial connected graph. It follows that the (ordinary)
domination number of such a graph is at most twice the size of its smallest
edge dominating set. Senthilkumar, Venkatakrishna and Kumar [15] characterized
the trees that achieve equality of these numbers, and Baste, Fürst, Henning,
Mohr and Rautenbach [2] gave an improvement of this relationship when the
graph is regular. They conjectured that the domination number is at most the
edge domination number in every regular graph. Klostermeyer and Yeo [10]
investigated edge domination in grid graphs. See [1, 5, 17] for other problems
involving edge domination.

The graphs for which all maximal matchings have the same cardinality were
first studied independently by Lewin [12] and Meng [13] in 1974. These two
authors presented different characterizations of this class of graphs that
have come to be known as _equimatchable_. Lesk, Plummer and Pulleyblank [11]
gave a characterization of equimatchable graphs that gave rise to a polynomial
time algorithm for recognizing membership in this class of graphs. Since then
the structure of several subclasses of equimatchable graphs have been
investigated. Frendrup, Hartnell and Vestergaard [7] proved that a connected
equimatchable graph with no cycles of length less than $5$ is either a
$5$-cycle, a $7$-cycle or belongs to the family $\mathcal{C}$ that contains
$K_{2}$ and all the bipartite graphs one of whose partite sets consists of all
its support vertices. Büyükçolak, Gözüpek and S. Özkan [4] provided a complete
structural characterization of the connected, triangle-free equimatchable
graphs that are not bipartite.

If $M$ is a maximal matching in a graph $G$, then every edge not in $M$ is
adjacent to at least one edge in $M$. That is, $M$ is an edge dominating set
of $G$. A maximal matching in $G$ corresponds to a maximal independent set in
the line graph of $G$. Since line graphs are claw-free, the independent
domination number (the smallest cardinality among the independent dominating
sets) of the line graph equals its domination number. Translating this back to
the original graph, it means the size of a smallest maximal matching in $G$
and the edge domination number of $G$ coincide. Frendrup, et al. also proved
in [7] that every graph in $\mathcal{C}$ has the additional property that all
of its minimal edge dominating sets have the same cardinality. In this paper
we study graphs that have this latter property and call them _well-edge-
dominated_. In particular, we completely characterize three classes of
connected well-edge-dominated graphs.

Our main result on triangle-free, nonbipartite well-edge-dominated graphs is
the following result, which is proved in Section 4. We use the
characterization, mentioned above, by Büyükçolak, et al. [4], of the
equimatchable graphs satisfying the hypothesis of Theorem 1 and determine
which of these belong to the smaller class of well-edge-dominated graphs. The
graph $H^{*}$ is defined in Section 4.

######  Theorem 1.

If $G$ is a connected, nonbipartite, well-edge-dominated graph of girth at
least $4$, then $G\in\\{C_{5},C_{7},H^{*}\\}$.

A graph is a _split graph_ if its vertex set admits a partition into two sets,
one of which is independent and the other which induces a complete graph. We
show that a connected split graph is well-edge-dominated if and only if it is
a star, a complete graph of order at most $4$, a graph obtained from $C_{5}$
by adding two adjacent chords, or belongs to one of two families of graphs
constructed from $K_{4}$. These are defined in Section 5.

In Section 6 we finish by showing that $C_{4}$ is the only nontrivial,
connected, well-edge-dominated Cartesian product.

######  Theorem 2.

If $G$ and $H$ are two connected, nontrivial graphs, then $G\Box H$ is well-
edge-dominated if and only if $G\Box H=K_{2}\Box K_{2}$.

##  2 Preliminaries

All the graphs considered in this paper are simple and have finite order. Let
$G$ be a graph with vertex set $V(G)$ and edge set $E(G)$. We write
$n(G)=|V(G)|$. If $n(G)\geq 2$, then $G$ is _nontrivial_. For a positive
integer $k$ the set of positive integers no larger than $k$ is denoted $[k]$.
Although edges are $2$-element subsets of vertices, for simplicity we will
shorten the notation of an edge $\\{u,v\\}$ to $uv$. If $X\subseteq E(G)$,
then $G-X$ is the graph with vertex set $V(G)$ and edge set $E(G)-X$. For
graphs $G$ and $H$, the Cartesian product $G\Box H$ has vertex set
$\\{(g,h)\,:\,g\in V(G),h\in V(H)\\}$. Two vertices $(g_{1},h_{1})$ and
$(g_{2},h_{2})$ are adjacent in $G\Box H$ if either $g_{1}=g_{2}$ and
$h_{1}h_{2}\in E(H)$ or $h_{1}=h_{2}$ and $g_{1}g_{2}\in E(G)$. For $g\in
V(G)$ the _$H$ -fiber_ ${}^{g}H$ is the subgraph of $G\Box H$ induced by the
set $\\{(g,h)\,:\,h\in V(H)\\}$. Similarly, the _$G$ -fiber_ $G^{h}$ for a
given vertex $h\in V(H)$ denotes the subgraph induced by $\\{(g,h)\,:\,g\in
V(G)\\}$. Note that ${}^{g}H$ is isomorphic to $H$ and $G^{h}$ is isomorphic
to $G$.

Two distinct edges $e$ and $f$ in a graph $G$ are _adjacent_ if $e\cap
f\neq\emptyset$ and are _independent_ if $e\cap f=\emptyset$. A vertex $x$ of
$G$ is _incident_ to an edge $e$ if $x\in e$. If $X\subseteq E(G)$, then the
set of vertices _covered_ by $X$ is denoted by $S(X)$ and is defined by
$S(X)=\\{u\in V(G)\,:\,u\text{ is incident to an edge in }X\\}$. Let $f\in
E(G)$ and let $F\subseteq E(G)$. The _closed edge neighborhood_ of $f$ is the
set $N_{e}[f]$ consisting of $f$ together with all edges in $G$ that are
adjacent to $f$. The _closed edge neighborhood_ of $F$ is the set $N_{e}[F]$
defined by $N_{e}[F]=\cup_{f\in F}N_{e}[f]$. Let $f\in F$. The edge $f$ is
said to _dominate_ the set $N_{e}[f]$. An edge $g$ is called a _private edge
neighbor_ of $f$ with respect to $F$ if $g\in N_{e}[f]-N_{e}[F-\\{f\\}]$. If
$N_{e}[F]=E(G)$, then $F$ is called an _edge dominating set_ of $G$. The _edge
domination number_ of $G$, denoted by $\gamma^{\prime}(G)$, is the smallest
cardinality of an edge dominating set in $G$, and the _upper edge domination
number_ of $G$ is the largest cardinality, $\Gamma^{\prime}(G)$, of a minimal
edge dominating set. A _matching_ in $G$ is a set of independent edges. The
_matching number_ of $G$, denoted $\alpha^{\prime}(G)$, is the number of edges
in a matching of largest cardinality in $G$, while the _lower matching number_
is the number of edges, denoted by $i^{\prime}(G)$, in a smallest maximal
matching. Any maximal matching $M$ in $G$ is clearly a minimal edge dominating
set of $G$, which gives

$\gamma^{\prime}(G)\leq
i^{\prime}(G)\leq\alpha^{\prime}(G)\leq\Gamma^{\prime}(G)\,.$

A graph $G$ is called _equimatchable_ if $i^{\prime}(G)=\alpha^{\prime}(G)$
and is called _well-edge-dominated_ if
$\gamma^{\prime}(G)=\Gamma^{\prime}(G)$. Using the inequality above it is
clear that the class of well-edge-dominated graphs is a subclass of the
equimatchable graphs.

It is clear that a graph is well-edge-dominated if and only if each of its
components is well-edge-dominated. We use this fact throughout the paper
together with the following lemmas.

A very useful tool in our study of well-edge-dominated graphs is the following
lemma, which is the “edge version” of a fact used by Finbow, Hartnell and
Nowakowski in [6]. It follows from the fact that $M\cup D_{1}$ and $M\cup
D_{2}$ are both minimal edge dominating sets of $G$ for any matching $M$ and
any pair $D_{1}$ and $D_{2}$ of minimal edge dominating sets of the graph
$G-N_{e}[M]$.

######  Lemma 1.

If $G$ is a well-edge-dominated graph and $M$ is any matching in $G$, then
$G-N_{e}[M]$ is well-edge-dominated.

The next two results show that several common graph families contain only a
small number of well-edge-dominated graphs.

######  Lemma 2.

A complete graph of order $n$ is well-edge-dominated if and only if $n\leq 4$.

###### Proof.

Using the definition we see that the complete graphs of order at most $4$ are
well-edge-dominated. For the converse suppose $n\geq 5$. Label the vertices of
$K_{n}$ as $1,\dots,n$ and consider the set $D=\\{12,13,\dots,1(n-1)\\}$. We
claim that $D$ is a minimal edge dominating set. Indeed, $D-\\{1j\\}$ is not
an edge dominating set since $jn$ is not adjacent to any edge in $D-\\{1j\\}$.
Therefore, $D$ is in fact a minimal edge dominating set of cardinality $n-2$
where $n\geq 5$. On the other hand, we can choose a matching of $K_{n}$ of
cardinality $\left\lfloor\frac{n}{2}\right\rfloor$. Note that
$n-2>\frac{n}{2}$ when $n\geq 5$. Thus, $K_{n}$ is not well-edge-dominated. ∎

Any star is well-edge-dominated and we show in Theorem 4 that $K_{n,n}$ is
well-edge-dominated for any $n\geq 1$. No other complete bipartite graph is
well-edge-dominated as the following lemma shows.

######  Lemma 3.

If $2\leq r<s$, then $K_{r,s}$ is not well-edge-dominated.

###### Proof.

Assume $2\leq r<s$ and write the partite sets of $K_{r,s}$ as
$\\{x_{1},\dots,x_{r}\\}$ and $\\{y_{1},\dots,y_{s}\\}$. Note that
$\\{x_{1}y_{1},\ldots,x_{1}y_{s}\\}$ and
$\\{x_{1}y_{1},x_{2}y_{2},\ldots,x_{r}y_{r}\\}$ are two minimal edge
dominating sets of different cardinalities. Therefore, $K_{r,s}$ is not well-
edge-dominated. ∎

##  3 Randomly matchable graphs

A graph is said to be randomly matchable if every maximal matching is a
perfect matching. That is, a randomly matchable graph is an equimatchable
graph whose matching number is half its order. Sumner [16] determined all the
randomly matchable graphs.

######  Theorem 3.

([16]) A connected graph is randomly matchable if and only if it is isomorphic
to $K_{2n}$ or $K_{n,n}$ for $n\geq 1$.

Using Theorem 3 we can now show which randomly matchable graphs are well-edge-
dominated.

######  Theorem 4.

A connected graph $G$ containing a perfect matching is well-edge-dominated if
and only if $G=K_{4}$ or $G=K_{n,n}$ for $n\geq 1$.

###### Proof.

Suppose first that $G$ contains a perfect matching and is well-edge-dominated.
It follows that $G$ is equimatchable and every maximal matching is of size
$n(G)/2$. Therefore, $G$ is randomly matchable and by Theorem 3, $G=K_{2n}$ or
$G=K_{n,n}$ for $n\geq 1$. By Lemma 2, $K_{2n}$ for $n\geq 3$ is not well-
edge-dominated. It follows that $G=K_{4}$ or $G=K_{n,n}$ for $n\geq 1$.

In the other direction, suppose $G=K_{4}$ or $G=K_{n,n}$ for $n\geq 1$. One
can easily verify that $K_{4}$ is well-edge-dominated. Therefore, we shall
assume $G=K_{n,n}$ and let $A$ and $B$ be the partite sets of $G$. We show
that $G$ is well-edge-dominated. Let $D$ be an edge dominating set of $G$.
Suppose $D$ does not cover $a\in A$ and $b\in B$. Then $ab$ is not dominated
by $D$, which is a contradiction. Thus, we may assume $D$ covers $A$ which
implies $|D|\geq n$. Suppose that $|D|>n$. It follows that some vertex of $A$
is incident to two edges in $D$, say $e$ and $f$. Note that $D-\\{e\\}$ is an
edge dominating set of $G$ since $D-\\{e\\}$ covers $A$ and every edge of $G$
is incident to exactly one vertex of $A$. Thus, $|D|=n$ and $G$ is well-edge-
dominated.

∎

##  4 Triangle-free nonbipartite graphs

In this section we prove there are only three nonbipartite, triangle-free,
connected, well-edge-dominated graphs. These three graphs are the $5$-cycle,
the $7$-cycle and $H^{*}$, which is depicted in Figure 1.

Figure 1: The graph $H^{*}$

We will use the structural characterization of the class of triangle-free,
equimatchable graphs in the recent paper of Büyükçolak, Gözüpek and Özkan [4].
To describe their characterization, they defined several graph families using
the following notation. Let $H$ be a graph on $k$ vertices
$v_{1},v_{2},\dots,v_{k}$ and let $m_{1},m_{2},\dots,m_{k}$ be nonnegative
integers. Then $H(m_{1},m_{2},\dots,m_{k})$ denotes the graph obtained from
$H$ by repeatedly replacing each vertex $v_{i}$ with an independent set of
$m_{i}$ vertices, each of which has the same neighborhood as $v_{i}$. For
example, using the graph $G^{*}$ in Figure 2, we see that
$G^{*}(1,1,1,0,1,1,1,1,0,0,0)=C_{7}$ and
$G^{*}(2,0,0,0,3,0,0,0,2,3,0)=K_{4,6}$.

$u_{10}$$u_{11}$$u_{2}$$u_{3}$$u_{8}$$u_{7}$$u_{6}$$u_{5}$$u_{9}$$u_{1}$$u_{4}$
Figure 2:  The graph $G^{*}$

The following definition was made in [4].

######  Definition 1.

([4]) Let $G^{*}$ be the graph in Figure 2 and let $\mathcal{F}$ be the union
of the following six graph families.

  1. 1.

$\mathcal{F}_{11}=\\{G^{*}(1,1,1,1,1,n,n,0,0,0,0):n\geq 1\\}$

  2. 2.

$\mathcal{F}_{12}=\\{G^{*}(1,1,1,0,1,n+1,n+1,1,0,0,0):n\geq 1\\}$

  3. 3.

$\mathcal{F}_{21}=\\{G^{*}(1,1,1,n-r-s+1,1,r,n,s,0,0,0):n-1\geq r\geq
1,n-1\geq s\geq 1,n\geq r+s\\}$

  4. 4.

$\mathcal{F}_{22}=\\{G^{*}(1,1,1,n-r-s,1,r+1,n+1,s+1,0,0,0):n-1\geq r\geq
1,n-1\geq s\geq 1,n\geq r+s\\}$

  5. 5.

$\mathcal{F}_{3}=\\{G^{*}(1,1,r+1,s+1,1,0,n-s,n-r,0,0,0):n-1\geq r\geq
1,n-1\geq s\geq 1\\}$

  6. 6.

$\mathcal{F}_{4}=\\{G^{*}(r+1,n+1,s+1,1,1,0,0,0,0,0,n-r-s):n-1\geq r\geq
1,n-1\geq s\geq 1,n\geq r+s\\}$

By analyzing each of the six families of equimatchable graphs listed above, we
determine all the well-edge-dominated graphs in $\mathcal{F}$.

######  Proposition 1.

If $G\in\mathcal{F}$ is well-edge-dominated, then $G=H^{*}$.

###### Proof.

Throughout this proof when considering a graph from one of these six families
of graphs we will always assume the variables (that is, whichever of $n,r$ and
$s$ are used) satisfy the conditions in Definition 1 for that particular
family.

First, let $G=G^{*}(1,1,1,1,1,n,n,0,0,0,0)\in\mathcal{F}_{11}$. Note first
that if $n=1$, then $G=H^{*}$ depicted in Figure 1. It is straightforward to
show that $H^{*}$ is well-edge-dominated. Suppose $n\geq 3$ and let
$\\{x_{1},\dots,x_{n}\\}$ be the set of vertices that replace $u_{6}$ and let
$\\{y_{1},\dots,y_{n}\\}$ be the set of vertices that replace $u_{7}$. Note
that $K_{n-1,n}$ is a component of $G-N_{e}[\\{x_{1}u_{5},u_{3}u_{4}\\}]$. By
Lemma 3, we infer that $G$ is not well-edge-dominated. Therefore, we shall
assume $n=2$. Now, $\\{u_{1}u_{2},u_{3}u_{4}\\}$ is a matching, and $K_{2,3}$
is a component of $G-N_{e}[\\{u_{1}u_{2},u_{3}u_{4}\\}]$. By Lemma 1 and Lemma
3, it follows that $G$ is not well-edge-dominated.

Next, let $G=G^{*}(1,1,1,0,1,n+1,n+1,1,0,0,0)\in\mathcal{F}_{12}$. Let
$\\{x_{1},\dots,x_{n+1}\\}$ be the set of vertices that replace $u_{6}$ and
let $\\{y_{1},\dots,y_{n+1}\\}$ be the set of vertices that replace $u_{7}$.
Suppose first that $n\geq 2$. Note that $K_{n,n+1}$ is a component of
$G-N_{e}[\\{x_{1}u_{5},u_{3}u_{8}\\}]$. Since $K_{n,n+1}$ is not well-edge-
dominated by Lemma 3, it follows from Lemma 1 that $G$ is not well-edge-
dominated. Therefore, we shall assume $n=1$. In this case, both
$\\{x_{1}y_{1},x_{2}y_{2},u_{1}u_{5},u_{3}u_{8}\\}$ and
$\\{x_{1}y_{1},x_{2}y_{1},u_{8}y_{1},u_{1}u_{5},u_{2}u_{3}\\}$ are both
minimal edge dominating sets, and hence $G$ is not well-edge-dominated.

Next, let $G\in\mathcal{F}_{21}\cup\mathcal{F}_{22}\cup\mathcal{F}_{4}$. Note
that $n\geq 2$ for every such $G$. Suppose
$G=G^{*}(1,1,1,n-r-s+1,1,r,n,s,0,0,0)\in\mathcal{F}_{21}$. Note that
$G-N_{e}[\\{u_{2}u_{3},u_{1}u_{5}\\}]=K_{n,n+1}$. If
$G=G^{*}(1,1,1,n-r-s,1,r+1,n+1,s+1,0,0,0)\in\mathcal{F}_{22}$, then
$G-N_{e}[\\{u_{1}u_{5},u_{2}u_{3}\\}]=K_{n+1,n+2}$. If
$G=G^{*}(r+1,n+1,s+1,1,1,0,0,0,0,0,n-r-s)\in\mathcal{F}_{4}$, then
$G-N_{e}[\\{u_{4}u_{5}\\}]=K_{n+1,n+2}$. Therefore, for every
$G\in\mathcal{F}_{21}\cup\mathcal{F}_{22}\cup F_{4}$, we see by Lemmas 1 and 3
that $G$ is not well-edge-dominated.

Finally, assume $G\in\mathcal{F}_{3}$ and
$G=G^{*}(1,1,r+1,s+1,1,0,n-s,n-r,0,0,0)$. Let $\\{x_{1},\ldots,x_{s+1}\\}$ be
the set of vertices that replace $u_{4}$. The complete bipartite graph
$K_{n-s+r+1,n-r+s}$ is a component of $G-N_{e}[\\{u_{1}u_{2},u_{5}x_{1}\\}]$.
Observe that $n-s+r+1\neq n-r+s$ for otherwise $2r+1=2s$, which is not
possible. Furthermore, using the conditions $n-1\geq r\geq 1$ and $n-1\geq
s\geq 1$ we see that $n-s+r+1\geq 3$ and $n-r+s\geq 2$. It follows by Lemma 3
that $G$ is not well-edge-dominated. ∎

######  Definition 2.

([4]) Let $G^{*}$ be the graph in Figure 2 and let $\mathcal{G}$ be the union
of the following seven graph families.

  1. 1.

$\mathcal{G}_{11}=\\{G^{*}(m+1,m+1,1,0,1,1,n+1,n+1,0,0,0):n\geq 1,m\geq 1\\}$

  2. 2.

$\mathcal{G}_{12}=\\{G^{*}(m+1,m+1,1,n-r-s,1,r+1,n+1,s+1,0,0,0):m\geq
1,n-1\geq r\geq 1,n-1\geq s\geq 1,n\geq r+s\\}$

  3. 3.

$\mathcal{G}_{21}=\\{G^{*}(1,1,1,n-r-s+1,1,r,n,s,0,m,m):m\geq 1,n-1\geq r\geq
1,n-1\geq s\geq 1,n\geq r+s\\}$

  4. 4.

$\mathcal{G}_{22}=\\{G^{*}(1,1,r+1,s+1,1,0,n-s,n-r,0,m,m):m\geq 1,n-1\geq
r\geq 1,n-1\geq s\geq 1\\}$

  5. 5.

$\mathcal{G}_{23}=\\{G^{*}(r+1,n+1,s+1,1,1,m,m,0,0,0,n-r-s):m\geq 1,n-1\geq
r\geq 1,n-1\geq s\geq 1,n\geq r+s\\}$

  6. 6.

$\mathcal{G}_{31}=\\{G^{*}(m-k-\ell+1,1,1,n-r-s+1,1,r,n,s,\ell,m,k):n-1\geq
r\geq 1,n-1\geq s\geq 1,n\geq r+s,m-1\geq\ell\geq 1,m-1\geq k\geq 1,m\geq
k+\ell\\}$

  7. 7.

$\mathcal{G}_{32}=\\{G^{*}(k+1,\ell+1,1,n-r-s+1,1,r,n,s,0,m-\ell,m-k):n-1\geq
r\geq 1,n-1\geq s\geq 1,n\geq r+s,m-1\geq\ell\geq 1,m-1\geq k\geq 1,m\geq
k+\ell\\}$

As we did in Proposition 1, an analysis of all the graphs in $\mathcal{G}$
will show that no such graph is well-edge-dominated.

######  Proposition 2.

If $G\in\mathcal{G}$, then $G$ is not well-edge-dominated.

###### Proof.

Throughout this proof when considering a graph from one of these seven
families of graphs we will always assume the variables (that is, whichever of
$n,m,r,s,k$ and $\ell$ are used) satisfy the conditions in Definition 2 for
that particular family.

First, suppose $G\in\mathcal{G}_{11}\cup\mathcal{G}_{12}$. Let
$\\{x_{1},\dots,x_{m+1}\\}$ be the set of vertices that replace $u_{2}$ and
let $\\{y_{1},\dots,y_{m+1}\\}$ be the set of vertices that replace $u_{1}$.
If $G=G^{*}(m+1,m+1,1,0,1,1,n+1,n+1,0,0,0)\in\mathcal{G}_{11}$, then
$K_{n+1,n+2}$ is a component of $G-N_{e}[\\{x_{1}u_{3},y_{1}u_{5}\\}]$. If
$G=G^{*}(m+1,m+1,1,n-r-s,1,r+1,n+1,s+1,0,0,0)\in\mathcal{G}_{12}$, then
$K_{n+1,n+2}$ is a component of $G-N_{e}[\\{x_{1}u_{3},y_{1}u_{5}\\}]$. Since
$n+1\geq 2$, it follows from Lemmas 1 and 3 in both cases that $G$ is not
well-edge-dominated.

Next, suppose $G=G^{*}(1,1,1,n-r-s+1,1,r,n,s,0,m,m)\in\mathcal{G}_{21}$. Note
that this implies $n\geq 2$ and $G-N_{e}[\\{u_{1}u_{5},u_{2}u_{3}\\}]$
contains the component $K_{n,n+1}$. By Lemmas 1 and 3 we infer that $G$ is not
well-edge-dominated.

Next, suppose $G=G^{*}(1,1,r+1,s+1,1,0,n-s,n-r,0,m,m)\in\mathcal{G}_{22}$. Let
$\\{x_{1},\ldots,x_{m}\\}$ be the set of vertices that replace $u_{11}$ and
let $\\{y_{1},\ldots,y_{r+1}\\}$ be the set of vertices that replace $u_{3}$.
The complete bipartite graph $K_{n-r+s+1,n-s+r+1}$ is a component of
$G-N_{e}[\\{x_{1}u_{2},u_{1}u_{5}\\}]$. Note that $n-r+s+1\geq s+2\geq 3$ and
$n-s+r+1\geq r+2\geq 3$. If $n-r+s+1\neq n-s+r+1$, then $K_{n-r+s+1,n-s+r+1}$
is not well-edge-dominated by Lemma 3. On the other hand, if
$n-r+s+1=n-s+r+1$, then $G-N_{e}[\\{u_{2}y_{1},u_{1}u_{5}\\}]$ has a component
isomorphic to $K_{n-r+s+1,n-s+r}$, which is not well-edge-dominated. Again by
Lemmas 1 and 3 we conclude that $G$ is not well-edge-dominated.

Next, suppose $G=G^{*}(r+1,n+1,s+1,1,1,m,m,0,0,0,n-r-s)\in\mathcal{G}_{23}$.
The graph $K_{n+1,n+2}$ is a component of $G-N_{e}[u_{4}u_{5}]$. Using Lemmas
1 and 3 we infer that $G$ is not well-edge-dominated.

Next, suppose
$G=G^{*}(m-k-\ell+1,1,1,n-r-s+1,1,r,n,s,\ell,m,k)\in\mathcal{G}_{31}$. Let
$\\{x_{1},\ldots,x_{m-k-\ell+1}\\}$ be the set of vertices that replace
$u_{1}$. Note that $n\geq 2$ and that $K_{n,n+1}$ is a component of
$G-N_{e}[\\{x_{1}u_{5},u_{2}u_{3}\\}]$. By Lemmas 1 and 3, this implies that
$G$ is not well-edge-dominated.

Finally, suppose
$G=G^{*}(k+1,\ell+1,1,n-r-s+1,1,r,n,s,0,m-\ell,m-k)\in\mathcal{G}_{32}$. Note
that $n\geq 2$. Let $\\{x_{1},\dots,x_{\ell+1}\\}$ be the set of vertices that
replace $u_{2}$ and let $\\{y_{1},\dots,y_{k+1}\\}$ be the set of vertices
that replace $u_{1}$. Since $K_{n,n+1}$ is a component of
$G-N_{e}[\\{x_{1}u_{3},y_{1}u_{5}\\}]$, we conclude by Lemmas 1 and 3 that $G$
is not well-edge-dominated.

∎

Theorem 1 _If $G$ is a connected, nonbipartite, well-edge-dominated graph of
girth at least $4$, then $G\in\\{C_{5},C_{7},H^{*}\\}$. _

###### Proof.

It is straightforward to check that every graph in
$\mathcal{F}\cup\mathcal{G}$ is connected, has girth $4$ but is not bipartite.
If we consider only nonbipartite graphs, then the main result of Büyükçolak,
et. al [4, Theorem 36] states that a graph $G$ is a connected, nonbipartite,
triangle-free equimatchable graph if and only if
$G\in\mathcal{F}\cup\mathcal{G}\cup\\{C_{5},C_{7}\\}$. Applying Proposition 1
and Proposition 2 completes the proof. ∎

##  5 Split graphs

Recall that a graph is a split graph if its vertex set can be partitioned into
an independent set and a set that induces a complete graph. In this section we
prove a complete characterization of the family of split graphs that are well-
edge-dominated. We will use the following definitions. Let $\mathcal{H}_{1}$
be the family of graphs obtained by appending any finite number of leaves to a
single vertex of $K_{4}$ and let $\mathcal{H}_{2}$ be the family of graphs
obtained from $K_{4}$ by removing any edge $uv$ and appending at least one
leaf to $u$. Let $H_{3}$ be the graph of order $5$ obtained from $K_{4}-e$ by
adding a new vertex adjacent to one of the vertices of degree $2$ and one of
the vertices of degree $3$.

######  Lemma 4.

If
$G\in\\{K_{2},K_{3},K_{4},H_{3}\\}\cup\mathcal{H}_{1}\cup\mathcal{H}_{2}\cup\\{K_{1,n}:n\in\mathbb{N}\\}$,
then $G$ is well-edge-dominated.

###### Proof.

By Lemma 2, $K_{2}$, $K_{3}$, and $K_{4}$ are well-edge-dominated. It is easy
to see that every minimal edge dominating set of a nontrivial star $K_{1,n}$
consists of exactly one edge. Therefore, $K_{1,n}$ is well-edge-dominated. It
is straightforward to check that all minimal edge dominating sets of $H_{3}$
have cardinality $2$.

Next, assume $G\in\mathcal{H}_{1}$. Suppose the vertices $v_{1},v_{2},v_{3}$
and $v_{4}$ of $G$ induce a complete graph and $v_{1}$ is the support vertex.
Let $D$ be a minimal edge dominating set of $G$. First assume that $D$
contains an edge, say $v_{1}w$, where $w$ is a leaf. Note that $D$ cannot
contain more than one edge incident with $v_{1}$ since $D$ is minimal. The
only edges not dominated by $v_{1}w$ are $v_{2}v_{3},v_{2}v_{4}$ and
$v_{3}v_{4}$. Exactly one of those edges must be in $D$ in order for it to be
a minimal edge dominating set. Thus, $|D|=2$. Next, assume $D$ does not
contain an edge incident to a leaf. Then
$D\cap\\{v_{1}v_{2},v_{1}v_{3},v_{1}v_{4}\\}\neq\emptyset$. Without loss of
generality, assume $v_{1}v_{2}\in D$. The only edge of $G$ not dominated by
$v_{1}v_{2}$ is $v_{3}v_{4}$, so by minimality $|D|=2$ and $G$ is well-edge-
dominated.

Now, assume $G\in\mathcal{H}_{2}$. Label the vertices of the $K_{4}$ as
$v_{1},v_{2},v_{3}$ and $v_{4}$, remove the edge $v_{1}v_{3}$, and append
leaves to vertex $v_{1}$. Let $D$ be a minimal edge dominating set of $G$.
Using a similar argument to the one above we conclude that $G$ is well-edge-
dominated.

∎

######  Theorem 5.

A nontrivial, connected split graph $G$ is well-edge-dominated if and only if
$G\in\\{K_{2},K_{3},K_{4},H_{3}\\}\cup\mathcal{H}_{1}\cup\mathcal{H}_{2}\cup\\{K_{1,n}:n\in\mathbb{N}\\}$.

###### Proof.

By Lemma 4, each graph in
$\\{K_{2},K_{3},K_{4},H_{3}\\}\cup\mathcal{H}_{1}\cup\mathcal{H}_{2}\cup\\{K_{1,n}:n\in\mathbb{N}\\}$
is well-edge-dominated and is a split graph by definition.

For the converse let $G$ be a connected, well-edge-dominated split graph. We
let $V(G)=K\cup I$ where $I$ is an independent set,
$K=\\{x_{1},\ldots,x_{k}\\}$, and $G[K]$ is a clique. If $k=1$, then
$G=K_{1,n}$ where $n=|I|$. So we may assume $k\geq 2$. Suppose first that
$I=\emptyset$. Thus, $G=K_{k}$, and $G\in\\{K_{2},K_{3},K_{4}\\}$ by Lemma 2.
Therefore, we shall assume $I\neq\emptyset$. Assume first that $I=\\{u\\}$. If
$u$ is adjacent to every vertex in $K$, then $G$ is clique. So we shall assume
$N(u)=\\{x_{1},\ldots,x_{r}\\}$ where $r<k$. Let
$M=\\{x_{1}x_{2},x_{3}x_{4},\dots,x_{i}x_{i+1}\\}$ where $i+1=k$ if $k$ even
or $i+1=k-1$ if $k$ odd. We see that $M$ is a maximal matching in $G$ of size
$\left\lfloor\frac{k}{2}\right\rfloor$ and therefore a minimal edge dominating
set. Let $M^{\prime}=\\{x_{1}x_{2},x_{1}x_{3},\dots,x_{1}x_{k-1}\\}$. Note
that $M^{\prime}$ is a minimal edge dominating set since
$M^{\prime}-\\{x_{1}x_{j}\\}$ for $2\leq j\leq k-1$ does not dominate
$x_{j}x_{k}$. However,
$|M^{\prime}|=k-2\neq\left\lfloor\frac{k}{2}\right\rfloor=|M|$ when $k=2$ or
$k\geq 5$. If $k=3$, then $r\in\\{1,2\\}$. In this case both
$\\{ux_{1},x_{2}x_{3}\\}$ and $\\{x_{1}x_{2}\\}$ are maximal matchings in $G$,
which implies that $G$ is not well-edge-dominated. Suppose then that $k=4$. If
$r=1$, then $G\in\mathcal{H}_{1}$. If $r=2$, then $G$ is not well-edge-
dominated since $\\{ux_{1},x_{1}x_{3},x_{1}x_{4}\\}$ and
$\\{ux_{1},x_{2}x_{4}\\}$ are minimal edge dominating sets. If $r=3$, then
$\\{x_{1}x_{2},x_{3}x_{4}\\}$ and $\\{ux_{1},ux_{2},ux_{3}\\}$ are minimal
edge dominating sets so $G$ is not well-edge-dominated.

Thus, we assume for the remainder of the proof that $|I|\geq 2$. We let
$J=\\{x\in K:N(x)\cap I\neq\emptyset\\}$. Suppose first that $k=2$. If $J\neq
K$, then $G=K_{1,n}$ where $n-1=|I|$. Therefore, we shall assume $J=K$.
Without loss of generality, we may assume $x_{1}w_{1}\in E(G)$ for some
$w_{1}\in I$. If there exists $w_{2}\in I-\\{w_{1}\\}$ such that
$x_{2}w_{2}\in E(G)$, then both $\\{x_{1}x_{2}\\}$ and
$\\{x_{1}w_{1},x_{2}w_{2}\\}$ are maximal matchings in $G$ and $G$ is not
well-edge-dominated. So we may assume $N(x_{2})\cap I=\\{w_{1}\\}$. Since $G$
is connected and $|I|\geq 2$, it follows that there exists $w_{2}\in
I-\\{w_{1}\\}$ adjacent to $x_{1}$. Thus, $\\{x_{1}x_{2}\\}$ and
$\\{x_{1}w_{2},x_{2}w_{1}\\}$ are both maximal matchings, which implies that
$G$ is not well-edge-dominated. Having considered all cases for $k=2$, we now
assume $k\geq 3$.

Suppose there exist distinct vertices $x$ and $y$ in $J$ and distinct vertices
$w_{1}$ and $w_{2}$, such that $w_{1}\in N(x)\cap I$ and $w_{2}\in N(y)\cap
I$. If $k$ is even, then extend $xy$ to a maximal matching $M$ in $G[K]$. Note
that $M$ is a maximal matching in $G$. If $k$ is odd and $J\neq K$, then let
$z\in K-J$ and extend $xy$ to a maximal matching $M$ of $G[K]$ such that
$z\notin S(M)$. Again, $M$ is a maximal matching in $G$. In both of these
cases let $M^{\prime}=(M-\\{xy\\})\cup\\{xw_{1},yw_{2}\\}$. Since $M^{\prime}$
is also a maximal matching, $G$ is not equimatchable and thus also not well-
edge-dominated, which is a contradiction.

Therefore, we shall assume that $k$ is odd and $K=J$. If there exists a $z\in
K-\\{x,y\\}$ such that $N(z)\cap I\not\subseteq\\{w_{1},w_{2}\\}$, then extend
$xy$ to a maximal matching $M$ of $G[K]$ such that $z\notin S(M)$. Let
$u\in(N(z)\cap I)-\\{w_{1},w_{2}\\}$ and let $M^{\prime}=M\cup\\{uz\\}$. In
this case, both $M^{\prime}$ and
$M^{\prime\prime}=(M^{\prime}-\\{xy\\})\cup\\{xw_{1},yw_{2}\\}$ are maximal
matchings in $G$. Therefore, $G$ is not equimatchable, which is a
contradiction. Therefore, we shall assume for all $z\in K-\\{x,y\\}$,
$N(z)\cap I\subseteq\\{w_{1},w_{2}\\}$.

Suppose in addition that $I=\\{w_{1},w_{2}\\}$. Reindexing if necessary, we
may assume that $\deg_{G}(w_{1})\geq\deg_{G}(w_{2})$ and we may assume the
vertices of $K$ have been enumerated in such a way that $N(w_{1})\cap
K=\\{x_{1},\dots,x_{\ell}\\}$. If $\ell=k$, then we could instead partition
$V(G)$ as $K^{\prime}\cup I^{\prime}$ where $I^{\prime}=\\{w_{2}\\}$ and
$K^{\prime}=K\cup\\{w_{1}\\}$ and $K^{\prime}$ induces a clique in $G$. Having
already considered this case above, we instead assume $\ell\leq k-1$. If
$\ell=k-1$, then $x_{k}w_{2}\in E(G)$ since $K=J$. Let
$M^{\prime}=\\{w_{1}x_{1},\dots,w_{1}x_{k-2},w_{2}x_{k}\\}$. Note that
$M^{\prime}$ is edge dominating since all vertices other than $x_{k-1}$ are
covered by $M^{\prime}$. Moreover, $M^{\prime}$ is minimal since $w_{2}x_{k}$
is its own private neighbor and $M^{\prime}-\\{w_{1}x_{i}\\}$ does not
dominate $x_{i}x_{k-1}$ for each $i\in[k-2]$. On the other hand,
$M=\\{x_{1}x_{2},x_{3}x_{4},\dots,x_{k-2}x_{k-1},w_{2}x_{k}\\}$ is a maximal
matching and therefore is a minimal edge dominating set. Thus,
$\frac{k+1}{2}=|M|=|M^{\prime}|=k-1$, or equivalently, $k=3$. Since
$\deg_{G}(w_{1})=2\geq\deg_{G}(w_{2})$, the vertex $w_{2}$ is adjacent to at
most one of $x_{1}$ or $x_{2}$. If $\deg_{G}(w_{2})=2$, then $G=H_{3}$. On the
other hand, $G\in\mathcal{H}_{2}$ if $\deg_{G}(w_{2})=1$.

Hence, we shall assume $\ell<k-1$. Let
$M^{\prime}=\\{x_{1}x_{2},x_{1}x_{3},\dots,x_{1}x_{k-2},x_{k}w_{2}\\}$. The
only vertices that are not covered by $M^{\prime}$ are $x_{k-1}$ and $w_{1}$.
It follows that $M^{\prime}$ edge dominates $G$ since $x_{k-1}w_{1}\not\in
E(G)$. Moreover, $M^{\prime}$ is a minimal edge dominating set since
$x_{k}w_{2}$ is its own private neighbor and $M^{\prime}-\\{x_{1}x_{j}\\}$
does not dominate $x_{j}x_{k-1}$, for each $2\leq j\leq k-2$. Now, since
$M=\\{x_{1}x_{2},x_{3}x_{4},\dots,x_{k-2}x_{k-1},w_{2}x_{k}\\}$ is a maximal
matching, we get $\frac{k+1}{2}=|M|=|M^{\prime}|=k-2$, or equivalently $k=5$.
Notice that $\deg_{G}(w_{1})\leq 3$ since we have assumed $\ell<k-1$. On the
other hand, $\deg_{G}(w_{1})\geq 3$, for otherwise
$\deg_{G}(w_{2})>\deg_{G}(w_{1})$ since $K=J$. Therefore, $\deg_{G}(w_{1})=3$.
Furthermore, $x_{4}w_{2},x_{5}w_{2}\in E(G)$, and it is possible that $w_{2}$
is adjacent to exactly one of $x_{1},x_{2}$ or $x_{3}$, which does not affect
the following argument. The set
$M^{\prime}=\\{w_{1}x_{1},w_{1}x_{2},w_{1}x_{3},w_{2}x_{4}\\}$ covers all
vertices of $G$ other than $x_{5}$, so it is edge dominating. Moreover, since
any proper subset of $M^{\prime}$ does not dominate some edge of the form
$x_{i}x_{5}$, $M^{\prime}$ is a minimal edge dominating set and we have a
contradiction since $|M|=3<4=|M^{\prime}|$. Therefore, for the remainder of
the proof we shall assume $|I|>2$.

Note that we are assuming for all $z\in K-\\{x,y\\}$, $N(z)\cap
I\subseteq\\{w_{1},w_{2}\\}$, $k$ is odd, and $K=J$. Without loss of
generality, we may assume the vertices of $K$ are enumerated in such a way
that $x=x_{1}$ and $y=x_{2}$; in particular, $x_{1}w_{1}\in E(G)$ and
$x_{2}w_{2}\in E(G)$. Furthermore, we may assume $x_{2}$ has a neighbor
$w_{3}\in I-\\{w_{1},w_{2}\\}$. Assume first there exists $t\in
K-\\{x_{1},x_{2}\\}$ such that $tw_{2}\in E(G)$. Reindexing if necessary, we
may write $t=x_{k}$. Let
$M=\\{x_{1}x_{2},x_{3}x_{4},\dots,x_{k-2}x_{k-1},x_{k}w_{2}\\}$. Both $M$ and
$M^{\prime}=\\{x_{1}w_{1},x_{2}w_{3},x_{3}x_{4},x_{5}x_{6},\ldots,x_{k-2}x_{k-1},x_{k}w_{2}\\}$
are maximal matchings in $G$. However,
$|M|=\frac{k+1}{2}<3+\frac{k-3}{2}=|M^{\prime}|$, which contradicts the
assumption that $G$ is well-edge-dominated. Therefore, no such vertex $t\in K$
exists; that is, $N(x_{i})\cap I=\\{w_{1}\\}$, for all $3\leq i\leq k$.
Moreover, a similar argument (by interchanging $x_{1}$ and $x_{3}$) may be
used to show that $x_{1}w_{2}\not\in E(G)$. This implies that each vertex of
$I-\\{w_{1}\\}$ is a leaf adjacent to $x_{2}$. Now the set
$M^{\prime\prime}=\\{x_{1}x_{3},x_{1}x_{4},\dots,x_{1}x_{k},x_{2}w_{3}\\}$ is
an edge dominating set since all vertices of $K$ are covered. Since
$x_{2}w_{3}$ is its own private neighbor with respect to $M^{\prime\prime}$
and $M^{\prime\prime}-\\{x_{1}x_{j}\\}$ does not dominate $w_{1}x_{j}$, for
$3\leq j\leq k$, it follows that $M^{\prime\prime}$ is a minimal edge
dominating set of $G$. On the other hand,
$M=\\{x_{1}x_{2},x_{3}x_{4},\dots,x_{k-2}x_{k-1},x_{k}w_{1}\\}$ is a maximal
matching in $G$. Since $G$ is a well-edge-dominated graph, we infer that
$\frac{k+1}{2}=|M|=|M^{\prime\prime}|=k-1$. This implies that $k=3$, and in
this case $G\in\mathcal{H}_{2}$.

Finally, we may assume there do not exist distinct vertices $x$ and $y$ in $J$
and distinct vertices $w_{1}$ and $w_{2}$, such that $w_{1}\in N(x)\cap I$ and
$w_{2}\in N(y)\cap I$. Since $|I|\geq 2$ and $G$ is connected, it follows that
$|J|=1$. Without loss of generality we assume $J=\\{x_{1}\\}$ and every vertex
of $I$ is a leaf adjacent to $x_{1}$. Let
$M=\\{x_{1}x_{2},x_{1}x_{3},\dots,x_{1}x_{k-1}\\}$ and let
$M^{\prime}=\\{x_{1}x_{2},x_{3}x_{4},\dots,x_{j}x_{j+1}\\}$, where $j=k-1$ if
$k$ is even and $j=k-2$ if $k$ is odd. It is easy to see that both $M$ and
$M^{\prime}$ are minimal edge dominating sets, which implies that
$k-2=|M|=|M^{\prime}|=\left\lfloor\frac{k}{2}\right\rfloor$. It follows that
$k\in\\{3,4\\}$. If $k=4$, then $G\in\mathcal{H}_{1}$. On the other hand,
$k=3$ gives a contradiction since it yields a graph obtained by attaching at
least two leaves adjacent to one fixed vertex of $K_{3}$. This graph is not
well-edge-dominated as can be easily shown. This completes the proof. ∎

##  6 Cartesian products

This section is devoted to proving our characterization of well-edge-dominated
Cartesian products.

######  Lemma 5.

Let $G$ and $H$ be nontrivial, connected graphs such that at least one of $G$
or $H$ has order at least $3$. If $G$ has a perfect matching, then $G\Box H$
is not well-edge-dominated.

###### Proof.

Suppose $G$ admits a perfect matching $M$ and suppose for the sake of
contradiction that $G\Box H$ is well-edge-dominated. By “copying” $M$ to each
$G$-fiber we see that $G\Box H$ also has a perfect matching. Suppose $G\Box H$
has order $2n$. By Theorem 3, it follows that $G\Box H=K_{2n}$ or $G\Box
H=K_{n,n}$. This is a contradiction since no graph of order at least $6$ that
is complete or complete bipartite is the Cartesian product of nontrivial
factors. ∎

######  Proposition 3.

Let $G$ and $H$ be nontrivial connected graphs, neither of which has a perfect
matching. If $G\Box H$ is well-edge-dominated, then both $G$ and $H$ are well-
edge-dominated.

###### Proof.

Let $M=\\{e_{1},\dots,e_{k}\\}$ be any maximal matching in $G$ where
$e_{i}=x_{i}y_{i}$ for $i\in[k]$. Let $H$ be any connected graph with
$V(H)=\\{h_{1},\dots,h_{n}\\}$. Note that

$P=\bigcup_{j=1}^{n}\bigcup_{i=1}^{k}\\{(x_{i},h_{j})(y_{i},h_{j})\\}$

is a matching in $G\Box H$. By Lemma 1, $G\Box H-N_{e}[P]$ is well-edge-
dominated since $G\Box H$ is well-edge-dominated. Let $I=V(G)-S(M)$. Since $M$
is a maximal matching that is not a perfect matching, the set $I$ is nonempty
and independent. Therefore, the nontrivial components of $G\Box H-N_{e}[P]$
are isomorphic to $H$. This implies $H$ is well-edge-dominated. Similarly, $G$
is well-edge-dominated. ∎

######  Lemma 6.

If $G$ and $H$ are connected, nontrivial graphs neither of which has a perfect
matching, then $G\Box H$ is not well-edge-dominated.

###### Proof.

Suppose to the contrary that there exist connected, nontrivial graphs $G$ and
$H$, neither of which has a perfect matching, such that $G\Box H$ is well-
edge-dominated. Thus, we may assume $n(G)\geq 3$ and $n(H)\geq 3$. By
Proposition 3, both $G$ and $H$ are well-edge-dominated. Let $r$ be the
matching number of $G$ and $s$ be the matching number of $H$. Choose any
maximal matching $M_{1}=\\{e_{1},\dots,e_{s}\\}$ in $H$ and write
$e_{i}=x_{i}y_{i}$ for $i\in[s]$. Let $I_{H}=V(H)-S(M_{1})$. Choose any
maximal matching $M_{G}=\\{f_{1},\dots,f_{r}\\}$ in $G$ and write
$f_{i}=u_{i}v_{i}$ for $i\in[r]$. Let $I_{G}=V(G)-S(M_{G})$. Let

$P_{1}=\bigcup_{g\in V(G)}\bigcup_{i=1}^{s}\\{(g,x_{i})(g,y_{i})\\}$

and

$P_{2}=\bigcup_{h\in I_{H}}\bigcup_{i=1}^{r}\\{(u_{i},h)(v_{i},h)\\}.$

Note that $P_{1}\cup P_{2}$ is a maximal matching in $G\Box H$ since the only
vertices in $G\Box H$ that are not covered by $P_{1}\cup P_{2}$ are in
$I_{G}\times I_{H}$, which is an independent set in $G\Box H$. Also,

$|P_{1}\cup P_{2}|=sn(G)+(n(H)-2s)r.$

Next, choose a maximal matching $M_{2}=\\{a_{1},\dots,a_{s}\\}$ in $H$ such
that $S(M_{1})\neq S(M_{2})$ and write $a_{i}=w_{i}z_{i}$ for $i\in[s]$. Let
$L=V(H)-(S(M_{1})\cup S(M_{2}))$, $L^{\prime}=S(M_{1})-S(M_{2})$, and
$L^{\prime\prime}=S(M_{2})-S(M_{1})$. Choose any maximal independent set $J$
in $G$ and let $N_{1}=\\{b_{1}c_{1},\dots,b_{t}c_{t}\\}$ be a minimal edge
dominating set of $G-J$.

Let

$Q_{1}=\bigcup_{g\in V(G)-J}\bigcup_{i=1}^{s}\\{(g,x_{i})(g,y_{i})\\},$

$Q_{2}=\bigcup_{g\in J}\bigcup_{i=1}^{s}\\{(g,w_{i})(g,z_{i})\\},$
$Q_{3}=\bigcup_{h\in L}\bigcup_{i=1}^{r}\\{(u_{i},h)(v_{i},h)\\},$

and

$Q_{4}=\bigcup_{h\in
L^{\prime\prime}}\bigcup_{i=1}^{t}(\\{(b_{i},h)(c_{i},h)\\}.$

We claim that $Q=\cup_{i=1}^{4}Q_{i}$ is a minimal edge dominating set of
$G\Box H$. If $g\in J$, then $Q_{2}\cap E(^{g}H)$ is an edge dominating set of
${}^{g}H$. If $g\in V(G)-J$, then $Q_{1}\cap E(^{g}H)$ is an edge dominating
set of ${}^{g}H$. Thus, for every $h_{1}h_{2}\in E(H)$ and every $g\in V(G)$,
the set $Q_{1}\cup Q_{2}$ dominates the edge $(g,h_{1})(g,h_{2})$. Note that
we can write $V(H)$ as a weak partition

$V(H)=L\cup L^{\prime}\cup L^{\prime\prime}\cup(S(M_{1})\cap S(M_{2})).$

If $h\in L^{\prime}$ and $g_{1}g_{2}\in E(G)$, then $Q_{1}$ dominates the edge
$(g_{1},h)(g_{2},h)$ since $J\times L^{\prime}$ is independent and every
vertex of $(V(G)-J)\times L^{\prime}$ is covered by $Q_{1}$. If $h\in
S(M_{1})\cap S(M_{2})$ and $g\in V(G)$, then $(g,h)$ is covered by $Q_{1}\cup
Q_{2}$. If $h\in L^{\prime\prime}$ and $g\in J$, then $(g,h)$ is covered by
$Q_{2}$. On the other hand, if $h\in L^{\prime\prime}$ and
$(g_{1},h)(g_{2},h)$ is an edge of $G\Box H$ where neither $g_{1}$ nor $g_{2}$
is in $J$, then $(g_{1},h)(g_{2},h)$ is dominated by $Q_{4}$. Finally,
$Q_{3}\cap E(G^{h})$ is an edge dominating set of $G^{h}$, for any $h\in L$
since $M_{G}$ is a maximal matching in $G$. Therefore, $Q$ is an edge
dominating set of $G\Box H$.

Next, we show $Q$ is in fact a minimal edge dominating set. Let $e$ be an
arbitrary edge in $Q$. If $e\in Q_{1}\cup Q_{2}\cup Q_{3}$, then $Q-\\{e\\}$
does not dominate $e$. If $e\in Q_{4}$, say $e=(g_{1},h)(g_{2},h)$ where $h\in
L^{\prime\prime}$, then some edge in the subgraph induced by
$(V(G)-J)\times\\{h\\}$ is not dominated by $Q-\\{e\\}$ since $N_{1}$ is a
minimal edge dominating set of $G-J$. Thus, $Q$ is a minimal edge dominating
set of $G\Box H$.

Since $G\Box H$ is well-edge-dominated, $|P_{1}\cup P_{2}|=|Q|$ where

$\displaystyle|Q|$ $\displaystyle=$
$\displaystyle|Q_{1}|+|Q_{2}|+|Q_{3}|+|Q_{4}|$ $\displaystyle=$
$\displaystyle(n(G)-|J|)s+|J|s+|L|r+|L^{\prime\prime}|t$ $\displaystyle=$
$\displaystyle n(G)s+(n(H)-|S(M_{1})|-|S(M_{2})|+|S(M_{1})\cap S(M_{2})|)r$
$\displaystyle+(2s-|S(M_{1})\cap S(M_{2})|)t$ $\displaystyle=$ $\displaystyle
n(G)s+(n(H)-4s+|S(M_{1})\cap S(M_{2})|)r+(2s-|S(M_{1})\cap S(M_{2})|)t.$

In particular, this means

$n(G)s+(n(H)-2s)r=n(G)s+(n(H)-4s+|S(M_{1})\cap S(M_{2})|)r+(2s-|S(M_{1})\cap
S(M_{2})|)t$

or equivalently

$(|S(M_{1})\cap S(M_{2})|-2s)(r-t)=0.$

Note that $|S(M_{1})\cap S(M_{2})|\neq 2s$ since $S(M_{1})\neq S(M_{2})$.
Thus, $r=t$ and every minimal edge dominating set of $G-J$ has cardinality $r$
since $N_{1}$ was chosen arbitrarily. It follows that $G-J$ is well-edge-
dominated and $\gamma^{\prime}(G-J)=\gamma^{\prime}(G)$. Furthermore, we claim
$G-J$ contains a perfect matching. Suppose to the contrary that $G-J$ does not
admit a perfect matching. Let $A$ be any maximal matching of $G-J$ and let $x$
be a vertex of $G-J$ that is not covered by $A$. Since $J$ is a maximal
independent set of $G$, there exists a vertex $y\in J$ where $xy\in E(G)$.
However, $A\cup\\{xy\\}$ is a matching in $G$ of cardinality $r+1$, which is a
contradiction. Hence, $A$ is a perfect matching of $G-J$, and so $G-J$ is a
well-edge-dominated, randomly matchable graph. By Theorem 4, $G-J=K_{4}$ or
$G-J=K_{n,n}$ for some $n\geq 1$.

Notice that since $J$ is assumed to be a maximal independent set, each vertex
of $G-J$ is adjacent to a vertex in $J$. Let $e=wz$ be an arbitrary edge in
$A$. If there exists a pair $u,v$ of distinct vertices in $J$ such that $u\in
N(w)\cap J$ and $v\in N(z)\cap J$, then $(A-\\{wz\\})\cup\\{uw,vz\\}$ is a
matching in $G$ of cardinality $r+1$, which is a contradiction. It follows
that $|N(w)\cap J|=1=|N(z)\cap J|$, and in fact $N(w)\cap J=N(z)\cap J$. Since
every edge of $G-J$ can be extended to a perfect matching of $G-J$ and since
$G-J$ is connected, it follows that $|J|=1$ and therefore $G$ is a complete
graph. This implies that $G=K_{5}$, which is not well-edge-dominated. This
contradiction completes the proof. ∎

Theorem 2 is restated here for ease of reference. Theorem 2 _If $G$ and $H$
are two connected, nontrivial graphs, then $G\Box H$ is well-edge-dominated if
and only if $G\Box H=K_{2}\Box K_{2}$. _

###### Proof.

The Cartesian product $K_{2}\Box K_{2}$ is well-edge-dominated. Conversely,
suppose $G$ and $H$ are connected and nontrivial such that $G\Box H$ is well-
edge-dominated. By Lemma 6, at least one of $G$ or $H$ has a perfect matching,
and then by Lemma 5 it follows that $G\Box H=K_{2}\Box K_{2}$. ∎

##  7 Open Questions

In their study of connected, equimatchable graphs of girth at least $5$,
Frendrup, Hartnell and Vestergaard [7] characterized the connected, well-edge-
dominated graphs of girth at least $5$. In particular, they proved the
following result.

######  Theorem 6.

([7]) If $G$ is a connected graph with $g(G)\geq 5$, then $G$ is well-edge-
dominated if and only if $G\in\\{K_{2},C_{5},C_{7}\\}$ or $G$ is bipartite
with partite sets $V_{1}$ and $V_{2}$ such that $V_{1}$ is the set of all
support vertices of $G$.

In Theorem 1 of this paper we showed that only one additional graph, namely
$H^{*}$, is added to the list of connected, well-edge-dominated graphs if the
girth restriction is lowered to $4$ but we now require that the graph be
nonbipartite.

A natural problem now presents itself.

######  Problem 1.

Find a structural characterization of the class of connected, bipartite graphs
of girth $4$ that are well-edge-dominated.

By Theorem 4 this class contains $K_{n,n}$, for any $n\geq 2$ and by Theorem 2
it does not contain any nontrivial Cartesian products other than $K_{2}\Box
K_{2}$.

For graphs that contain a triangle, we have characterized the connected, split
graphs that are well-edge-dominated in Theorem 5. Determining the structure
for arbitrary well-edge-dominated graphs of girth $3$ is an interesting
problem.

######  Problem 2.

Find a structural characterization of the class of connected graphs of girth
$3$ that are well-edge-dominated.

## References

  * [1] S. Arumugam and S. Velammal. Edge domination in graphs. Taiwanese J. Math., 2(2): 173–179 (1998)
  * [2] J. Baste, M. Fürst, M. A. Henning, E. Mohr and D. Rautenbach. Domination versus edge domination. Discrete Appl. Math., 285: 343–349 (2020)
  * [3] A. Berger and O. Parekh. Linear time algorithms for generalized edge dominating set problems. Algorithmica, 50(2): 244–254 (2008)
  * [4] Y. Büyükçolak, D. Gözüpek and S. Özkan. Triangle-free equimatchable graphs. J. Graph Theory, 1-22, to appear.
  * [5] A. Chaemchan. The edge domination number of connected graphs. Australas. J. Combin., 48: 185–189 (2010)
  * [6] A. Finbow, B. Hartnell and R. Nowakowski. Well-dominated graphs: a collection of well-covered ones. Ars Comb., 25A: 5–10 (1988)
  * [7] A. Frendrup, B. Hartnell and P. L. Vestergaard. A note on equimatchable graphs. Australas. J. Combin., 46: 185–190 (2010)
  * [8] J. D. Horton and K. Kilakos. Minimum edge dominating sets. SIAM J. Discrete Math., 6(3): 375–387 (1993)
  * [9] S. F. Hwang and G. J. Chang. The edge domination problem. Discuss. Math. Graph Theory, 15(1): 51–57 (1995)
  * [10] W. F. Klostermeyer and A. Yeo. Edge domination in grids. J. Combin. Math. Combin. Comput., 95: 99–117 (2015)
  * [11] M. Lesk, M. D. Plummer and W. R. Pulleyblank. Equi-matchable graphs. Graph theory and combinatorics, Academic Press, London, 239–254 (1984)
  * [12] M. Lewin. Matching-perfect and cover-perfect graphs. Israel J. Math., 18: 345–347 (1974)
  * [13] D. H-C. Meng. Matching and coverings for graphs. Ph. D. Thesis, Michigan State University, East Lansing, MI. (1974)
  * [14] S. Mitchell and S. Hedetniemi. Edge domination in trees. Congr. Numer., 19: 489–509 (1977)
  * [15] B. Senthilkumar, Y. B. Venkatakrishnan and H. N. Kumar. Domination and edge domination in trees. Ural Math. J., 6: 147–152 (2020)
  * [16] D. P. Sumner. Randomly matchable graphs. J. Graph Theory, 3(2): 183–186 (1979)
  * [17] J. Topp. Graphs with unique minimum edge dominating sets and graphs with unique maximum independent sets of vertices. Discrete Math., 121: 199–210 (1993)
  * [18] M. Yannakakis and F. Gavril. Edge dominating sets in graphs. SIAM J. Appl. Math., 38(3): 364–372 (1980)


# Deciding minimal distinguishing DFAs is NP-complete

Jan Martens
<EMAIL_ADDRESS>
###### Abstract

In this paper, we present a proof of the NP-completeness of computing the
smallest Deterministic Finite Automaton (DFA) that distinguishes two given
regular languages as DFAs. A distinguishing DFA is an automaton that
recognizes a language which is a subset of exactly one of the given languages.
We establish the NP-hardness of this decision problem by providing a reduction
from the Boolean Satisfiability Problem (SAT) to deciding the existence of a
distinguishing automaton of a specific size.

##  1 Introduction

We consider the problem of automatically explaining the inequivalence of
Deterministic Finite Automata (DFAs). In particular, we are interested in
short witnesses for the inequivalence. A straightforward approach to explain
the inequivalence of two DFAs would be to provide a distinguishing word, i.e.
a word that is accepted by one of the automata but not the other.

This method of finding minimal distinguishing words is well understood and
decidable in polynomial time [6]. An efficient implementation is given in [8]
that has the same runtime complexity as the best known algorithm that decides
language equivalence, known as Hopcroft’s minimization [3].

In this work we are motivated by smaller witnesses of inequivalence in the
form of regular languages. These languages might contain invariants that
provide a shorter and more intuitive explanation. For example, consider the
DFAs $\mathcal{A}$ and $\mathcal{B}$ shown in Figure 1. The shortest
distinguishing word for these DFAs is $a^{7}$. Indeed, we confirm
$a^{7}\in\mathcal{L}(\mathcal{A})$ but $a^{7}\not\in\mathcal{L}(\mathcal{B})$.
A different explanation for the inequivalence of $\mathcal{A}$ and
$\mathcal{B}$ could be: every odd length sequence of $a$’s is accepted by
$\mathcal{A}$ and not by $\mathcal{B}$.

We call a DFA a distinguishing automaton for two DFAs if the language
recognized is a subset of exactly one of the two DFAs. In the example from
Figure 1, we see that our distinguishing witness with invariant is equivalent
to a distinguishing automaton with only two states, i.e. the DFA $A_{odd}$
such that $\mathcal{L}(A_{odd})=\\{a^{2i+1}\mid i\in\mathbb{N}\\}$. An
automaton recognizing only the minimal distinguishing word $a^{7}$ would
contain at least eight states.

In the setting of model based development it can be key to understand the
differences between state based systems. This led us to study the synthesis of
distinguishing DFAs, and leads naturally to following decision problem.

$k$-DFA-DIST: Let $A_{1}$ and $A_{2}$ be DFAs such that
$\mathcal{L}(A_{1})\neq\mathcal{L}(A_{2})$, and $k\in\mathbb{N}$ a number.
Decide if there is a DFA $A_{dist}$ with at most $k$ states such that:

$\mathcal{L}(A_{dist})\subseteq\mathcal{L}(A_{1})\iff\mathcal{L}(A_{dist})\not\subseteq\mathcal{L}(A_{2}).$

$q_{0}$$q_{1}$$q_{2}$$q_{3}$$a$$a$$a$$a$$p_{0}$$p_{1}$$p_{2}$$p_{3}$$p_{4}$$a$$a$$a$$a$$a$
Figure 1: The DFA $\mathcal{A}$ on the left and the DFA $\mathcal{B}$ on the
right side.

The contribution of this work is that we prove the intractability of $k$-DFA-
DIST.

######  Theorem 1.

Deciding $k$-DFA-DIST is NP-complete.

The reduction from CNF-SAT that proves the NP-completeness is new to our
knowledge. We believe this reduction of CNF-SAT formulas to regular languages
is an intuitive method of showing DFA problems NP-complete.

There are some decision problems on DFAs that show some similarities, but are
different from the work here. For instance the early work of Gold [2] and
Pfleeger [7] in which it is shown that learning minimal DFAs from (partial)
observations is NP-complete. In the line of this work by Gold, so-called
separating languages are widely studied in the literature [1, 5]. Here the
separating problem is, given languages $L_{1}$ and $L_{2}$, to find a
separating language $L_{sep}$ such that $L_{sep}\subseteq L_{1}$ and
$L_{sep}\cap L_{2}=\emptyset$. Although this resembles our distinguishing
problem, a direct relation is not trivial.

Another influential work is due to Kozen [4]. This work includes a proof of
NP-hardness of deciding whether the intersection of a finite number of DFAs is
empty.

##  2 Notation & Background

For two natural numbers $i,j\in\mathbb{N}$ we write $[i,j]={i,i+1,\dots,j}$ as
the closed interval from $i$ to $j$. Given a finite alphabet $\Sigma$, a
sequence of elements of $\Sigma$ is called a word. We define $\Sigma^{i}$ as
the set of all words over $\Sigma$ of length $i$, and
$\Sigma^{*}=\bigcup_{i\in\mathbb{N}}\Sigma^{i}$ for all words over $\Sigma$.
Given words $u,v\in\Sigma^{*}$, we write $u\cdot v$ and $uv$ for word
concatenation. Additionally, given a number $i\in\mathbb{N}$ and a word
$u\in\Sigma^{*}$ we write $u^{i}$ for the concatenation of $i$ times the word
$u$.

######  Definition 2.

A Deterministic Finite Automata (DFA) $A=(Q,\Sigma,\delta,q_{0},F)$ is a five-
tuple consisting of:

  * –

$Q$ a finite set of states,

  * –

$\Sigma$ a finite set of symbols called the alphabet,

  * –

$\delta:Q\times\Sigma\rightarrow Q$ the transition function,

  * –

$q_{0}\in Q$ the initial state, and

  * –

$F\subseteq Q$ the set of final states.

The transition function $\delta$ extends naturally to a transition function
for words $\delta^{*}:Q\times\Sigma^{*}\rightarrow Q$. This is done
inductively as follows:

$\displaystyle\delta^{*}(q,\varepsilon)$ $\displaystyle=q$
$\displaystyle\delta^{*}(q,aw)$ $\displaystyle=\delta^{*}(\delta(q,a),w).$

The language recognized by a DFA $A=(Q,\Sigma,\delta,q_{0},F)$, is denoted by
$\mathcal{L}(A)$, and consists of all words $w\in\Sigma^{*}$ such that
$\delta^{*}(q_{0},w)\in F$.

The Myhill-Nerode theorem is a useful tool to establish the number of states
necessary to recognize a language. It is based on the equivalence relation
relating words that have the exact same accepting extensions.

######  Definition 3.

Let $x,y\in\Sigma^{*}$ be words and $L\subseteq\Sigma^{*}$ a language, then
$x\equiv_{L}y$ if and only if for all $z\in\Sigma^{*}$ it holds that $xz\in
L\iff yz\in L$.

######  Theorem 4.

(Myhill-Nerode [3, Theorem 3.9]) Let $L\subseteq\Sigma^{*}$ be a language,
then $L$ is regular if and only if the relation $\equiv_{L}$ has a finite
number of equivalence classes.

A more specific corollary of the theorem relates the number of equivalence
classes of $\equiv_{L}$ to the smallest number of states a DFA needs in order
to recognize $L$.

######  Corollary 5.

Let $L$ be a regular language over an alphabet $\Sigma$, then the smallest DFA
$A$ that recognizes $L$ has $k$ states where $k$ is the number of equivalence
classes of the relation $\equiv_{L}$.

##  3 Reduction

Before we introduce the reduction we define some notation in which we encode
truth values of propositions. In the reduction we represent truth assignments
as words over the Boolean alphabet $\mathbb{B}=\\{\mathtt{0},\mathtt{1}\\}$.
Given a set of propositional variables
$\mathit{Prop}=\\{p_{1},\dots,p_{k}\\}$, a truth assignment
$\rho:\mathit{Prop}\to\mathbb{B}$ is represented by the word $a_{1}\dots
a_{k}\in\mathbb{B}^{k}$, where $a_{i}=\rho(p_{i})$ for every $i\in[1,k]$. The
set $\mathcal{X}=\mathbb{B}^{k}$ defines all words that represent truth
assignments.

Now we are ready to introduce our reduction from CNF-SAT in order to prove
Theorem 1. Let $\phi=C_{1}\wedge\dots\wedge C_{n}$ be a CNF formula over the
propositional variables $\mathit{Prop}=\\{p_{1},\dots,p_{k}\\}$, we define two
regular languages over the alphabet $\Sigma=\mathbb{B}\cup\\{\sharp\\}$. The
first language $L^{-}_{\phi}\subseteq\Sigma^{*}$ is the finite set of at most
$n$ concatenated truth assignments separated by a $\sharp$, i.e.

$L^{-}_{\phi}=\\{w_{1}\sharp\dots w_{j}\sharp\mid j\in[1,k]\text{ and
}w_{1},\dots,w_{j}\in\mathcal{X}\\}.$

The second language $L^{+}_{\phi}\subseteq\Sigma^{*}$ is a superset of
$L^{-}_{\phi}$. In addition to all the word of $L^{-}_{\phi}$, the language
$L^{+}_{\phi}$ contains all words that have as prefix $n$ truth assignments
$w_{1},\dots,w_{n}\in\mathcal{X}$ that consecutively satisfy all clauses
$C_{1},\dots,C_{n}$, more precisely that is,

$\displaystyle L^{+}_{\phi}=L^{-}_{\phi}\cup\\{w_{1}\sharp\cdots w_{n}\sharp
w\mid$ $\displaystyle w\in\Sigma^{*}\text{,}w_{i}\in\mathcal{X}\text{ and
$w_{i}$ satisfies }C_{i}\text{ for all }i\in[1,n]\\}.$

The languages $L^{-}_{\phi}$ and $L^{+}_{\phi}$ are regular, and hence there
are automata that recognize these languages. In particular there are automata
recognizing these languages that are polynomial in size. One way of observing
this fact is by inspecting the number of Myhill-Nerode equivalence classes of
$L^{+}_{\phi}$ and $L^{-}_{\phi}$.

######  Lemma 6.

Given a CNF formula $\phi$, the languages $L_{\phi}^{+}$ and $L_{\phi}^{-}$
are recognizable by an automaton that is polynomial in the size of $\phi$.

The next lemma proves the key fact of our reduction. A truth assignment that
satisfies a CNF formula $\phi$ as recurring pattern forms a small
distinguishing automaton. Inversely a distinguishing automaton smaller than a
certain size necessarily implies the existence of a satisfying truth
assignment for $\phi$.

######  Lemma 7.

Let $\phi=C_{1}\wedge\dots\wedge C_{n}$ be a CNF formula over $k$
propositional letters $\mathit{Prop}=\\{p_{1},\dots,p_{k}\\}$. Then $\phi$ is
satisfiable if and only if there is a DFA $A_{dist}$ with at most $k+2$ states
such that $\mathcal{L}(A_{dist})\subseteq L^{+}_{\phi}$ and
$\mathcal{L}(A_{dist})\not\subseteq L^{-}_{\phi}$.

###### Proof.

We prove both directions of the implication separately.

($\Rightarrow$)

Assume $\phi$ is satisfiable, then there is a satisfying truth assignment
$\rho$ that is mapped to the word
$w_{\rho}=\rho(p_{1})\dots\rho(p_{k})\in\mathcal{X}$. We define the language
$L_{dist}=\\{(w_{\rho}\cdot\sharp)^{i}\mid i\in\mathbb{N}\\}$, and show that
$L_{dist}$ witnesses this implication.

First we show that $L_{dist}\subseteq L^{+}_{\phi}$. Assume $i\in\mathbb{N}$,
if $i\leqslant n$ then by definition $(w_{\rho}\cdot\sharp)^{i}\in
L_{\phi}^{-}$ and hence also in $(w_{\rho}\cdot\sharp)^{i}\in L_{\phi}^{+}$.
If $i>n$, since $\rho$ is a satisfying assignment, it holds for any
$w^{\prime}\in\Sigma^{*}$ that $(w_{\rho}\cdot\sharp)^{n}w^{\prime}\in
L^{+}_{\phi}$, and thus also
$(w_{\rho}\cdot\sharp)^{n}(w_{\rho}\cdot\sharp)^{i-n}\in L^{+}_{\phi}$. By
covering both cases this means $L_{dist}\subseteq L^{+}_{\phi}$.

Next, we observe that $(w_{\rho}\cdot\sharp)^{n+1}\not\in L^{-}_{\phi}$, and
thus $L_{dist}\not\subseteq L^{-}_{\phi}$. Hence, since $L_{dist}\subseteq
L^{+}_{\phi}$ any DFA that recognizes $L_{dist}$ is a distinguishing
automaton.

The minimal DFA $A_{dist}$ such that $\mathcal{L}(A_{dist})=L_{dist}$ contains
one loop with $k+1$ states containing all positions of the word
$w_{\rho}\cdot\sharp$ and a sink state to reject all other words. Thus, if
$\phi$ is satisfiable we can construct $A_{dist}$ with $k+2$ states that
distinguishes $L^{+}_{\phi}$ and $L^{-}_{\phi}$, which was to be showed.

($\Leftarrow$)

We assume $A_{dist}$ is a DFA with at most $k+2$ states such that for the
language accepted $\hat{L}=\mathcal{L}(A_{dist})$ it holds that
$\hat{L}\subseteq L_{\phi}^{+}$ and $\hat{L}\not\subseteq L_{\phi}^{-}$. We
show that this means $\phi$ is satisfiable.

Since $\hat{L}\setminus L_{\phi}^{-}\neq\emptyset$ and $\hat{L}\subseteq
L_{\phi}^{+}$ there is a word $w\in L^{+}_{\phi}\setminus L^{-}_{\phi}$
accepted by $A_{dist}$. By definition $w$ is of shape $w=w_{1}\sharp\dots
w_{n}\sharp w^{\prime}$ where $w^{\prime}\in\Sigma^{+}$ and
$w_{1},\dots,w_{n}\in\mathcal{X}$ and for every $i\in[1,k]$ the word $w_{i}$
represents a satisfying truth assignment for the clause $C_{i}$. Next we show
that $w_{1}$ represents a satisfying truth assignment for $\phi$ by counting
the number of equivalence classes of $\equiv_{\hat{L}}$ for the prefixes of
$w_{1}\cdot\sharp$, together with the postfix $w_{post}=w_{2}\sharp\dots
w_{n}\sharp w^{\prime}$ that witnesses an accepting postfix for $w_{1}\sharp$.

We define the set $U$ as the set containing all prefixes of $w_{1}=a_{1}\dots
a_{k}$, i.e.

$U=\\{\varepsilon\\}\cup\\{a_{1}\dots a_{j}\mid j\in[1,k]\\}.$

If $v,u\in U$ and $v\neq u$ then $v\not\equiv_{\hat{L}}u$, since there is a
$\sigma\in\Sigma^{*}$ such that $v\sigma=w$ and $w\in\hat{L}$ and
$u\sigma\not\in\hat{L}$. This means there are $|U|=k+1$ distinct classes of
${\equiv_{\hat{L}}}$. Lastly, since $\sharp z\not\in\hat{L}$ for any
$z\in\Sigma^{*}$ we can also conclude that $\sharp\not\equiv_{\hat{L}}u$ for
all $u\in U$.

Since we assumed that $A_{dist}$ has at most $k+2$ states, by Corollary 5
there are at most $k+2$ equivalence classes of ${\equiv_{\hat{L}}}$. Since
trivially $w_{1}\sharp\not\equiv_{\hat{L}}\sharp$, by the pigeonhole principle
there is a prefix $u\in U$ such that at $w_{1}\sharp\equiv_{\hat{L}}u$.

It can not be the case that $u=a_{1}\dots a_{i}$ for some $i\in[1,k]$, since

$\displaystyle a_{1}\dots a_{i}$ $\displaystyle\cdot a_{i+1}\dots a_{k}\sharp
w_{post}\in\hat{L}$ $\displaystyle w_{1}\sharp$ $\displaystyle\cdot
a_{i+1}\dots a_{k}\sharp w_{post}\not\in\hat{L}.$

By eliminating all alternatives we conclude $u=\varepsilon$. Using this
equivalence and since $\varepsilon\cdot w_{1}\sharp w_{post}\in L_{dist}$ we
derive that $w_{1}\sharp\cdot w_{1}\sharp w_{post}\in L_{dist}$. In
particular, this means that $(w_{1}\sharp)^{n}\cdot w_{post}\in L_{dist}$. By
definition of $L_{\phi}^{+}$ this means that the truth assignment $w_{1}$
satisfies all clauses $C_{1},\dots,C_{n}$ and hence it is a satisfying
assignment for $\phi$. This witnesses that $\phi$ is a satisfying formula. ∎

This lemma allows us to prove Theorem 1.

###### Proof of Theorem 1.

Membership of NP follows naturally. For two DFAs $A_{1}$ and $A_{2}$ we can,
in polynomial time, check if $\mathcal{L}(A_{1})\subseteq\mathcal{L}(A_{2})$.
This can be done by computing the emptiness of
$\mathcal{L}(A_{1})\cap\overline{\mathcal{L}(A_{2})}$. Moreover, either
$A_{1}$ or $A_{2}$ itself necessarily already is a distinguishing automaton,
so the minimal distinguishing DFA is definitely polynomial in size.

NP-hardness is a direct consequence of Lemma 7 and of the fact that
$L_{\phi}^{-}\subseteq L_{\phi}^{+}$, so the language of any distinguishing
automaton is a subset of $L_{\phi}^{+}$ and not vice-versa. ∎

### Acknowledgements:

The author thanks Tim Willemse for raising the question of distinguishing
transition-systems with invariants. Thanks also to Jan Friso Groote and Anna
Stramaglia for providing helpful suggestions on this document.

## References

  * [1] Erik D Demaine, Sarah Eisenstat, Jeffrey Shallit, and David A Wilson.  Remarks on separating words.  In Descriptional Complexity of Formal Systems: 13th International Workshop, DCFS 2011, Gießen/Limburg, Germany, July 25-27, 2011. Proceedings 13, pages 147–157. Springer, 2011.
  * [2] E Mark Gold.  Complexity of automaton identification from given data.  Information and Control, 37(3):302–320, 1978.
  * [3] John Hopcroft.  An n log n algorithm for minimizing states in a finite automaton.  In Zvi Kohavi and Azaria Paz, editors, Theory of Machines and Computations, pages 189–196. Academic Press, 1971.
  * [4] Dexter Kozen.  Lower bounds for natural proof systems.  In 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), pages 254–266. IEEE, 1977.
  * [5] Orna Kupferman, Nir Lavee, and Salomon Sickert.  Certifying dfa bounds for recognition and separation.  Innovations in Systems and Software Engineering, 18(3):405–416, 2022.
  * [6] Tyler Moore.  Gedanken-experiments on sequential machines.  In C. E. Shannon and J. McCarthy, editors, Automata Studies, Annals of Mathematical Studies, no. 34. Citeseer, 1956.
  * [7] Charles P Pfleeger.  State reduction in incompletely specified finite-state machines.  IEEE Transactions on Computers, 100(12):1099–1102, 1973.
  * [8] Rick Smetsers, Joshua Moerman, and David N Jansen.  Minimal separating sequences for all pairs of states.  In Adrian-Horia Dediu, Jan Janoušek, Carlos Martín-Vide, and Bianca Truthe, editors, Language and Automata Theory and Applications (LATA 2016), pages 181–193. Springer, 2016.


11institutetext: TNO, 2597 AK The Hague, The Netherlands

# Open-World Visual Reasoning by a Neuro-Symbolic Program of Zero-Shot
Symbols††thanks: Supported by TNO ERP APPL.AI program.

G.J. Burghouts  F. Hillerström  E. Walraven  M. van Bekkum  F. Ruis  J. Sijs
J. van Mil  J. Dijk  W. Meijer

###### Abstract

We consider the problem of finding spatial configurations of multiple objects
in images, e.g., a mobile inspection robot is tasked to localize abandoned
tools on the floor. We define the spatial configuration of objects by first-
order logic in terms of relations and attributes. A neuro-symbolic program
matches the logic formulas to probabilistic object proposals for the given
image, provided by language-vision models by querying them for the symbols.
This work is the first to combine neuro-symbolic programming (reasoning) and
language-vision models (learning) to find spatial configurations of objects in
images in an open world setting. We show the effectiveness by finding
abandoned tools on floors and leaking pipes. We find that most prediction
errors are due to biases in the language-vision model.

###### Keywords:

Neuro-Symbolic Programming Open World Robotics Zero-shot Models Language-
Vision Models Knowledge Representation.

##  1 Introduction

Finding spatial configurations of multiple objects in images is a very
relevant capability. For instance, a mobile inspection robot is tasked to
localize situations of interest on an industrial site, such as abandoned tools
on the floor, because they may pose a hazard to the personnel and robot
itself. Once such a spatial configuration is found, proper action can be
taken, such as reporting it to the operator or removing the object using the
robot. On such sites, there may be many activities; as a consequence, the
objects, their position, and the environment may change constantly and this
may differ per site. Therefore the robot may encounter new objects, e.g., a
new type of tool; new environments, e.g., the floor is made of a different
material; and new relevant situations, e.g., a leaking pipe. This is a
challenge of the open world: handling previously unseen objects and
configurations. We consider the problem of localizing spatial configurations
of interest in an open world, with a focus on situations that require an
action of some kind.

To identify situations of interest, which deviate from the normal, a common
approach is to use a statistical model of the sensory data [3, 17, 18].
However, the robot’s goal, its context and explicit prior knowledge are not
taken into account. As a consequence, the detected anomalies are not
necessarily relevant for the robot’s mission. Another drawback of statistical
models is that they do not generalize well to new observations in the open
world. They cannot be adapted quickly, because it requires a significant
amount of training samples to adjust the statistical model.

We take a different approach by leveraging prior knowledge, in this case
knowledge about spatial configurations of objects. This knowledge can be
adapted quickly during operation and via generic definitions it can generalize
better to new situations. An example of a spatial configuration is a tool that
is left behind on the floor. A tool can be one of many types, such as a
hammer, screwdriver, wrench, and many more. Likewise, floors can be composed
of different materials with various appearances. Our goal is to find spatial
configurations in images, based on a high-level definition of the involved
object (categories) and the spatial relations between them, with the ability
to define the object or its category, and without learning dedicated models
for each of them. The rationale is that such an approach has a broader
applicability, because it can generalize better across similar configurations
and is adaptable to new configurations by formulating a new definition.

Figure 1: Finding spatial configurations of object categories in an open
world. A configuration is specified by first-order logic. The symbols relate
to (possibly novel) objects that are extracted from images in a zero-shot,
probabilistic manner. A neuro-symbolic program validates hypotheses.

We start by defining the configuration of interest by first-order logic. Logic
formulas specify the object categories and their spatial configuration in
terms of relations between them. For flexibility and generalization, the logic
formulas may entail the categories of the objects (tool), instead of the
specific objects (hammer, screwdriver, etc.). This reduces the amount of human
effort. The logic formulas are symbolic, where each relation and object
(category) is expressed as a symbol. Each symbol is used as a query to
generate object proposals for the current image. Object proposals are
generated from language-vision models [19, 20, 9], by querying them for the
symbols that are in the logic formulas. In the image, there may be many
objects and their proposals will be imperfect, leading to many possible
hypotheses. Therefore, a multi-hypothesis framework is required. A natural
choice is to leverage a neuro-symbolic program [5, 6, 8] for this purpose, as
it validates the logic formulas against many hypotheses about the object
proposals and the relations between them. Our method is outlined in Figure 1.
Our contribution is the integration of the neuro-symbolic programming
(reasoning) with the language-vision models (learned) for the purpose of
finding spatial configurations of objects. We show the effectiveness on real-
world images by finding specific situations in a robotic inspection setting.

##  2 Related Work

To operate in an open world, it is essential to interpret situations well. One
aspect of such interpretation is to analyze configurations of objects in the
scene. A typical approach is to incorporate prior knowledge when analyzing
images [15]. Connecting knowledge representation and reasoning mechanisms with
deep learning models [5] shows great promise for learning from the environment
and at the same time reasoning about what has been learned [6]. Previous
reasoning methods based on logic, such as DeepProbLog [11, 12], were limited
in terms of scalability when there were many possible hypotheses. For
instance, a task such as industrial inspection involves many possible objects
and relations and therefore many possible hypotheses. Therefore, such methods
were ill-suited for real-world applications. A more efficient variant of
DeepProbLog was proposed [13]. Recently, a framework was proposed that further
improved the efficiency: the neuro-symbolic programming framework called
Scallop [8]. Scallop is based on first-order logic and introduces a tunable
parameter $k$ to specify the level of reasoning granularity. It restrains the
validation of hypotheses by the top-$k$ proofs. This asymptotically reduces
the computational cost while providing relative accuracy guarantees. This is
beneficial for our purpose, as we expect many possible hypotheses in complex
environments with many objects and imperfect observations. In [8], the neuro-
symbolic programming framework was used to reason about visual scenes using a
pre-defined set of classes of objects. End-to-end learning between objects and
a neuro-symbolic program was proposed to jointly learn visual concepts, words
and semantic parsing [14]. Both approaches rely on a fixed set of visual
concepts, since a vocabulary, knowledge graph, or learning scheme are
involved. We aim to generalize to the open world, extending the vocabulary of
logical symbols to previously unseen objects, and enabling one to define
symbols at the category level instead of the class level.

For open world settings, perception models have to be applicable for a wide
variety of tasks in a broad range of settings. General-purpose vision systems
have been proposed, e.g., [7], that are trained on a large set of datasets and
tasks. Because some of these models can solve various tasks at the same time,
these are coined foundation models [2]. An example of such a complex task is
where the model provides answers to textual questions about images [15, 1].
Large progress has been achieved in language-vision tasks. Language-vision
models learn directly from huge datasets of texts describing images, which
offers a broad source of supervision [19, 16, 20, 9]. They have shown great
promise to generalize beyond crisp classes and towards semantically related
classes. This so-called zero-shot capability is beneficial for recognizing the
object categories that are involved in the spatial configuration of interest.
Recently, these models were extended with capabilities to localize objects in
images via co-attentions [4] and to segment parts of the scene based on
textual descriptions [10]. We adopt both methods to relate image parts to
respectively objects and segments from the environment, which are relevant for
the configuration at hand.

The abovementioned works in language-vision models have made huge progress in
learning visual concepts in relation to language and semantics. However, they
have not considered a combination with reasoning. We integrate neuro-symbolic
programming with language-vision models.To the best of our knowledge, this
work is the first to combine neuro-symbolic programming and language-vision
models to find spatial configurations of objects in images in an open world
setting.

##  3 Method

We find spatial configurations of object categories, based on prior knowledge
about the involved objects and their relations. An overview of our method is
shown in Figure 1. At the top, it shows how a configuration of interest, such
as our working example ‘tool on floor’, is translated into symbolic predicates
such as $object(o,\,tool)$, $segment(x,\,floor)$ and $above(o,x)$. At the
bottom left, the figure shows how the symbols from the predicates, such as
‘tool’ and ‘floor’, are measured from images by language-vision models. These
measurements are transformed into probabilistic facts, e.g., $P(tool|image)$
and $P(floor|image)$, which are provided to the neuro-symbolic program which
validates them against the logic (bottom right). Each component is detailed in
the following paragraphs.

###  3.1 First-order logic

The configuration of interest is defined by logic formulas and predicates. The
symbols in the predicates are about the objects and segments in an image. For
a tool that is left on the floor, the formulas are:

$\begin{split}\exists o:&object(o,tool)\land side(o,s_{1})\,\,\land\\\
&segment(s_{1},floor)\land above(o,s_{2})\,\,\land\\\
&segment(s_{2},floor)\land\lnot between_{vert}(z,o,s_{2})\end{split}$ (1)

This defines that a tool on the floor is defined by seeing the tool above and
aside the floor. For a robot, its perspective is oblique downward, i.e., the
floor will be visible at the bottom of the tool and on the side of the tool.
We also define that the tool should be on the floor, without anything ($z$) in
between. Otherwise, a tool that is on a cabinet standing on the floor, would
also fulfil the definition. The helper predicates are:

$\begin{split}between_{vert}(o_{1},o_{2},o_{3})&=above(o_{1},o_{2})\land
above(o_{3},o_{1})\\\ side(o_{1},o_{2})&=left(o_{1},o_{2})\lor
right(o_{1},o_{2})\end{split}$ (2)

to express that some $o_{2}$ is vertically between $o_{1}$ and $o_{3}$.
Finally, these are the predicates for positioning of one object relative to
the left, right and above another object:

$\begin{split}left(o_{1},o_{2})&=pos_{x}(o_{1})<pos_{x}(o_{2})\\\
right(o_{1},o_{2})&=pos_{x}(o_{1})>pos_{x}(o_{2})\\\
above(o_{1},o_{2})&=pos_{y}(o_{1})<pos_{y}(o_{2})\\\ \end{split}$ (3)

Another example of a spatial configuration is a leaking pipe. Analogous to the
abandoned tool, it can be formulated by predicates that relate objects and
segments:

$\begin{split}\exists o:&object(o,pipe)\land neighbor(o,s)\,\,\land\\\
&segment(s,leakage)\end{split}$ (4)

An additional helper predicate is needed to express that one object is
neighboring another object:

$\begin{split}neighbor(o_{1},o_{2})=&|pos_{x}(o_{1})-pos_{x}(o_{2})|\leq
1\,\,\land\\\ &|pos_{y}(o_{1})-pos_{y}(o_{2})|\leq 1\\\ \end{split}$ (5)

We refer to the set of logic formulas as $L$.

###  3.2 Image to Symbols

To find a specified configuration in the current image, the symbols from the
logic formulas are used to initiate corresponding image measurements. From the
image, measurements are taken that are an estimate of the symbols. We refer to
this process as ‘image to symbols’. For each logical symbol, we produce a
probabilistic fact about that symbol for the given image, e.g.,
$P(tool|image)$ and $P(floor|image)$. The probabilistic facts are input to the
neuro-symbolic inference process (next subsection).

Each symbol generates probabilistic proposals for the image by prompting a
language-vision model. For our purpose, we adopt CLIP [19] because we found
its performance to be solid for various symbols, even for niche objects (i.e.,
zero-shot performance [16]). We query CLIP by a text prompt of the symbol,
e.g. ‘tool’. CLIP operates on the image level, i.e., matching a prompt to the
full image. Our objective is different: we aim to localize the symbols, such
that we can analyze their spatial configurations within the image. We adopt
recent extensions of CLIP that can generate attention maps [4] and
segmentation maps [10] for text prompts. The attention maps show where the
model is activated regarding objects, as the model is specialized to learn the
important objects in images. Hence we use them to localize objects (e.g.,
tool). However, this model is object-specific and not suitable for
environmental elements such as walls and floors. For this purpose, we leverage
a segmentation model to segment scenes, in order to localize environmental
segments (e.g., floor). In this way, we obtain probabilistic symbols.

The attention maps for the CLIP model are obtained by [4]:

$\overline{A}=\mathbb{E}_{h}((\nabla A\odot A)^{+})$ (6)

where $\odot$ is the Hadamard product, $\nabla A=\frac{\partial
y_{k}}{\partial A}$ is CLIP’s output for a textual prompt $T_{k}$,
$\mathbb{E}_{h}$ is the mean across CLIP’s transformer heads, and $\cdot^{+}$
denotes removal of negative contributions [4].

$\overline{A}$ is an attention map and therefore it is not calibrated to
probabilistic values. For that purpose, we scale $\overline{A}$ to the range
$[0,1]$ by dividing by its maximum value, thereby we obtain
$\overline{A}^{\prime}$. The values of $\overline{A}^{\prime}$ are not
probabilities. That is, the values are uncalibrated for the prompt $T_{k}$,
since the maximum value is always 1. To calibrate $\overline{A}^{\prime}$ for
a prompt $T_{k}$, we weight $\overline{A}^{\prime}$ with the confidence for
$T_{k}$, $Y_{k}$: $G(k)=\overline{A}^{\prime}\odot Y_{k}$, with
$Y=softmax(\\{y\\})$ for CLIP’s outputs $\\{y\\}_{1:N}$ for the respective set
of prompts $\\{T\\}_{1:N}$. We consider a set of prompts that contrast the
objects of interest (e.g., tool) with irrelevant negatives (e.g., wall, floor,
closet, ceiling, etc.): $T$ $=$ $\\{tool,...,ceiling\\}$. Since $G(k)$ is
calculated for an image $I$ at its pixels $(i,j)$, we rewrite: $G(I,i,j,k)$.
To obtain a proxy for the probability for the object of interest $o$ at index
$k$ from set $T$, we take: $G(I,i,j,k_{o})$. For the full image, we denote the
probability map shortly as $G(I,o)$.

To segment image $I$ at image location $(i,j)$, the response to a textual
prompt $T_{k}$ from the set of prompts $\\{T\\}_{1:N}$ is given by [10]:

$f(I,i,j,k)=I^{\prime}(i,j)\cdot T^{\prime}_{k},\,\,k\in\\{1,...,N\\}$ (7)

where $I^{\prime}$ is the visual encoding of image $I$, $T^{\prime}$ the
textual encoding of prompt $T$ and $\cdot$ is the dot product. The vector $f$
is transformed by the softmax operator to obtain values in the range of
$[0,1]$: $F(I,i,j,:)=softmax(f(I,i,j,:))$. We consider a set of prompts that
contrast the segments of interest (e.g., floor) with irrelevant negatives
(e.g., wall, ceiling, etc.): $T$ $=$ $\\{floor,...,ceiling\\}$. To obtain the
proxy of a probability for the segment of interest $s$ at index $k$ from set
$T$, within image $I$ at pixel $(i,j)$, we take: $F(I,i,j,k_{s})$. For the
full image, we denote the probability map shortly as $F(I,s)$.

Using $F(I,s)$ and $G(I,o)$, we obtain a probability for each symbol from the
logic formulas, where for each pixel of image $I$ the probability is stored:

$\begin{split}P(object=o\,|\,I,o)=&\,\,G(I,o),\,\,\,o\in\\{tool,pipe,etc.\\}\\\
P(segment=s\,|\,I,s)=&\,\,F(I,s),\,\,\,s\in\\{floor,leakage,etc.\\}\end{split}$
(8)

###  3.3 Neuro-Symbolic Inference

Inference of the probability for the (spatial) configuration $C$ as defined by
$L$, in the image $I$ is performed by the neuro-symbolic program. This program
operates on probabilistic facts [8] which we derive from the symbolic heatmaps
$P(s)$ and $P(o)$ (Equation 8). We consider various spatial scales to infer
$C$, because the distance between the robot and the scene may differ from time
to time. As a consequence, the amount of pixels on the objects may vary. The
original heatmaps $P(s)$ and $P(o)$ are finegrained. For multi-scale analysis,
we add down-sampled versions of them, $P(s,\sigma)$ and $P(o,\sigma)$ at
spatial scales $\sigma$ $\in$ $\\{1,2,..,32\\}$ to indicate the down-sampling
factor. This enables both finegrained and coarser inference, to accommodate
for varying distances from camera to the relevant objects. To achieve scale-
invariant inference, we select the scale $\sigma$ that maximizes the
probability $P(C)$ for the spatial configuration $C$ in the current image $I$
given the logic $L$ and its symbols $S$ and $O$:

$P(C)=\operatorname*{arg\,max}_{\sigma\in\\{1,\,2,\,4,\,8,\,16\\}}P(C\,|\,I,\,L,\,\\{P(s,\sigma)\\}_{s\in
S},\,\\{P(o,\sigma)\\}_{o\in O})$ (9)

Note that this can be generalized to an optimal scale $\sigma$ specifically
for each segment $s$ and object $o$ in Equation 9. However, this requires that
all possible combinations of $s$ and $o$ at all scales $\sigma$ are analyzed
by the neuro-symbolic program $P$. This will cause a computational burden. For
computational efficiency, we optimize a single scale $\sigma$ for all $s$ and
$o$.

##  4 Experiments

To analyze the performance of our method, we collected a wide variety of test
images to find various spatial configurations of objects. The configurations
are about undesired situations that require action: finding an abandoned tool
on the floor inside a factory, and detecting a leaking pipe on an industrial
site. We evaluate our method in a zero-shot manner: we use the models without
any retraining so they have not been optimized for the tested situations. The
purpose of this setup is to validate the method in an open world.

###  4.1 Abandoned Tool on Floor

We collected 31 test images about an abandoned tool on the floor. To validate
how well the method generalizes to various tools, we include images with
hammers, screwdrivers, wrenches, etc. For the same reason, we include various
floors, with different materials, textures and colors. Moreover, the viewpoint
and zoom are varied significantly. There are 9 images of tools on floors.
These are the positives which should be detected by our method. To verify true
negatives, we include 8 images where there is a both a tool and a floor, but
the tool is not on the floor (but on a cabinet, wall, etc.). There are 5
images with only a floor (no tool) and 4 images with only a tool (no floor).
To verify true negatives, there are also 5 images where there is no tool and
no floor.

There are 9 positives, from which we detect 7 cases. Figure 2(a) \- 2(d) shows
4 out of those 7 cases. Each case is illustrated by showing the original image
in the top left and the result of the neuro-symbolic program in the top right.
The involved symbols are shown in the lower left and right. The visualizations
are heatmaps, where a high probability is red, whereas blue indicates a low
probability. For the symbols (lower rows), the full heatmap is shown. For the
result of the neuro-symbolic program (top-rights), only the most likely
location is shown.

The resolution of the heatmaps indicates the granularity of the reasoning, as
it reflects the optimal spatial scale which maximized the resulting
probability (Equation 9). In Figure 2, most spatial scales are relatively
small, indicated by the fine-grained heatmaps. Since the symbols are predicted
well (often the tools and floors have a high probability at the respective
symbols), the reasoning is able to pinpoint a place in the image where the
spatial configuration is fulfilled mostly (a peak in the neuro-symbolic
output). In the case of a negative, the probability is typically much lower,
as shown in the next paragraph.

Out of the 17 negatives, there are 8 hard cases, as these images contain both
a tool and a floor, but not in the defined configuration: the tool is not on
the floor. Out of these 8 negatives, 6 are correctly assessed as such. The two
errors (i.e., false positives) are shown in the next subsection. Figure 2(e)
and 2(f) show 2 out of 6 true negatives. Although there are both a floor and
tools, the reasoner correctly finds that the spatial configuration is not a
tool that is on the floor.

The two false positives are shown in Figure 3(a) and 3(b). The neuro-symbolic
program incorrectly reasons that these cases are a tool left on the floor
(false positives). This is due to errors in the symbols. There is a wrong
association of the symbol tool in both images. On the left, the Gazelle logo
is associated with a tool. We hypothesize that the reason for this flaw is
that Gazelle is a manufacturer of bicycles: many images on the web about this
brand involve tools. The language-vision model probably has learned a bias to
associate Gazelle with tools. On the right, the duct tape is considered to be
a tool. From a semantic point of view this makes sense. These symbol errors
propagate into the reasoner’s outputs. Refining the prompts that we pose to
the language-vision models, may overcome such errors in the symbols.

(a) True positive

(b) True positive

(c) True positive

(d) True positive

(e) True negative

(f) True negative

Figure 2: Tool on floor: good predictions.

Figure 3(c) and 3(d) show missed cases (false negatives). Again, the source of
the errors is in the symbols. On the left, the tool (a grinder) is not
recognized as such. This is a flaw in the language-vision model, probably
because this tool does not appear often in everyday images and language. On
the right, the floor is not recognized as such. We hypothesize that this is
due to a lack of context within the image: it could also be a wooden plate.
Without the proper evidence for each involved symbol, the reasoner cannot
assess these configurations correctly. The computation time per image is
approximately 1 second on a standard CPU without any optimization of
efficiency.

(a) False positive

(b) False positive

(c) False negative

(d) False negative

Figure 3: Tool on floor: errors.

###  4.2 Leaking Pipe

The second experiment is about another task: to find a leaking pipe. We
collected 15 images of very different cases with various pipes and leaking
fluids. Likewise the abandoned tool, we include various viewpoints and
distances to the scenes.

(a) True positive

(b) True positive

(c) False negative

(d) False negative

Figure 4: Leaking pipe.

There are 15 positives, from which we detect 13 cases. Figure 4(a) and 4(b)
show 2 out of those 13 cases. The organization of the figure is the same as
previous result figures. Although the scenes are very different, the symbols
are predicted well. Often the pipes and leakages have a high probability at
the respective symbols. The neuro-symbolic program is able to pinpoint a place
in the image where the spatial configuration is fulfilled (bright spot in the
heatmap).

Out of the 15 actual cases, 2 were considered to be a negative (miss). Figure
4(c) shows a false negative where the leakage was localized too far away from
the pipe. Hence the spatial arrangement did not fulfil the definition and
therefore it was not assessed as a leaking pipe. In 4(d) there is a false
negative, because the left part of the broken pipe was not assessed as such.
Therefore the leakage is not close to a part in the image that was considered
as a pipe.

###  4.3 Performance and Ablations

The performance is evaluated by ROC curves as shown in Figure 5. Our neuro-
symbolic program is compared against baselines that use partial information
(only the tool or only the floor) and a baseline that uses the same
information (tool and floor) but without the spatial configuration. For
ablation, three variants of the neuro-symbolic program are evaluated, each
having more contextual knowledge and multi-scale reasoning.

Figure 5: ROC curves for abandoned tool on floor. The neuro-symbolic program
is more effective than alternative combinations of tool and floor. Spatial
information and multi-scale reasoning are helpful.

It can be concluded that both tool and floor are required, and the spatial
configuration is also essential. With only tool and floor as inputs, the
performance becomes almost random, resp. AUC=0.55 and AUC=0.63. With both
inputs, yet without spatial configuration, the performance increases only
slightly: AUC=0.70. Including tool and floor in the neuro-symbolic program,
without taking their spatial relations into account, is equally ineffective:
AUC=0.71. When the spatial configuration is considered by the neuro-symbolic
program, the performance increases significantly: AUC=0.83. Including multi-
scale makes the neuro-symbolic program very effective: AUC=0.98. Most of the
situations of interest can be detected without false positives, whereas the
alternatives produce many false positives.

##  5 Conclusions

For open world settings, we proposed a method to find spatial configurations
of multiple objects in images. It enables expert-driven localization of new or
unseen object configurations. Our method is able to find situations of
interest in a robotic inspection setting: abandoned tools on floors and
leaking pipes. The tools, floors, pipes and leakages have not seen before and
no task-specific training was performed. Most of the situations of interest
were correctly localized. A few false positives occurred, due to erroneous
object proposals. This was caused by a bias in the language-vision model,
e.g., a logo of a tool that was considered to be a tool. A few false negatives
happened, due to missed object proposals. A typical example is a close-up
image of a floor, which was missed because context was lacking. Our method
avoids the necessity of learning dedicated models for each of the involved
objects, which makes our method flexible and quickly operational in an open
world.

## References

  * [1] Antol, S., Agrawal, A., Lu, J., Mitchell, M., Batra, D., Zitnick, C.L., Parikh, D.: Vqa: Visual question answering. In: Proceedings of the IEEE international conference on computer vision. pp. 2425–2433 (2015)
  * [2] Bommasani, R., Hudson, D.A., Adeli, E., Altman, R., Arora, S., von Arx, S., Bernstein, M.S., Bohg, J., Bosselut, A., Brunskill, E., et al.: On the opportunities and risks of foundation models. arXiv preprint arXiv:2108.07258 (2021)
  * [3] Chandola, V., Banerjee, A., Kumar, V.: Anomaly detection: A survey. ACM computing surveys (CSUR) 41(3), 1–58 (2009)
  * [4] Chefer, H., Gur, S., Wolf, L.: Generic attention-model explainability for interpreting bi-modal and encoder-decoder transformers. In: Proceedings of the IEEE/CVF International Conference on Computer Vision. pp. 397–406 (2021)
  * [5] De Raedt, L., Dumančić, S., Manhaeve, R., Marra, G.: From statistical relational to neuro-symbolic artificial intelligence. International Joint Conference on Artificial Intelligence pp. 4943–4950 (2020)
  * [6] Garcez, A.d., Gori, M., Lamb, L.C., Serafini, L., Spranger, M., Tran, S.N.: Neural-symbolic computing: An effective methodology for principled integration of machine learning and reasoning. Journal of Applied Logics 6, 611–632 (2019)
  * [7] Hu, R., Singh, A.: Unit: Multimodal multitask learning with a unified transformer. In: Proceedings of the IEEE/CVF International Conference on Computer Vision. pp. 1439–1449 (2021)
  * [8] Huang, J., Li, Z., Chen, B., Samel, K., Naik, M., Song, L., Si, X.: Scallop: From probabilistic deductive databases to scalable differentiable reasoning. vol. 34, pp. 25134–25145 (2021)
  * [9] Jia, C., Yang, Y., Xia, Y., Chen, Y.T., Parekh, Z., Pham, H., Le, Q., Sung, Y.H., Li, Z., Duerig, T.: Scaling up visual and vision-language representation learning with noisy text supervision. In: International Conference on Machine Learning. pp. 4904–4916. PMLR (2021)
  * [10] Li, B., Weinberger, K.Q., Belongie, S., Koltun, V., Ranftl, R.: Language-driven semantic segmentation. In: International Conference on Learning Representations (2022)
  * [11] Manhaeve, R., Dumancic, S., Kimmig, A., Demeester, T., De Raedt, L.D.: Neural probabilistic logic programming. Advances in Neural Information Processing Systems 31, 3753–3763 (2021)
  * [12] Manhaeve, R., Dumančić, S., Kimmig, A., Demeester, T., De Raedt, L.: Neural probabilistic logic programming in deepproblog. Artificial Intelligence 298, 103504 (2021)
  * [13] Manhaeve, R., Marra, G., De Raedt, L.: Approximate inference for neural probabilistic logic programming. In: Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning. pp. 475–486. IJCAI Organization (2021)
  * [14] Mao, J., Gan, C., Kohli, P., Tenenbaum, J.B., Wu, J.: The neuro-symbolic concept learner: Interpreting scenes, words, and sentences from natural supervision. In: International Conference on Learning Representations. International Conference on Learning Representations, ICLR (2019)
  * [15] Marino, K., Rastegari, M., Farhadi, A., Mottaghi, R.: Ok-vqa: A visual question answering benchmark requiring external knowledge. In: Proceedings of the IEEE/cvf conference on computer vision and pattern recognition. pp. 3195–3204 (2019)
  * [16] OpenAI: https://openai.com/blog/clip/ (2021)
  * [17] Pang, G., Shen, C., Cao, L., Hengel, A.V.D.: Deep learning for anomaly detection: A review. ACM Computing Surveys (CSUR) 54(2), 1–38 (2021)
  * [18] Paschalidis, I.C., Chen, Y.: Statistical anomaly detection with sensor networks. ACM Transactions on Sensor Networks (TOSN) 7(2), 1–23 (2010)
  * [19] Radford, A., Kim, J.W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry, G., Askell, A., Mishkin, P., Clark, J., et al.: Learning transferable visual models from natural language supervision. In: International Conference on Machine Learning. pp. 8748–8763. PMLR (2021)
  * [20] Yuan, L., Chen, D., Chen, Y.L., Codella, N., Dai, X., Gao, J., Hu, H., Huang, X., Li, B., Li, C., et al.: Florence: A new foundation model for computer vision. arXiv preprint arXiv:2111.11432 (2021)