# Proximity Search For Maximal Subgraph Enumeration

Alessio Conte  University of Pisa, Italy<EMAIL_ADDRESS>,  Roberto Grossi
University of Pisa, Italy<EMAIL_ADDRESS>,  Andrea Marino  University of
Florence, Italy<EMAIL_ADDRESS>,  Takeaki Uno  National Institute of
Informatics, Japan<EMAIL_ADDRESS>and  Luca Versari  University of Pisa, Italy
and Google Research<EMAIL_ADDRESS>
(2018)

###### Abstract.

This paper proposes a new general technique for maximal subgraph enumeration
which we call proximity search, whose aim is to design efficient enumeration
algorithms for problems that could not be solved by existing frameworks. To
support this claim and illustrate the technique we include output-polynomial
algorithms for several problems for which output-polynomial algorithms were
not known, including the enumeration of Maximal Bipartite Subgraphs, Maximal
$k$-Degenerate Subgraphs (for bounded $k$), Maximal Induced Chordal Subgraphs,
and Maximal Induced Trees. Using known techniques, such as reverse search, the
space of all maximal solutions induces an implicit directed graph called
“solution graph” or “supergraph”, and solutions are enumerated by traversing
it; however, nodes in this graph can have exponential out-degree, thus
requiring exponential time to be spent on each solution. The novelty of
proximity search is a formalization that allows us to define a better solution
graph, and a technique, which we call canonical reconstruction, by which we
can exploit the properties of given problems to build such graphs. This
results in solution graphs whose nodes have significantly smaller (i.e.,
polynomial) out-degree with respect to existing approaches, but that remain
strongly connected, so that all solutions can be enumerated in polynomial
delay by a traversal. A drawback of this approach is the space required to
keep track of visited solutions, which can be exponential: we further propose
a technique to induce a parent-child relationship among solutions and achieve
polynomial space when suitable conditions are met. 111A preliminary version of
this paper has been presented in (Conte2019proximity, ), containing some of
the exponential-space algorithms. In this extended version, we factorize the
fundamental principles of algorithms in (Conte2019proximity, ) to define a
general guide for designing a proximity search algorithm, which we call
canonical reconstruction. We also introduce a general technique to obtain
proximity search algorithms that use polynomial space, as well as proximity
search algorithms for new problems, both with exponential-space and
polynomial-space requirements. A draft of this extended version is also
available at (conte2019proximityArxiv, ).

graph enumeration, polynomial delay, proximity search

††copyright: acmcopyright††journalyear: 2018††doi:
10.1145/1122445.1122456††conference: Woodstock ’18: ACM Symposium on Neural
Gaze Detection; June 03–05, 2018; Woodstock, NY††booktitle: Woodstock ’18: ACM
Symposium on Neural Gaze Detection, June 03–05, 2018, Woodstock, NY††price:
15.00††isbn: 978-1-4503-XXXX-X/18/06††ccs: Mathematics of computing Graph
enumeration††ccs: Mathematics of computing Graph algorithms

##  1\. Introduction

Given a universe of elements, such as the vertices or edges of a graph, and a
property on them, such as being a clique or a tree, a listing problem asks to
return all subsets of the universe which satisfy the given property.

Listing structures, within graphs or other types of data, is a basic problem
in computer science, and it is at the core of data analysis. While many
problems can be solved by optimization approaches for the best solution, e.g.,
by finding the shortest path, or the largest clique, others require finding
several solutions to the input problem: in community detection, for example,
finding just one “best” community only gives us local information regarding
some part of the data, so we may want to find several communities to make
sense of the input. Furthermore, many real-world scenarios may not have a
clear objective function for the best solution: We may define an algorithm to
optimize some desired property, but the optimal solution found may be lacking
further properties that emerge during listing or simply not be practical. We
may want instead to quickly list several solutions, suitable according to some
metrics, then analyze them a posteriori to find the desired one.

In these scenarios, listing only the solutions that are maximal under
inclusion is a common-sense requirement whenever it can be applied,222In other
problems, we may want minimal solutions instead, although this is usually an
equivalent concept, as it corresponds to the complement of a solution being
maximal. as maximal solutions subsume the information contained in all others,
and can be exponentially fewer: For example, a graph may have up to $2^{n}$
cliques, but only $3^{n/3}$ maximal ones (moon1965cliques, ). For brevity, we
call maximal listing problem a listing problem where only the inclusion-
maximal solutions should be output.

From a theoretical point of view, listing provides many challenging problems,
especially when maximality is required. When dealing with listing algorithms,
we are often interested in their complexity with respect to both $n$, the
input size, and $\mathcal{N}$, the size of the output. Algorithms whose
complexity can be bounded by a polynomial of these two factors are called
output polynomial or polynomial total time (JOHNSON1988119, ). Interestingly,
the hardness of listing problems does not seem to be correlated with that of
optimization: there are several np-hard maximum optimization problems whose
corresponding maximal listing problem admits an output-polynomial solution
(see, e.g., (tsukiyama1977new, ; avis1996reverse, )); on the other hand, there
are problems for which one maximal (or maximum) solution can be identified in
polynomial time, but an output-polynomial algorithm for listing maximal
solutions would imply p=np (lawler1980generating, ).

A long-standing question in the area is to find a characterization of which
listing problems allow for output-polynomial solutions and which do not.
Furthermore, within output-polynomial algorithms stricter complexity classes
exist, such as incremental polynomial time, where the time to output the
$i$-th solution is polynomial in $n$ and $i$, and polynomial delay, where the
time elapsed for outputting the next solution is upper bounded by a polynomial
in $n$. The latter class is of particular interest in practical scenarios, as
it guarantees that solutions are output at a regular pace.

In this paper we add a few points to the latter class, by showing that there
exist polynomial delay algorithms for some subgraph listing problems. More
formally, we prove Theorem 1.1.

###### Theorem 1.1.

The following problems allow polynomial delay listing algorithms by proximity
search:

problem | delay
---|---
maximal induced bipartite sg. | $O(n(m+n\alpha(n)))$
maximal connected induced bipartite sg. | $O(mn)$
maximal bipartite edge-induced sg. |  $O(m^{3})$
maximal induced $k$-degenerate sg. | $O(mn^{k+2})$
maximal edge-induced $k$-degenerate sg. |  $O(m^{3}n^{k-1})$
maximal induced chordal sg. | $O(m^{2}n)$
maximal connected induced chordal sg. | $O(m^{2}n)$
maximal edge-induced chordal sg. |  $O(m^{4}n)$
maximal induced proper interval sg. | $O(m^{2}n^{3})$
maximal connected induced proper interval sg. | $O(mn^{3})$
maximal connected obstacle-free convex hulls |  $O(n^{4})$
maximal induced trees |  $O(m^{2})$
maximal connected induced directed acyclic sg. | $O(mn^{2})$
maximal connected edge-induced directed acyclic sg. | $O(m^{3})$

Where “sg.” stands for subgraphs, $n$ and $m$ are the number of vertices and
edges, $\alpha(\cdot)$ is the functional inverse of the Ackermann function
(Tarjan75UF, ).

All the algorithms use $O(\mathcal{N}n)$ space, where $\mathcal{N}$ is the
number of solutions.

To the best of our knowledge, no output-polynomial result was previously known
for these problems. For completeness, we consider both induced subgraphs
(i.e., sets of vertices) and edge-induced subgraphs (i.e., sets of edges), as
well as the connected case where solutions are required to be connected, as
the structure of such variants can differ significantly.

Furthermore, we abstract a general technique that can be used to obtain
similar results on other problems. We do so by defining a graph whose vertices
are the maximal solutions to the listing problem, and with directed edges
between pairs of solutions, which we call solution graph. The listing problem
is solved by traversing the solution graph, and proving that all solutions are
found this way. The concept of solution graph is common to existing
approaches, and general techniques already exist for building them, e.g.,
(Cohen20081147, ). However, the solution graph built with known approaches
such as (Cohen20081147, ) may have too many edges, resulting in a traversal
with exponential delay.

The key concept given in this paper is a technique to build a solution graph
with fewer edges, while proving that all solutions are still found by its
traversal. An interesting property of this approach is that the resulting
algorithms are remarkably simple to implement, while the complexity lies in
proving their correctness. We call this technique proximity search since at
its core lies a problem-specific notion of proximity. This notion acts as a
sort of compass on the solution graph built by our algorithm, as given any two
solutions $S$ and $S^{*}$, we will show that we always traverse an edge from
$S$ to another solution $S^{\prime}$ that has higher proximity to $S^{*}$; as
$S^{*}$ has the highest proximity to itself, this implies that a traversal of
the solution graph from any solution finds all others. While others, such as
(Cohen20081147, ; schwikowski2002enumerating, ), already used the principle of
reachability in the solution graph, we aim to define a looser set of necessary
condition in order to guarantee this reachability, allowing more freedom in
the design of algorithms, while at the same time formalize a technique called
canonical reconstruction that is effective in decomposing the structure of
several problems to fit these rules. The combination of these two parts
creates algorithms that overcome the exponential burden imposed by the so-
called input-restricted problem, a reduced instance of the original problem
that dominates the cost per solution of such approaches whose cost may be
inherently exponential.

While the space required for a traversal of the graph is inherently
proportional to the number of solutions, i.e., can be exponential in $n$, some
output-polynomial techniques such as reverse search are able to work in
polynomial space by inducing a tree-like structure on the solution graph,
provided that the problem at hand is hereditary (i.e. its property holds for
the induced subgraphs) and the input-restricted problem is solvable
efficiently.

By adding suitable constraints to the problems considered, we show a technique
that combines proximity search with a recent generalization of reverse search
to non-hereditary problems (conte2019framework, ), obtaining algorithms with
both polynomial-delay and polynomial space for some instances of proximity
search. In particular, we prove that:

###### Theorem 1.2.

The following problems allow polynomial delay listing and polynomial space
algorithms by proximity search, with the following bounds:

problem | delay | space
---|---|---
maximal induced bipartite sg. | $O(n^{2}(m+n\alpha(n)))$ | $O(m)$
maximal connected induced bipartite sg. | $O(mn^{2})$ |  $O(m)$
maximal obstacle-free convex hulls | $O(n^{4})$ |  $O(n)$
maximal induced trees | $O(m^{2}n^{2})$ | $O(m)$
maximal induced forests | $O(m^{2}n^{2})$ |  $O(m)$

Where notation is as in Theorem 1.1.

###  1.1. Related Work

The listing problems considered in this paper model solutions as sets of
elements (e.g., sets of vertices or edges of a graph), and consist in listing
sets of elements with some required property, e.g., inducing a bipartite
subgraph, or a tree. We observe that the output is a family of sets, we can
associate properties with the corresponding set systems: for example, a
property is hereditary when each subset of a solution is a solution, which
corresponds to the well-known independence systems (lawler1980generating, ).

In this context, a simple yet powerful technique is recursively partitioning
the search space into all solutions containing a certain element, and all that
do not. This technique, usually called binary partition or simply
backtracking, proves efficient when listing all solutions
(Ruskey03combinatorialgeneration, ), and can be used to design algorithms that
are fast in practice,333E.g., implementations of the Bron-Kerbosh
(tomita2006worst, ) algorithm tend to be faster than those of output-
polynomial algorithms (DBLP:conf/icalp/ConteGMV16, ) for listing maximal
cliques. or that can bound the number of solutions in the worst-case
(Fomin:2008:CBV:1435375.1435384, ). On the other hand, this strategy rarely
gives output-polynomial algorithms when dealing with maximal solutions, as we
may spend time exploring a solution subspace that contains many solutions but
no maximal one.

To obtain output-polynomial algorithms for maximal solutions, many algorithms
rely on the following idea: given a maximal solution $S$, and some element
$x\not\in S$, the hardness of listing solutions maximal within $S\cup\\{x\\}$
is linked to the hardness of listing them in a general instance. One of the
earliest mentions of the idea can be found in the seminal paper by Lawler et
al. (lawler1980generating, ), that generalizes ideas from Paull et al.
(paull1959minimizing, ) and Tsukiyama et al. (tsukiyama1977new, ), and has
been formally defined as input-restricted problem by Cohen et al.
(Cohen20081147, ).

The intuition is that the solutions obtained this way, using a maximal
solution $S$ and an element not in $S$, can be used to generate new maximal
solutions of the original problem. We can thus traverse an implicit directed
graph, which we will call solution graph, where the vertices are the maximal
solutions and the out-neighbors are obtained by means of the input-restricted
problem.

In particular, (lawler1980generating, ) showed how solving this problem could
yield an output-polynomial and polynomial space listing algorithm for
properties corresponding to independence systems, assuming the input-
restricted problem has a bounded number of solutions. (Cohen20081147, ) showed
that the strategy could be extended to the more challenging connected-
hereditary graph properties (i.e., where connected subsets of solutions are
solutions) using exponential space, and recently, (conte2019framework, )
showed that the same result can be obtained in polynomial space for commutable
set systems (which include connected-hereditary properties).

A clear limitation of this approach is that, in order to obtain polynomial-
delay algorithms, the input-restricted problem needs to be solved in
polynomial time. This is possible for some problems (e.g., cliques and
independent sets), but impossible for others, simply because their input-
restricted problems may have exponentially many solutions. Figure 1 shows an
example for maximal bipartite subgraphs.

Figure 1. Instances of input-restricted problem for maximal bipartite
subgraphs. On the left: the black dots define a maximal bipartite induced
subgraph; adding the vertex $v$ creates a graph with exponentially many
maximal induced bipartite subgraphs, as we can obtain one by removing a vertex
from each connected pair in the bottom in any combination. On the right: the
black edges define a maximal bipartite subgraph, and the addition of edge $e$
creates a graph with exponentially many maximal edge-induced bipartite
subgraphs: every vertex on the bottom is incident to two edges; removing
exactly one for each vertex yields a maximal edge-induced bipartite subgraph.

The literature contains many more results concerning the enumeration of
maximal/minimal solutions, e.g., (avis1996reverse, ; koch1996algorithm, ;
schwikowski2002enumerating, ; Golovach2018, ; GELY20091447, ; CARMELI2020, ),
and in particular regarding challenging problems such as the well-known
minimal hypergraph transversals/dominating sets problem (kante2014enumeration,
; golovach2015incremental, ; elbassioni2009output, ). However, to the best of
our knowledge, the only two effective general techniques for listing maximal
solutions in an output-sensitive fashion are the extension problem (binary
partition, flashlight search), and the input-restricted problem: proximity
search can be a valuable tool when the previous two fail. We motivate this by
showing the first polynomial delay algorithms for several maximal listing
problems whose associated input-restricted problem is not solvable in
polynomial time.

As mentioned above, a preliminary version of this paper containing some of the
exponential-space algorithms has appeared in (Conte2019proximity, ). Since its
publication, some preprints (brosse2020efficient, ; kurita2020efficient, ;
Cao:arXiv:2020, ) have appeared that apply the technique to obtain new output-
polynomial algorithms. In particular, (Cao:arXiv:2020, ) solves the
enumeration of Maximal Induced Interval Subgraphs by proposing some variations
to proximity search (Conte2019proximity, ).

###  1.2. Overview

The main contribution of the paper is presenting proximity search, a general
technique that can be used to solve several enumeration problems in polynomial
delay, and canonical reconstruction, a way to design a proximity search
algorithm by exploiting orderings of solutions of the problem at hand.
exponentially many solutions.

By using this technique we show polynomial delay algorithms for several
maximal listing problems such as maximal bipartite subgraphs and the others
mentioned in Theorem 1.1. Other than providing efficient algorithms, we remark
that the technique may help gain further insight on which classes of problems
allow output-polynomial listing algorithms and which do not.

The paper is organized as follows: First, we introduce some basic concepts and
notation in Section 2. We then explain the proximity search technique, and
formally define a class of problems, called proximity searchable, which allow
for a polynomial delay algorithm by its application.

Generality comes sometimes at the expense of efficiency but allows for a more
intuitive understanding of the concepts at hand. For this reason, we divide
the explanation in two parts: the first one, in Section 3, formalizes the
constraints required for a proximity search algorithm. The second, Section 4,
introduces a technique which we call canonical reconstruction for implementing
proximity search. While canonical reconstruction is not the only way to obtain
a proximity search algorithm, we observed that is often a powerful and elegant
way to model the problem at hand.

Following, Sections 5-10, shows how to prove that the problems in Theorem 1.1
are proximity searchable and thus allow polynomial-delay algorithms.

As a drawback of the above algorithms is an exponential space requirement, we
then propose a technique to address this issue, when suitable conditions are
met: define a parent-child relation between solutions, in the style of
reverse-search, as detailed in Section 11, and give the algorithms in Section
12. The resulting bounds are shown in Theorem 1.2. While this technique does
not apply to all problems in Theorem 1.1, when it does it allows us to obtain
polynomial-delay and polynomial-space algorithms for several problems whose
input-restricted problem cannot be solved in polynomial time, including non-
hereditary ones.

##  2\. Preliminaries

Most of the enumeration problems addressed in this paper consider a simple
undirected graph $G$, whose vertex set is denoted as $V(G)$ and edge set as
$E(G)$, or simply $G=(V,E)$ when it is clear from the context. The
neighborhood of a vertex $v$ is denoted as $N(v)$. For brevity, we refer to
$|V(G)|$ as the number $n$ of vertices, to $|E(G)|$ as the number $m$ of
edges, and to the maximum degree of a vertex in $G$ as $\Delta=\max_{v\in
V}|N(v)|$. Furthermore, we assume the vertices to be labeled arbitrarily in
increasing order $v_{1},\ldots,v_{n}$, and say that $v_{i}$ is smaller than
$v_{j}$ if $i<j$. We say that a neighbor of $v_{i}$ is a forward neighbor if
it comes later than $v_{i}$ in the order, and a backward neighbor otherwise.

For a set of vertices $A\subseteq V(G)$, $E[A]$ denotes the edges of $G$ whose
endpoints are both in $A$, and $G[A]$ the graph $(A,E[A])$, i.e., the subgraph
induced in $G$ by $A$. Similarly, for a set $B$ of edges, $V[B]$ denotes the
vertices incident to an edge in $B$ and $G[B]=(V[B],B)$. As common in the
literature, we call induced subgraphs those of the former kind, defined by a
set of vertices, and edge-induced subgraphs (or simply subgraphs) those of the
latter, defined by a set of edges. When dealing with subgraphs defined by a
set of vertices (resp. edges) $A$, we will sometimes use $A$ to refer to both
the vertex set (resp. edge set) and the subgraph $G[A]$ it induces, when this
causes no ambiguity. We will also use $\texttt{cc}_{v}(A)$ to refer to the
connected component of $G[A]$ which includes the vertex $v$. For further
notation, we refer to the standard terminology in (Diestel2005, ).

For a set of vertices $A\subseteq V(G)$ which corresponds to a solution of the
problem at hand, we say that $A$ is _maximal_ if there is no
$A^{\prime}\subseteq V(G)$ such that $A^{\prime}\supset A$ and $A^{\prime}$ is
also a solution. While not strictly necessary for the proximity search
technique, in the following we will often rely on a simple “maximalization”
function, named $\textsc{comp}(A)$: this function takes a (not necessarily
maximal) solution $A$ and “completes” it, returning some maximal solution
$A^{\prime}\supseteq A$. We will refer to the computational cost of this
function as $\mathcal{C}_{t}$. Note that it is always possible to devise a
polynomial-time computable $\textsc{comp}(\cdot)$ function for hereditary and
connected-hereditary properties where solutions can be recognized in
polynomial time, by simply trying to add vertices until no longer possible
(Cohen20081147, ).

For simplicity, we disregard the presence of isolated vertices in the
complexity analysis of the algorithms provided: these are trivially handled
for the problems considered in this paper (either they can all be added “in
bulk” to every solution, as for bipartite subgraphs, or each constitutes a
maximal solution by itself, as for connected bipartite subgraphs), can be
removed with an $O(n)$ time preprocessing; this means we are able to perform
operations like a visit of the graph in $O(m)$ time rather than $O(m+n)$ time.

##  3\. Proximity search outline

Proximity search is based on traversing an implicit solution graph, where the
vertices are all the solutions to be listed and each directed arc goes from a
solution to another using a neighboring function. Several solution graphs are
possible, depending on how the neighboring function is defined. Apart from the
fact that the resulting solution graphs are not necessarily strongly connected
and some care should be taken to list all the solutions, the main hurdle is
that the degree of the solution graphs can be exponential (as the number of
solutions can be exponentially large in the input size), thus preventing to
achieve polynomial delay when running a simple traversal. Proximity search
circumvents these issues by designing a suitable neighboring function, denoted
$\textsc{neighbors}(\cdot)$, that guarantees that the resulting solution graph
it implicitly defines is strongly connected and of polynomial degree. Both
these properties cannot be guaranteed with the current state of the art for a
number of problems discussed later.

We devote this section to formalize the general structure of proximity search,
and the class of problems to which the technique can be applied. Also, we
introduce the notion of proximity, symbolized by $\tilde{\cap}$, to act as a
sort of oracle for navigating the solution graph.

For reference in what we discuss next, we give the pseudo-code of the generic
traversal of a solution graph based on the $\textsc{neighbors}(\cdot)$
function, as shown in Algorithm 1. As noted earlier, the algorithms obtained
by specializing this generic traversal are remarkably simple: In a depth-first
search traversal where the set $\mathcal{S}$ keeps track of just the last
visited solution, we only need to implement the $\textsc{neighbors}(\cdot)$
function. On the other hand, the complexity is mostly hidden behind proving
their completeness: Notably, the very notion of proximity $\tilde{\cap}$ is
only used in the proofs, and never actually appears in Algorithm 1.

1

input : Graph $G=(V,E)$ and listing problem $\mathcal{P}$

output : All (maximal) solutions of $\mathcal{P}$ in $G$

global : Set $\mathcal{S}$ of solutions found, initially empty

2

$S\leftarrow$ an arbitrary solution of $\mathcal{P}$ /* (e.g.
$\textsc{comp}(\emptyset)$) */

3 Call $\textsc{enum}(S)$

4

5

6Function  _$\textsc{enum}(S)$_

7

8 Add $S$ to $\mathcal{S}$

9

/* Output $S$ if recursion depth is even */

10

11 foreach  _$S^{\prime}\in\textsc{neighbors}(S)$_ do

12

13 if  _$S^{\prime}\not\in\mathcal{S}$_ then $\textsc{enum}(S^{\prime})$

14

15

/* Output $S$ if recursion depth is odd */

16

Algorithm 1 Traversal of the solution graph by proximity search.

In order to start the algorithm, we need one arbitrary maximal solution $S$.
We remark that identifying one maximal (not maximum) solution is typically
trivial, and can be achieved for example by running $\textsc{comp}(\emptyset)$
when the $\textsc{comp}(\cdot)$ function is computable in polynomial time.

We formally define the class of problems which allow for a polynomial delay
algorithm using this structure as proximity searchable.

###### Definition 3.1 (Proximity searchable).

Let $\mathcal{P}$ be a listing problem over a universe $\mathcal{U}$ with set
of solutions $\mathcal{S}\subseteq 2^{\mathcal{U}}$, where each solution is a
subset of the universe. $\mathcal{P}$ is proximity searchable if there exists
a proximity function $\tilde{\cap}:\mathcal{S}\times\mathcal{S}\rightarrow
2^{\mathcal{U}}$ and a neighboring function
$\textsc{neighbors}(\cdot):\mathcal{S}\rightarrow 2^{\mathcal{S}}$, such that
the following holds:

  1. (1)

One solution of $\mathcal{P}$ can be identified in time polynomial in
$|\mathcal{U}|$.

  2. (2)

$\textsc{neighbors}(\cdot)$ is computable in time polynomial in
$|\mathcal{U}|$.

  3. (3)

Given any two distinct solutions $S,S^{*}\in\mathcal{S}$, there exists
$S^{\prime}\in\textsc{neighbors}(S)$ such that
$|S^{\prime}\tilde{\cap}S^{*}|>|S\tilde{\cap}S^{*}|$.

The above conditions imply the following one, which is reported for the sake
of clarity.

  1. (4)

For any fixed $S^{*}$, $|S\tilde{\cap}S^{*}|$ is maximized for (and only for)
$S=S^{*}$.

If a problem is proximity searchable, then it is straightforward to see that
we obtain a polynomial delay algorithm for it by using the corresponding
$\textsc{neighbors}(\cdot)$ function in Algorithm 1. Let us formally prove it.

###### Theorem 3.2.

All proximity searchable listing problems have a polynomial delay listing
algorithm.

###### Proof.

We first show that if a $\textsc{neighbors}(\cdot)$ function satisfies
Definition 3.1, the implicit solution graph it induces is strongly connected.
Given any two distinct solutions $S,S^{*}\in\mathcal{S}$, we know by
Definition 3.1.(3) that there exists $S^{\prime}\in\textsc{neighbors}(S)$ such
that $|S^{\prime}\tilde{\cap}S^{*}|>|S\tilde{\cap}S^{*}|$. By induction on $S$
and $S^{\prime}$, it follows that we will eventually reach a solution $S$ that
globally maximizes $|\cdot\tilde{\cap}S^{*}|$, which by Definition 3.1.(4) is
precisely $S^{*}$.

Based on the above properties, we next show that Algorithm 1 outputs (all and
only) the solutions of any proximity searchable problem with no duplication.
Firstly, Algorithm 1 returns only maximal solutions, as it only outputs the
initial maximal solution found on line 1, found polynomial time by Definition
3.1.(1), and the output of calls to $\textsc{neighbors}(S)$ which contain
maximal solutions.

We say that a solution is visited when $\textsc{enum}(S)$ is called. In
Algorithm 1 all solutions added to $\mathcal{S}$ are visited at most once,
thanks to the membership test in the set $\mathcal{S}$; this guarantees that
the same solution is never output twice. As the graph defined by
$\textsc{neighbors}(S)$ is strongly connected, the traversal done by Algorithm
1 starting from the solution found on line 1 must find all solutions.

To complete the proof, we show that Algorithm 1 runs in polynomial delay.

Firstly, $\textsc{neighbors}(S)$ requires polynomial time by Definition
3.1.(2) and thus can only return a polynomial number of solutions; this means
the out-degree of every node in the implicit solution graph is polynomial and
we can iterate over it in polynomial time.

As a new recursive call is performed only when a new solution is found, the
amortized cost per solution is bound by the cost of a recursive call, i.e.,
the cost of lines 1–1. As the cost of $\textsc{neighbors}(\cdot)$ is
polynomial, and $\mathcal{S}$ can be easily maintained in polynomial time (in
Appendix A we show this latter cost to be negligible for all algorithms
presented here), it follows that the amortized cost per solution is
polynomial. In order to get polynomial delay, we can employ the alternative
output (Uno2003, ) method, that can be applied to any recursive algorithm that
outputs a solution in each recursive call: by performing output in pre-order
when the recursion depth is even, and post-order when it is odd, the delay
will be bounded by that of a constant number of recursive calls, i.e.,
polynomial. ∎

The following observations are in order:

  * •

$\tilde{\cap}$ is not actually used in Algorithm 1, and does not need to be
computed.

  * •

Proximity search can be applied to all listing domains where solutions are
modeled by set systems, not just graphs.

  * •

Proximity search is mainly intended for maximal listing problems, however, it
is not strictly limited to it.

  * •

Maximal listing problems in which the input-restricted problem is computable
in polynomial time (as well as the $\textsc{comp}(\cdot)$ function) are
proximity searchable.444In essence, we obtain as a special case the same
solution graph as known algorithms based on the input-restricted problem
(tsukiyama1977new, ; lawler1980generating, ; Cohen20081147, ): For a solution
$S$ we compute $\textsc{neighbors}(S)$ by sequentially taking all elements
$v\in\mathcal{U}\setminus S$, solving the input-restricted problem for
$S\cup\\{v\\}$, and applying $\textsc{comp}(\cdot)$ on the results.

  * •

The polynomiality constraint on $\textsc{neighbors}(\cdot)$ can be relaxed: it
can be trivially seen how computing $\textsc{neighbors}(\cdot)$ in Incremental
Polynomial Time (resp. Polynomial Total Time) yields and Incremental
Polynomial Time (resp. Polynomial Total Time) algorithm.

  * •

The cost per solution and delay of the algorithm is the complexity of the
$\textsc{neighbors}(\cdot)$ function (we show in Appendix A how maintaining
$\mathcal{S}$ is negligible).

In the rest of the paper, we show how to suitably model several problems to
obtain new polynomial-delay algorithms for problems that, to the best of our
knowledge, could not be previously solved in polynomial delay. We show these
algorithms by providing suitable $\tilde{\cap}$ and
$\textsc{neighbors}(\cdot)$ functions, proving that they satisfy Definition
3.1, which automatically give us a polynomial delay listing algorithm by
Algorithm 1.

We will use a common notation: $S$ is an arbitrary solution, and $S^{*}$ the
“target” solution.

(a)(b)(c)(d)(e)(f)

Figure 2. a: a graph. b,c: two maximal connected induced bipartite subgraphs
of (a). d,e: two maximal induced bipartite subgraphs of (a). f: a maximal
edge-induced bipartite subgraph of (a).

##  4\. Proximity search by canonical reconstruction

We make concrete use of the abstract notion of proximity search and introduce
a technique, which we call canonical reconstruction. While it is kept separate
from the previous section for cohesiveness, we find this technique to often be
the right way to look at maximal subgraph listing problems. Since we deal with
graphs, the universe $\mathcal{U}$ is the vertex set, unless explicitly
specified.

To accompany the explanation, we detail its implementation in the case of
Maximal Connected Induced Bipartite Subgraphs in Section 5.

The technique is based on the definitions of canonical order and canonical
extender for solutions, which depend entirely on the problem at hand, and it
is intuitively a way to harness its structure.

###### Example 0.

For a Maximal Connected Induced Bipartite Subgraph $S$, we will use as
canonical order a BFS-order of $G[S]$ starting from its vertex of smallest id,
where ties are broken by vertex id: For the subgraph in Figure 2 (b) this
order is$2,3,5,8,11,7,10$, and for the one in (c) it is $2,3,8,12,11$.

#### Canonical order and proximity

Simply assume that each solution $S$ is given an ordering
$s_{1},\ldots,s_{|S|}$ of its elements which will satisfy some problem-
specific conditions. We require that any prefix $s_{1},\ldots,s_{i}$ of this
order corresponds to a (non-maximal) solution $\\{s_{1},\ldots,s_{i}\\}$. In
the rest of the paper, we will refer as prefix of the order to both the
sequence $s_{1},\ldots,s_{i}$ and the corresponding set of elements
$\\{s_{1},\ldots,s_{i}\\}$. Note that the ordering is _not_ required to be
efficiently computable, as the proximity search algorithm never actually
computes it: it is only used in the correctness proof of the neighboring
function. Moreover, the ordering is adaptive to each solution, so the same
elements can be ranked differently in distinct solutions.

Given the order, we define the proximity function $\tilde{\cap}$ as follows.

###### Definition 4.1 (proximity).

Given two solutions $S$ and $S^{*}$, let $s^{*}_{1},\ldots s^{*}_{|S^{*}|}$ be
the canonical order of $S^{*}$: the proximity $S\tilde{\cap}S^{*}$ between $S$
and $S^{*}$ is the longest _prefix_ $s^{*}_{1},\ldots,s^{*}_{i}$ of the
canonical order of $S^{*}$ whose elements are all contained in $S$.

It should also be noted that the operation is not symmetric, i.e., we may have
$S\tilde{\cap}S^{*}\neq S^{*}\tilde{\cap}S$.

###### Example 0.

Let $S$ be the subgraph shown in Figure 2 (b) and $S^{*}$ the one shown in
(c). Considering the canonical orders mentioned above, we can see that
$S\tilde{\cap}S^{*}=\\{2,3,8\\}$, while $S^{*}\tilde{\cap}S=\\{2,3\\}$.

#### Canonical extender

The goal of a proximity search algorithm is to exploit Definition 3.1.(3):
given $S$, for any $S^{*}$, find some $S^{\prime}$ such that
$|S^{\prime}\tilde{\cap}S^{*}|>|S\tilde{\cap}S^{*}|$. Using Definition 4.1,
$S\tilde{\cap}S^{*}$ is a prefix $s^{*}_{1},\ldots,s^{*}_{i}$ of the canonical
order of $S^{*}$, so we want to find any solution $S^{\prime}$ that contains a
longer prefix, i.e., $s^{*}_{1},\ldots,s^{*}_{i+1}$ (possibly ordered
differently and interspersed in the canonical order of $S^{\prime}$). Since we
must at least add the vertex $s^{*}_{i+1}$, we call $s^{*}_{i+1}$ the
canonical extender of $S,S^{*}$. Armed with this notion, we want to proceed
conceptually as follows for a given solution $S$.

  1. (1)

Guess which node $v\not\in S$ is the canonical extender $s^{*}_{i+1}$ (try all
possibilities, $n$ at most).

  2. (2)

Guess a removable set $X\subseteq S$ from $S\cup\\{v\\}$, i.e., such that
$S\setminus X\cup\\{v\\}$ is a solution and
$X\cap\\{s^{*}_{1},\ldots,s^{*}_{i}\\}=\emptyset$.

  3. (3)

Obtain $S^{\prime}$ as the outcome of $\textsc{comp}(S\setminus
X\cup\\{v\\})$.

In essence, we want to add $s^{*}_{i+1}$ to $S$, then turn the result back
into a solution by removing some elements, but without affecting the proximity
$s^{*}_{1},\ldots,s^{*}_{i}$.

Recalling that prefixes of a canonical order are required to be (non-maximal)
solutions, indeed $s^{*}_{1},\ldots,s^{*}_{i+1}$ is a solution; hence, a
removable set $X$ always exists (e.g.,
$X=S\setminus\\{s^{*}_{1},\ldots,s^{*}_{i}\\}$). The key point is that we want
to satisfy the proximity requirement for all $S^{*}$ (that can be
exponentially many) using only a polynomial number of removable sets $X$.
While there is no general rule for this, and indeed, solving this for some
problems would imply p=np, we will observe in this paper how it is possible to
do so in some cases where a canonical order can efficiently decompose the
underlying structure of the solution.

#### Canonical reconstruction

Now we have all the ingredients to formalize below the required structure for
adopting our strategy.

###### Definition 4.2.

(Proximity search by canonical reconstruction) Given a maximal listing problem
$\mathcal{P}$, in which each maximal solution $S$ is associated with a
canonical ordering $s_{1},\ldots,s_{|S|}$, we say that $\mathcal{P}$ admits a
_canonical reconstruction_ if the following holds.

  1. (1)

Any prefix $s_{1},\ldots,s_{i}$ of the canonical order of any maximal solution
$S$ is a (non-maximal) solution of $~{}\mathcal{P}$.

  2. (2)

Given a maximal solution $S$ and any $v\not\in S$, there is set
$\mathcal{X}\subseteq 2^{S}$ of _removables_ , such that

     * •

$\mathcal{X}=\\{X_{1},X_{2},~{}\ldots\\}$ can be computed in polynomial time.

     * •

$S\setminus X_{i}\cup\\{v\\}$ is a solution of $\mathcal{P}$ for any
$X_{i}\in\mathcal{X}$.

     * •

For any $S^{*}$ such that $v$ is the canonical extender of $S,S^{*}$, there is
at least one $X_{i}\in\mathcal{X}$ such that $(S\tilde{\cap}S^{*})\cap
X_{i}=\emptyset$. 555Indeed, $(S\tilde{\cap}S^{*})\cap X_{i}=\emptyset$, i.e.,
$X_{i}$ does not intersect the proximity, implies that $S\setminus
X_{i}\cup\\{v\\}$ contains $(S\tilde{\cap}S^{*})\cup\\{v\\}$, which extends
the proximity with $v$.

  3. (3)

There is a polynomial-time computable function $\textsc{comp}(A)$ which takes
a solution $A$ of $~{}\mathcal{P}$ and returns a maximal solution
$A^{\prime}\supseteq A$ of $~{}\mathcal{P}$.

We further define the _canonical reconstruction function_ , as

$\textsc{neighbors}(S,v)=\bigcup_{X_{i}\in\mathcal{X}}\textsc{comp}((S\setminus
X_{i})\cup\\{v\\})$

and this corresponds to the solutions $S^{\prime}\in\textsc{neighbors}(S)$ for
which $v$ is the canonical extender of $S,S^{\prime}$. Hence,
$\textsc{neighbors}(S)$ is obtained as $\bigcup_{v\in
V(G)}\textsc{neighbors}(S,v)$.666For completeness, we define
$\textsc{neighbors}(S,v)=\\{S\\}$ for $v\in S$, as $S\cup\\{v\\}=S$ is already
a solution of $\mathcal{P}$.

We observe how the removables and the neighboring function can be derived from
one another, so the algorithm can be defined by providing either one: one can
focus on defining removables from $S\cup\\{v\\}$ that do not intersect the
proximity, or equivalently solutions contained in $S\cup\\{v\\}$ that fully
contain the proximity.

We also recall that a polynomial-time computable function
$\textsc{comp}(\cdot)$ trivially exists for all hereditary and connected-
hereditary properties that can be recognized in polynomial time (these include
all the example problems shown in this paper).

$S=\\{2,3,5,7,8,10,11\\}$, with $S_{0}=\\{2,8,11\\}$, $S_{1}=\\{3,5,7,10\\}$,
and $v=12$$X_{0}=N(v)\cap S_{0}=\\{8,11\\}$, $X_{1}=N(v)\cap
S_{1}=\\{5,7,10\\}$$S\setminus
X_{1}\cup\\{v\\}=\\{2,3,8,11,12\\}$(top)$S\setminus
X_{0}\cup\\{v\\}=\\{2,3,5,7,10,12\\}$, with vertex $9$ added by
$\textsc{comp}(\cdot)$ (bottom)

Figure 3. The steps taken by the neighboring function
$\textsc{neighbors}(S,v)$, for a possible solution $S$ of the graph in Figure
2 and $v=12$. The bottom two lines correspond to the neighboring solutions
produced by the function $\textsc{neighbors}(S,12)$.

Finally, we show how canonical reconstruction immediately implies the maximal
listing problem at hand is proximity searchable, using the
$\textsc{neighbors}(\cdot)$ function defined above:

###### Theorem 4.3.

All maximal listing problems that allow a canonical reconstruction are
proximity searchable.

###### Proof.

Let us show that a listing problem $\mathcal{P}$ that satisfies Definition 4.2
satisfies the four conditions of Definition 3.1. Condition (1) is trivially
satisfied, say, using $\textsc{comp}(\emptyset)$. As for condition (2), recall
that

$\textsc{neighbors}(S)=\bigcup_{v\in
V(G)}\bigcup_{X_{i}\in\mathcal{X}}(\textsc{comp}(S\setminus
X_{i}\cup\\{v\\})).$

Considering that both $|V(G)|$ and $|\mathcal{X}|$ are polynomial, and
$\textsc{comp}(\cdot)$ takes polynomial time, it follows that computing
$\textsc{neighbors}(S)$ takes polynomial time.

For condition (3), consider the canonical extender $v$ for $S,S^{*}$: By
Definition 4.2 there is $X_{i}\in\mathcal{X}$ such that
$X_{i}\cap(S\tilde{\cap}S^{*})=\emptyset$; it holds that
$S^{\prime}=\textsc{comp}(S\setminus
X_{i}\cup\\{v\\})\in\textsc{neighbors}(S,v)\subseteq\textsc{neighbors}(S)$,
and $(S\tilde{\cap}S^{*})\cup\\{v\\}\subseteq S^{\prime}$, thus
$|S^{\prime}\tilde{\cap}S^{*}|>|S\tilde{\cap}S^{*}|$ because of $v$.

Finally, condition (4) is satisfied by looking at the definition of proximity
in Definition 4.1: fixed $S^{*}$, the proximity $S\tilde{\cap}S^{*}$ is
maximized if $S\supseteq S^{*}$, as we have $S\tilde{\cap}S^{*}=S^{*}=S$;
however, as this is a maximal listing problem, all solutions are inclusion-
wise maximal, meaning that $S\supseteq S^{*}$ is only true for $S=S^{*}$. ∎

As a final remark, we note a somewhat surprising feature of this technique:
while in general connected-hereditary properties (e.g., Maximal Connected
Induced Bipartite Subgraphs) are more challenging to deal with than hereditary
ones (e.g., Maximal Induced Bipartite Subgraphs), in the case of proximity
search there is typically no difference, and in some instances, we even use
the connected case as a starting point for the non-connected one (see, e.g.,
Section 5.2).

##  5\. Maximal Bipartite Subgraphs

We now illustrate how to apply proximity search to maximal bipartite subgraph
enumeration, giving the full details for the example in the previous section.

A graph $G$ is bipartite if its vertices can be partitioned into two sets
$V_{0},V_{1}$, such that $V_{0}\cap V_{1}=\emptyset$, $V_{0}\cup V_{1}=V(G)$,
and both $G[V_{0}]$ and $G[V_{1}]$ are edge-less graphs. Equivalently, $G$ is
bipartite if it has no cycle of odd length. Maximal bipartite subgraphs have
also been studied as minimal odd cycle transversals (kratsch2014compression,
), as one is the complement of the other.

The problem of listing all bipartite (and induced bipartite) subgraphs has
been efficiently solved in (wasa2018bipartite, ). However, to the best of our
knowledge, neither the techniques in (wasa2018bipartite, ) nor other known
ones extend to efficiently listing maximal bipartite subgraphs, which poses a
challenge. Consider the instance of input-restricted problem shown in Figure 1
(left). We can exploit the fact that a subgraph of a bipartite graph is itself
bipartite, meaning that the property is hereditary. Hence, we could take the
current solution $S$ (which are the endpoints of the bold edges) and a vertex
$v\not\in S$, to then try to list all the maximal solutions contained in the
induced subgraph $G[S\cup\\{v\\}]$; however, $G[S\cup\\{v\\}]$ has
exponentially many solutions, meaning we cannot solve the input-restricted
problem in polynomial time and thus we cannot get polynomial delay with the
techniques from (lawler1980generating, ; Cohen20081147, ; conte2019framework,
). The best we could hope for is solving the input-restricted problem in
polynomial delay or incremental polynomial time, which would yield an
incremental polynomial time algorithm for the general problem (Cohen20081147,
). Figure 1 (right) shows an analogous situation for edge-induced subgraphs.

We thus turn to proximity search. First, let us introduce some preliminary
notions: We denote an induced bipartite subgraph of $G$ as a pair of vertex
sets $\langle B_{0},B_{1}\rangle$, with $B_{0}\cap B_{1}=\emptyset$ and
$B_{0}\cup B_{1}\subseteq V(G)$, such that $G[B_{0}]$ and $G[B_{1}]$ are edge-
less graphs. By convention, $B_{0}$ is the side of the bipartition containing
the vertex of smallest label among those in the subgraph. In case $G[B_{0}\cup
B_{1}]$ has multiple connected components, this applies to all components.
This way, any bipartite subgraph (connected or not) always has a _unique_
representation $\langle B_{0},B_{1}\rangle$. We will sometimes use simply $B$
to refer to the subgraph $G[B_{0}\cup B_{1}]$ induced by $\langle
B_{0},B_{1}\rangle$. When performing $\textsc{comp}(B)$ (defined at the end of
Section 2) and $B$ is not connected, this may move some vertices from $B_{0}$
to $B_{1}$ and vice versa due to different components becoming connected; even
when $B$ is connected, if a vertex with smaller label than all others in $B$
is added to $B_{1}$, then $B_{0}$ and $B_{1}$ are immediately swapped to
preserve the invariant of the smallest vertex being in $B_{0}$. We define the
intersection between two bipartite subgraphs $B$ and $B^{\prime}$ as the set
of all shared vertices, i.e.: $B\cap B^{\prime}=(B_{0}\cup
B_{1})\cap(B^{\prime}_{0}\cup B^{\prime}_{1})$.

We consider the case of connected induced bipartite subgraphs in Section 5.1.
We will later briefly show how this structure can be adapted to cover the non-
connected and non-induced cases with small changes in Sections 5.2 and 5.3.
Their complexity will be discussed in Section 5.4.

###  5.1. Listing Maximal Connected Induced Bipartite Subgraphs

Let $B=\langle B_{0},B_{1}\rangle$ be a maximal induced bipartite subgraph of
$G$, and $v$ a vertex not in $B$, i.e., in $v\in V(G)\setminus B$. Looking at
Definition 4.2, we immediately observe that a polynomial-time computable
function $\textsc{comp}(\cdot)$ exists since the problem is connected-
hereditary. Then, we need to define a suitable canonical order, and prove the
existence of the corresponding removables.

Consider a BFS order of $G[B]$ starting from its vertex of smallest label, say
$b_{1}$. In this order, a vertex $u$ precedes a vertex $v$ if the distance of
$u$ from $b_{1}$ is smaller than that of $v$ or, in case the distance is
equal, $u$’s label is smaller than $v$’s.

###### Definition 5.1 (canonical order for connected induced bipartite
subgraphs).

The _canonical_ order of a _connected induced bipartite subgraph_ $B$ is the
sequence $b_{1},\ldots,b_{|B|}$ given by a BFS order of $G[B]$ rooted at the
vertex $b_{1}$ of smallest label, where ties are broken by placing the vertex
of smallest label first.

For the subgraph in Figure 2 (b) the canonical order is $2,3,5,8,11,7,10$, and
for the one in (c) it is $2,3,8,12,11$. The definition of proximity is then
automatically given by Definition 4.1.

Last ingredient for Definition 4.2 is the set $\mathcal{X}\subseteq 2^{B}$,
that contains just _two_ removables. In order to get a bipartite graph, it is
possible to make two removables as follows:

  * •

$X_{0}=N(v)\cap B_{0}$,

  * •

$X_{1}=N(v)\cap B_{1}$.

That is, remove all the neighbors of $v$ in one of the two sides $B_{i}$:
clearly, $v$ can be included in $B_{i}$ as it is now only adjacent to vertices
of $B_{1-i}$. While this works for the Maximal Induced Bipartite Subgraphs
problem, we have the further constraint of connectivity, so we must also
discard every vertex that is not in the same connected component as $v$. The
removables become as follows:

  * •

$X_{0}=B\setminus\texttt{cc}_{v}(\\{v\\}\cup(B_{0}\setminus N(v))\cup B_{1})$,

  * •

$X_{1}=B\setminus\texttt{cc}_{v}(\\{v\\}\cup(B_{1}\setminus N(v))\cup B_{0})$.

That is, we remove all vertices not in the same connected component as $v$,
after introducing $v$ and removing all its neighbors in either $B_{0}$ or
$B_{1}$.

We can use these to create the neighboring function to be plugged in Algorithm
1, following Definition 4.2:

###### Definition 5.2 (neighboring function for maximal connected induced
bipartite subgraphs).

$\textsc{neighbors}(B,v)=\\{\textsc{comp}(\texttt{cc}_{v}(\\{v\\}\cup(B_{i}\setminus
N(v))\cup B_{1-i}))\mid i=0,1\\}$

A graphical example of this procedure is given in Figure 3 (for simplicity, we
adopt an example where the subgraphs are connected after removing $v$’s
neighbors, so the removables are equivalent to the simpler ones of the non-
connected version).

###### Lemma 5.3.

The problem of listing all Maximal Connected Induced Bipartite Subgraphs
admits a canonical reconstruction.

###### Proof.

For the canonical order given in Definition 5.1, any prefix induces a graph
that is connected because of the BFS order, and bipartite because bipartite
subgraphs are hereditary, so condition (1) of Definition 4.2 is satisfied. As
for condition (2), it is evident from the definition of removables
(alternatively, of the neighboring function) that they can be computed in
polynomial time, and that they produce connected bipartite subgraphs. We only
need to show that the third item holds: given $B$, $B^{*}$ and their canonical
extender $\dot{v}$, we have $B\tilde{\cap}B^{*}\cap X_{i}=\emptyset$ for
either $i=0$ or $i=1$; this will imply that
$|B^{\prime}\tilde{\cap}B^{*}|>|B\tilde{\cap}B^{*}|$ for
$B^{\prime}=\textsc{comp}(\texttt{cc}_{\dot{v}}(\\{\dot{v}\\}\cup(B_{i}\setminus
N(\dot{v}))\cup B_{1-i}))$, so the proximity is successfully increased.

If $B\tilde{\cap}B^{*}=\emptyset$ the claim is trivially true, as we can
consider $b^{*}_{1}$ as canonical extender. Otherwise, let
$Z=B\tilde{\cap}B^{*}=\\{b^{*}_{1},\ldots,b^{*}_{h}\\}$, and we have
$\dot{v}=b^{*}_{h+1}$. By Definition 5.1, $Z$ is a connected induced bipartite
subgraph, meaning that it allows a unique bipartition $Z_{0},Z_{1}$ (with
$Z_{0}$ being the set containing the vertex of smallest label in $Z$, that is,
$b^{*}_{1}$). Since $b^{*}_{1}$ is the vertex of smallest label in $B^{*}$, it
will be in $B^{*}_{0}$, so it follows that $Z_{0}\subseteq B^{*}_{0}$ and
$Z_{1}\subseteq B^{*}_{1}$.

Let $j$ be the value in $\\{0,1\\}$ such that $\dot{v}\in B^{*}_{j}$, and
observe that $N(\dot{v})\cap Z_{j}\subseteq N(\dot{v})\cap
B^{*}_{j}=\emptyset$. Furthermore, we know that $b^{*}_{1}\in B^{*}_{0}$ and
$b^{*}_{1}\in B$, but we do not know whether $b^{*}_{1}\in B_{0}$ or
$b^{*}_{1}\in B_{0}$; however, there exists a value $i$ in $\\{0,1\\}$ such
that either $b^{*}_{1}\in(B_{i}\cap B^{*}_{j})$ or $b^{*}_{1}\in(B_{1-i}\cap
B^{*}_{1-j})$. Observe that $Z_{j}\subseteq B^{*}_{j}\cap B_{i}$ and
$Z_{1-j}\subseteq B^{*}_{1-j}\cap B_{1-i}$.

Finally, let
$B^{\prime}=\texttt{cc}_{\dot{v}}(\\{\dot{v}\\}\cup(B_{i}\setminus
N(\dot{v}))\cup B_{1-i})$, and consequently we have $X_{i}=B\setminus
B^{\prime}$. $Z$ is fully contained in $B^{\prime}$: the only vertices removed
from $B$ by $X_{i}$ are (i) those in $N(\dot{v})\cap B_{i}$, but
$N(\dot{v})\cap B_{i}\cap Z\subseteq N(\dot{v})\cap B_{i}\cap Z_{j}\subseteq
N(\dot{v})\cap Z_{j}=\emptyset$, and (ii) the vertices not in the connected
component of $\dot{v}$ in $G[\\{\dot{v}\\}\cup(B_{i}\setminus N(\dot{v}))\cup
B_{1-i}]$, but no such vertex can be in $Z$ as $Z\cup\\{\dot{v}\\}$ is a
prefix of the canonical order of $B^{*}$, so it induces a connected subgraph.

We thus have that $Z\cup\\{\dot{v}\\}\subseteq B^{\prime}$, meaning that
$X_{i}\cap Z=\emptyset$, which proves the claim. Constructively, we can
finally observe how the maximal solution
$B^{\prime\prime}=\textsc{comp}(B^{\prime})$ is the one produces by the
algorithm which increases the proximity to $B^{*}$, as we have
$\\{b^{*}_{1},\ldots,b^{*}_{h},b^{*}_{h+1}\\}\subseteq
B^{\prime\prime}\tilde{\cap}B^{*}$ and thus
$|B^{\prime\prime}\tilde{\cap}B^{*}|\geq|B\tilde{\cap}B^{*}|+1$. ∎

From this, we immediately obtain the correctness of the algorithm.

###### Theorem 5.4.

A proximity search algorithm (Algorithm 1), using
the$\textsc{neighbors}(\cdot)$ function from Definition 5.2 outputs all
Maximal Connected Induced Bipartite Subgraphs of a graph $G$ without
duplication with $O(nm)$ delay.

###### Proof.

The correctness follows from Theorem 4.3. The delay is dominated by the cost
of the $\textsc{neighbors}(B)$ function, i.e., calling $O(n)$ times
$\textsc{neighbors}(B,v)$. The cost of the latter is $O(m)$ time to compute
$\texttt{cc}_{v}(\cdot)$, and $O(m)$ time to compute the
$\textsc{comp}(\cdot)$ function by Lemma 5.9 (delayed to Section 5.4 for
compactness). The statement follows. ∎

###  5.2. Listing Maximal Induced Bipartite Subgraphs

We can extend our solution to the non-connected case by building one connected
component at a time. We obtain the canonical order by Definition 11.6, that
is, a BFS order of each component:

###### Definition 5.5 (canonical order for induced bipartite subgraphs).

The _canonical_ order of an _induced bipartite subgraph_ $B$ is the sequence
$b_{1},\ldots,b_{|B|}$ obtained by first ordering the connected components of
$G[B]$ by incremental order of smallest-id vertex, then ordering each
component by a BFS order (given in Definition 5.1) rooted in its smallest-id
vertex.

In essence, this corresponds to ordering each connected component as in the
connected case (Definition 5.2), and placing earlier components whose
smallest-id vertex is smaller. Looking again at Figure 2, and letting $B$ be
the subgraph shown in (d) and $B^{*}$ as that shown in (e), the canonical
order of $B$ is $\langle 1,2,7,8,11,10\rangle$, that of $B^{*}$ is $\langle
1,2,7,9,12,10\rangle$. By the definition of proximity for canonical
reconstruction, we also obtain $B\tilde{\cap}B^{*}=\\{1,2,7\\}$.

The removables become simpler for this case, as we can simply remove $N(v)\cap
B_{i}$ for $i=0,1$. As a result, the neighboring function is essentially the
same as the connected case (Definition 5.2), with minor changes as we do not
require the connectivity:

###### Definition 5.6 (neighboring function for maximal induced bipartite
subgraphs).

$\textsc{neighbors}(B,v)=\\{\textsc{comp}(\\{v\\}\cup(B_{i}\setminus N(v))\cup
B_{1-i})\mid i=0,1\\}$

We can then proceed to prove correctness and complexity of this case:

###### Theorem 5.7.

A proximity search algorithm (Algorithm 1), using
the$\textsc{neighbors}(\cdot)$ function from Definition 5.6 outputs all
maximal induced bipartite subgraphs of a graph $G$ without duplication with
$O(n(m+n\alpha(n)))$ delay.

###### Proof.

Consider the solutions $B$ and $B^{*}$. Let $b^{*}_{1},\ldots,b^{*}_{|B^{*}|}$
be the canonical ordering of $B^{*}$ by Definition 5.6,
$B\tilde{\cap}B^{*}=b^{*}_{1},\ldots,b^{*}_{i}$, and $u=b^{*}_{i+1}$ the
canonical extender for $B,B^{*}$. Let $C$ be the connected component of
$B^{*}$ containing $u$. Since all the neighbors of $u$ in $B^{*}$ must be in
its same connected component $C^{B^{*}}_{x}$, and the neighbouring function
(Definition 5.6) only removes neighbors of $u$ from $B$, the function may not
remove from $B$ any vertex of $B^{*}$ that is not in $C$. As for vertices in
$C$, $B\tilde{\cap}B^{*}$ contains a (possibly empty) prefix of its BFS order,
which is itself a connected bipartite subgraph in canonical order. By the
correctness of Lemma 5.3, for either
$B^{\prime}=\textsc{comp}(\texttt{cc}_{v}(\\{v\\}\cup(B_{0}\setminus N(v))\cup
B_{1}))$ or
$B^{\prime}=\textsc{comp}(\texttt{cc}_{v}(\\{v\\}\cup(B_{1}\setminus N(v))\cup
B_{0}))$, this prefix is expanded with $u$, giving us
$B^{\prime}\tilde{\cap}B^{*}\supseteq(B\tilde{\cap}B^{*})\cup\\{u\\}$ and
proving correctness.

As for the delay, we can see that the cost of $\textsc{neighbors}(B)$ is
bounded as for the connected case by $O(n)$ times the cost of
$\textsc{neighbors}(B,v)$, which is in turn bounded by $O(m+n\alpha(n))$ by
Lemma 5.9, proving the statement.

∎

###  5.3. Maximal Edge Bipartite Subgraphs

Finally, we show how to adapt the above algorithm to Maximal Edge Bipartite
Subgraphs, where edge-induced subgraphs are denoted by a set of edges, rather
than vertices. In the following, given two sets of vertices $A$ and $B$, let
$E(A,B)$ be the set of edges with one endpoint in $A$ and the other in $B$. We
observe that the Maximal Edge Bipartite Subgraphs of a connected graph are
always connected, otherwise some edge could be added to joint components
without creating cycles; by the same logic they span all vertices, and may
thus be represented by simply a bipartition $\langle B_{0},B_{1}\rangle$ of
$V(G)$, where the bipartite subgraph corresponds to the edges in
$E(B_{0},B_{1})$. For readability, we use the shorthand $E_{B}\equiv
E(B_{0},B_{1})$ to refer to the edges of the bipartite subgraph $B$.

We also observe that the problem is hereditary and allows for a polynomial
time computable $\textsc{comp}(\cdot)$ function. We define the canonical order
of a solution $B$ by taking the canonical order $b_{1},\ldots,b_{|B|}$ of the
vertices of $G[B]$ according to Definition 5.1,777Note that the vertices of
$G[B]$ are all of $V(G)$, but to compute the canonical order we need to
consider only the edges in the bipartite subgraph $G[B]$. then taking the
edges of $B$ in increasing order of their latter vertex in the vertex order,
and breaking ties by increasing order of the earlier endpoint. This
essentially corresponds to “building” $B$ in a similar fashion as in the
induced version, but adding one edge at a time incident to the newly selected
vertex. The removables for an edge $e=\\{a,b\\}$, where $a<b$, are as follows.

  * •

$X_{0}=(E_{B}\setminus N_{E}(a))\cup\\{e\\})$,

  * •

$X_{1}=(E_{B}\setminus N_{E}(b))\cup\\{e\\})$.

The principle behind the neighboring function is different but inspired by the
induced case: rather than taking a vertex out of the solution and trying to
add it to $B_{0}$ or $B_{1}$, we take an edge $e=\\{a,b\\}$ with both
endpoints in the same $B_{i}$, and try to move the two vertices $a$ and $b$ to
opposite sides of the bipartition.

This can be achieved by including the edge $e$ in the solution, and then, to
preserve the subgraph being bipartite, removing either $N_{E}(a)$ or
$N_{E}(b)$ from it. Finally we apply the $\textsc{comp}(\cdot)$ function to
obtain a solution that is maximal.

More formally, recalling $E_{B}\equiv E(B_{0},B_{1})$, we define
$\textsc{neighbors}(B)$ as

$\bigcup\limits_{e=\\{a,b\\}\in E(G)\setminus
E_{B}}\\{\textsc{comp}((E_{B}\setminus
N_{E}(a))\cup\\{e\\}),\;\textsc{comp}((E_{B}\setminus
N_{E}(b))\cup\\{e\\})\\}$

Consider two solution $B$ and $B^{*}$, with
$e_{1},\ldots,e_{|E(B^{*}_{0},B^{*}_{1})|}$ being the canonical order of
$B^{*}$. Furthermore, let $B\tilde{\cap}B^{*}=\\{e_{1},\ldots,e_{h}\\}$ and
$\dot{e}=e_{h+1}=\\{a,b\\}$ the canonical extender, i.e., the first edge in
the ordering of $B^{*}$ which is not in $B$.

By the definition of the canonical ordering, we have that
$\\{e_{1},\ldots,e_{h}\\}$ is a connected bipartite subgraph, meaning that it
allows a unique bipartition $B^{\prime}=B^{\prime}_{0},B^{\prime}_{1}$ of its
incident vertices. As $\\{e_{1},\ldots,e_{h}\\}\cup\\{\dot{e}\\}$ is also a
connected bipartite subgraph, for some $j\in\\{0,1\\}$ we must have both
$N(a)\cap B^{\prime}_{j}=\emptyset$ and $N(b)\cap B^{\prime}_{1-j}=\emptyset$.

Since $B^{\prime}$ is included in $B$, we must have either (i)
$B^{\prime}_{j}\subseteq B_{i}$ and $B^{\prime}_{1-j}\subseteq B_{1-i}$ or
(ii) $B^{\prime}_{1-j}\subseteq B_{i}$ and $B^{\prime}_{j}\subseteq B_{1-i}$.
Recall now that both $a$ and $b$ are assumed wlog to be in $B_{i}$, meaning
that $N(a)\cap B_{i}=N(b)\cap B_{i}=\emptyset$. In the (i) case, we have
$N(b)\cap B_{1-i}\cap B^{\prime}_{1-j}=\emptyset$, so removing $N_{E}(b)$ from
$B$ may not remove any edge of $B^{\prime}$. Thus
$\textsc{comp}((E_{B}\setminus N_{E}(b))\cup\\{\dot{e}\\})$, which belongs to
$\textsc{neighbors}(B)$, will contain $(B\tilde{\cap}B^{*})\cup\\{e\\}$.

In the (ii) case, we have $N(a)\cap B_{1-i}\cap B^{\prime}_{1-j}=\emptyset$,
removing $N_{E}(a)$ may not remove any edge of $B^{\prime}$. Thus
$\textsc{comp}((E_{B}\setminus N_{E}(a))\cup\\{\dot{e}\\})$, which also
belongs to $\textsc{neighbors}(B)$, will contain
$(B\tilde{\cap}B^{*})\cup\\{e\\}$.

This means that in both cases, $\textsc{neighbors}(B)$ will yield a solution
$S^{\prime}$ that contains $(B\tilde{\cap}B^{*})\cup\\{e\\}$, i.e., such that
$|S^{\prime}\tilde{\cap}S^{*}|>|S\tilde{\cap}S^{*}|$.

As the complexity is bounded by $O(m)$ calls to the
$\textsc{neighbors}(B_{i},B_{1-i},e)$ function, whose cost is again bounded by
that of $\textsc{comp}(\cdot)$, that is $O(m^{2})$ time (By Lemma 5.9), the
following theorem holds:

###### Theorem 5.8.

Maximal (edge-induced) Bipartite Subgraphs can be listed in $O(m^{3})$ time
delay.

###  5.4. Complexity

In order to complete the analysis, let us look at the cost $\mathcal{C}_{t}$
for the three variants considered:

###### Lemma 5.9.

$\mathcal{C}_{t}$ is $O(m)$ for Maximal Connected Induced Bipartite Subgraphs,
$O(m+n\alpha(n))$ for Maximal Induced Bipartite Subgraphs, and $O(m^{2})$ for
Maximal Edge-induced Bipartite Subgraphs, where $n$ and $m$ are the number of
vertices and edges, and $\alpha(\cdot)$ is the functional inverse of the
Ackermann function (Tarjan75UF, ).

###### Proof.

$\mathcal{C}_{t}$ is a bound for computing the $\textsc{comp}(S)$ function as
well as a canonical order. As the latter is computed by a BFS, it takes $O(m)$
time in all three cases, let us then focus on $\textsc{comp}(S)$:

Firstly, observe that using $O(n)$ space and standard data structures, we can
mark to which bipartition each vertex of $S$ belongs to (using $O(m)$ time to
compute the initial bipartition of $S$), and which vertices have been already
tested for addition, in $O(1)$ time per vertex. If a vertex fails the test to
be added, it will not be possible to add it later on, so the total cost of
$\textsc{comp}(S)$ comes from selecting which vertices to test, and testing
each of these vertices once.

For the connected case, we must test only vertices adjacent to $S$ (in no
particular order): we can find these initial “candidates” in $O(\sum_{x\in
S}|N(x)|)=O(m)$ time, marking each vertex as tested the first time so it is
not tested again. Whenever trying to add a vertex $v$ to $S$, we must pay
$O(|N(v)|)$ time to check that all its neighbors belong to the same
bipartition of $S$, in which case $v$ belongs to the other one. If $v$ is not
addible, we immediately discard it. If instead we add it to $S$, we mark it
with the correct bipartition, and update the list of candidate with its
neighbors in $O(|N(v)|)$ time. As each vertex is only tested once and only
added once, the total cost of $\mathcal{C}_{t}$ is bounded by $O(m)$.

For the non-connected case, we further keep track of connected components via
union-find (Tarjan75UF, ) (actually, for each connected component we will keep
track of its two partitions). To test a vertex $v$ we must just check that it
does not connect to two vertices in different partitions $C_{0}$ and $C_{1}$
of the same connected component $C$ of $X$: this can be done in $O(|N(v)|)$.
Updating the union-find can be done in total $O(n\alpha(n))$, where
$\alpha(\cdot)$ is the functional inverse of the Ackermann function
(Tarjan75UF, ).888As $\alpha(n)$ grows extremely slowly, we remark that
$\alpha(n)$ is in essence $O(1)$ on real, finite, graphs.

Once we tested a vertex, if this was not addible, it will never become
addible, thus we only need to test each vertex once. The cumulative cost for
testing will be the sum of the degrees of all tested vertices, that is bounded
by $O(m)$. The total time is thus $O(m+n\alpha(n))$.

Finally, for Maximal Edge-induced Bipartite Subgraphs, we need to test each
edge for addition just once as the property is hereditary. For each test we
can simply check if the resulting graph is bipartite, which takes $O(m)$ time,
for a total cost of $O(m^{2})$. ∎

##  6\. Maximal k-Degenerate Subgraphs

We here consider the enumeration of maximal $k$-degenerate subgraphs, giving
an algorithm that has polynomial delay when $k$ is bounded.

A graph $G$ is $k$-degenerate if it allows an elimination order where each
vertex has degree at most $k$ when deleted. Equivalently, it is $k$-degenerate
if no subgraph of $G$ is a $(k+1)$-core, that is a graph where each vertex has
degree greater or equal to $k+1$. The degeneracy $d$ of $G$ is the smallest
$k$ for which $G$ is $k$-degenerate.

A degeneracy ordering of $G$ is an order of its vertices in which each vertex
$v$ has at most $d$ neighbors occurring later than $v$, where $d$ is the
degeneracy of $G$. It is well known that a degeneracy ordering can be found in
$O(m)$ time by iteratively removing the vertex of smallest degree
(DBLP:journals/corr/cs-DS-0310049, ). To remove ambiguity, when multiple
vertices have the same degree we can remove the one with smallest label.

The degeneracy is a well-known sparsity measure (EppsteinLS13, ); its
definition generalizes that of independent sets ($0$-degenerate graphs) and
trees and forests (connected and non-connected $1$-degenerate graphs).
Furthermore, degeneracy is linked to planarity as all planar graphs are
$5$-degenerate, while outerplanar graphs are $2$-degenerate (lick1970k, ).

We are interested in listing all maximal $k$-degenerate subgraphs of a graph
$G$. An output-polynomial algorithm is known for maximal induced
$k$-degenerate subgraphs if $G$ is chordal (DBLP:conf/cocoon/ConteKOUW17, ),
but no output-polynomial results are known for general graphs.

###  6.1. Maximal Induced k-Degenerate Subgraphs

A subgraph of a $k$-degenerate graph is $k$-degenerate so the property is
hereditary, and degeneracy can be computed in linear time so we can implement
the $\textsc{comp}(\cdot)$ function in polynomial time.

Given a maximal induced $k$-degenerate subgraph $S$, we define its canonical
order as the reverse of its degeneracy ordering, i.e., an ordering
$s_{1},\ldots,s_{|S|}$, such that $s_{|S|},\ldots,s_{1}$ is the degeneracy
ordering of $S$. In the case of non connected subgraphs, this is adapted by
considering the connected components one at a time in lexicographical order.
Then, the proximity is defined by Definition 4.1.

In the resulting ordering we have
$|N(s_{i})\cap\\{s_{1},\ldots,s_{i-1}\\}|\leq k$, i.e., the neighbors of
$s_{i}$ in $S$ that precede $s_{i}$ in the canonical order are at most $k$.
This is the key property that gives us the intuition for the algorithm: the
removables correspond to all neighbors of the canonical extender except a set
of size at most $k$. The neighboring function is obtained as follows.

###### Definition 6.1 (Neighboring function for Maximal Induced $k$-Degenerate
Subgraphs).

$\textsc{neighbors}(S)=\bigcup\limits_{v\in V(G)}\textsc{neighbors}(S,v)$

Where $\textsc{neighbors}(S,v)=\\{\textsc{comp}(\\{v\\}\cup
S\setminus(N(v)\setminus K):K\subseteq(S\cap N(v))\text{ and }|K|\leq k\\}$

Less formally, when computing $\textsc{neighbors}(S,v)$, we try to add $v$ to
$S$ as canonical extender. Since $S$ is maximal, this violates the degeneracy
constraint, so we remove all neighbors of $v$ except at most $k$ (the
removable set being $N(v)\setminus K$). The resulting subgraph $D=\\{v\\}\cup
S\setminus(N(v)\setminus K)$ is $k$-degenerate: as $D\setminus\\{v\\}$ is
$k$-degenerate as it is a subgraph of $S$, and any degeneracy ordering of
$D\setminus\\{v\\}$ becomes a $k$-degenerate ordering for $D$ if we prepend
$v$ in the beginning, because $v$ has at most $k$ neighbors in $D$. This means
$N(v)\setminus K$ is a suitable removable according to Definition 4.2.

We now show how these choices for $K$ satisfy Definition 4.2: we iteratively
try for $K$ all possible subsets of $S\cap N(v)$ of size at most $k$. These
combinations, i.e., the number of removables, are
$O(\sum_{i\in\\{1,\ldots,k\\}}\binom{|N(v)|}{i})=O(n^{k})$, which is
polynomial when $k$ is bounded.

Let us now look at a target solution $S^{*}$ such that $v$ is the canonical
extender for $S,S^{*}$, and let $s^{*}_{1},\ldots,s^{*}_{|S^{*}|}$ be the
canonical order of $S^{*}$: if $v=s_{i}$ in this order, it follows that
$S\tilde{\cap}S^{*}=\\{s^{*}_{1},\ldots,s^{*}_{i-1}\\}$, and
$|N(v)\cap\\{s^{*}_{1},\ldots,s^{*}_{i-1}\\}|\leq k$.

We also have that $\\{s^{*}_{1},\ldots,s^{*}_{i-1}\\}\subseteq S$, so
$N(v)\cap\\{s^{*}_{1},\ldots,s^{*}_{i-1}\\}\subseteq N(v)\cap S$: since we try
as $K$ all possible subsets of $N(v)\cap S$ of size at most $k$, we will
eventually have $K=N(v)\cap\\{s^{*}_{1},\ldots,s^{*}_{i-1}\\}$.

At this point the neighboring function will yield
$S^{\prime}=\textsc{comp}(\\{v\\}\cup S\setminus(N(v)\setminus
K)=\textsc{comp}(\\{v\\}\cup S\setminus(N(v)\setminus(S\tilde{\cap}S^{*}))$.
In other words, we only remove some neighbors of $v$ from $S$, but all the
neighbors that are part of $S\tilde{\cap}S^{*}$ are not removed, thus
$S^{\prime}\supseteq\\{v\\}\cup(S\tilde{\cap}S^{*})$, meaning
$|S^{\prime}\tilde{\cap}S^{*}|>|S\tilde{\cap}S^{*}|$.

As for the running time, let us consider the cost $\mathcal{C}_{t}$ of a
$\textsc{comp}(X)$ call. $k$-degenerate graphs are hereditary, i.e., if a
vertex is not addible it will not become addible later, so we need to test
each $v\in V(G)\setminus X$ for addition at most once. As testing the
degeneracy takes $O(m)$ time, $\mathcal{C}_{t}=O(mn)$ time.

Consider now $\textsc{neighbors}(S,v)$: firstly, we enumerate each possible
$K\subseteq N(v)\cap S$, which takes
$O(\sum_{i\in\\{1,\ldots,k\\}}\binom{|N(v)|}{i})=O(|N(v)|^{k})$ time. For
each, we run $\textsc{comp}(\\{v\\}\cup(S\setminus N(v))\cup K)$, which takes
$O(mn)$ time. The total cost is $O(n^{k+1}m)$ time.

The problem is thus proximity searchable, and the delay of the listing
algorithm is the cost of $\textsc{neighbors}(S)$, i.e., running $O(n)$ times
$\textsc{neighbors}(S,v)$ (maintaining $\mathcal{S}$ is negligible). More
formally:

###### Theorem 6.2.

Maximal Induced $k$-degenerate Subgraphs are proximity searchable when $k$ is
constant, and can be enumerated in $O(mn^{k+2})$ time delay.

We now observe that $1$-degenerate subgraphs are exactly forests, and the
connected ones are trees; setting $k=1$ we immediately obtain polynomial-delay
algorithms for listing Maximal Induced Forests that could be easily adapted to
Maximal Induced Trees. However, an ad-hoc analysis, delayed to Section 12.2,
shows we can obtain algorithms with better delay, and even reduce the space
usage to polynomial for these problems.

###  6.2. Maximal Edge-induced k-Degenerate Subgraphs

We now consider Maximal Edge-induced k-Degenerate Subgraphs, i.e., maximal
sets of edges $E\subseteq E(G)$ that correspond to a $k$-degenerate subgraph
of $G$. An algorithm for this case can be obtained by exploiting the structure
of the induced one. In the following, let $N_{E}(v)$ be the edge neighborhood
of $v$, i.e., the set of edges of $G$ incident to the vertex $v$. Note that
edge-induced $k$-degenerate subgraphs are also hereditary, and so
$\textsc{comp}(\cdot)$ takes polynomial time.

Let $S$ be an edge-induced $k$-degenerate subgraph, and let
$v_{1},\ldots,v_{l}$ be the canonical order of the vertices of $G[S]$ (i.e.,
the graph containing only edges in $S$ and vertices incident to them), as in
Section 6.1.

The canonical ordering of $S$ is obtained by selecting the edges of $B$ by
increasing order w.r.t. their later endpoint in the vertex order, breaking
ties by order of the other (earlier) endpoint.

This corresponds to selecting the vertices $v_{1},\ldots,v_{l}$ in order, and
for each adding the edges towards the preceding vertices one by one. Whenever
all the edges from $v_{i}$ to the preceding vertices have been added, we can
observe that the graph corresponds to that induced in $G[S]$ by the vertices
$\\{v_{1},\ldots,v_{i}\\}$. By the canonical order of the vertices defined in
Section 6.1, this means $v_{i}$ has at most $k$ neighbors in
$\\{v_{1},\ldots,v_{i-1}\\}$.

Again, the proximity $\tilde{\cap}$ is given by Definition 4.1.

We can now define the neighboring function:

###### Definition 6.3 (Neighboring function for Maximal Edge-induced
$k$-DegenerateSubgraphs).

Let $S$ be a maximal edge-induced $k$-degenerate subgraph, and $e=\\{a,b\\}$
an edge not in $S$. We define:

$\textsc{neighbors}(S)=\bigcup\limits_{e=\\{a,b\\}\in E\setminus
S}\textsc{neighbors}(S,a,b)\cup\textsc{neighbors}(S,b,a)$

Where $\textsc{neighbors}(S,a,b)=\\{\textsc{comp}(\\{e\\}\cup(S\setminus
N_{E}(a))\cup K):K\subseteq(S\cap N_{E}(a))\text{ and }$$|K|\leq k-1\\}$

In other words, we add an edge $e=\\{a,b\\}$ to $S$, then force $a$ (or,
respectively, $b$) to have degree at most $k$, by removing all other edges
incident to it except at most $k-1$, as well as adding $e$. The resulting
graph is $k$-degenerate as $a$ (respectively $b$) has degree $k$, and the
residual graph is a subgraph of $S$, which is $k$-degenerate, so it is
possible to compute a degeneracy ordering.

Consider now two solutions $S$, $S^{*}$, with
$S\tilde{\cap}S^{*}=\\{e_{1},\ldots,e_{h}\\}$, and let $\dot{e}=\\{x,y\\}$ be
the earliest edge in the canonical order of $S^{*}$ that is not in $S$, i.e,
$e_{h+1}$. Assume wlog that $x$ comes before $y$ in the canonical (vertex)
ordering of $S^{*}$. In this ordering, $y$ has at most $k$ neighbors preceding
it, i.e, $|\\{e_{1},\ldots,e_{h}\\}\cap N_{E}(y)|\leq k$. Furthermore, by the
same definition, all edges incident to $y$ that precede $\dot{e}$ in the
ordering must be between $y$ and another vertex which comes earlier than $x$,
and thus than $y$, in the ordering, thus they may be at most $k-1$ ($k$,
including $\dot{e}$ itself, from $y$ to $x$). Let $K^{\prime}$ be the set of
these edges (not including $\dot{e}$).

When computing $\textsc{neighbors}(S,y,x)$, we consider all subsets of edges
in $S$ incident to $y$ of size at most $k-1$. By what stated above, at some
point we will consider exactly $K^{\prime}$. In this case, we will obtain
$S^{\prime}=\textsc{comp}(\\{\dot{e}\\}\cup(S\setminus N_{E}(y))\cup
K^{\prime})$. This must contain all edges in $\\{e_{1},\ldots,e_{h}\\}$, as we
only removed edges neighboring $y$, but all those in
$\\{e_{1},\ldots,e_{h}\\}$ were in $K^{\prime}$. Thus we have
$\\{e_{1},\ldots,e_{h}\\}\cup\dot{e}=\\{e_{1},\ldots,e_{h},e_{h+1}\\}\subseteq
S^{\prime}$, which implies
$|S^{\prime}\tilde{\cap}S^{*}|>|S\tilde{\cap}S^{*}|$. The case in which $x$
comes after $y$ in the ordering is similarly satisfied by
$\textsc{neighbors}(S,x,y)$.

Finally, we only need to show that $\textsc{neighbors}(S)$ takes polynomial
time to compute: indeed this is $O(m)$ times the cost of
$\textsc{neighbors}(S,y,x)$, which in turn has the cost of computing
$\textsc{comp}(\cdot)$ once for each possible considered set $K$. These latter
are $O(\binom{N_{E}(y)}{k-1})$, and the $\textsc{comp}(\cdot)$ can be easily
implemented in $O(m^{2})$ (as above, testing degeneracy takes $O(m)$ time and
each edge needs to be considered at most once for addition since the problem
is hereditary), for a total cost that is polynomial when $k$ is constant. We
can thus state the following:

###### Theorem 6.4.

Maximal Edge-induced $k$-degenerate Subgraphs are proximity searchable when
$k$ is constant, and can be enumerated with delay $O(\binom{n}{k-1}m^{3})$.

##  7\. Maximal Chordal Subgraphs

###  7.1. Maximal Induced Chordal Subgraphs

A graph $G$ is chordal if every cycle in $G$ of length greater than 3 has a
chord, i.e., an edge between two non-consecutive vertices in the cycle.
Chordal graphs have been widely studied, and it is known that several problems
which are challenging on general graphs become easier on chordal graphs (see,
e.g., (Chandran2001, ; Okamoto2005, ; blair1993introduction, )). While the
problem of finding a largest chordal subgraph has been studied
(bliznets2016largest, ), to the best of our knowledge there are no known
enumeration results.

We here aim at listing Maximal Induced Chordal Subgraphs of $G$. The problem
is hereditary, and chordality can be tested in $O(m)$ time
(rose1976algorithmic, ), thus $\textsc{comp}(\cdot)$ takes $O(mn)$ time.

A (sub)graph is chordal iff it allows a perfect elimination ordering
$\\{v_{1},\ldots,v_{n}\\}$ of its vertices, i.e., such that for all $i$,
$N(v_{i})\cap\\{v_{i+1},\ldots,v_{n}\\}$ is a clique
(DBLP:conf/cocoon/ConteKOUW17, ). We can obtain this by recursively removing
simplicial vertices, i.e., vertices whose neighborhood in the residual graph
is a clique.999To remove ambiguity, we can remove the lexicographically
smallest when multiple simplicial vertices are present.

As the neighbors of a simplicial vertex form a clique, we observe that
removing a simplicial vertex cannot disconnect the residual graph. It is also
known that a chordal graph has $O(n)$ maximal cliques, and a vertex $v$
participates in $O(|N(v)|)$ maximal cliques (DBLP:conf/cocoon/ConteKOUW17, ).

We use this to define the canonical order, which is then combined with
Definition 4.1 to obtain the proximity function $\tilde{\cap}$.

###### Definition 7.1 (Canonical Order for Maximal (Connected) Induced Chordal
Subgraphs).

The canonical order $\\{s_{1},\ldots,s_{|S|}\\}$ of $S$ is the reverse of its
perfect elimination ordering, i.e., such that $\\{s_{|S|},\ldots,s_{1}\\}$ is
the perfect elimination ordering.

This way, the neighbors of $v$ that precede $v$ in the ordering form a clique.
Furthermore, when $S$ is a connected subgraph, any prefix
$\\{s_{1},\ldots,s_{j\leq|S|}\\}$ of the canonical order induces a connected
subgraph, because we can iteratively remove the last vertex, which is always
simplicial. This means the canonical order satisfies condition (1) of
Definition 4.2, in the case of both Maximal Induced Chordal Subgraphs and
Maximal Connected Induced Chordal Subgraphs. The neighboring function is
defined as follows.

###### Definition 7.2 (Neighboring function for Maximal (Connected)
InducedChordal Subgraphs).

We define $\textsc{neighbors}(S)=\bigcup\limits_{v\in V(G)\setminus
S}\textsc{neighbors}(S,v)$.

For the non connected case we define

$\textsc{neighbors}(S,v)=\\{\textsc{comp}(S\cup\\{v\\}\setminus(N(v)\setminus
Q)):$

$Q\text{ is a maximal clique of }G[S\cup\\{v\\}]\text{ containing v}\\}$

While for the connected case we define

$\textsc{neighbors}(S,v)=\\{\textsc{comp}(\texttt{cc}_{v}(S\cup\\{v\\}\setminus(N(v)\setminus
Q))):$

$Q\text{ is a maximal clique of }G[S\cup\\{v\\}]\text{ containing v}\\}$

Less formally, we add a vertex $v$ to $S$, then remove all its neighbors
except one maximal clique $Q$ (meaning the removable by definition of
canonical reconstruction will be $N(v)\setminus Q$). In the connected case, we
further remove vertices not in the connected component of $v$.

We can easily see that $S\cup\\{v\\}\setminus(N(v)\setminus Q)$ is chordal, by
showing a perfect elimination ordering: $v$ itself is simplicial as its
neighbors form a clique, and can be removed; we can then complete the perfect
elimination order as the remaining vertices form an induced subgraph of $S$,
which is chordal as induced chordal subgraphs are hereditary.

We now need to prove the last condition; let $S$ and $S^{*}$ be two solutions,
$S\tilde{\cap}S^{*}=\\{s^{*}_{1},\ldots,s^{*}_{h}\\}$ and
$\dot{v}=s^{*}_{h+1}$ the earliest vertex in the canonical order of $S^{*}$
not in $S$.

By the canonical order,
$N(\dot{v})\cap(S\tilde{\cap}S^{*})=N(\dot{v})\cap\\{s^{*}_{1},\ldots,s^{*}_{h}\\}$
is a clique. When computing $\textsc{neighbors}(S,\dot{v})$, as we try all
maximal cliques, for some $Q$ we will have
$N(\dot{v})\cap(S\tilde{\cap}S^{*})\subseteq Q$. The resulting $S^{\prime}$
will thus contain all neighbors of $\dot{v}$ in $S\tilde{\cap}S^{*}$, and thus
all of $S\tilde{\cap}S^{*}$, plus $\dot{v}$, meaning that
$|S^{\prime}\tilde{\cap}S^{*}|>|S\tilde{\cap}S^{*}|$, which proves the
correctness the $\textsc{neighbors}(\cdot)$ function.

Finally, $\textsc{neighbors}(\cdot)$ can indeed be computed in polynomial
time. We first need to list all maximal cliques containing $v$ in
$G[S\cup\\{v\\}]$: these correspond exactly to the maximal cliques of
$G[(S\cap N(v))\cup\\{v\\}]$; as $v$ is adjacent to all vertices in $(S\cap
N(v))$, we can further say that these correspond exactly to all maximal
cliques of $G[(S\cap N(v))]$, to which we then add $v$ ($v$ can clearly be
added to any clique of $G[(S\cap N(v))]$ since it is adjacent to all its
vertices).

This correspondence is important, because $G[(S\cap N(v))]$ is an induced
subgraph of $S$, and thus a chordal graph.

Recall now that a chordal graph has $O(n)$ cliques and they can be listed in
$O(m)$ time (e.g., by computing a perfect elimination ordering
(rose1976algorithmic, )): $G[S\cap N(v)]$ has at most $|N(v)|$ vertices and
$O(|N(v)|^{2})$ edges, so we can list all the maximal cliques of $G[S\cap
N(v)]$ –and thus all maximal cliques of $G[S\cup\\{v\\}]$ containing $v$– in
$O(|N(v)|^{2})$ time, obtaining at most $|N(v)|$ maximal cliques.

The cumulative cost of listing all cliques for each $v\in V(G)\setminus S$ is
thus bounded by $O(\sum\limits_{v\in V(G)\setminus S}|N(v)|^{2})=O(mn)$ time,
and the process yields $O(\sum\limits_{v\in V(G)\setminus S}|N(v)|)=O(m)$
maximal cliques. For each clique $Q$, we must further compute the
corresponding $\textsc{comp}(\cdot)$ call: as the problem is hereditary, again
we only need to test each vertex at most once for addition, and a chordality
can be tested in $O(m)$ time, the cost $\mathcal{C}_{t}$ of a
$\textsc{comp}(\cdot)$ is $O(mn)$ time (which dominates the time for checking
membership in $\mathcal{S}$). Furthermore, the same bound applied to the
connected case, as we simply need to consider vertices for addition only when
they become adjacent to the current solution. Scanning the neighborhoods of
the vertices that are added to the solution to find these candidates has an
additional cost of $O(m)$ which does not affect the $O(mn)$ bound. The total
cost will be $O(mn+m\cdot mn)=O(m^{2}n)$

We can thus state that:

###### Theorem 7.3.

Maximal Induced Chordal Subgraphs and Maximal Connected Induced Chordal
Subgraphs are proximity searchable, and can be listed with $O(m^{2}n)$ time
delay.

###  7.2. Maximal Edge-induced Chordal Subgraphs

An algorithm for the edge version can be obtained by defining the canonical
order for the edge-induced subgraph in the same way as for Bipartite
Subgraphs, based on the canonical ordering of the vertices (see Definition
5.5).

In this problem too, note how all Maximal Edge-induced Chordal Subgraphs of a
connected graph are connected, as we can always add edges to a non-connected
subgraph without creating cycles, so we do not need to separately consider the
connected and non-connected case.

We can then devise a neighboring function $\textsc{neighbors}(S,(x,y))$ like
the first one in Definition 7.2, where we use an edge $(x,y)$ as canonical
extender.

When adding an edge $(x,y)$ to a maximal solution $S$, we try as $Q$ all
maximal cliques containing either $x$ or $y$ in $G[S]$. In any $S^{*}$ (for
which $(x,y)$ is the canonical extender) one between $x$ and $y$ will occur
later in the canonical ordering; wlog, let us say $y$. As the canonical
ordering is based on a reversed perfect elimination ordering, the neighbors of
$y$ preceding $y$ in the canonical order of $S^{*}$ form a clique (including
$x$ as well). Thus the neighboring funciton will eventually consider a clique
$Q$ containing $y$ and all its preceding neighbors, and when this happens the
proximity with $S^{*}$ is extended. The number of neighboring solutions
generated this way will be $O(\sum_{(x,y)\in E(G)}|N(x)|+N|(y)|)=O(mn)$.

The only further requirement is a polynomial time $\textsc{comp}(\cdot)$
function which needs to be applied to each neighboring solution: this follows
from (HEGGERNES20091, ), who prove that edge-induced chordal subgraphs are
sandwich monotone. In other words, if a edge-induced chordal subgraph
$S\subseteq E(G)$ is not maximal, then there is always a single edge $e\in
E(G)\setminus S$ such that $S\cup\\{e\\}$ is a chordal subgraph.

This means $\textsc{comp}(\cdot)$ can be computed in a greedy way by testing,
up to $m$ times, that any of the $O(m)$ remaining edges in the graph can be
added, which takes $O(m)$ time, for a total cost $\mathcal{C}_{t}=O(m^{3})$.
The total cost follows.

###### Theorem 7.4.

Maximal Edge-induced Chordal Subgraphs are proximity searchable, and can be
listed with $O(m^{4}n)$ time delay.

##  8\. Maximal Induced Proper Interval Subgraphs

Interval graphs are a well-known subclass of chordal graphs, whose vertices
can be arranged as intervals on a line such that two vertices are adjacent if
and only if their intervals intersect. In this section, we present a
polynomial-delay enumeration algorithm for Maximal Proper Interval Subgraphs,
a subclass of interval subgraphs corresponding to interval graphs where no two
intervals properly contain another.

Despite chordal graphs, interval graphs, and proper interval graphs being
closely related to each other, it is interesting to observe how the three
enumeration algorithms proposed here (chordal subgraphs, proper interval
subgraphs) and in (Cao:arXiv:2020, ) (interval subgraphs) differ
significantly. Furthermore, an interesting open question would be to determine
whether it is possible to enumerate Maximal Interval Subgraphs directly via
proximity search, or whether there is an intrinsic difference in what can be
achieved with retaliation-free paths.

###  8.1. Maximal Connected Induced Proper Interval Subgraphs

A proper interval graph is an interval graph where, in the interval
representation, no interval properly contains another. Equivalently, it can be
defined as interval graphs that admit a unit-length representation, i.e.,
where all intervals have length $1$ (fulkerson1965incidence, ). In this
section we will adopt this latter definition, and all interval representations
considered will be intended as unit-length.

In the following, we show how to enumerate Maximal (Connected) Proper Interval
Subgraphs of a graph $G$. We show the connected version of the problem, and
later remark how to adapt it to the non-connected case.

It is important to observe that every connected proper interval (sub)graph $S$
has two unique interval representation represented by a sequence
$v_{1},\ldots,v_{|S|}$, and its reverse.101010Ambiguity may be caused by
identical vertices, i.e., adjacent and with the same sets of neighbors, but it
can be resolved by taking the smallest-id vertex first. The canonical order
$v_{1},\ldots,v_{|S|}$ of a Maximal Proper Interval Subgraph $S$ is defined as
the sequence given by the interval representation of $S$ which has as $s_{1}$
the smallest among the two possible values.

A graphical example is given in Figure 4 (a),(b),(d),(e).

(a)(b)(c)(d)(e)(f)

Figure 4. a: a proper interval subgraph $S$ of the graph in Figure 2. d:
another proper interval subgraph $T$. b: the unit interval representation of
$S$, which induces the canonical order $1,2,4,3,8,7,9,12,11$. e: the
representation of $T$, which induces the canonical order
$1,2,4,5,11,12,9,10,8$.

In order to generate neighboring solutions, we take each of the two
representations, and for each we proceed as follows. Firstly, we try all
vertices $v\in V(G)\setminus S$ as canonical extender. Next, we want to
identify the right way of inserting $v$ in the interval representation of $S$.
As the interval length is fixed to 1, there are $5|S|$ possibilities: for any
other $w\in S$, we can place $v$ ending just before / just after the start of
$w$, exactly overlapping $w$, or starting just before / just after the end of
$w$. We can observe how these capture all possible ways to insert $v$, since
given any other placement we can slide $v$ in any direction until it is about
to gain or lose an overlap, i.e., one of the endpoints of $v$ will approach
the endpoint of another interval, which puts us into one of the $5|S|$ cases
above.

Finally, we have to make the representation consistent, by removing from
$S\cup\\{v\\}$:

  * •

All vertices (intervals) coming _after_ $v$ in this representation.

  * •

All neighbors of $v$ that do _not_ overlap its interval.

  * •

All non-neighbors of $v$ that do overlap its interval.

  * •

Finally, all vertices that have become disconnected from the connected
component containing $v$ by performing the previous steps.

The resulting representation is consistent with a proper interval graph, so
the resulting graph is clearly a proper interval graph. Let us call it $X$,
and let us call $S^{\prime}=\textsc{comp}(\texttt{cc}_{v}(X))$. The following
example illustrates these operations on the example graphs from Figure 4.

###### Example 0.

Looking at the graphs in Figure 4 ((a), (d)) and their canonical orderings
(see (b),(e)) we can give an example of the operations performed by the
neighboring function.

(c): $5$ is added as canonical extender and placed “just before” $3$; we
remove vertices the dashed vertices $3$ and $8$ (overlapping $5$ but not
neighbors of $5$ in $G$), and $11$ and $12$ (not overlapping $5$ but neighbors
of $5$ in $G$); $9$ and $7$ are also removed as not part of the same connected
component as $5$. The resulting graph (f) is then is maximalized with
$\textsc{comp}(\cdot)$, and has greater proximity with $b$ than $a$.

Indeed, $S\tilde{\cap}T=\\{1,2,3,4\\}$, while the maximal solution obtained
maximalizing (f) contains $1,2,3,4,5$.

The set $\textsc{neighbors}(S)$ will be made of the $S^{\prime}$ obtained by
trying both representations of $S$, for each all $v\in V(G)\setminus S$, and
for each all possible insertions, for a total of $O(n^{2})$ neighboring
solutions.

We now show that, given $S,T$, we always obtain some
$S^{\prime}\in\textsc{neighbors}(S)$ such that
$|S^{\prime}\tilde{\cap}T|>|S\tilde{\cap}T|$.

Let the proximity $S\tilde{\cap}T$ be $t_{1},\ldots,t_{i-1}$: this is a prefix
of $T$, and since it is a connected subgraph, its vertices in the same order
as in $T$ in one of the two representations of $S$. Furthermore, let $v$ be
our canonical extender.

Looking at the canonical order of $T$, consider the placement of $t_{i}$
relative to the preceding intervals $t_{1},\ldots,t_{i-1}$. Now, consider the
case where $v=t_{i}$, the correct one between the two representations of $S$
is considered, and the placement of $v$ relative to $t_{1},\ldots,t_{i-1}$ is
the same as $t_{i}$ in $T$.

As we try all possible placements for $v=t_{i}$, and as $t_{1},\ldots,t_{i-1}$
is a connected subgraph of $T$, we will also try the placement of $t_{i}$
considered above. The correct placement of $v$ tells us that, when we remove
all intervals coming _after_ $v$ from $S\cup\\{v\\}$, we do not remove
vertices from $t_{1},\ldots,t_{i-1}$. The placement also tells us that all
neighbors of $v$ in $t_{1},\ldots,t_{i-1}$ overlap with $v$ in the interval
representation, while all non-neighbors of $v$ in $t_{1},\ldots,t_{i-1}$ do
not, so vertices of $t_{1},\ldots,t_{i-1}$ are not removed in the remaining
steps. It follows that the set $X$ obtained is a proper interval subgraph of
$G$ containing $t_{1},\ldots,t_{i}$, and that $S^{\prime}=\textsc{comp}(X)$ is
such that $|S^{\prime}\tilde{\cap}T|>|S\tilde{\cap}T|$.

###  8.2. Induced Proper Interval Subgraphs

The non-connected version is similarly solved: as in previous sections, we
define the canonical order by ordering each connected component as in the
connected case, then ordering the components by smallest-id vertex.

The proximity is then defined by canonical reconstruction (Definition 4.1).

Let $S_{1},\ldots,S_{j}$ be the connected components of $S$, and
$T_{1},\ldots,T_{k}$ those of $T$, for some $T$.

We will have that $S\tilde{\cap}T$ consists of some complete connected
components of $T$, as well as a (possibly empty) subset of one component
$T_{i}$. The canonical extender $t_{i}$ will be the earliest vertex of the
canonical ordering of $T_{i}$ that is not in $S$. We can also observe that
each of these components is contained itself in some connected component of
$S$.

When we select a canonical extender $v$, we also select a component $S_{i}$
(of course, trying all possibilities): we aim to find the component which
contains the partially formed $T_{i}$.

As we add $v$ to $S$, we can immediately remove from $S$ all neighbors of $v$
in $S\setminus S_{i}$, as indeed as $t_{i}$ only has neighbors in $T_{i}$.

We then proceed as in the connected case, ordering $S_{i}$ in the two possible
ways, and trying all $O(n)$ insert possibilities. However, we must take care
of the fact that $S_{i}$ may contain more than one connected component of $T$:
components preceding $v$ in the order are preserved (they cannot overlap $v$
as they precede the other elements of $T_{i}$, to which they are not
adjacent), but there may be some following $v$.

For this reason, we must introduce another “guess”, that is we guess which of
the intervals preceding $v$ is $t_{i-1}$ (as, to obtain the correct placement
of $v$ in the interval representation, we may not have placed it just after
$t_{i-1}$). Note how the number of possible $t_{i-1}$ is at most $|N(v)|$.
This step, which was not necessary in the connected version, allows us to
effectively compute a safe way of detaching the intervals following $v$.

Specifically, we remove from $S_{i}\cup\\{v\\}$ the following vertices:

  * •

All vertices (intervals) between $t_{i-1}$ and $v$.

  * •

All vertices (intervals) coming _after_ $v$ in this representation that are
adjacent to $v$ or to $t_{i-1}$.

  * •

All neighbors of $v$ that do _not_ overlap its interval.

  * •

All non-neighbors of $v$ that do overlap its interval.

In this way, all the vertices removed could not be part of the proximity
$S\tilde{\cap}T$: the ones between $t_{i-1}$ and $t_{i}$ cannot be in the
interval representation since $t_{i-1}$ and $t_{i}$ are consecutive in the
interval representation of $T$; the others we remove were neighbors of
$t_{i-1}$ or $t_{i}$, but did not precede them in the interval representation
(i.e., in the canonical order), so they could not be part of $S\tilde{\cap}T$.
On the other hand, the remaining intervals following $v$ are now in a separate
connected component, thus the interval representation of the resulting graph
is consistent, contains $t_{1},\ldots,t_{i}$ (for any $T$, when the correct
choices are performed), and we can apply the $\textsc{comp}(\cdot)$ function
to obtain a neighboring solution $S^{\prime}$.

###  8.3. Running time

As for the complexity, the neighboring function tries $O(n)$ candidates for
$v$, and for each, $5|S|=O(n)$ possible placements in $S$, in each of the $2$
representations. For each, the cost of the procedure is dominated by the
application of the $\textsc{comp}(X)$ call.

Since we can test whether a graph is a proper interval graph in $O(m)$ time
(booth1975linear, ), the $\textsc{comp}(X)$ function can be implemented in
$O(mn)$ time as for chordal subgraphs, giving us a total cost per solution of
$O(n^{3}m)$ time.

For the non-connected version, we must consider two additional phases: for
each $v$, we firstly selected a connected component $S_{i}$ of $S$, and
secondly we selected the possible $t_{i-1}$ among the neighbors of $v$. We can
bound the number of connected components by $O(n)$, and, rather than adding
another factor $O(n)$ for the choice of $t_{i-1}$, we can observe how each
distinct pair $v,t_{i-1}$ corresponds to an edge, so the number of possible
$v$ and $t_{i-1}$ pairs is $O(m)$, for a total complexity of $O(n^{3}m^{2})$

###### Theorem 8.1.

Maximal Induced Proper Interval Subgraphs and Maximal Connected Induced Proper
Interval Subgraphs are proximity searchable, and can be listed with
$O(n^{3}m^{2})$ time delay and $O(n^{3}m)$ time delay, respectively.

##  9\. Maximal Obstacle-free Convex Hulls

In application domains such as robotics planning and routing, a common problem
is finding areas, typically convex, in a given environment which are free from
obstacles (see, e.g., (Deits2015, ; savin2017algorithm, )).

In this section we solve the following formulation of the problem: let $V$ and
$X$ be two sets of elements, which corresponds to points on a 2-dimensional
plane. $V$ represents the point of interest for our application, and $X$
represents the obstacles. For short, let $|V|=j$ and $|X|=h$, and let $n=j+h$
be the total number of points. We are interested in listing all maximal
obstacle-free convex hulls (mocs for short), where an obstacle-free convex
hull is a set of elements $S\subseteq V$ such that the convex hull of $S$ does
not contain any element of $X$.

This problem does not concern a graph, but its solutions are modeled as sets
of elements, thus the technique may still be applied. Furthermore, we can
naturally generalize the problem by adding a graph structure to $V$, i.e.,
adding edges between its points, and considering the problem of Maximal
Connected Obstacle-free Convex hulls.

###  9.1. Maximal Obstacle-free Convex Hulls

Again, note that the problem is hereditary, i.e., each subset $S^{\prime}$ of
a solution $S$ clearly also admits a convex hull which does not include
elements of $X$ (since it will be contained in that of $S$).

It is worth observing that this is the only problem in this paper to which we
do not apply the canonical reconstruction strategy.

Consider a maximal solution $S$ and an element $v\in V\setminus S$. As $S$ is
maximal, there is at least one element $x\in X$ included in the convex hull of
$S\cup\\{v\\}$. This element $x$ casts two “shadows” $S_{1}$ and $S_{2}$ on
$S$, seen by $v$: consider the straight line between $v$ and $x$, $S_{1}$
consists of all elements of $S$ above this line, and $S_{2}$ of all those
below it. It is straightforward to see how both the convex hull of
$S_{1}\cup\\{v\\}$ and that of $S_{2}\cup\\{v\\}$ do not contain $x$. Any
element of $S$ that falls exactly on the line may not participate in any
solution involving $v$.111111Note that it may not fall between $v$ and $x$
otherwise the convex hull of $S$ would have included $x$. Furthermore, any
element $x^{\prime}\in X$ above this line, and still in the convex hull of
$S\cup\\{v\\}$, further casts two shadows on $S_{1}$, as any element below
this line casts them on $S_{2}$. If we repeat this process for all elements of
$X$ in the convex hull of $S\cup\\{v\\}$ we obtain a number of shadows of $S$
which is at most linear in the number of elements of $X$. Let $\phi(S,v)$ be
the set of these shadows. For each of these shadows $S_{i}\in\phi(S,v)$, we
have that the convex hull of $S_{i}\cup\\{v\\}$ may not include elements of
$X$, i.e., $S_{i}\cup\\{v\\}$ is a (possibly not maximal) solution.

The neighboring function is then obtained as follows.

###### Definition 9.1 (Neighboring function for mocs).

$\textsc{neighbors}(S)=\bigcup\limits_{v\in V(G)\setminus
S}\textsc{neighbors}(S,v)$

Where

$\textsc{neighbors}(S,v)=\\{\textsc{comp}(S_{i}\cup\\{v\\}):S_{i}\in\phi(S,v)\\}$

Finally, for two solutions $S$ and $S^{*}$, we simply define
$S\tilde{\cap}S^{*}$ as the intersection $S\cap S^{*}$ between their elements.

Let $I=S\cap S^{*}=S\tilde{\cap}S^{*}$, and $v$ any element in $S^{*}\setminus
S$. Since $I\cup\\{v\\}$ is contained in a moc, $S^{*}$, its convex hull
cannot contain any element of $X$. It follows that $I$ must be fully contained
in a single $S_{i}\in\phi(S,v)$: indeed, if we take two points $u_{i}\in
S_{i}$ and $u_{j}\in S_{j}$, it is evident by the definition of $\phi(S,v)$
that the convex hull of $\\{v,u_{i},u_{j}\\}$ (or any superset of it) contains
at least an element of $X$. We have that the neighboring function will return
$S^{\prime}=\textsc{comp}(S_{i}\cup\\{v\\})$, with $I\cup\\{v\\}\subseteq
S^{\prime}$, which implies
$|S^{\prime}\tilde{\cap}S^{*}|>|S\tilde{\cap}S^{*}|$. The algorithm is thus
correct.

As for the complexity, the problem is hereditary, so we may compute a
$\textsc{comp}(S)$ call by testing each vertex in $V\setminus S$ once. The
convex hull of $S$ can be computed in $O(|S|\log|S|)$ time (Chan1996, ), and
testing a solution consists in checking that each vertex of $X$ is not in this
hull, which can trivially be done in $O(|S|\cdot h)$ time. The cost of
$\textsc{comp}(\cdot)$ is thus $O(j(h+\log j))$ time. For each candidate $v$,
we have at most $h$ neighboring solutions, and since we need to consider at
most $j$ candidates, the delay of the algorithm will be $j\cdot h$ times the
cost of a $\textsc{comp}(\cdot)$ call.

We thus obtain an algorithm with the following complexity:

###### Theorem 9.2.

Maximal Obstacle-free Convex Hulls are proximity searchable, and can be listed
in $O(j^{2}h(h+\log j))=O(n^{4})$ time delay.

It could be argued that the neighboring function actually reports all
solutions of the input-restricted problem in this instance, allowing us to
induce a parent-child relationship with the structure of
(lawler1980generating, ; Cohen20081147, ), and reducing the space usage to
$O(n)$ by using stateless iteration (DBLP:conf/icalp/ConteGMV16, ). However,
it is worth observing that proximity search required proving a weaker
statement, and allows for an arguably simpler proof.

###  9.2. Maximal Connected Obstacle-free Convex Hulls

We now consider an extension of the problem where on top of $V$ and $X$ we
have a graph structure $G=(V,E)$ on the points of $V$, and we are interested
in listing all maximal set of points $S\subseteq V$ such that the convex hull
of $S$ is obstacle-free, and $G[S]$ is connected.

We consider this a natural extension as, in the applications mentioned above,
it could model requirements on the structure of the obstacle-free areas
identified.

The algorithm is remarkably similar to the above version, as the neighboring
function still considers $S_{i}\cup\\{v\\}$ for all $S_{i}\in\phi(S,v)$, but
only keeps the connected component of $G[S_{i}\cup\\{v\\}]$ containing $v$.

###### Definition 9.3 (Neighboring function for mocs).

$\textsc{neighbors}(S)=\bigcup\limits_{v\in V(G)\setminus
S}\textsc{neighbors}(S,v)$

Where

$\textsc{neighbors}(S,v)=\\{\texttt{cc}_{v}(\textsc{comp}(S_{i}\cup\\{v\\})):S_{i}\in\phi(S,v)\\}$

For two solutions $S$ and $S^{*}$, we define $S\tilde{\cap}S^{*}$ as the
largest connected component of their intersection $S\cap S^{*}$. We now prove
that there is $S^{\prime}\in\textsc{neighbors}(S)$ such that
$|S^{\prime}\tilde{\cap}S^{*}|>|S\tilde{\cap}S^{*}|$.

Let $I=S\cap S^{*}=S\tilde{\cap}S^{*}$, and $v$ any element in $S^{*}\setminus
S$ such that $G[I\cup\\{v\\}]$ is connected. Note that a suitable $v$ must
exist, otherwise $I$ would not be connected to the elements of $S^{*}\setminus
I$, contradicting the fact that $S^{*}$ is a connected solution. Since
$I\cup\\{v\\}$ is contained in $S^{*}$, its convex hull cannot contain any
element of $X$. It follows that $I$ must be fully contained in a single
$S_{i}\in\phi(S,v)$. Furthermore, as $I\cup\\{v\\}$ is connected, it must be
contained in $\texttt{cc}_{v}(S_{i}\cup\\{v\\})$, the connected component of
$G[S_{i}\cup\\{v\\}]$ containing $v$.

Similarly to the above case, we have that the neighboring function will return
$S^{\prime}=\textsc{comp}(\texttt{cc}_{v}(S_{i}\cup\\{v\\}))$, with
$I\cup\\{v\\}\subseteq S^{\prime}$, which implies
$|S^{\prime}\tilde{\cap}S^{*}|>|S\tilde{\cap}S^{*}|$. The algorithm is thus
correct.

The complexity can be also derived from the non-connected case: the only
additional step is applying $\texttt{cc}_{v}(\cdot)$ before the
$\textsc{comp}(\cdot)$ function. As $\texttt{cc}_{v}(\cdot)$ takes $O(m)$
time, where $m=|E(G)|=O(n^{2})$, we can conclude the following:

###### Theorem 9.4.

Maximal Connected Obstacle-free Convex Hulls are proximitysearchable, and can
be listed in $O(jh(m+j(h+\log j)))=O(n^{4})$ time delay.

##  10\. Maximal Connected Directed Acyclic Subgraphs

In this section we consider a directed graph, where each edge has a head and a
tail, and its direction is from the tail to the head. We call $N^{+}(v)$ the
out-neighbors of the vertex $v$ and $N^{-}(v)$ its in-neighbors.

The goal of this section is listing Maximal Induced Connected Acyclic
Subgraphs (mcais hereafter) of a given directed graph $G$. The problem is
connected-hereditary, and acyclicity can be tested in $O(m)$ time, thus
$\textsc{comp}(\cdot)$ can be implemented in $O(mn)$ time.

For completeness, we remark that the non-connected version (Maximal Induced
Directed Acyclic Subgraphs), corresponds to listing the complements of Minimal
Feedback Vertex Sets in a directed graph, and is of no interest here as an
output-polynomial algorithm is given in (schwikowski2002enumerating, ). We
thus address the connected version of the problem, which has no natural
counterpart in terms of feedback vertex set. Let us define the canonical
order:

###### Definition 10.1 (Canonical Order for Maximal Connected Induced Acyclic
Subgraphs).

The canonical order of a mcais $S$ is the order $\\{s_{1},\ldots,s_{|S|}\\}$
such that, for each $s_{i}$, $\\{s_{1},\ldots,s_{i}\\}$ is connected, and
either $\\{s_{1},\ldots,s_{i-1}\\}\cap N^{+}(s_{i})=\emptyset$ or
$\\{s_{1},\ldots,s_{i-1}\\}\cap N^{-}(s_{i})=\emptyset$. If multiple orders
are possible let it be the lexicographically minimum.

Our algorithm does not need to compute this order or $\tilde{\cap}$, but we
need to show that it always exists.

Firstly, recall that every acyclic graph has at least one source and one
target, and let us observe an important property of acyclic graphs with a
single source (whose proof trivially follows from the fact that any non-source
vertex has a neighbor occurring before itself in the order):

###### Lemma 10.2.

Let $G$ be a single-source acyclic connected graph, and $v_{1},\ldots,v_{n}$
any topological order of $G$. Any prefix $v_{1},\ldots,v_{i}$ of this order
induces a connected subgraph.

Lemma 10.2 also implies that the reversed topological order (i.e., where
vertices have no forward out-neighbors) of a single-target acyclic connected
graph is such that every prefix induces a connected subgraph. We also remark
that both these orders satisfy the intersection properties of Definition 10.1.

We now use this lemma to show that the defined canonical order exists for any
mcais. In the following, we define collapsing a set of vertices $A\subseteq S$
into $x$ as replacing them with a single vertex $x$, whose in- and out-
neighbors correspond to all vertices in $S\setminus A$ that were respectively
in- and out-neighbors of some vertex in $A$.

###### Lemma 10.3.

Every Directed Acyclic Graph allows a canonical order by Definition 10.1.

###### Proof.

Let $S$ be a Directed Acyclic Graph. Let $v_{1}$ be a source of $S$, and
$S_{1}$ be the set of vertices reachable by $v_{1}$, including $v_{1}$. Let
$s_{1,1},\ldots,s_{1,|S_{1}|}$ a topological ordering of $S_{1}$.

No vertex in $S_{1}$ can have an out-neighbor outside of $S_{1}$ as otherwise
said vertex would be in $S_{1}$ itself. Let instead $S_{2}$ be the set of all
vertices in $S\setminus S_{1}$ that can reach some vertex of $S_{1}$.

If we collapse $S_{1}$ into a vertex $x$, we can observe that
$S_{2}\cup\\{x\\}$ is acyclic subgraph with $x$ being the only target. Let
$x,s_{2,1},\ldots,s_{2,|S_{2}|}$ be a reverse topological ordering of
$S_{2}\cup\\{x\\}$.

If we replace $x$ with the previously computed order of $S_{1}$, we obtain an
order $s_{1,1},\ldots,s_{1,|S_{1}|},s_{2,1},\ldots,s_{2,|S_{2}|}\\}$ which
respects Definition 10.1: Each vertex in $s_{1,1},\ldots,s_{1,|S_{1}|}$ has no
backward out-neighbor by the topological ordering of $S_{1}$; each
$s_{2,1},\ldots,s_{2,|S_{2}|}$ has no backward in-neighbor by the reverse
topological ordering of $S_{2}$, and because vertices of $S_{1}$ can not have
out-neighbors outside $S_{1}$; finally, every prefix of
$s_{1,1},\ldots,s_{1,|S_{1}|},s_{2,1},\ldots,s_{2,j}$ is connected, as
$x,s_{2,1},\ldots,s_{2,j}$ is connected, meaning that all vertices in
$s_{2,1},\ldots,s_{2,j}$ are connected to some vertex in $S_{1}$, that is
itself connected.

We may now repeat this step by collapsing $S_{1}\cup S_{2}$ into a vertex
$x^{\prime}$, and since $x^{\prime}$ will be a source, take $S_{3}$ as all
vertices reached by $x^{\prime}$ in $S\setminus(S_{1}\cup S_{2})$, and take a
topological order of $S_{3}\cup\\{x^{\prime}\\}$, which we append to the order
obtained so far (excluding $x^{\prime}$).

By iterating steps, we obtain an ordering
$s_{1,1},\ldots,s_{1,|S_{1}|},s_{2,1},\ldots,s_{2,|S_{2}|},$$s_{3,1},\ldots,s_{3,|S_{3}|}\ldots,s_{k,1},\ldots,s_{k,|S_{k}|}$,
with $k\leq|S|$, that contains all vertices of $S$, and such that any prefix
will induce a connected subgraph, and any $s_{i,j}$ will have no backward out-
neighbors if $i$ is odd, and no backward in-neighbors if $i$ is even, thus
there exist an ordering satisfying Definition 10.1 (if a feasible order
exists, a lexicographically minimum one must exist too). ∎

Finally, the proximity $\tilde{\cap}$ follows by Definition 4.1. We define the
neighboring function as follows.

###### Definition 10.4 (Neighboring Function for Maximal Connected Induced
Acyclic Subgraphs).

For a solution $S$ and a vertex $v\in V(G)\setminus S$, we define

$\textsc{neighbors}(S)=\bigcup\limits_{v\in V(G)\setminus
S}\textsc{neighbors}(S,v)$

Where $\textsc{neighbors}(S,v)=\\{\textsc{comp}(\texttt{cc}_{v}(\\{v\\}\cup
S\setminus N^{+}(v))),\textsc{comp}(\texttt{cc}_{v}(\\{v\\}\cup S\setminus
N^{-}(v)))\\}$

In other words, the function will add $v$ to $S$. $S\cup\\{v\\}$ is not
acyclic, but all cycles must involve $v$, so we make it acyclic by removing
either all the out-neighbors $N^{+}(v)$, which makes $v$ a target, or all its
in-neighbors $N^{-}(v)$, which makes $v$ a source. It then takes the connected
component containing $v$ and feeds the result to $\textsc{comp}(\cdot)$, to
surely obtain a mcais.

Consider now two solutions $S$ and $S^{*}$, and again let $\dot{v}$ be the
first vertex in the canonical order of $S^{*}$ which is not in
$S\tilde{\cap}S^{*}$. More formally, let
$S\tilde{\cap}S^{*}=\\{s^{*}_{1},\ldots,s^{*}_{h}\\}$ and
$\dot{v}=s^{*}_{h+1}$.

Let $S^{\prime}=\textsc{comp}(\texttt{cc}_{\dot{v}}(\\{\dot{v}\\}\cup
S\setminus N^{+}(\dot{v})))$ and
$S^{\prime\prime}=\textsc{comp}(\texttt{cc}_{\dot{v}}(\\{\dot{v}\\}\cup
S\setminus N^{-}(\dot{v})))$ be the two solutions generated by
$\textsc{neighbors}(S,\dot{v})$.

By the canonical order of $S^{*}$, we have that
$(S\tilde{\cap}S^{*})\cup\\{\dot{v}\\}$ is connected, and either
$(S\tilde{\cap}S^{*})\cap N^{+}(\dot{v})=\emptyset$ or
$(S\tilde{\cap}S^{*})\cap N^{-}(\dot{v})=\emptyset$.

It follows that if $(S\tilde{\cap}S^{*})\cap N^{+}(\dot{v})=\emptyset$, then
$(S\tilde{\cap}S^{*})\cup\\{\dot{v}\\}\subseteq\texttt{cc}_{\dot{v}}(\\{\dot{v}\\}\cup
S\setminus N^{+}(\dot{v}))\subseteq S^{\prime}$, and otherwise we have
$(S\tilde{\cap}S^{*})\cap N^{-}(\dot{v})=\emptyset$, which means
$(S\tilde{\cap}S^{*})\cup\\{\dot{v}\\}\subseteq\texttt{cc}_{\dot{v}}(\\{\dot{v}\\}\cup
S\setminus N^{-}(\dot{v}))\subseteq S^{\prime\prime}$.

We thus have that either $|S^{\prime}\tilde{\cap}S^{*}|>|S\tilde{\cap}S^{*}|$
or $|S^{\prime\prime}\tilde{\cap}S^{*}|>|S\tilde{\cap}S^{*}|$, which gives us
the second necessary condition of proximity search.

Finally, it is straightforward to see that $\textsc{neighbors}(S)$ takes
polynomial time, as its cost is bounded by $O(n)$ calls to
$\textsc{comp}(\cdot)$, which can be implemented in $O(mn)$, meaning that all
conditions of Definition 3.1 are satisfied. Theorem 10.5 follows.

###### Theorem 10.5.

Maximal Connected Induced Directed Acyclic Subgraphs are proximity searchable,
and can be listed $O(mn^{2})$ time delay.

###  10.1. Maximal Connected Edge-induced Directed Acyclic Subgraphs

We remark here that the structure can be adapted to the edge case, i.e.,
Maximal Connected Edge-induced Directed Acyclic Subgraphs (mcaes).

As the problem is still hereditary and acyclic subgraphs can be tested in
linear time, we can implement the $\textsc{comp}(\cdot)$ function in
$O(m^{2})$ time. The canonical order is as follows.

###### Definition 10.6 (Canonical order for mcaes).

Given a mcaes $S$, let the canonical ordering of the vertices of $G[S]$
according to Definition 10.1 be $v_{1},\ldots,v_{|V[S]|}$.

The canonical ordering of $S$ is obtained by selecting the edges of $S$ by
increasing order with respect to their later endpoint in the vertex order, and
breaking ties by increasing order of the other (earlier) endpoint.

We obtain a canonical ordering $e_{1},\ldots e_{|S|}$ of $S$ with the
following properties: take an edge $e_{i}=\\{v_{j},v_{k}\\}$, assuming wlog
$j<k$. All edges whose latter endpoint comes earlier than $v_{k}$ in the
vertex order are preceding $e_{i}$ in the order, thus all edges in the induced
subgraph $G[\\{v_{1},\ldots,v_{k-1}\\}]$ will be in the prefix $e_{1},\ldots
e_{i}$ of the canonical ordering of $S$. By Definition 10.1
$G[\\{v_{1},\ldots,v_{k-1}\\}]$ is connected. Finally, the only other edges in
$e_{1},\ldots,e_{i}$ are those whose latter endpoint is $v_{k}$, so their
earlier endpoint is in $\\{v_{1},\ldots,v_{k-1}\\}$. Thus each prefix
$e_{1},\ldots e_{i}$ forms a connected (edge) subgraph, which is also acyclic
as it is a subgraph of the acyclic subgraph $S$.

Furthermore, it also holds that, for the latter endpoint $v_{k}$ of $e_{i}$,
either$\\{v_{1},\ldots,v_{k-1}\\}\cap N^{+}(v_{k})=\emptyset$ or
$\\{v_{1},\ldots,v_{k-1}\\}\cap N^{-}(v_{k})=\emptyset$. This implies that
either $\\{e_{1},\ldots,e_{i-1}\\}\cap N_{E}^{+}(v_{k})=\emptyset$, or
$\\{e_{1},\ldots,e_{i-1}\\}\cap N_{E}^{-}(v_{k})=\emptyset$, which gives us
our neighboring function:

###### Definition 10.7 (Neighboring Function for mcaes).

Let $S$ be a mcaes and $e=(v_{t},v_{h})$ a directed edge in $E(G)\setminus S$
directed from its tail $v_{t}$ to its head $v_{h}$. Furthermore, let
$N_{E}^{+}(v_{h})$ and $N_{E}^{-}(v_{t})$ be the out-edges and in-edges of
$v_{h}$ and $v_{t}$, respectively. We define
$\textsc{neighbors}(S,v_{t},v_{h})=\\{\textsc{comp}(\texttt{cc}_{v_{t}}(\\{e\\}\cup(S\setminus
N_{E}^{-}(v_{t}))),\textsc{comp}(\texttt{cc}_{v_{h}}(\\{e\\}\cup(S\setminus
N_{E}^{+}(v_{h})))\\}$

And thus

$\textsc{neighbors}(S)=\bigcup\limits_{e=(v_{t},v_{h})\in E(G)\setminus
S}\textsc{neighbors}(S,v_{t},v_{h})$

In other words, we add $e$ to $S$, and try each of the two possibilities to
obtain the latter vertex in the canonical order of $S^{*}$: if it is the tail
$v_{t}$ of the edge, surely its backward out-neighborhood in the canonical
order of $S^{*}$ is not empty as it contains $v_{h}$, so it’s in-neighborhood
must be, thus we can safely remove $N_{E}^{-}(v_{t})$ to make $S\cup\\{e\\}$
acyclic. Conversely, if it is the head $v_{h}$ we can safely remove
$N_{E}^{+}(v_{h})$. We thus obtain
$|S^{\prime}\tilde{\cap}S^{*}|>|S\tilde{\cap}S^{*}|$ for some
$S^{\prime}\in\textsc{neighbors}(S)$.

We can observe that the cost $\mathcal{C}_{t}$ of a $\textsc{comp}(X)$ call is
$O(m^{2})$ since we can test acyclicity in $O(m)$ time, which we do up to $m$
times, and finding and selecting the edges connected to $X$ take in total
$O(m)$ time as well. As the neighboring function produces $O(m)$ solutions, we
obtain:

###### Theorem 10.8.

Maximal Connected Edge-induced Directed Acyclic Subgraphs are proximity
searchable, and can be listed $O(m^{3})$ time delay.

##  11\. Proximity search in polynomial space

Proximity search consists in a graph traversal, where the number of nodes
corresponds to that of solutions. If we store the set of visited nodes, as
done in the algorithms presented until now, it follows that the space
requirement of the algorithm becomes exponential in $n$.

Techniques such as reverse-search are able to turn this graph into a rooted
tree, that can be traversed without keeping track of visited nodes, by means
of a parent-child relationship among solutions, thus achieving polynomial
space. However, known instances of reverse search have de facto relied on the
problem at hand being hereditary, and the input-restricted problem being
solvable in polynomial time (respectively, polynomial total time) to obtain
polynomial delay (polynomial total time). Recently, a generalization of
reverse-search to non-hereditary properties has been proposed in
(conte2019framework, ): this allows us to induce a parent-child relationship
for maximal solutions in any commutable set system (a class of set systems
which includes both hereditary and connected-hereditary properties), and
obtain maximal listing algorithm with polynomial space, and whose delay is
linked to the input-restricted problem.

In this section we show that, when suitable conditions are met, it is possible
to get the best of both worlds: on one hand, using proximity search to
overcome the burden of the input-restricted problem and achieve polynomial
delay; on the other, using (conte2019framework, ) to induce a parent-child
relationship among solutions and achieve polynomial space at the same time.

The final goal of the section is proving the following result.

###### Theorem 11.1.

Let $(\kern 0.75pt\mathcal{U},\mathcal{F})$ be a commutable set system, and
$\textsc{neighbors}(S,s)$ a canonical reconstruction function for a proximity
search algorithm (see Definition 4.2). If the canonical order relative to the
function $\textsc{neighbors}(S,s)$ satisfies the properties of a prefix-closed
order (Definition 11.2), the maximal solutions of $(\kern
0.75pt\mathcal{U},\mathcal{F})$ can be enumerated without duplication in
polynomial delay and polynomial space.

###  11.1. Requirements and notation of (conte2019framework, )

Let us briefly recall the requirements of (conte2019framework, ). In a set
system $(\kern 0.75pt\mathcal{U},\mathcal{F})$, $\kern 0.75pt\mathcal{U}$ is
the ground set, i.e., the elements constituting the solutions, and
$\mathcal{F}$ defines the solutions, i.e., $S\in\mathcal{F}$ iff
$S\subseteq\kern 0.75pt\mathcal{U}$ satisfies the property at hand.

A set system is strongly accessible if for any two distinct solutions
$S,S^{\prime}\in\mathcal{F}$ with $S\subset S^{\prime}$, there exists an
element $x\in S^{\prime}\setminus S$ such that $S\cup\\{x\\}\in\mathcal{F}$.
This is equivalent to saying that any non-maximal solution can be extended
into a larger solution with a single element.

We say that a set system is commutable if (i) it is strongly accessible, and
(ii) it respects the commutable property: for any $S,T\in\mathcal{F}$ with
$S\subset T$, and any $a,b\in T\setminus S$, we have that
$S\cup\\{a\\}\in\mathcal{F}\land S\cup\\{b\\}\in\mathcal{F}$ implies
$S\cup\\{a,b\\}\in\mathcal{F}$. As mentioned in (conte2019framework, ), it is
straightforward to see that both hereditary and connected-hereditary
properties correspond to commutable set systems.

Furthermore, we call $Z$ the set of “singleton solutions”, i.e.,
$Z=\\{e\in\kern 0.75pt\mathcal{U}:\\{e\\}\in\mathcal{F}\\}$, and recall that
in any strongly accessible set system $Z\cap S\neq\emptyset$ for any
$S\in\mathcal{F}$. We also define, $S^{+}=\\{x:S\cup\\{x\\}\in\mathcal{F}\\}$.

Given any commutable set system, we can obtain a maximal listing algorithm
with two components. Firstly we need an efficient algorithm for solving the
input-restricted problem. Secondly, to induce a parent-child structure we need
what is called a family of prefix-closed orders for the problem, satisfying
the following properties:

###### Definition 11.2 (Prefix-closed orders, from (conte2019framework, )).

Let $\Pi(X,v)$ be a family of orders parameterized by $X\in\mathcal{F}$ and
$v\in X\cap Z$ such that $\Pi(X,v)$ yields a permutation of $X\cup X^{+}$. For
$X\in\mathcal{F}$ and $v\in X\cap Z$, let us denote by
$x^{v}_{1},\ldots,x^{v}_{k}$ the elements of $X$ ordered according to
$\Pi(X,v)$.121212Note that $x_{1}=v$ and that $x_{i},x_{i+1}\in X$ are not
necessarily consecutive in $\Pi(X,v)$ as some elements from $X^{+}$ can be
interleaved with them. We call the family $\Pi$ _prefix-closed_ if for all
$X\in\mathcal{F}$ and $v\in X\cap Z$, and $i\in\\{1,\ldots,k-1\\}$, the
following properties hold:

(first):

The minimal element is $v$, i.e., $x^{v}_{1}=v$.

(prefix):

The $i$-th prefix $X_{i}=\\{x^{v}_{1},\ldots,x^{v}_{i}\\}$ of $X$ is a
solution, i.e., $X_{i}\in\mathcal{F}$.

(greedy):

The element $x_{i+1}$ is the minimal element of $X_{i}^{+}\cap X$ with respect
to the order $\Pi(X_{i},v)$.

As explained in (conte2019framework, ), each subset $X$ of a maximal solution
$S$ does not necessarily belong to $\mathcal{F}$ (as the set system is not
necessarily hereditary). The _first_ property indicates that we can build $S$
starting from an element $v\in S\cap Z$, whereas the _greedy_ property
indicates that we can iteratively expand $X=\\{v\\}$ by considering the
elements of $X\cup X^{+}$ in a prefix-closed order, so that at any point, the
prefix $\\{x_{1},\ldots,x_{j}\\}$ found so far is a solution thank to the
_prefix_ property.

We use the shorthand notation $\prec^{t}_{S}$ to represent $\Pi(S,t)$, where
$a\prec^{t}_{S}b$ for any two elements $a,b\in\kern 0.75pt\mathcal{U}$ means
that $a$ occurs before $b$ in $\Pi(S,t)$.

Given a solution $S\in\mathcal{F}$ we define its _seed_ , $\textsc{seed}(S)$,
as the element of smallest id in $S\cap Z$, i.e., the element $s$ of smallest
id in $S$ such that $\\{s\\}\in\mathcal{F}$. Observe that every non-empty
solution $S$ of a strongly accessible set system has a seed: since
$\emptyset\subset S$, there is some $s\in S\setminus\emptyset$ such that
$\emptyset\cup\\{s\\}=\\{s\\}\in\mathcal{F}$.

The simplified notations $\prec_{S}$ corresponds to $\prec^{t}_{S}$ with
$t=\textsc{seed}(S)$. When $S$ is a maximal solution, $\prec_{S}$ defines an
order $s_{1},\ldots,s_{|S|}$ which is called the _solution order_ of $S$.

As in (conte2019framework, ), we will also require a lexicographic
$\textsc{comp}(\cdot)$ function: for a solution $S$, $\textsc{comp}(S)$ must
be obtained by iteratively adding to $S$ the smallest element in $S^{+}$
according to the order $\prec_{S}$ (i.e., the earliest in
$\Pi(S,\textsc{seed}(S))$), until $S^{+}$ is empty. The resulting solution is
maximal by definition of strongly accessible set systems. We remark that this
alternative definition of $\textsc{comp}(S)$ still returns a maximal solution
containing $S$, and is thus compatible with canonical reconstruction
(Definition 4.2).

Finally, given the canonical ordering $s_{1},\ldots,s_{|S|}$ of $S$, the core
$\textsc{core}(S)$ of $S$ is the longest prefix $s_{1},\ldots,s_{i}$ of this
order such that $\textsc{comp}(s_{1},\ldots,s_{i})\neq S$; its parent is
$\textsc{parent}(S)=\textsc{comp}(\textsc{core}(S))=\textsc{comp}(s_{1},\ldots,s_{i})$;
its parent index is $\textsc{pi}(S)=s_{i+1}$, i.e., the element following the
last one of the core. It follows by definition of parent that
$\textsc{comp}(\textsc{core}(S)\cup\\{\textsc{pi}(S)\\})=\textsc{comp}(s_{1},\ldots,s_{i+1})=S$.

The function $\textsc{parent}(S)$ defines a forest among solutions, as every
solution has a unique parent, except for the ones such that
$\textsc{comp}(\textsc{seed}(S))=S$ which are called roots, and indeed
correspond to the roots of the forest: these are linear in number (as each has
a unique seed) and can be found by calling $\textsc{comp}(\\{u\\})$ for any
$u\in\kern 0.75pt\mathcal{U}$. The function $\textsc{children}(P,w)$ lets us
perform a traversal of this structure, since it will find all $S$ such that
$P=\textsc{parent}(S)$ and $w=\textsc{pi}(S)$.

###  11.2. Combining proximity search with (conte2019framework, )

Input : Commutable set system $(\kern 0.75pt\mathcal{U},\mathcal{F})$

Prefix-closed order family $\preceq^{s}_{S}$

$\textsc{neighbors}(S,s)$ for canonical reconstruction based on
$\preceq^{s}_{S}$

Output : All maximal $X\in\mathcal{F}$

1 foreach  _$S$ such that $\textsc{comp}(\textsc{seed}(S))=S$_ do

2 $\textsc{enum}(S)$

3

Function  _$\textsc{enum}(X)$_

/* Output $X$ if depth is odd */

4

5 foreach  _$w\in\kern 0.75pt\mathcal{U}\setminus X$_ do

6 foreach  _$S\in\textsc{children}(X,w)$_ do

7 $\textsc{enum}(S)$

8

/* Output $X$ if depth is even */

9

10

11 Function  _$\textsc{children}(P,w)$_

12 foreach  _$R\in\textsc{neighbors}(P,w)$_ do

13 foreach  _$s\in(R\cap Z)\setminus\\{w\\}$_ do

14 $\mathit{prefix}\leftarrow\\{x\in R:x\preceq_{R}^{s}w\\}$

15 $S\leftarrow\textsc{comp}(\mathit{prefix})$

16 if
$\langle\textsc{parent}(S),\textsc{pi}(S),\textsc{seed}(S),\textsc{r}(S)\rangle=\langle
P,w,s,R\rangle$ then yield $S$

17

18

19

20

21Function  _$\textsc{r}(S)$_ /* finds the first $R$ that can generate $S$ */

22 $P\leftarrow\textsc{parent}(S)$

23 $w\leftarrow\textsc{pi}(S)$

24 $s\leftarrow\textsc{seed}(S)$

25 foreach  _$R\in\textsc{neighbors}(P,w)$_ do

26 $\mathit{prefix}\leftarrow\\{x\in R:x\preceq_{R}^{s}w\\}$

27 if  _$\textsc{comp}(\mathit{prefix})=S$_ then return $R$

28

29

30

Algorithm 2 Polynomial-space proximity search

When using proximity search in the canonical reconstruction flavour, we use a
canonical order to define the proximity by Definition 4.1, and a suitable
$\textsc{neighbors}(S,s)$ function such that together they satisfy Definition
3.1. In this section we show that we can combine proximity search and
(conte2019framework, ) for commutable properties, if we can produce a
canonical order for the canonical reconstruction that corresponds to the
solution order induced by $\prec_{S}$.

We then show in Section 11.3 that it is possible to meet these conditions for
canonical orderings that are defined in a greedy way, e.g., by a BFS order
like in bipartite subgraphs. Assuming that we meet these conditions, i.e., we
have a $\textsc{neighbors}(S,s)$ function that fits canonical reconstruction
(Definition 4.2), based on a canonical order defined by a prefix-closed order
$\preceq_{S}$, we define a variant of (conte2019framework, ), showed in
Algorithm 2.

The main idea behind this combination comes from the following observation:
the parent $P=\textsc{parent}(S)=\textsc{comp}(\textsc{core}(S))$ of $S$ is
obtained from a prefix of $S$, and extending this prefix with
$\textsc{pi}(S)$, then applying $\textsc{comp}(\cdot)$, gives us
$\textsc{comp}(\textsc{core}(S)\cup\textsc{pi}(S))=S$ (see definitions in
Section 11.1). On the other hand, we will show that applying Definition 4.1,
$P\tilde{\cap}S$ is exactly $\textsc{core}(S)$. Relying on the neighboring
function $\textsc{neighbors}(P,\textsc{pi}(S))$ of canonical reconstruction,
and the core property defined in (conte2019framework, ), we are able to find
the set $\textsc{core}(S)\cup\textsc{pi}(S)$, and finally obtain $S$.

We can now state:

###### Theorem 11.3.

Given a commutable set system $(\kern 0.75pt\mathcal{U},\mathcal{F})$, a
prefix-closed order family $\preceq^{s}_{S}$ for $(\kern
0.75pt\mathcal{U},\mathcal{F})$, and a function $\textsc{neighbors}(S,s)$ for
canonical reconstruction (Definition 4.2) based on $\preceq^{s}_{S}$,
Algorithm 2 enumerates all maximal solutions of $(\kern
0.75pt\mathcal{U},\mathcal{F})$ without duplication in polynomial delay.

###### Proof.

To prove the correctness, we show that any $S$ is found in
$\textsc{children}(P,w)$ when $P=\textsc{parent}(S)$ and $w=\textsc{pi}(S)$.

We will first prove that there exists a solution
$R\in\textsc{neighbors}(P,\textsc{pi}(S))$ (on Line 2) such that
$\textsc{core}(S)\cup\\{\textsc{pi}(S)\\}\subseteq R$.

Consider the proximity $P\tilde{\cap}S$ by Definition 4.1: the longer prefix
of the solution order of $S$ that is completely in $P$ must include
$\textsc{core}(S)$ since $P=\textsc{comp}(\textsc{core}(S))$. If $w\in P$ then