Alessio Conte
email: conte@di.unipi.it

Roberto Grossi
email: grossi@di.unipi.it

Andrea Marino
email: andrea.marino@unifi.it

Takeaki Uno
email: uno@nii.ac.jp

Luca Versari

Proximity Search For Maximal Subgraph Enumeration

Keywords: • Mathematics of computing → Graph enumeration; Graph algorithms graph enumeration, polynomial delay, proximity search

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 𝑘-Degenerate Subgraphs (for bounded 𝑘), 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.

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, 2 as maximal solutions subsume the information contained in all others, and can be exponentially fewer: For example, a graph may have up to 2 𝑛 cliques, but only 3 𝑛/3 maximal ones [START_REF] Moon | On cliques in graphs[END_REF]. 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 𝑛, the input size, and 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 [START_REF] Johnson | On generating all maximal independent sets[END_REF]. 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 outputpolynomial solution (see, e.g., [START_REF] Avis | Reverse search for enumeration[END_REF][START_REF] Tsukiyama | A new algorithm for generating all the maximal independent sets[END_REF]); 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 [START_REF] Lawler | Generating all maximal independent sets: NP-hardness and polynomial-time algorithms[END_REF].

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 𝑖-th solution is polynomial in 𝑛 and 𝑖, and polynomial delay, where the time elapsed for outputting the next solution is upper bounded by a polynomial in 𝑛. 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.

𝑂 (𝑛 (𝑚 + 𝑛𝛼 (𝑛))) maximal connected induced bipartite sg.

𝑂 (𝑚𝑛) maximal bipartite edge-induced sg.

𝑂 (𝑚 3 ) maximal induced 𝑘-degenerate sg.

𝑂 (𝑚𝑛 𝑘+2 ) maximal edge-induced 𝑘-degenerate sg.

𝑂 (𝑚 3 𝑛 𝑘-1 ) maximal induced chordal sg.

𝑂 (𝑚 2 𝑛) maximal connected induced chordal sg.

𝑂 (𝑚 2 𝑛) maximal edge-induced chordal sg.

𝑂 (𝑚 4 𝑛) maximal induced proper interval sg.

𝑂 (𝑚 2 𝑛 3 ) maximal connected induced proper interval sg.

𝑂 (𝑚𝑛 3 ) maximal connected obstacle-free convex hulls 𝑂 (𝑛 4 ) maximal induced trees 𝑂 (𝑚 2 ) maximal connected induced directed acyclic sg.

𝑂 (𝑚𝑛 2 ) maximal connected edge-induced directed acyclic sg.

𝑂 (𝑚 3 ) Where "sg. " stands for subgraphs, 𝑛 and 𝑚 are the number of vertices and edges, 𝛼 ( •) is the functional inverse of the Ackermann function [START_REF] Endre | Efficiency of a good but not linear set union algorithm[END_REF]. All the algorithms use 𝑂 ( N𝑛) space, where 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., [START_REF] Cohen | Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties[END_REF]. However, the solution graph built with known approaches such as [START_REF] Cohen | Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties[END_REF] 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 𝑆 and 𝑆 * , we will show that we always traverse an edge from 𝑆 to another solution 𝑆 ′ that has higher proximity to 𝑆 * ; as 𝑆 * 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 [START_REF] Cohen | Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties[END_REF][START_REF] Schwikowski | On enumerating all minimal solutions of feedback problems[END_REF], 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 𝑛, 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 inputrestricted 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 [START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF], 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.

𝑂 (𝑛 2 (𝑚 + 𝑛𝛼 (𝑛))) 𝑂 (𝑚) maximal connected induced bipartite sg.

𝑂 (𝑚𝑛 2 ) 𝑂 (𝑚) maximal obstacle-free convex hulls 𝑂 (𝑛 4 ) 𝑂 (𝑛) maximal induced trees 𝑂 (𝑚 2 𝑛 2 ) 𝑂 (𝑚) maximal induced forests 𝑂 (𝑚 2 𝑛 2 ) 𝑂 (𝑚)

Where notation is as in Theorem 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 [START_REF] Lawler | Generating all maximal independent sets: NP-hardness and polynomial-time algorithms[END_REF].

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 [START_REF] Ruskey | Combinatorial generation[END_REF], and can be used to design algorithms that are fast in practice, 3 or that can bound the number of solutions in the worstcase [START_REF] Fedor | Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications[END_REF]. On the other hand, this strategy rarely gives outputpolynomial 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 𝑆, and some element 𝑥 ∉ 𝑆, the hardness of listing solutions maximal within 𝑆 ∪ {𝑥 } 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. [START_REF] Lawler | Generating all maximal independent sets: NP-hardness and polynomial-time algorithms[END_REF], that generalizes ideas from Paull et al. [START_REF] Marvin | Minimizing the number of states in incompletely specified sequential switching functions[END_REF] and Tsukiyama et al. [START_REF] Tsukiyama | A new algorithm for generating all the maximal independent sets[END_REF], and has been formally defined as input-restricted problem by Cohen et al. [START_REF] Cohen | Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties[END_REF].

The intuition is that the solutions obtained this way, using a maximal solution 𝑆 and an element not in 𝑆, 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, [START_REF] Lawler | Generating all maximal independent sets: NP-hardness and polynomial-time algorithms[END_REF] 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. [START_REF] Cohen | Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties[END_REF] 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, [START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF] showed that the same result can be obtained in polynomial space for commutable set systems (which include connectedhereditary 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.

The literature contains many more results concerning the enumeration of maximal/minimal solutions, e.g., [START_REF] Avis | Reverse search for enumeration[END_REF][START_REF] Carmeli | Efficiently enumerating minimal triangulations[END_REF][START_REF] Gély | Enumeration aspects of maximal cliques and bicliques[END_REF][START_REF] Golovach | Output-polynomial enumeration on graphs of bounded (local) linear mim-width[END_REF][START_REF] Koch | An algorithm for finding maximal common subtopologies in a set of protein structures[END_REF][START_REF] Schwikowski | On enumerating all minimal solutions of feedback problems[END_REF], and in particular regarding challenging problems such as the wellknown minimal hypergraph transversals/dominating sets problem [START_REF] Elbassioni | Output-sensitive algorithms for enumerating minimal transversals for some geometric hypergraphs[END_REF][START_REF] Golovach | An incremental polynomial time algorithm to enumerate all minimal edge dominating sets[END_REF][START_REF] Mamadou | On the enumeration of minimal dominating sets and related notions[END_REF]. 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 [START_REF] Conte | New polynomial delay bounds for maximal subgraph enumeration by proximity search[END_REF]. Since its publication, some preprints [START_REF] Brosse | Efficient enumeration of maximal split subgraphs and sub-cographs and related classes[END_REF][START_REF] Cao | Enumerating maximal induced subgraphs[END_REF][START_REF] Kurita | Efficient enumerations for minimal multicuts and multiway cuts[END_REF] have appeared that apply the technique to obtain new output-polynomial algorithms. In particular, [START_REF] Cao | Enumerating maximal induced subgraphs[END_REF] solves the enumeration of Maximal Induced Interval Subgraphs by proposing some variations to proximity search [START_REF] Conte | New polynomial delay bounds for maximal subgraph enumeration by proximity search[END_REF].

3 E.g., implementations of the Bron-Kerbosh [START_REF] Tomita | The worst-case time complexity for generating all maximal cliques and computational experiments[END_REF] algorithm tend to be faster than those of output-polynomial algorithms [START_REF] Conte | Sublinear-space bounded-delay enumeration for massive network analytics: Maximal cliques[END_REF] for listing maximal cliques.

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 outputpolynomial 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 polynomialdelay 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.

PRELIMINARIES

Most of the enumeration problems addressed in this paper consider a simple undirected graph 𝐺, whose vertex set is denoted as 𝑉 (𝐺) and edge set as 𝐸 (𝐺), or simply 𝐺 = (𝑉 , 𝐸) when it is clear from the context. The neighborhood of a vertex 𝑣 is denoted as 𝑁 (𝑣). For brevity, we refer to |𝑉 (𝐺)| as the number 𝑛 of vertices, to |𝐸 (𝐺)| as the number 𝑚 of edges, and to the maximum degree of a vertex in 𝐺 as Δ = max 𝑣 ∈𝑉 |𝑁 (𝑣)|. Furthermore, we assume the vertices to be labeled arbitrarily in increasing order 𝑣 1 , . . . , 𝑣 𝑛 , and say that 𝑣 𝑖 is smaller than 𝑣 𝑗 if 𝑖 < 𝑗. We say that a neighbor of 𝑣 𝑖 is a forward neighbor if it comes later than 𝑣 𝑖 in the order, and a backward neighbor otherwise.

For a set of vertices 𝐴 ⊆ 𝑉 (𝐺), 𝐸 [𝐴] denotes the edges of 𝐺 whose endpoints are both in 𝐴, and 𝐺 [𝐴] the graph (𝐴, 𝐸 [𝐴]), i.e., the subgraph induced in 𝐺 by 𝐴. Similarly, for a set 𝐵 of edges, 𝑉 [𝐵] denotes the vertices incident to an edge in 𝐵 and 𝐺 [𝐵] = (𝑉 [𝐵], 𝐵).

• • • • • • • • • ... • • • • • • v e •
...

•

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 𝑣 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 𝑒 creates a graph with exponentially many maximal edgeinduced 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.

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) 𝐴, we will sometimes use 𝐴 to refer to both the vertex set (resp. edge set) and the subgraph 𝐺 [𝐴] it induces, when this causes no ambiguity. We will also use cc 𝑣 (𝐴) to refer to the connected component of 𝐺 [𝐴] which includes the vertex 𝑣. For further notation, we refer to the standard terminology in [START_REF] Diestel | Graph Theory[END_REF]. For a set of vertices 𝐴 ⊆ 𝑉 (𝐺) which corresponds to a solution of the problem at hand, we say that 𝐴 is maximal if there is no 𝐴 ′ ⊆ 𝑉 (𝐺) such that 𝐴 ′ ⊃ 𝐴 and 𝐴 ′ 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 comp(𝐴): this function takes a (not necessarily maximal) solution 𝐴 and "completes" it, returning some maximal solution 𝐴 ′ ⊇ 𝐴. We will refer to the computational cost of this function as C 𝑡 . Note that it is always possible to devise a polynomial-time computable comp(•) 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 [START_REF] Cohen | Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties[END_REF].

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 𝑂 (𝑛) time preprocessing; this means we are able to perform operations like a visit of the graph in 𝑂 (𝑚) time rather than 𝑂 (𝑚 + 𝑛) time.

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 neighbors(•), 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 ∩, 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 neighbors(•) 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 S keeps track of just the last visited solution, we only need to implement the neighbors(•) function. On the other hand, the complexity is mostly hidden behind proving their completeness: Notably, the very notion of proximity ∩ is only used in the proofs, and never actually appears in Algorithm 1. In order to start the algorithm, we need one arbitrary maximal solution 𝑆. We remark that identifying one maximal (not maximum) solution is typically trivial, and can be achieved for example by running comp(∅) when the comp(•) 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 P be a listing problem over a universe U with set of solutions S ⊆ 2 U , where each solution is a subset of the universe. P is proximity searchable if there exists a proximity function ∩ : S × S → 2 U and a neighboring function neighbors(•) : S → 2 S , such that the following holds:

(1) One solution of P can be identified in time polynomial in |U|.

(2) neighbors(•) is computable in time polynomial in |U|.

(3) Given any two distinct solutions 𝑆, 𝑆 * ∈ S, there exists

𝑆 ′ ∈ neighbors(𝑆) such that |𝑆 ′ ∩𝑆 * | > |𝑆 ∩𝑆 * |.
The above conditions imply the following one, which is reported for the sake of clarity.

( 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 neighbors(𝑆) which contain maximal solutions.

) 4
We say that a solution is visited when enum(𝑆) is called. In Algorithm 1 all solutions added to S are visited at most once, thanks to the membership test in the set S; this guarantees that the same solution is never output twice. As the graph defined by neighbors(𝑆) 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, neighbors(𝑆) 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 4-6. As the cost of neighbors(•) is polynomial, and 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 [START_REF] Uno | Two general methods to reduce delay and change of enumeration algorithms[END_REF] 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:

• ∩ is not actually used in Algorithm 1, and does not need to be computed. 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 ∩ and neighbors(•) 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: 𝑆 is an arbitrary solution, and 𝑆 * the "target" solution.

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 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. For a Maximal Connected Induced Bipartite Subgraph 𝑆, we will use as canonical order a BFS-order of 𝐺 [𝑆] 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. 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).

Canonical order and proximity. Simply assume that each solution 𝑆 is given an ordering 𝑠 1 , . . . , 𝑠 |𝑆 | of its elements which will satisfy some problem-specific conditions. We require that any prefix 𝑠 1 , . . . , 𝑠 𝑖 of this order corresponds to a (non-maximal) solution {𝑠 1 , . . . , 𝑠 𝑖 }. In the rest of the paper, we will refer as prefix of the order to both the sequence 𝑠 1 , . . . , 𝑠 𝑖 and the corresponding set of elements {𝑠 1 , . . . , 𝑠 𝑖 }. 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 ∩ as follows. The key point is that we want to satisfy the proximity requirement for all 𝑆 * (that can be exponentially many) using only a polynomial number of removable sets 𝑋 . 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 P, in which each maximal solution 𝑆 is associated with a canonical ordering 𝑠 1 , . . . , 𝑠 |𝑆 | , we say that P admits a canonical reconstruction if the following holds.

(1) Any prefix 𝑠 1 , . . . , 𝑠 𝑖 of the canonical order of any maximal solution 𝑆 is a (non-maximal) solution of P.

(2) Given a maximal solution 𝑆 and any 𝑣 ∉ 𝑆, there is set X ⊆ 2 𝑆 of removables, such that • X = {𝑋 1 , 𝑋 2 , . . .} can be computed in polynomial time.

• 𝑆 \ 𝑋 𝑖 ∪ {𝑣 } is a solution of P for any 𝑋 𝑖 ∈ X.

• For any 𝑆 * such that 𝑣 is the canonical extender of 𝑆, 𝑆 * , there is at least one 𝑋 𝑖 ∈ X such that (𝑆 ∩𝑆 * ) ∩ 𝑋 𝑖 = ∅.5 (3) There is a polynomial-time computable function comp(𝐴) which takes a solution 𝐴 of P and returns a maximal solution 𝐴 ′ ⊇ 𝐴 of P.

We further define the canonical reconstruction function, as neighbors(𝑆, 𝑣) =

𝑋 𝑖 ∈X comp((𝑆 \ 𝑋 𝑖 ) ∪ {𝑣 })
and this corresponds to the solutions 𝑆 ′ ∈ neighbors(𝑆) for which 𝑣 is the canonical extender of 𝑆, 𝑆 ′ . Hence, neighbors(𝑆) is obtained as 𝑣 ∈𝑉 (𝐺) neighbors(𝑆, 𝑣). 6We 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 𝑆 ∪ {𝑣 } that do not intersect the proximity, or equivalently solutions contained in 𝑆 ∪ {𝑣 } that fully contain the proximity.

We also recall that a polynomial-time computable function comp(•) 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).

Finally, we show how canonical reconstruction immediately implies the maximal listing problem at hand is proximity searchable, using the neighbors(•) 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 P that satisfies Definition 4.2 satisfies the four conditions of Definition 3.1. Condition ( 1) is trivially satisfied, say, using comp(∅). As for condition [START_REF] Batagelj | An o(m) algorithm for cores decomposition of networks[END_REF], recall that

neighbors(𝑆) = 𝑣 ∈𝑉 (𝐺) 𝑋 𝑖 ∈X (comp(𝑆 \ 𝑋 𝑖 ∪ {𝑣 })).
Considering that both |𝑉 (𝐺)| and |X| are polynomial, and comp(•) takes polynomial time, it follows that computing neighbors(𝑆) takes polynomial time.

For condition (3), consider the canonical extender 𝑣 for 𝑆, 𝑆 * : By Definition 4.2 there is 𝑋 𝑖 ∈ X such that 𝑋 𝑖 ∩ (𝑆 ∩𝑆 * ) = ∅; it holds that 𝑆 ′ = comp(𝑆 \ 𝑋 𝑖 ∪ {𝑣 }) ∈ neighbors(𝑆, 𝑣) ⊆ neighbors(𝑆), and

(𝑆 ∩𝑆 * ) ∪ {𝑣 } ⊆ 𝑆 ′ , thus |𝑆 ′ ∩𝑆 * | > |𝑆 ∩𝑆 * | because of 𝑣.
Finally, condition (4) is satisfied by looking at the definition of proximity in Definition 4.1: fixed 𝑆 * , the proximity 𝑆 ∩𝑆 * is maximized if 𝑆 ⊇ 𝑆 * , as we have 𝑆 ∩𝑆 * = 𝑆 * = 𝑆; however, as this is a maximal listing problem, all solutions are inclusion-wise maximal, meaning that 𝑆 ⊇ 𝑆 * is only true for 𝑆 = 𝑆 * . □

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).

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 𝐺 is bipartite if its vertices can be partitioned into two sets 𝑉 0 , 𝑉 1 , such that 𝑉 0 ∩ 𝑉 1 = ∅, 𝑉 0 ∪ 𝑉 1 = 𝑉 (𝐺), and both 𝐺 [𝑉 0 ] and 𝐺 [𝑉 1 ] are edge-less graphs. Equivalently, 𝐺 is bipartite if it has no cycle of odd length. Maximal bipartite subgraphs have also been studied as minimal odd cycle transversals [START_REF] Kratsch | Compression via matroids: a randomized polynomial kernel for odd cycle transversal[END_REF], as one is the complement of the other.

The problem of listing all bipartite (and induced bipartite) subgraphs has been efficiently solved in [START_REF] Wasa | Efficient enumeration of bipartite subgraphs in graphs[END_REF]. However, to the best of our knowledge, neither the techniques in [START_REF] Wasa | Efficient enumeration of bipartite subgraphs in graphs[END_REF] 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 𝑆 (which are the endpoints of the bold edges) and a vertex 𝑣 ∉ 𝑆, to then try to list all the maximal solutions contained in the induced subgraph 𝐺 [𝑆 ∪ {𝑣 }]; however, 𝐺 [𝑆 ∪ {𝑣 }] 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 [START_REF] Cohen | Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties[END_REF][START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF][START_REF] Lawler | Generating all maximal independent sets: NP-hardness and polynomial-time algorithms[END_REF]. 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 [START_REF] Cohen | Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties[END_REF]. 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 𝐺 as a pair of vertex sets ⟨𝐵 0 , 𝐵 1 ⟩, with 𝐵 0 ∩ 𝐵 1 = ∅ and 𝐵 0 ∪ 𝐵 1 ⊆ 𝑉 (𝐺), such that 𝐺 [𝐵 0 ] and 𝐺 [𝐵 1 ] are edge-less graphs. By convention, 𝐵 0 is the side of the bipartition containing the vertex of smallest label among those in the subgraph. In case 𝐺 [𝐵 0 ∪ 𝐵 1 ] has multiple connected components, this applies to all components. This way, any bipartite subgraph (connected or not) always has a unique representation ⟨𝐵 0 , 𝐵 1 ⟩. We will sometimes use simply 𝐵 to refer to the subgraph 𝐺 [𝐵 0 ∪ 𝐵 1 ] induced by ⟨𝐵 0 , 𝐵 1 ⟩. When performing comp(𝐵) (defined at the end of Section 2) and 𝐵 is not connected, this may move some vertices from 𝐵 0 to 𝐵 1 and vice versa due to different components becoming connected; even when 𝐵 is connected, if a vertex with smaller label than all others in 𝐵 is added to 𝐵 1 , then 𝐵 0 and 𝐵 1 are immediately swapped to preserve the invariant of the smallest vertex being in 𝐵 0 . We define the intersection between two bipartite subgraphs 𝐵 and 𝐵 ′ as the set of all shared vertices, i.e.: 𝐵 ∩ 𝐵 ′ = (𝐵 0 ∪ 𝐵 1 ) ∩ (𝐵 ′ 0 ∪ 𝐵 ′ 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.

Listing Maximal Connected Induced Bipartite Subgraphs

Let 𝐵 = ⟨𝐵 0 , 𝐵 1 ⟩ be a maximal induced bipartite subgraph of 𝐺, and 𝑣 a vertex not in 𝐵, i.e., in 𝑣 ∈ 𝑉 (𝐺) \𝐵. Looking at Definition 4.2, we immediately observe that a polynomial-time computable function comp(•) 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 𝐺 [𝐵] starting from its vertex of smallest label, say 𝑏 1 . In this order, a vertex 𝑢 precedes a vertex 𝑣 if the distance of 𝑢 from 𝑏 1 is smaller than that of 𝑣 or, in case the distance is equal, 𝑢's label is smaller than 𝑣's. Last ingredient for Definition 4.2 is the set X ⊆ 2 𝐵 , that contains just two removables. In order to get a bipartite graph, it is possible to make two removables as follows:

𝑋 0 = 𝑁 (𝑣) ∩ 𝑆 0 = {8, 11}, 𝑋 1 = 𝑁 (𝑣) ∩ 𝑆 1 = {5, 7, 10} 𝑆 \ 𝑋 1 ∪ {𝑣 } = {2, 3, 8, 11, 12} (top) 𝑆 \ 𝑋 0 ∪ {𝑣 } = {2,
• 𝑋 0 = 𝑁 (𝑣) ∩ 𝐵 0 , • 𝑋 1 = 𝑁 (𝑣) ∩ 𝐵 1 .
That is, remove all the neighbors of 𝑣 in one of the two sides 𝐵 𝑖 : clearly, 𝑣 can be included in 𝐵 𝑖 as it is now only adjacent to vertices of 𝐵 1-𝑖 . 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 𝑣. The removables become as follows:

• 𝑋 0 = 𝐵 \ cc 𝑣 ({𝑣 } ∪ (𝐵 0 \ 𝑁 (𝑣)) ∪ 𝐵 1 ), • 𝑋 1 = 𝐵 \ cc 𝑣 ({𝑣 } ∪ (𝐵 1 \ 𝑁 (𝑣)) ∪ 𝐵 0 ).
That is, we remove all vertices not in the same connected component as 𝑣, after introducing 𝑣 and removing all its neighbors in either 𝐵 0 or 𝐵 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).

neighbors(𝐵, 𝑣) = {comp(cc 𝑣 ({𝑣 }∪ (𝐵 𝑖 \𝑁 (𝑣)) ∪𝐵 1-𝑖 )) | 𝑖 = 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 𝑣'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 𝐵, 𝐵 * and their canonical extender 𝑣, we have 𝐵 ∩𝐵 * ∩ 𝑋 𝑖 = ∅ for either 𝑖 = 0 or 𝑖 = 1; this will imply that

|𝐵 ′ ∩𝐵 * | > |𝐵 ∩𝐵 * | for 𝐵 ′ = comp(cc 𝑣 ({ 𝑣 } ∪ (𝐵 𝑖 \ 𝑁 ( 𝑣)) ∪ 𝐵 1-𝑖 ))
, so the proximity is successfully increased.

If 𝐵 ∩𝐵 * = ∅ the claim is trivially true, as we can consider 𝑏 * 1 as canonical extender. Otherwise, let 𝑍 = 𝐵 ∩𝐵 * = {𝑏 * 1 , . . . , 𝑏 * ℎ }, and we have 𝑣 = 𝑏 * ℎ+1 . By Definition 5.1, 𝑍 is a connected induced bipartite subgraph, meaning that it allows a unique bipartition 𝑍 0 , 𝑍 1 (with 𝑍 0 being the set containing the vertex of smallest label in 𝑍 , that is, 𝑏 * 1 ). Since 𝑏 * 1 is the vertex of smallest label in 𝐵 * , it will be in 𝐵 * 0 , so it follows that 𝑍 0 ⊆ 𝐵 * 0 and 𝑍 1 ⊆ 𝐵 * 1 . Let 𝑗 be the value in {0, 1} such that 𝑣 ∈ 𝐵 * 𝑗 , and observe that 𝑁 ( 𝑣)∩𝑍 𝑗 ⊆ 𝑁 ( 𝑣)∩𝐵 * 𝑗 = ∅. Furthermore, we know that 𝑏 * 1 ∈ 𝐵 * 0 and 𝑏 * 1 ∈ 𝐵, but we do not know whether 𝑏 * 1 ∈ 𝐵 0 or 𝑏 * 1 ∈ 𝐵 0 ; however, there exists a value 𝑖 in {0, 1} such that either

𝑏 * 1 ∈ (𝐵 𝑖 ∩𝐵 * 𝑗 ) or 𝑏 * 1 ∈ (𝐵 1-𝑖 ∩ 𝐵 * 1-𝑗 ). Observe that 𝑍 𝑗 ⊆ 𝐵 * 𝑗 ∩ 𝐵 𝑖 and 𝑍 1-𝑗 ⊆ 𝐵 * 1-𝑗 ∩ 𝐵 1-𝑖 . Finally, let 𝐵 ′ = cc 𝑣 ({ 𝑣 } ∪ (𝐵 𝑖 \ 𝑁 ( 𝑣)) ∪ 𝐵 1-𝑖 )
, and consequently we have

𝑋 𝑖 = 𝐵 \ 𝐵 ′ . 𝑍 is fully contained in 𝐵 ′ : the only vertices removed from 𝐵 by 𝑋 𝑖 are (i) those in 𝑁 ( 𝑣) ∩𝐵 𝑖 , but 𝑁 ( 𝑣) ∩𝐵 𝑖 ∩𝑍 ⊆ 𝑁 ( 𝑣) ∩ 𝐵 𝑖 ∩ 𝑍 𝑗 ⊆ 𝑁 ( 𝑣) ∩ 𝑍 𝑗 = ∅, and (ii) the vertices not in the connected component of 𝑣 in 𝐺 [{ 𝑣 } ∪ (𝐵 𝑖 \ 𝑁 ( 𝑣)) ∪ 𝐵 1-𝑖 ]
, but no such vertex can be in 𝑍 as 𝑍 ∪ { 𝑣 } is a prefix of the canonical order of 𝐵 * , so it induces a connected subgraph.

We thus have that 𝑍 ∪ { 𝑣 } ⊆ 𝐵 ′ , meaning that 𝑋 𝑖 ∩ 𝑍 = ∅, which proves the claim. Constructively, we can finally observe how the maximal solution 𝐵 ′′ = comp(𝐵 ′ ) is the one produces by the algorithm which increases the proximity to 𝐵 * , as we have

{𝑏 * 1 , . . . , 𝑏 * ℎ , 𝑏 * ℎ+1 } ⊆ 𝐵 ′′ ∩𝐵 * and thus |𝐵 ′′ ∩𝐵 * | ≥ |𝐵 ∩𝐵 * | + 1. □
From this, we immediately obtain the correctness of the algorithm.

Theorem 5.4. A proximity search algorithm (Algorithm 1), using the neighbors(•) function from Definition 5.2 outputs all Maximal Connected Induced Bipartite Subgraphs of a graph 𝐺 without duplication with 𝑂 (𝑛𝑚) delay.

Proof. The correctness follows from Theorem 4.3. The delay is dominated by the cost of the neighbors(𝐵) function, i.e., calling 𝑂 (𝑛) times neighbors(𝐵, 𝑣). The cost of the latter is 𝑂 (𝑚) time to compute cc 𝑣 (•), and 𝑂 (𝑚) time to compute the comp(•) function by Lemma 5.9 (delayed to Section 5.4 for compactness). The statement follows. □

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 𝐵 is the sequence 𝑏 1 , . . . , 𝑏 |𝐵 | obtained by first ordering the connected components of 𝐺 [𝐵] 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 𝐵 be the subgraph shown in (d) and 𝐵 * as that shown in (e), the canonical order of 𝐵 is ⟨1, 2, 7, 8, 11, 10⟩, that of 𝐵 * is ⟨1, 2, 7, 9, 12, 10⟩. By the definition of proximity for canonical reconstruction, we also obtain 𝐵 ∩𝐵 * = {1, 2, 7}.

The removables become simpler for this case, as we can simply remove 𝑁 (𝑣) ∩ 𝐵 𝑖 for 𝑖 = 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).

neighbors(𝐵, 𝑣) = {comp({𝑣 } ∪ (𝐵 𝑖 \ 𝑁 (𝑣)) ∪ 𝐵 1-𝑖 ) | 𝑖 = 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 neighbors(•) function from Definition 5.6 outputs all maximal induced bipartite subgraphs of a graph 𝐺 without duplication with 𝑂 (𝑛(𝑚 + 𝑛𝛼 (𝑛))) delay.

Proof

𝐵 ′ = comp(cc 𝑣 ({𝑣 } ∪ (𝐵 0 \ 𝑁 (𝑣)) ∪ 𝐵 1 )) or 𝐵 ′ = comp(cc 𝑣 ({𝑣 } ∪ (𝐵 1 \ 𝑁 (𝑣)) ∪ 𝐵 0 )
), this prefix is expanded with 𝑢, giving us 𝐵 ′ ∩𝐵 * ⊇ (𝐵 ∩𝐵 * ) ∪ {𝑢} and proving correctness.

As for the delay, we can see that the cost of neighbors(𝐵) is bounded as for the connected case by 𝑂 (𝑛) times the cost of neighbors(𝐵, 𝑣), which is in turn bounded by 𝑂 (𝑚 + 𝑛𝛼 (𝑛)) by Lemma 5.9, proving the statement. □

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 𝐴 and 𝐵, let 𝐸 (𝐴, 𝐵) be the set of edges with one endpoint in 𝐴 and the other in 𝐵. 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 ⟨𝐵 0 , 𝐵 1 ⟩ of 𝑉 (𝐺), where the bipartite subgraph corresponds to the edges in 𝐸 (𝐵 0 , 𝐵 1 ). For readability, we use the shorthand 𝐸 𝐵 ≡ 𝐸 (𝐵 0 , 𝐵 1 ) to refer to the edges of the bipartite subgraph 𝐵.

We also observe that the problem is hereditary and allows for a polynomial time computable comp(•) function. We define the canonical order of a solution 𝐵 by taking the canonical order 𝑏 1 , . . . , 𝑏 |𝐵 | of the vertices of 𝐺 [𝐵] according to Definition 5.1,7 then taking the edges of 𝐵 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" 𝐵 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 𝑒 = {𝑎, 𝑏}, where 𝑎 < 𝑏, are as follows.

•

𝑋 0 = (𝐸 𝐵 \ 𝑁 𝐸 (𝑎)) ∪ {𝑒}), • 𝑋 1 = (𝐸 𝐵 \ 𝑁 𝐸 (𝑏)) ∪ {𝑒}).
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 𝐵 0 or 𝐵 1 , we take an edge 𝑒 = {𝑎, 𝑏} with both endpoints in the same 𝐵 𝑖 , and try to move the two vertices 𝑎 and 𝑏 to opposite sides of the bipartition.

This can be achieved by including the edge 𝑒 in the solution, and then, to preserve the subgraph being bipartite, removing either 𝑁 𝐸 (𝑎) or 𝑁 𝐸 (𝑏) from it. Finally we apply the comp(•) function to obtain a solution that is maximal.

More formally, recalling 𝐸 𝐵 ≡ 𝐸 (𝐵 0 , 𝐵 1 ), we define neighbors(𝐵) as

𝑒={𝑎,𝑏 } ∈𝐸 (𝐺)\𝐸 𝐵 {comp((𝐸 𝐵 \𝑁 𝐸 (𝑎))∪{𝑒}), comp((𝐸 𝐵 \𝑁 𝐸 (𝑏))∪{𝑒})}
Consider two solution 𝐵 and 𝐵 * , with 𝑒 1 , . . . , 𝑒 |𝐸 (𝐵 * 0 ,𝐵 * 1 ) | being the canonical order of 𝐵 * . Furthermore, let 𝐵 ∩𝐵 * = {𝑒 1 , . . . , 𝑒 ℎ } and 𝑒 = 𝑒 ℎ+1 = {𝑎, 𝑏} the canonical extender, i.e., the first edge in the ordering of 𝐵 * which is not in 𝐵.

By the definition of the canonical ordering, we have that {𝑒 1 , . . . , 𝑒 ℎ } is a connected bipartite subgraph, meaning that it allows a unique bipartition 𝐵 ′ = 𝐵 ′ 0 , 𝐵 ′ 1 of its incident vertices. As {𝑒 1 , . . . , 𝑒 ℎ } ∪ { 𝑒} is also a connected bipartite subgraph, for some 𝑗 ∈ {0, 1} we must have both

𝑁 (𝑎) ∩ 𝐵 ′ 𝑗 = ∅ and 𝑁 (𝑏) ∩ 𝐵 ′ 1-𝑗 = ∅. Since 𝐵 ′ is included in 𝐵, we must have either (i) 𝐵 ′ 𝑗 ⊆ 𝐵 𝑖 and 𝐵 ′ 1-𝑗 ⊆ 𝐵 1-𝑖 or (ii) 𝐵 ′ 1-𝑗 ⊆ 𝐵 𝑖 and 𝐵 ′ 𝑗 ⊆ 𝐵 1-𝑖 .
Recall now that both 𝑎 and 𝑏 are assumed wlog to be in 𝐵 𝑖 , meaning that 𝑁 (𝑎) ∩ 𝐵 𝑖 = 𝑁 (𝑏) ∩ 𝐵 𝑖 = ∅. In the (i) case, we have 𝑁 (𝑏) ∩ 𝐵 1-𝑖 ∩ 𝐵 ′ 1-𝑗 = ∅, so removing 𝑁 𝐸 (𝑏) from 𝐵 may not remove any edge of 𝐵 ′ . Thus comp((𝐸 𝐵 \ 𝑁 𝐸 (𝑏)) ∪ { 𝑒}), which belongs to neighbors(𝐵), will contain (𝐵 ∩𝐵 * ) ∪ {𝑒}.

In the (ii) case, we have 𝑁 (𝑎) ∩ 𝐵 1-𝑖 ∩ 𝐵 ′ 1-𝑗 = ∅, removing 𝑁 𝐸 (𝑎) may not remove any edge of 𝐵 ′ . Thus comp((𝐸 𝐵 \ 𝑁 𝐸 (𝑎)) ∪ { 𝑒}), which also belongs to neighbors(𝐵), will contain (𝐵 ∩𝐵 * ) ∪ {𝑒}.

This means that in both cases, neighbors(𝐵) will yield a solution 𝑆 ′ that contains (𝐵 ∩𝐵 * ) ∪ {𝑒}, i.e., such that

|𝑆 ′ ∩𝑆 * | > |𝑆 ∩𝑆 * |.
As the complexity is bounded by 𝑂 (𝑚) calls to the neighbors(𝐵 𝑖 , 𝐵 1-𝑖 , 𝑒) function, whose cost is again bounded by that of comp(•), that is 𝑂 (𝑚 2 ) time (By Lemma 5.9), the following theorem holds: Theorem 5.8. Maximal (edge-induced) Bipartite Subgraphs can be listed in 𝑂 (𝑚 3 ) time delay.

Complexity

In order to complete the analysis, let us look at the cost C 𝑡 for the three variants considered: Lemma 5.9. C 𝑡 is 𝑂 (𝑚) for Maximal Connected Induced Bipartite Subgraphs, 𝑂 (𝑚 + 𝑛𝛼 (𝑛)) for Maximal Induced Bipartite Subgraphs, and 𝑂 (𝑚 2 ) for Maximal Edge-induced Bipartite Subgraphs, where 𝑛 and 𝑚 are the number of vertices and edges, and 𝛼 (•) is the functional inverse of the Ackermann function [START_REF] Endre | Efficiency of a good but not linear set union algorithm[END_REF].

Proof. C 𝑡 is a bound for computing the comp(𝑆) function as well as a canonical order. As the latter is computed by a BFS, it takes 𝑂 (𝑚) time in all three cases, let us then focus on comp(𝑆):

Firstly, observe that using 𝑂 (𝑛) space and standard data structures, we can mark to which bipartition each vertex of 𝑆 belongs to (using 𝑂 (𝑚) time to compute the initial bipartition of 𝑆), and which vertices have been already tested for addition, in 𝑂 (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 comp(𝑆) 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 𝑆 (in no particular order): we can find these initial "candidates" in 𝑂 ( 𝑥 ∈𝑆 |𝑁 (𝑥)|) = 𝑂 (𝑚) time, marking each vertex as tested the first time so it is not tested again. Whenever trying to add a vertex 𝑣 to 𝑆, we must pay 𝑂 (|𝑁 (𝑣)|) time to check that all its neighbors belong to the same bipartition of 𝑆, in which case 𝑣 belongs to the other one. If 𝑣 is not addible, we immediately discard it. If instead we add it to 𝑆, we mark it with the correct bipartition, and update the list of candidate with its neighbors in 𝑂 (|𝑁 (𝑣)|) time. As each vertex is only tested once and only added once, the total cost of C 𝑡 is bounded by 𝑂 (𝑚).

For the non-connected case, we further keep track of connected components via union-find [START_REF] Endre | Efficiency of a good but not linear set union algorithm[END_REF] (actually, for each connected component we will keep track of its two partitions). To test a vertex 𝑣 we must just check that it does not connect to two vertices in different partitions 𝐶 0 and 𝐶 1 of the same connected component 𝐶 of 𝑋 : this can be done in 𝑂 (|𝑁 (𝑣)|). Updating the union-find can be done in total 𝑂 (𝑛𝛼 (𝑛)), where 𝛼 (•) is the functional inverse of the Ackermann function [START_REF] Endre | Efficiency of a good but not linear set union algorithm[END_REF]. 8Once 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 𝑂 (𝑚). The total time is thus 𝑂 (𝑚 + 𝑛𝛼 (𝑛)).

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 𝑂 (𝑚) time, for a total cost of 𝑂 (𝑚 2 ). □

MAXIMAL K-DEGENERATE SUBGRAPHS

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

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

A degeneracy ordering of 𝐺 is an order of its vertices in which each vertex 𝑣 has at most 𝑑 neighbors occurring later than 𝑣, where 𝑑 is the degeneracy of 𝐺. It is well known that a degeneracy ordering can be found in 𝑂 (𝑚) time by iteratively removing the vertex of smallest degree [START_REF] Batagelj | An o(m) algorithm for cores decomposition of networks[END_REF]. 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 [START_REF] Eppstein | Listing all maximal cliques in large sparse real-world graphs[END_REF]; 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 [START_REF] Don | k-degenerate graphs[END_REF].

We are interested in listing all maximal 𝑘-degenerate subgraphs of a graph 𝐺. An output-polynomial algorithm is known for maximal induced 𝑘-degenerate subgraphs if 𝐺 is chordal [START_REF] Conte | Efficient enumeration of maximal k-degenerate subgraphs in a chordal graph[END_REF], but no output-polynomial results are known for general graphs.

Maximal Induced k-Degenerate Subgraphs

A subgraph of a 𝑘-degenerate graph is 𝑘-degenerate so the property is hereditary, and degeneracy can be computed in linear time so we can implement the comp(•) function in polynomial time.

Given a maximal induced 𝑘-degenerate subgraph 𝑆, we define its canonical order as the reverse of its degeneracy ordering, i.e., an ordering 𝑠 1 , . . . , 𝑠 |𝑆 | , such that 𝑠 |𝑆 | , . . . , 𝑠 1 is the degeneracy ordering of 𝑆. 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 |𝑁 (𝑠 𝑖 ) ∩ {𝑠 1 , . . . , 𝑠 𝑖-1 }| ≤ 𝑘, i.e., the neighbors of 𝑠 𝑖 in 𝑆 that precede 𝑠 𝑖 in the canonical order are at most 𝑘. 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 𝑘. The neighboring function is obtained as follows. Less formally, when computing neighbors(𝑆, 𝑣), we try to add 𝑣 to 𝑆 as canonical extender. Since 𝑆 is maximal, this violates the degeneracy constraint, so we remove all neighbors of 𝑣 except at most 𝑘 (the removable set being 𝑁 (𝑣) \ 𝐾). The resulting subgraph 𝐷 = {𝑣 } ∪ 𝑆 \ (𝑁 (𝑣) \ 𝐾) is 𝑘-degenerate: as 𝐷 \ {𝑣 } is 𝑘-degenerate as it is a subgraph of 𝑆, and any degeneracy ordering of 𝐷 \ {𝑣 } becomes a 𝑘-degenerate ordering for 𝐷 if we prepend 𝑣 in the beginning, because 𝑣 has at most 𝑘 neighbors in 𝐷. This means 𝑁 (𝑣) \ 𝐾 is a suitable removable according to Definition 4.2.

We now show how these choices for 𝐾 satisfy Definition 4.2: we iteratively try for 𝐾 all possible subsets of 𝑆 ∩ 𝑁 (𝑣) of size at most 𝑘. These combinations, i.e., the number of removables, are 𝑂 ( 𝑖 ∈ {1,...,𝑘 }

|𝑁 (𝑣) | 𝑖

) = 𝑂 (𝑛 𝑘 ), which is polynomial when 𝑘 is bounded.

Let us now look at a target solution 𝑆 * such that 𝑣 is the canonical extender for 𝑆, 𝑆

′ = comp({𝑣 }∪ 𝑆 \ (𝑁 (𝑣) \ 𝐾) = comp({𝑣 } ∪ 𝑆 \ (𝑁 (𝑣) \ (𝑆 ∩𝑆 * )).
In other words, we only remove some neighbors of 𝑣 from 𝑆, but all the neighbors that are part of 𝑆 ∩𝑆 * are not removed, thus

𝑆 ′ ⊇ {𝑣 } ∪ (𝑆 ∩𝑆 * ), meaning |𝑆 ′ ∩𝑆 * | > |𝑆 ∩𝑆 * |.
As for the running time, let us consider the cost C 𝑡 of a comp(𝑋 ) call. 𝑘-degenerate graphs are hereditary, i.e., if a vertex is not addible it will not become addible later, so we need to test each 𝑣 ∈ 𝑉 (𝐺) \𝑋 for addition at most once. As testing the degeneracy takes 𝑂 The problem is thus proximity searchable, and the delay of the listing algorithm is the cost of neighbors(𝑆), i.e., running 𝑂 (𝑛) times neighbors(𝑆, 𝑣) (maintaining S is negligible). More formally: Theorem 6.2. Maximal Induced 𝑘-degenerate Subgraphs are proximity searchable when 𝑘 is constant, and can be enumerated in 𝑂 (𝑚𝑛 𝑘+2 ) time delay.

We now observe that 1-degenerate subgraphs are exactly forests, and the connected ones are trees; setting 𝑘 = 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.

Maximal Edge-induced k-Degenerate Subgraphs

We now consider Maximal Edge-induced k-Degenerate Subgraphs, i.e., maximal sets of edges 𝐸 ⊆ 𝐸 (𝐺) that correspond to a 𝑘-degenerate subgraph of 𝐺. An algorithm for this case can be obtained by exploiting the structure of the induced one. In the following, let 𝑁 𝐸 (𝑣) be the edge neighborhood of 𝑣, i.e., the set of edges of 𝐺 incident to the vertex 𝑣. Note that edge-induced 𝑘-degenerate subgraphs are also hereditary, and so comp(•) takes polynomial time.

Let 𝑆 be an edge-induced 𝑘-degenerate subgraph, and let 𝑣 1 , . . . , 𝑣 𝑙 be the canonical order of the vertices of 𝐺 [𝑆] (i.e., the graph containing only edges in 𝑆 and vertices incident to them), as in Section 6.1.

The canonical ordering of 𝑆 is obtained by selecting the edges of 𝐵 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 𝑣 1 , . . . , 𝑣 𝑙 in order, and for each adding the edges towards the preceding vertices one by one. Whenever all the edges from 𝑣 𝑖 to the preceding vertices have been added, we can observe that the graph corresponds to that induced in 𝐺 [𝑆] by the vertices {𝑣 1 , . . . , 𝑣 𝑖 }. By the canonical order of the vertices defined in Section 6.1, this means 𝑣 𝑖 has at most 𝑘 neighbors in {𝑣 1 , . . . , 𝑣 𝑖-1 }.

Again, the proximity ∩ is given by Definition 4.1.

We can now define the neighboring function: In other words, we add an edge 𝑒 = {𝑎, 𝑏} to 𝑆, then force 𝑎 (or, respectively, 𝑏) to have degree at most 𝑘, by removing all other edges incident to it except at most 𝑘 -1, as well as adding 𝑒. The resulting graph is 𝑘-degenerate as 𝑎 (respectively 𝑏) has degree 𝑘, and the residual graph is a subgraph of 𝑆, which is 𝑘-degenerate, so it is possible to compute a degeneracy ordering.

Consider now two solutions 𝑆, 𝑆 * , with 𝑆 ∩𝑆 * = {𝑒 1 , . . . , 𝑒 ℎ }, and let 𝑒 = {𝑥, 𝑦} be the earliest edge in the canonical order of 𝑆 * that is not in 𝑆, i.e, 𝑒 ℎ+1 . Assume wlog that 𝑥 comes before 𝑦 in the canonical (vertex) ordering of 𝑆 * . In this ordering, 𝑦 has at most 𝑘 neighbors preceding it, i.e, |{𝑒 1 , . . . , 𝑒 ℎ } ∩ 𝑁 𝐸 (𝑦)| ≤ 𝑘. Furthermore, by the same definition, all edges incident to 𝑦 that precede 𝑒 in the ordering must be between 𝑦 and another vertex which comes earlier than 𝑥, and thus than 𝑦, in the ordering, thus they may be at most 𝑘 -1 (𝑘, including 𝑒 itself, from 𝑦 to 𝑥). Let 𝐾 ′ be the set of these edges (not including 𝑒).

When computing neighbors(𝑆, 𝑦, 𝑥), we consider all subsets of edges in 𝑆 incident to 𝑦 of size at most 𝑘 -1. By what stated above, at some point we will consider exactly 𝐾 ′ . In this case, we will obtain 𝑆 ′ = comp({ 𝑒} ∪ (𝑆 \ 𝑁 𝐸 (𝑦)) ∪ 𝐾 ′ ). This must contain all edges in {𝑒 1 , . . . , 𝑒 ℎ }, as we only removed edges neighboring 𝑦, but all those in {𝑒 1 , . . . , 𝑒 ℎ } were in 𝐾 ′ . Thus we have {𝑒 1 , . . . , 𝑒 ℎ } ∪ 𝑒 = {𝑒 1 , . . . , 𝑒 ℎ , 𝑒 ℎ+1 } ⊆ 𝑆 ′ , which implies |𝑆 ′ ∩𝑆 * | > |𝑆 ∩𝑆 * |. The case in which 𝑥 comes after 𝑦 in the ordering is similarly satisfied by neighbors(𝑆, 𝑥, 𝑦).

Finally, we only need to show that neighbors(𝑆) takes polynomial time to compute: indeed this is 𝑂 (𝑚) times the cost of neighbors(𝑆, 𝑦, 𝑥), which in turn has the cost of computing comp(•) once for each possible considered set 𝐾. These latter are 𝑂 ( 𝑁 𝐸 (𝑦) 𝑘-1 ), and the comp(•) can be easily implemented in 𝑂 (𝑚 2 ) (as above, testing degeneracy takes 𝑂 (𝑚) 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 𝑘 is constant. We can thus state the following: Theorem 6.4. Maximal Edge-induced 𝑘-degenerate Subgraphs are proximity searchable when 𝑘 is constant, and can be enumerated with delay 𝑂 ( 𝑛 𝑘-1 𝑚 3 ).

MAXIMAL CHORDAL SUBGRAPHS 7.1 Maximal Induced Chordal Subgraphs

A graph 𝐺 is chordal if every cycle in 𝐺 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., [START_REF] Jean | An introduction to chordal graphs and clique trees[END_REF][START_REF] Chandran | A linear time algorithm for enumerating all the minimum and minimal separators of a chordal graph[END_REF][START_REF] Okamoto | Linear-time counting algorithms for independent sets in chordal graphs[END_REF]). While the problem of finding a largest chordal subgraph has been studied [START_REF] Bliznets | Largest chordal and interval subgraphs faster than 2 𝑛[END_REF], to the best of our knowledge there are no known enumeration results.

We here aim at listing Maximal Induced Chordal Subgraphs of 𝐺. The problem is hereditary, and chordality can be tested in 𝑂 (𝑚) time [START_REF] Donald J Rose | Algorithmic aspects of vertex elimination on graphs[END_REF], thus comp(•) takes 𝑂 (𝑚𝑛) time.

A (sub)graph is chordal iff it allows a perfect elimination ordering {𝑣 1 , . . . , 𝑣 𝑛 } of its vertices, i.e., such that for all 𝑖, 𝑁 (𝑣 𝑖 ) ∩ {𝑣 𝑖+1 , . . . , 𝑣 𝑛 } is a clique [START_REF] Conte | Efficient enumeration of maximal k-degenerate subgraphs in a chordal graph[END_REF]. We can obtain this by recursively removing simplicial vertices, i.e., vertices whose neighborhood in the residual graph is a clique. 9As 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 𝑂 (𝑛) maximal cliques, and a vertex 𝑣 participates in 𝑂 (|𝑁 (𝑣)|) maximal cliques [START_REF] Conte | Efficient enumeration of maximal k-degenerate subgraphs in a chordal graph[END_REF].

We use this to define the canonical order, which is then combined with Definition 4.1 to obtain the proximity function ∩. Definition 7.1 (Canonical Order for Maximal (Connected) Induced Chordal Subgraphs). The canonical order {𝑠 1 , . . . , 𝑠 |𝑆 | } of 𝑆 is the reverse of its perfect elimination ordering, i.e., such that {𝑠 |𝑆 | , . . . , 𝑠 1 } is the perfect elimination ordering. This way, the neighbors of 𝑣 that precede 𝑣 in the ordering form a clique. Furthermore, when 𝑆 is a connected subgraph, any prefix {𝑠 1 , . . . , 𝑠 𝑗 ≤ |𝑆 | } 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. Less formally, we add a vertex 𝑣 to 𝑆, then remove all its neighbors except one maximal clique 𝑄 (meaning the removable by definition of canonical reconstruction will be 𝑁 (𝑣) \𝑄). In the connected case, we further remove vertices not in the connected component of 𝑣.

We can easily see that 𝑆 ∪ {𝑣 } \ (𝑁 (𝑣) \𝑄) is chordal, by showing a perfect elimination ordering: 𝑣 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 𝑆, which is chordal as induced chordal subgraphs are hereditary.

We now need to prove the last condition; let 𝑆 and 𝑆 * be two solutions, 𝑆 ∩𝑆 * = {𝑠 * 1 , . . . , 𝑠 * ℎ } and 𝑣 = 𝑠 * ℎ+1 the earliest vertex in the canonical order of 𝑆 * not in 𝑆.

By the canonical order, 𝑁 ( 𝑣) ∩ (𝑆 ∩𝑆 * ) = 𝑁 ( 𝑣) ∩ {𝑠 * 1 , . . . , 𝑠 * ℎ } is a clique. When computing neighbors(𝑆, 𝑣), as we try all maximal cliques, for some 𝑄 we will have 𝑁 ( 𝑣) ∩ (𝑆 ∩𝑆 * ) ⊆ 𝑄. The resulting 𝑆 ′ will thus contain all neighbors of 𝑣 in 𝑆 ∩𝑆 * , and thus all of 𝑆 ∩𝑆 * , plus 𝑣, meaning that |𝑆 ′ ∩𝑆 * | > |𝑆 ∩𝑆 * |, which proves the correctness the neighbors(•) function.

Finally, neighbors(•) can indeed be computed in polynomial time. We first need to list all maximal cliques containing 𝑣 in 𝐺 [𝑆 ∪ {𝑣 }]: these correspond exactly to the maximal cliques of 𝐺 [(𝑆 ∩ 𝑁 (𝑣)) ∪ {𝑣 }]; as 𝑣 is adjacent to all vertices in (𝑆 ∩ 𝑁 (𝑣)), we can further say that these correspond exactly to all maximal cliques of 𝐺 [(𝑆 ∩ 𝑁 (𝑣))], to which we then add 𝑣 (𝑣 can clearly be added to any clique of 𝐺 [(𝑆 ∩ 𝑁 (𝑣))] since it is adjacent to all its vertices).

This correspondence is important, because 𝐺 [(𝑆 ∩ 𝑁 (𝑣))] is an induced subgraph of 𝑆, and thus a chordal graph.

Recall now that a chordal graph has 𝑂 (𝑛) cliques and they can be listed in 𝑂 (𝑚) time (e.g., by computing a perfect elimination ordering [START_REF] Donald J Rose | Algorithmic aspects of vertex elimination on graphs[END_REF] each clique 𝑄, we must further compute the corresponding comp(•) 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 𝑂 (𝑚) time, the cost C 𝑡 of a comp(•) is 𝑂 (𝑚𝑛) time (which dominates the time for checking membership in 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 𝑂 (𝑚) which does not affect the 𝑂 (𝑚𝑛) bound. The total cost will be 𝑂

(𝑚𝑛 + 𝑚 • 𝑚𝑛) = 𝑂 (𝑚 2 𝑛)
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 𝑂 (𝑚 2 𝑛) time delay.

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 nonconnected case.

We can then devise a neighboring function neighbors(𝑆, (𝑥, 𝑦)) like the first one in Definition 7.2, where we use an edge (𝑥, 𝑦) as canonical extender.

When adding an edge (𝑥, 𝑦) to a maximal solution 𝑆, we try as 𝑄 all maximal cliques containing either 𝑥 or 𝑦 in 𝐺 [𝑆]. In any 𝑆 * (for which (𝑥, 𝑦) is the canonical extender) one between 𝑥 and 𝑦 will occur later in the canonical ordering; wlog, let us say 𝑦. As the canonical ordering is based on a reversed perfect elimination ordering, the neighbors of 𝑦 preceding 𝑦 in the canonical order of 𝑆 * form a clique (including 𝑥 as well). Thus the neighboring funciton will eventually consider a clique 𝑄 containing 𝑦 and all its preceding neighbors, and when this happens the proximity with 𝑆 * is extended. The number of neighboring solutions generated this way will be 𝑂 ( (𝑥,𝑦) ∈𝐸 (𝐺) |𝑁 (𝑥

)| + 𝑁 |(𝑦)|) = 𝑂 (𝑚𝑛).
The only further requirement is a polynomial time comp(•) function which needs to be applied to each neighboring solution: this follows from [START_REF] Heggernes | Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions[END_REF], who prove that edge-induced chordal subgraphs are sandwich monotone. In other words, if a edge-induced chordal subgraph 𝑆 ⊆ 𝐸 (𝐺) is not maximal, then there is always a single edge 𝑒 ∈ 𝐸 (𝐺) \ 𝑆 such that 𝑆 ∪ {𝑒} is a chordal subgraph.

This means comp(•) can be computed in a greedy way by testing, up to 𝑚 times, that any of the 𝑂 (𝑚) remaining edges in the graph can be added, which takes 𝑂 (𝑚) time, for a total cost C 𝑡 = 𝑂 (𝑚 3 ). The total cost follows. Theorem 7.4. Maximal Edge-induced Chordal Subgraphs are proximity searchable, and can be listed with 𝑂 (𝑚 4 𝑛) time delay.

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 [START_REF] Cao | Enumerating maximal induced subgraphs[END_REF] (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 retaliationfree paths.

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 [START_REF] Fulkerson | Incidence matrices and interval graphs[END_REF]. 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 𝐺. 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 𝑆 has two unique interval representation represented by a sequence 𝑣 1 , . . . , 𝑣 |𝑆 | , and its reverse. 10 The canonical order 𝑣 1 , . . . , 𝑣 |𝑆 | of a Maximal Proper Interval Subgraph 𝑆 is defined as the sequence given by the interval representation of 𝑆 which has as 𝑠 1 the smallest among the two possible values.

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

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 𝑣 ∈ 𝑉 (𝐺) \𝑆 as canonical extender. Next, we want to identify the right way of inserting 𝑣 in the interval representation of 𝑆. As the interval length is fixed to 1, there are 5|𝑆 | possibilities: for any other 𝑤 ∈ 𝑆, we can place 𝑣 ending just before / just after the start of 𝑤, exactly overlapping 𝑤, or starting just before / just after the end of 𝑤. We can observe how these capture all possible ways to insert 𝑣, since given any other placement we can slide 𝑣 in any direction until it is about to gain or lose an overlap, i.e., one of the endpoints of 𝑣 will approach the endpoint of another interval, which puts us into one of the 5|𝑆 | cases above. Finally, we have to make the representation consistent, by removing from 𝑆 ∪ {𝑣 }:

• All vertices (intervals) coming after 𝑣 in this representation.

• All neighbors of 𝑣 that do not overlap its interval.

• All non-neighbors of 𝑣 that do overlap its interval.

• Finally, all vertices that have become disconnected from the connected component containing 𝑣 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 𝑋 , and let us call 𝑆 ′ = comp(cc 𝑣 (𝑋 )). The following example illustrates these operations on the example graphs from Figure 4.

Example. 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 𝐺), and 11 and 12 (not overlapping 5 but neighbors of 5 in 𝐺); 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 comp(•), and has greater proximity with 𝑏 than 𝑎.

Indeed, 𝑆 ∩𝑇 = {1, 2, 3, 4}, while the maximal solution obtained maximalizing (f) contains 1, 2, 3, 4, 5.

The set neighbors(𝑆) will be made of the 𝑆 ′ obtained by trying both representations of 𝑆, for each all 𝑣 ∈ 𝑉 (𝐺) \ 𝑆, and for each all possible insertions, for a total of 𝑂 (𝑛 2 ) neighboring solutions.

We now show that, given 𝑆,𝑇 , we always obtain some

𝑆 ′ ∈ neighbors(𝑆) such that |𝑆 ′ ∩𝑇 | > |𝑆 ∩𝑇 |.
Let the proximity 𝑆 ∩𝑇 be 𝑡 1 , . . . , 𝑡 𝑖-1 : this is a prefix of 𝑇 , and since it is a connected subgraph, its vertices in the same order as in 𝑇 in one of the two representations of 𝑆. Furthermore, let 𝑣 be our canonical extender.

Looking at the canonical order of 𝑇 , consider the placement of 𝑡 𝑖 relative to the preceding intervals 𝑡 1 , . . . , 𝑡 𝑖-1 . Now, consider the case where 𝑣 = 𝑡 𝑖 , the correct one between the two representations of 𝑆 is considered, and the placement of 𝑣 relative to 𝑡 1 , . . . , 𝑡 𝑖-1 is the same as 𝑡 𝑖 in 𝑇 .

As we try all possible placements for 𝑣 = 𝑡 𝑖 , and as 𝑡 1 , . . . , 𝑡 𝑖-1 is a connected subgraph of 𝑇 , we will also try the placement of 𝑡 𝑖 considered above. The correct placement of 𝑣 tells us that, when we remove all intervals coming after 𝑣 from 𝑆 ∪ {𝑣 }, we do not remove vertices from 𝑡 1 , . . . , 𝑡 𝑖-1 . The placement also tells us that all neighbors of 𝑣 in 𝑡 1 , . . . , 𝑡 𝑖-1 overlap with 𝑣 in the interval representation, while all non-neighbors of 𝑣 in 𝑡 1 , . . . , 𝑡 𝑖-1 do not, so vertices of 𝑡 1 , . . . , 𝑡 𝑖-1 are not removed in the remaining steps. It follows that the set 𝑋 obtained is a proper interval subgraph of 𝐺 containing 𝑡 1 , . . . , 𝑡 𝑖 , and that

𝑆 ′ = comp(𝑋 ) is such that |𝑆 ′ ∩𝑇 | > |𝑆 ∩𝑇 |.

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 𝑆 1 , . . . , 𝑆 𝑗 be the connected components of 𝑆, and 𝑇 1 , . . . ,𝑇 𝑘 those of 𝑇 , for some 𝑇 .

We will have that 𝑆 ∩𝑇 consists of some complete connected components of 𝑇 , as well as a (possibly empty) subset of one component 𝑇 𝑖 . The canonical extender 𝑡 𝑖 will be the earliest vertex of the canonical ordering of 𝑇 𝑖 that is not in 𝑆. We can also observe that each of these components is contained itself in some connected component of 𝑆.

When we select a canonical extender 𝑣, we also select a component 𝑆 𝑖 (of course, trying all possibilities): we aim to find the component which contains the partially formed 𝑇 𝑖 .

As we add 𝑣 to 𝑆, we can immediately remove from 𝑆 all neighbors of 𝑣 in 𝑆 \ 𝑆 𝑖 , as indeed as 𝑡 𝑖 only has neighbors in 𝑇 𝑖 .

We then proceed as in the connected case, ordering 𝑆 𝑖 in the two possible ways, and trying all 𝑂 (𝑛) insert possibilities. However, we must take care of the fact that 𝑆 𝑖 may contain more than one connected component of 𝑇 : components preceding 𝑣 in the order are (they cannot overlap 𝑣 as they precede the other elements of 𝑇 𝑖 , to which they are not adjacent), but there may be some following 𝑣.

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

Specifically, we remove from 𝑆 𝑖 ∪ {𝑣 } the following vertices:

• All vertices (intervals) between 𝑡 𝑖-1 and 𝑣.

• All vertices (intervals) coming after 𝑣 in this representation that are adjacent to 𝑣 or to 𝑡 𝑖-1 . • All neighbors of 𝑣 that do not overlap its interval.

• All non-neighbors of 𝑣 that do overlap its interval.

In this way, all the vertices removed could not be part of the proximity 𝑆 ∩𝑇 : the ones between 𝑡 𝑖-1 and 𝑡 𝑖 cannot be in the interval representation since 𝑡 𝑖-1 and 𝑡 𝑖 are consecutive in the interval representation of 𝑇 ; the others we remove were neighbors of 𝑡 𝑖-1 or 𝑡 𝑖 , but did not precede them in the interval representation (i.e., in the canonical order), so they could not be part of 𝑆 ∩𝑇 . On the other hand, the remaining intervals following 𝑣 are now in a separate connected component, thus the interval representation of the resulting graph is consistent, contains 𝑡 1 , . . . , 𝑡 𝑖 (for any 𝑇 , when the correct choices are performed), and we can apply the comp(•) function to obtain a neighboring solution 𝑆 ′ .

Running time

As for the complexity, the neighboring function tries 𝑂 (𝑛) candidates for 𝑣, and for each, 5|𝑆 | = 𝑂 (𝑛) possible placements in 𝑆, in each of the 2 representations. For each, the cost of the procedure is dominated by the application of the comp(𝑋 ) call.

Since we can test whether a graph is a proper interval graph in 𝑂 (𝑚) time [START_REF] Kellogg | Linear algorithms to recognize interval graphs and test for the consecutive ones property[END_REF], the comp(𝑋 ) function can be implemented in 𝑂 (𝑚𝑛) time as for chordal subgraphs, giving us a total cost per solution of 𝑂 (𝑛 3 𝑚) time.

For the non-connected version, we must consider two additional phases: for each 𝑣, we firstly selected a connected component 𝑆 𝑖 of 𝑆, and secondly we selected the possible 𝑡 𝑖-1 among the neighbors of 𝑣. We can bound the number of connected components by 𝑂 (𝑛), and, rather than adding another factor 𝑂 (𝑛) for the choice of 𝑡 𝑖-1 , we can observe how each distinct pair 𝑣, 𝑡 𝑖-1 corresponds to an edge, so the number of possible 𝑣 and 𝑡 𝑖-1 pairs is 𝑂 (𝑚), for a total complexity of 𝑂 (𝑛 3 𝑚 2 ) Theorem 8.1. Maximal Induced Proper Interval Subgraphs and Maximal Connected Induced Proper Interval Subgraphs are proximity searchable, and can be listed with 𝑂 (𝑛 3 𝑚 2 ) time delay and 𝑂 (𝑛 3 𝑚) time delay, respectively.

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., [START_REF] Deits | Computing Large Convex Regions of Obstacle-Free Space Through Semidefinite Programming[END_REF][START_REF] Savin | An algorithm for generating convex obstacle-free regions based on stereographic projection[END_REF]).

In this section we solve the following formulation of the problem: let 𝑉 and 𝑋 be two sets of elements, which corresponds to points on a 2-dimensional plane. 𝑉 represents the point of interest for our application, and 𝑋 represents the obstacles. For short, let |𝑉 | = 𝑗 and |𝑋 | = ℎ, and let 𝑛 = 𝑗 + ℎ 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 𝑆 ⊆ 𝑉 such that the convex hull of 𝑆 does not contain any element of 𝑋 . 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 𝑉 , i.e., adding edges between its points, and considering the problem of Maximal Connected Obstacle-free Convex hulls.

Maximal Obstacle-free Convex Hulls

Again, note that the problem is hereditary, i.e., each subset 𝑆 ′ of a solution 𝑆 clearly also admits a convex hull which does not include elements of 𝑋 (since it will be contained in that of 𝑆).

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 𝑆 and an element 𝑣 ∈ 𝑉 \ 𝑆. As 𝑆 is maximal, there is at least one element 𝑥 ∈ 𝑋 included in the convex hull of 𝑆 ∪ {𝑣 }. This element 𝑥 casts two "shadows" 𝑆 1 and 𝑆 2 on 𝑆, seen by 𝑣: consider the straight line between 𝑣 and 𝑥, 𝑆 1 consists of all elements of 𝑆 above this line, and 𝑆 2 of all those below it. It is straightforward to see how both the convex hull of 𝑆 1 ∪ {𝑣 } and that of 𝑆 2 ∪ {𝑣 } do not contain 𝑥. Any element of 𝑆 that falls exactly on the line may not participate in any solution involving 𝑣. 11 Furthermore, any element 𝑥 ′ ∈ 𝑋 above this line, and still in the convex hull of 𝑆 ∪ {𝑣 }, further casts two shadows on 𝑆 1 , as any element below this line casts them on 𝑆 2 . If we repeat this process for all elements of 𝑋 in the convex hull of 𝑆 ∪ {𝑣 } we obtain a number of shadows of 𝑆 which is at most linear in the number of elements of 𝑋 . Let 𝜙 (𝑆, 𝑣) be the set of these shadows. For each of these shadows 𝑆 𝑖 ∈ 𝜙 (𝑆, 𝑣), we have that the convex hull of 𝑆 𝑖 ∪ {𝑣 } may not include elements of 𝑋 , i.e., 𝑆 𝑖 ∪ {𝑣 } is a (possibly not maximal) solution.

The neighboring function is then obtained as follows. Let 𝐼 = 𝑆 ∩𝑆 * = 𝑆 ∩𝑆 * , and 𝑣 any element in 𝑆 * \𝑆. Since 𝐼 ∪ {𝑣 } is contained in moc, 𝑆 * , its convex hull cannot contain any element of 𝑋 . It follows that 𝐼 must be fully contained in a single 𝑆 𝑖 ∈ 𝜙 (𝑆, 𝑣): indeed, if we take two points 𝑢 𝑖 ∈ 𝑆 𝑖 and 𝑢 𝑗 ∈ 𝑆 𝑗 , it is evident by the definition of 𝜙 (𝑆, 𝑣) that the convex hull of {𝑣, 𝑢 𝑖 , 𝑢 𝑗 } (or any superset of it) contains at least an element of 𝑋 . We have that the neighboring function will return

𝑆 ′ = comp(𝑆 𝑖 ∪ {𝑣 }), with 𝐼 ∪ {𝑣 } ⊆ 𝑆 ′ , which implies |𝑆 ′ ∩𝑆 * | > |𝑆 ∩𝑆 * |. The algorithm is thus correct.
As for the complexity, the problem is hereditary, so we may compute a comp(𝑆) call by testing each vertex in 𝑉 \ 𝑆 once. The convex hull of 𝑆 can be computed in 𝑂 (|𝑆 | log |𝑆 |) time [START_REF] Chan | Optimal output-sensitive convex hull algorithms in two and three dimensions[END_REF], and testing a solution consists in checking that each vertex of 𝑋 is not in this hull, which can trivially be done in 𝑂 (|𝑆 | •ℎ) time. The cost of comp(•) is thus 𝑂 ( 𝑗 (ℎ + log 𝑗)) time. For each candidate 𝑣, we have at most ℎ neighboring solutions, and since we need to consider at most 𝑗 candidates, the delay of the algorithm will be 𝑗 • ℎ times the cost of a comp(•) 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 𝑂 ( 𝑗 2 ℎ(ℎ + log 𝑗)) = 𝑂 (𝑛 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 [START_REF] Cohen | Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties[END_REF][START_REF] Lawler | Generating all maximal independent sets: NP-hardness and polynomial-time algorithms[END_REF], and reducing the space usage to 𝑂 (𝑛) by using stateless iteration [START_REF] Conte | Sublinear-space bounded-delay enumeration for massive network analytics: Maximal cliques[END_REF]. However, it is worth observing that proximity search required proving a weaker statement, and allows for an arguably simpler proof.

Maximal Connected Obstacle-free Convex Hulls

We now consider an extension of the problem where on top of 𝑉 and 𝑋 we have a graph structure 𝐺 = (𝑉 , 𝐸) on the points of 𝑉 , and we are interested in listing all maximal set of points 𝑆 ⊆ 𝑉 such that the convex hull of 𝑆 is obstacle-free, and 𝐺 [𝑆] 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 𝑆 𝑖 ∪ {𝑣 } for all 𝑆 𝑖 ∈ 𝜙 (𝑆, 𝑣), but only keeps the connected component of 𝐺 [𝑆 𝑖 ∪ {𝑣 }] containing 𝑣. For two solutions 𝑆 and 𝑆 * , we define 𝑆 ∩𝑆 * as the largest connected component of their intersection 𝑆 ∩ 𝑆 * . We now prove that there is

𝑆 ′ ∈ neighbors(𝑆) such that |𝑆 ′ ∩𝑆 * | > |𝑆 ∩𝑆 * |.
Let 𝐼 = 𝑆 ∩ 𝑆 * = 𝑆 ∩𝑆 * , and 𝑣 any element in 𝑆 * \ 𝑆 such that 𝐺 [𝐼 ∪ {𝑣 }] is connected. Note that a suitable 𝑣 must exist, otherwise 𝐼 would not be connected to the elements of 𝑆 * \ 𝐼 , contradicting the fact that 𝑆 * is a connected solution. Since 𝐼 ∪ {𝑣 } is contained in 𝑆 * , its convex hull cannot contain any element of 𝑋 . It follows that 𝐼 must be fully contained in a single 𝑆 𝑖 ∈ 𝜙 (𝑆, 𝑣). Furthermore, as 𝐼 ∪ {𝑣 } is connected, it must be contained in cc 𝑣 (𝑆 𝑖 ∪ {𝑣 }), the connected component of 𝐺 [𝑆 𝑖 ∪ {𝑣 }] containing 𝑣.

Similarly to the above case, we have that the neighboring function will return

𝑆 ′ = comp(cc 𝑣 (𝑆 𝑖 ∪ {𝑣 })), with 𝐼 ∪ {𝑣 } ⊆ 𝑆 ′ , which implies |𝑆 ′ ∩𝑆 * | > |𝑆 ∩𝑆 * |. The algorithm is thus correct.
The complexity can be also derived from the non-connected case: the only additional step is applying cc 𝑣 (•) before the comp(•) function. As cc 𝑣 (•) takes 𝑂 (𝑚) time, where 𝑚 = |𝐸 (𝐺)| = 𝑂 (𝑛 2 ), we can conclude the following: Theorem 9.4. Maximal Connected Obstacle-free Convex Hulls are proximity searchable, and can be listed in 𝑂 ( 𝑗ℎ(𝑚 + 𝑗 (ℎ + log 𝑗))) = 𝑂 (𝑛 4 ) time delay.

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 𝑁 + (𝑣) the out-neighbors of the vertex 𝑣 and 𝑁 -(𝑣) its in-neighbors. The goal of this section is listing Maximal Induced Connected Acyclic Subgraphs (mcais hereafter) of a given directed graph 𝐺. The problem is connected-hereditary, and acyclicity can be tested in 𝑂 (𝑚) time, thus comp(•) can be implemented in 𝑂 (𝑚𝑛) 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 [START_REF] Schwikowski | On enumerating all minimal solutions of feedback problems[END_REF]. 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 𝑆 is the order {𝑠 1 , . . . , 𝑠 |𝑆 | } such that, for each 𝑠 𝑖 , {𝑠 1 , . . . , 𝑠 𝑖 } is connected, and either {𝑠 1 , . . . , 𝑠 𝑖-1 } ∩ 𝑁 + (𝑠 𝑖 ) = ∅ or {𝑠 1 , . . . , 𝑠 𝑖-1 } ∩ 𝑁 -(𝑠 𝑖 ) = ∅. If multiple orders are possible let it be the lexicographically minimum.

Our algorithm does not need to compute this order or ∩, 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 𝐺 be a single-source acyclic connected graph, and 𝑣 1 , . . . , 𝑣 𝑛 any topological order of 𝐺. Any prefix 𝑣 1 , . . . , 𝑣 𝑖 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 𝐴 ⊆ 𝑆 into 𝑥 as replacing them with a single vertex 𝑥, whose in-and out-neighbors correspond to all vertices in 𝑆 \ 𝐴 were respectively in-and out-neighbors of some vertex in 𝐴.

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

Proof. Let 𝑆 be a Directed Acyclic Graph. Let 𝑣 1 be a source of 𝑆, and 𝑆 1 be the set of vertices reachable by 𝑣 1 , including

𝑣 1 . Let 𝑠 1,1 , . . . , 𝑠 1, |𝑆 1 | a topological ordering of 𝑆 1 .
No vertex in 𝑆 1 can have an out-neighbor outside of 𝑆 1 as otherwise said vertex would be in 𝑆 1 itself. Let instead 𝑆 2 be the set of all vertices in 𝑆 \ 𝑆 1 that can reach some vertex of 𝑆 1 .

If we collapse 𝑆 1 into a vertex 𝑥, we can observe that 𝑆 2 ∪ {𝑥 } is acyclic subgraph with 𝑥 being the only target. Let 𝑥, 𝑠 2,1 , . . . , 𝑠 2, |𝑆 2 | be a reverse topological ordering of 𝑆 2 ∪ {𝑥 }.

If we replace 𝑥 with the previously computed order of 𝑆 1 , we obtain an order 𝑠 1,1 , . . . , 𝑠 We may now repeat this step by collapsing 𝑆 1 ∪ 𝑆 2 into a vertex 𝑥 ′ , and since 𝑥 ′ will be a source, take 𝑆 3 as all vertices reached by 𝑥 ′ in 𝑆 \ (𝑆 1 ∪ 𝑆 2 and take a topological order of 𝑆 3 ∪ {𝑥 ′ }, which we append to the order obtained so far (excluding 𝑥 ′ ).

By iterating steps, we obtain an ordering 𝑠 1,1 , . . . , 𝑠 1, |𝑆 1 | , 𝑠 2,1 , . . . , 𝑠 2, |𝑆 2 | , 𝑠 3,1 , . . . , 𝑠 3, |𝑆 3 | . . . , 𝑠 𝑘,1 , . . . , 𝑠 𝑘, |𝑆 𝑘 | , with 𝑘 ≤ |𝑆 |, that contains all vertices of 𝑆, and such that any prefix will induce a connected subgraph, and any 𝑠 𝑖,𝑗 will have no backward out-neighbors if 𝑖 is odd, and no backward in-neighbors if 𝑖 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 ∩ follows by Definition 4.1. We define the neighboring function as follows. In other words, the function will add 𝑣 to 𝑆. 𝑆 ∪ {𝑣 } is not acyclic, but all cycles must involve 𝑣, so we make it acyclic by removing either all the out-neighbors 𝑁 + (𝑣), which makes 𝑣 a target, or all its in-neighbors 𝑁 -(𝑣), which makes 𝑣 a source. It then takes the connected component containing 𝑣 and feeds the result to comp(•), to surely obtain a mcais.

Consider now two solutions 𝑆 and 𝑆 * , and again let 𝑣 be the first vertex in the canonical order of 𝑆 * which is not in 𝑆 ∩𝑆 Finally, it is straightforward to see that neighbors(𝑆) takes polynomial time, as its cost is bounded by 𝑂 (𝑛) calls to comp(•), which can be implemented in 𝑂 (𝑚𝑛), 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 𝑂 (𝑚𝑛 2 ) time delay.

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 comp(•) function in 𝑂 (𝑚 2 ) time. The canonical order is as follows.

Definition 10.6 (Canonical order for mcaes). Given a mcaes 𝑆, let the canonical ordering of the vertices of 𝐺 [𝑆] according to Definition 10.1 be 𝑣 1 , . . . , 𝑣 |𝑉 [𝑆 ] | .

The canonical ordering of 𝑆 is obtained by selecting the edges of 𝑆 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 𝑒 1 , . . . 𝑒 |𝑆 | of 𝑆 with the following properties: take an edge 𝑒 𝑖 = {𝑣 𝑗 , 𝑣 𝑘 }, assuming wlog 𝑗 < 𝑘. All edges whose latter endpoint comes earlier than 𝑣 𝑘 in the vertex order are preceding 𝑒 𝑖 in the order, thus all edges in the induced subgraph 𝐺 [{𝑣 1 , . . . , 𝑣 𝑘-1 }] will be in the prefix 𝑒 1 , . . . 𝑒 𝑖 of the canonical ordering of 𝑆. By Definition 10.1 𝐺 [{𝑣 1 , . . . , 𝑣 𝑘-1 }] is connected. Finally, the only other edges in 𝑒 1 , . . . , 𝑒 𝑖 are those whose latter endpoint is 𝑣 𝑘 , so their earlier endpoint is in {𝑣 1 , . . . , 𝑣 𝑘-1 }. Thus each prefix 𝑒 1 , . . . 𝑒 𝑖 forms a connected (edge) subgraph, which is also acyclic as it is a subgraph of the acyclic subgraph 𝑆.

Furthermore, it also holds that, for the latter endpoint In other words, we add 𝑒 to 𝑆, and try each of the two possibilities to obtain the latter vertex in the canonical order of 𝑆 * : if it is the tail 𝑣 𝑡 of the edge, surely its backward out-neighborhood in the canonical order of 𝑆 * is not empty as it contains 𝑣 ℎ , so in-neighborhood must be, thus we can safely remove 𝑁 - 𝐸 (𝑣 𝑡 ) to make 𝑆 ∪ {𝑒} acyclic. Conversely, if it is the head 𝑣 ℎ we can safely remove 𝑁 + 𝐸 (𝑣 ℎ ). We thus obtain |𝑆 ′ ∩𝑆 * | > |𝑆 ∩𝑆 * | for some 𝑆 ′ ∈ neighbors(𝑆).

𝑣 𝑘 of 𝑒 𝑖 , ei- ther {𝑣 1 , . . . , 𝑣 𝑘-1 } ∩ 𝑁 + (𝑣 𝑘 ) = ∅ or {𝑣 1 , . . . , 𝑣 𝑘-1 } ∩ 𝑁 -(𝑣 𝑘 ) = ∅. This implies that either {𝑒 1 , . . . , 𝑒 𝑖-1 } ∩ 𝑁 + 𝐸 (𝑣 𝑘 ) = ∅, or {𝑒 1 , . . . , 𝑒 𝑖-1 } ∩ 𝑁 - 𝐸 (𝑣 𝑘 ) = ∅,
We can observe that the cost C 𝑡 of a comp(𝑋 ) call is 𝑂 (𝑚 2 ) since we can test acyclicity in 𝑂 (𝑚) time, which we do up to 𝑚 times, and finding and selecting the edges connected to 𝑋 take in total 𝑂 (𝑚) time as well. As the neighboring function produces 𝑂 (𝑚) solutions, we obtain: Theorem 10.8. Maximal Connected Edge-induced Directed Acyclic Subgraphs are proximity searchable, and can be listed 𝑂 (𝑚 3 ) time delay.

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 𝑛.

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 [START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF]: 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 [START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF] 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 ( U, F ) be a commutable set system, and neighbors(𝑆, 𝑠) a canonical reconstruction function for a proximity search algorithm (see Definition 4.2). If the canonical order relative to the function neighbors(𝑆, 𝑠) satisfies the properties of a prefixclosed order (Definition 11.2), the maximal solutions of ( U, F ) can be enumerated without duplication in polynomial delay and polynomial space.

11.1 Requirements and notation of [START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF] Let us briefly recall the requirements of [START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF]. In a set system ( U, F ), U is the ground set, i.e., the elements constituting the solutions, and F defines the solutions, i.e., 𝑆 ∈ F iff 𝑆 ⊆ U satisfies the property at hand.

A set system is strongly accessible if for any two distinct solutions 𝑆, 𝑆 ′ ∈ F with 𝑆 ⊂ 𝑆 ′ , there exists an element 𝑥 ∈ 𝑆 ′ \ 𝑆 such that 𝑆 ∪ {𝑥 } ∈ 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 𝑆,𝑇 ∈ F with 𝑆 ⊂ 𝑇 , and any 𝑎, 𝑏 ∈ 𝑇 \𝑆, we have that 𝑆 ∪{𝑎} ∈ F ∧𝑆 ∪{𝑏} ∈ F implies 𝑆 ∪ {𝑎, 𝑏} ∈ F . As mentioned in [START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF], it is straightforward to see that both hereditary and connected-hereditary properties correspond to commutable set systems.

Furthermore, we call 𝑍 the set of "singleton solutions", i.e., 𝑍 = {𝑒 ∈ U : {𝑒} ∈ F }, and recall that in any strongly accessible set system 𝑍 ∩𝑆 ≠ ∅ for any 𝑆 ∈ F . We also define, 𝑆 + = {𝑥 : 𝑆 ∪ {𝑥 } ∈ 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 [START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF]). Let Π(𝑋, 𝑣) be a family of orders parameterized by 𝑋 ∈ F and 𝑣 ∈ 𝑋 ∩ 𝑍 such that Π(𝑋, 𝑣) yields a permutation of 𝑋 ∪ 𝑋 + . For 𝑋 ∈ F and 𝑣 ∈ 𝑋 ∩ 𝑍 , let us denote by 𝑥 𝑣 1 , . . . , 𝑥 𝑣 𝑘 the elements of 𝑋 ordered according to Π(𝑋, 𝑣). 12 We call the family Π prefix-closed if for all 𝑋 ∈ F and 𝑣 ∈ 𝑋 ∩ 𝑍 , and 𝑖 ∈ {1, . . . , 𝑘 -1}, the following properties hold:

(first) The minimal element is 𝑣, i.e., 𝑥 𝑣 1 = 𝑣. (prefix) The 𝑖-th prefix 𝑋 𝑖 = {𝑥 𝑣 1 , . . . , 𝑥 𝑣 𝑖 } of 𝑋 is a solution, i.e., 𝑋 𝑖 ∈ F . (greedy) The element 𝑥 𝑖+1 is the minimal element of 𝑋 + 𝑖 ∩ 𝑋 with respect to the order Π(𝑋 𝑖 , 𝑣).

As explained in [START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF], each subset 𝑋 of a maximal solution 𝑆 does not necessarily belong to F (as the set system is not necessarily hereditary). The first property indicates that we can build 𝑆 starting from an element 𝑣 ∈ 𝑆 ∩ 𝑍 , whereas the greedy property indicates that we can iteratively expand 𝑋 = {𝑣 } by considering the elements of 𝑋 ∪ 𝑋 + in a prefix-closed order, so that at any point, the prefix {𝑥 1 , . . . , 𝑥 𝑗 } found so far is a solution thank to the prefix property.

We use the shorthand notation ≺ 𝑡 𝑆 to represent Π(𝑆, 𝑡), where 𝑎 ≺ 𝑡 𝑆 𝑏 for any two elements 𝑎, 𝑏 ∈ U means that 𝑎 occurs before 𝑏 in Π(𝑆, 𝑡).

Given a solution 𝑆 ∈ F we define its seed, seed(𝑆), as the element of smallest id in 𝑆 ∩𝑍 , i.e., the element 𝑠 of smallest id in 𝑆 such that {𝑠} ∈ F . Observe that every non-empty solution 𝑆 of a strongly accessible set system has a seed: since ∅ ⊂ 𝑆, there is some 𝑠 ∈ 𝑆 \ ∅ such that ∅ ∪ {𝑠} = {𝑠} ∈ F .

The simplified notations ≺ 𝑆 corresponds to ≺ 𝑡 𝑆 with 𝑡 = seed(𝑆). When 𝑆 is a maximal solution, ≺ 𝑆 defines an order 𝑠 1 , . . . , 𝑠 |𝑆 | which is called the solution order of 𝑆.

As in [START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF], we will also require a lexicographic comp(•) function: for a solution 𝑆, comp(𝑆) must be obtained by iteratively adding to 𝑆 the smallest element in 𝑆 + according to the order ≺ 𝑆 (i.e., the earliest in Π(𝑆, seed(𝑆))), until 𝑆 + is empty. The resulting solution It is also straightforward to see that each recursive call uses polynomial space, and no solution dictionary S is maintained. However, the depth of the tree is a factor in the space complexity too: to obtain a polynomial space guarantee, we further need to turn the recursive algorithm into a stateless iterative one, as has been done in [START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF].

We can give a general bound with the following parameters: let 𝑞 be the maximum size of a solution; R 𝑇 be the time required to solve neighbors(𝑃, 𝑤); R 𝑁 a bound on the number of solutions returned by it; C 𝑡 be the time required to compute comp(𝑋 ) and O 𝑇 the time required to compute the canonical order of 𝑋 ∪ 𝑋 + . As these bounds are all assumed to be polynomial, we observe their space requirements will be polynomial as well.

Thanks to the alternative output technique, the delay will be bounded by the cost of one iteration of enum(𝑋 ), that is, 𝑂 (| U|) times the cost of children(𝑃, 𝑤). In turn, the cost of children(𝑃, 𝑤) is that of neighbors(𝑃, 𝑤), plus for each of the 𝑂 (R 𝑁 ) solutions 𝑅 returned, the cost of processing Lines 8-11. [START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF] proved that this can be done in 𝑂 (𝑞(O 𝑇 + C 𝑡 )) time for the given definition of r(𝑆). However, our definition of r(𝑆) is different from the one in [START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF], and has a cost of 𝑂 (R 𝑇 + R 𝑁 O 𝑇 ) instead of 𝑂 (O 𝑇 + C 𝑡 ). Thus, the total cost of processing Lines 8-11 is 𝑂 (𝑞(R 𝑇 + R 𝑁 O 𝑇 + C 𝑡 )).

We can thus claim the following:

Theorem 11.4. Given a commutable set system ( U, F ), a prefixclosed order family ⪯ 𝑠 𝑆 for ( U, F ), and a function neighbors(𝑆, 𝑠) for canonical reconstruction (Definition 4.2) based on ⪯ 𝑠 𝑆 , the maximal solutions of ( U, F ) can be enumerated in 𝑂 (| U|R 𝑇 + | U|R 𝑁 𝑞(R 𝑇 + R 𝑁 O 𝑇 + C 𝑡 )) time delay and polynomial space.

BFS-based canonical reconstruction

In this section, we provide a technique to implement the result of Section 11.2 (Theorem 11.4), i.e., a canonical reconstruction order that matches the prefix-closed order requirements, and can be applied to hereditary and connected-hereditary properties. We call this technique BFS-based canonical reconstruction.

While it is possibly not the only way to obtain a suitable order, it is worth defining formally as we will apply it to several problems in the following sections.

We will first define the order for connected-hereditary property, then exploit it to cover the hereditary case. 13 Definition 11.5 (canonical-BFS order for connected-hereditary properties). Let 𝑆 be a solution of a connected-hereditary set system, and 𝑣 any element in 𝑆. The canonical order Π(𝑆, 𝑣) = 𝑠 1 , . . . , 𝑠 |𝑆∪𝑆 + | is the lexicographical order of the tuples ⟨𝑑 𝑣 (𝑠 𝑖 ), 𝑠 𝑖 ⟩, where 𝑑 𝑣 (𝑠 𝑖 ) is the distance between 𝑠 𝑖 and 𝑣 in 𝐺 [𝑆 ∪ {𝑠 𝑖 }].

In other words, we order nodes first by 𝑑 𝑣 (𝑠 𝑖 ), i.e., their distance from 𝑣 in 𝐺 [𝑆], and break ties by vertex id. The same logic applies to nodes 𝑥 of 𝑆 + , for which we use the distance from 𝑣 in 𝐺 [𝑆 ∪ {𝑥 }]. This defines ⪯ 𝑠 𝑆 . Example. For the Maximal Connected Induced Bipartite Subgraph in Figure 2 (b), the order 2, 3, 5, 8, 11, 7, 10 (as defined in Section 4) is given by the tuples ⟨0, 2⟩, ⟨1, 3⟩, ⟨1, 5⟩, ⟨2, 8⟩, ⟨2, 11⟩, ⟨3, 7⟩, ⟨3, 10⟩. 13 Notably, this implies that a BFS-based canonical reconstruction algorithm for the non-connected case immediately follows from one for the connected case. Less formally, we order each component by a BFS strategy as in the above case (since 𝐺 [𝐶 𝑖 ] is connected) using the leader as root (i.e., 𝑠 if the component contains 𝑠, or its smallest id vertex otherwise); then, we concatenate the sequences obtained by putting the one containing 𝑠 first, followed by the others ordered by id of their leader.

Example. For the Maximal Induced Bipartite Subgraph in Figure 2 (d), the order is 1, 2, 7, 8, 11, 10, given by the tuples ⟨1, 0, 1⟩, ⟨1, 1, 2⟩, ⟨7, 0, 7⟩, ⟨7, 1, 8⟩, ⟨7, 1, 11⟩, ⟨7, 2, 10⟩.

Before proving that this defines a prefix-closed order, let us prove this auxiliary lemma: Lemma 11.7. Let 𝑋 be a solution and 𝑋 𝑖 any prefix of its canonical order. The following facts hold:

• ∀𝑧 ∈ 𝑋 + 𝑖 ∩ 𝑋, 𝑐𝑖𝑑 (𝑋 𝑖 , 𝑧) ≥ 𝑐𝑖𝑑 (𝑋, 𝑧) • 𝑐𝑖𝑑 (𝑋 𝑖 , 𝑥 𝑖+1 ) = 𝑐𝑖𝑑 (𝑋, 𝑥 𝑖+1 ) • ∀𝑧 ∈ 𝑋 + 𝑖 ∩ 𝑋, 𝑐𝑖𝑑 (𝑋 𝑖 , 𝑧) = 𝑐𝑖𝑑 (𝑋, 𝑧) ⇒ 𝑑 𝑙 (𝑋 𝑖 , 𝑧) = 𝑑 𝑙 (𝑋, 𝑧). Proof.
First, the leader of each connected component of 𝑋 𝑖 is the same as the leader of the corresponding connected component of 𝑋 (since the leader is always the first element of the connected component in a solution order, and prefixes of components are connected as they are in a BFS order).

Moreover, an element 𝑧 in 𝑋 + ∩ 𝑋 is either directly connected to a connected component of 𝑋 𝑖 , in which case it has the same leader in 𝑋 𝑖 and in 𝑋 by what stated above, or it belongs to its own connected component in 𝐺 [𝑋 𝑖 ∪ {𝑧}], in which case 𝑧 is its own leader in 𝐺 [𝑋 𝑖 ∪ {𝑧}], meaning 𝑐𝑖𝑑 (𝑋 𝑖 , 𝑧) = 𝑧. Since by definition 𝑐𝑖𝑑 (𝑋, 𝑧) ≤ 𝑧, it follows that 𝑐𝑖𝑑 (𝑋, 𝑧) ≤ 𝑐𝑖𝑑 (𝑋 𝑖 , 𝑧), proving the first statement.

We now prove that 𝑐𝑖𝑑 (𝑋 𝑖 , 𝑥 𝑖+1 ) = 𝑐𝑖𝑑 (𝑋, 𝑥 𝑖+1 ): Either 𝑥 𝑖+1 is directly connected to the last connected component of 𝑋 𝑖 (in which case we already proved the equality) or it isn't, in which case 𝑐𝑖𝑑 (𝑋 𝑖 , 𝑥 𝑖+1 ) = 𝑥 𝑖+1 . However, in this case 𝑥 𝑖+1 must be its own leader by definition of the order, so it follows that 𝑐𝑖𝑑 (𝑋, 𝑥 𝑖+1 ) = 𝑥 𝑖+1 , proving the second statement.

Finally, consider 𝑧 ∈ 𝑋 + 𝑖 ∩ 𝑋 such that 𝑐𝑖𝑑 (𝑋 𝑖 , 𝑧) = 𝑐𝑖𝑑 (𝑋, 𝑧). If 𝑐𝑖𝑑 (𝑋, 𝑧) = 𝑧 then 𝑑 𝑙 (𝑋 𝑖 , 𝑧) = 𝑑 𝑙 (𝑋, 𝑧) = 0; otherwise, let 𝑥 𝑙 be the leader of 𝑧 in 𝑋 𝑖 ∪ {𝑧}: 𝑧 is in the same connected component 𝐶 𝑧 as 𝑥 𝑙 in 𝑋 , and 𝑋 𝑖 contains a prefix of the canonical-BFS order of 𝐶 𝑧 ; by the properties of the canonical-BFS order, the shortest path from 𝑥 𝑙 to 𝑧 is in this prefix, implying the third statement. □

We can now observe how this order for hereditary properties also satisfies the properties of Definition 11.2 (first) By definition 𝑠 1 is the first element. (prefix) As this order is defined for hereditary properties, it follows that any subset (hence every prefix) is also a solution. (greedy) We proved in Lemma 11.7 that the tuple associated with each element of 𝑋 + 𝑖 ∩ 𝑋 with respect to 𝑋 𝑖 is either the same or lexicographically greater than the tuple with respect to 𝑋 . As the tuple for 𝑥 𝑖+1 is the same, and since 𝑥 𝑖+1 is the minimum of 𝑋 + 𝑖 ∩ 𝑋 with respect to the order in 𝑋 , it follows that it's also the minimum of 𝑋 + 𝑖 ∩ 𝑋 with respect to the order in 𝑋 𝑖 . We remark that it is possible to generalize this definition using different functions for 𝑑 (•) and 𝑑 𝑙 (•), as long as monotone behaviour can be guaranteed, i.e., 𝑑 (𝑋 𝑖 , 𝑥) (resp. 𝑑 𝑙 (𝑋 𝑖 , 𝑥)) is less than or equal to 𝑑 (𝑋, 𝑥) (resp. 𝑑 𝑙 (𝑋, 𝑥)) when 𝑋 𝑖 is a prefix of 𝑋 .

POLYNOMIAL SPACE ALGORITHMS

In this section we apply the technique defined in Section 11, and give polynomial-space-polynomial-delay proximity search algorithms, proving the bounds given in Theorem 1.2.

For the problems already solved in exponential space in the previous sections, we remark that it is simply necessary to define their canonical order as a canonical-BFS, then apply Theorem 11.4.

Maximal Bipartite Subgraphs

Looking at the canonical orders defined for Maximal Connected Induced Bipartite Subgraphs (Definition 5.1) and Maximal Induced Bipartite Subgraphs (Definition 5.5), we can see that their definitions match exactly those of canonical-BFS for connected-hereditary and hereditary properties (respectively, Definition 11.5 and Definition 11.6). We can thus immediately apply the polynomial space variant of the algorithm, and we proceed to compute its complexity.

The cost O 𝑇 for computing the canonical order will be 𝑂 (𝑚) in all cases, as it corresponds to performing a BFS, while C 𝑡 corresponds to adding edges in a BFS order, which will take 𝑂 (𝑚) on the connected version, but 𝑂 (𝑚 +𝑛𝛼 (𝑛)) on the non-connected one due to the need to dynamically maintain the connected components. The neighboring function for both cases produces a constant number of neighboring solutions, meaning R 𝑁 = 𝑂 (1) and R 𝑇 = 𝑂 (C 𝑡 ). At the same time, all operations require no more than 𝑂 (𝑚) space. Applying Theorem 11.4, we obtain: Theorem 12.1. Maximal Connected Induced Bipartite Subgraphs and Maximal Induced Bipartite Subgraphs of a graph 𝐺 can be enumerated via BFS-based canonical reconstruction (Algorithm 2) in 𝑂 (𝑚) space and, respectively, 𝑂 (𝑞𝑛𝑚) = 𝑂 (𝑛 2 𝑚) and 𝑂 (𝑞𝑛(𝑚 + 𝑛𝛼 (𝑛))) = 𝑂 (𝑛 2 (𝑚 + 𝑛𝛼 (𝑛))) time delay.

Maximal Induced Trees and Forests

As defined above, a forest is an acyclic undirected graph, and a connected forest is called a tree. These are a special cases of 𝑘degenerate subgraphs: 1-degenerate subgraphs are precisely forests, and connected 1-degenerate subgraphs are trees. However, it is worth consider these problems separately, since we can obtain algorithms with lower delay and polynomial space.

It should be observed that listing Maximal Induced Forests corresponds to listing minimal feedback vertex sets in undirected graph: if 𝑆 ⊂ 𝑉 is a Maximal Induced Forest, 𝑉 \ 𝑆 is a minimal feedback vertex set. A polynomial-delay solution for the enumeration of feedback vertex sets (and thus Maximal Induced Forests) has been proposed in [START_REF] Schwikowski | On enumerating all minimal solutions of feedback problems[END_REF]. This result, however, requires exponential space, and does not extend to Maximal Induced Trees.

Furthermore, while the algorithms proposed could be extended to enumerate maximal edge-induced trees and forests, we do not consider it: these correspond to just the spanning trees of a graph, which are already known to be enumerable in polynomial delay and even constant amortized time [START_REF] Shioura | An optimal algorithm for scanning all spanning trees of undirected graphs[END_REF].

Canonical order and neighboring function. Let 𝑆 be a maximal induced tree.

We define its canonical as a canonical-BFS order (Definition 11.5), i.e., the sequence 𝑠 1 , . . . , 𝑠 |𝑆 | given by a BFS order of 𝐺 [𝑆] rooted in the vertex 𝑠 1 of smallest id.

We then define the proximity by canonical reconstruction (Section 4), and we can immediately observe that this order meets the requirements of Section 11. Next, we focus on obtaining a suitable neighboring function.

Definition 12.2 (Neighboring function for Maximal Induced Trees).

We define neighbors(𝑆) = 𝑣 ∈𝑉 (𝐺)\𝑆 neighbors(𝑆, 𝑣).

Then, neighbors(𝑆, 𝑣) is defined as: neighbors(𝑆, 𝑣) = {comp(cc 𝑣 (𝑆 \ 𝑁 (𝑣) ∪ {𝑤, 𝑣 })) : 𝑤 ∈ 𝑁 (𝑣) ∩𝑆 }

The key property here is that each vertex 𝑠 𝑖 ∈ 𝑆 has a single neighbor preceding it in the canonical order, corresponding to its parent in the BFS.

Given two solutions 𝑆,𝑇 , let 𝑡 1 , . . . , 𝑡 |𝑇 | be the canonical order of 𝑇 , and 𝑡 𝑖 be the canonical extender for 𝑆,𝑇 , i.e., the vertex for which 𝑆 ∩𝑇 = {𝑡 1 , . . . , 𝑡 𝑖-1 } ⊆ 𝑆 and 𝑡 𝑖 ∉ 𝑆. Furthermore, let 𝑡 𝑗 be the parent of 𝑡 𝑖 in the canonical BFS-order of 𝑇 , observing that 𝑡 𝑗 ∈ {𝑡 1 , . . . , 𝑡 𝑖-1 }.

To a solution 𝑆 ′ ⊇ {𝑡 1 , . . . , 𝑡 𝑖 }, we can simply add 𝑡 𝑖 to 𝑆, then remove all neighbors of 𝑡 𝑖 except 𝑡 𝑗 so that we have again an acyclic subgraph, and finally discard every vertex not in the same connected component as 𝑡 𝑖 (which will include {𝑡 1 , . . . , 𝑡 𝑖 }). As we do not know which vertex is 𝑡 𝑗 , we of course try all 𝑂 (|𝑁 (𝑡 𝑖 )|) possibilities, thus a suitable 𝑆 ′ is always found.

Complexity. Firstly, we can use the neighbors(𝑆) function to build a proximity search algorithm whose delay is the cost of neighbors(•), and whose space is 𝑂 (N •𝑛) (where N is the number of solutions).

We show the cost of neighbors(•) -and the delay of the algorithmto be 𝑂 (𝑚 Furthermore, as we are satisfying all conditions of Section 11 (the order defined is a canonical BFS-order and the problem is connectedhereditary), we apply Theorem 11.4 to obtain a BFS-based canonical reconstruction algorithm, with higher delay but polynomial space.

We observe that no component of the algorithm will require more than 𝑂 (𝑚) space, and their time complexity is as follows: U = 𝑂 (𝑛), R 𝑇 = 𝑂 (𝑚Δ), R 𝑁 = 𝑂 (Δ) (but as observed above, | U| • R 𝑇 can be better bounded by 𝑂 (𝑚 2 ), and | U| • R 𝑁 can be bounded by 𝑂 (𝑚)), 𝑞 = 𝑂 (𝑛), O 𝑇 = 𝑂 (𝑚) and C 𝑡 = 𝑂 (𝑚). The bound of Theorem 11.4 thus resolves to 𝑂 (𝑚 2 +𝑚𝑞(𝑚Δ+Δ𝑚+𝑚)) = 𝑂 (𝑚𝑞(𝑚Δ)) = 𝑂 (𝑚 2 𝑛 2 ) time. We can thus conclude the following: Theorem 12.3. The Maximal Induced Trees of a graph 𝐺 can be enumerated in 𝑂 (𝑚 2 )-time delay using 𝑂 (N𝑛) space, or alternatively in 𝑂 (𝑚 2 𝑛 2 )-time delay and 𝑂 (𝑚) space.

Maximal Induced Forests

As showed in Section 11.3, a BFS-based canonical reconstruction algorithm for the non-connected case immediately follows from the connected one.

For completeness, we show how the algorithm for Maximal Induced Forests is obtained:

The canonical order is obtained by Definition 11.6, i.e., a canonical-BFS order of each connected component, where different components are then sorted by their vertex of smallest id.

The neighboring function is essentially obtained from the connected case by removing the use of the cc(•) function (as we do not require solutions to be connected).

Definition 12.4 (Neighboring function for Maximal Induced Forests).

We define neighbors(𝑆) = 𝑣 ∈𝑉 (𝐺)\𝑆 neighbors(𝑆, 𝑣).

Then, neighbors(𝑆, 𝑣) is defined as: neighbors(𝑆, 𝑣) = {comp(𝑆 \ 𝑁 (𝑣) ∪ 𝑤) : 𝑤 ∈ 𝑁 (𝑣) ∩ 𝑆 }

The complexity of the components of the algorithm is also inherently the same, with the only difference for the cost C 𝑡 of the comp(•) function: when we add a vertex, we need to make sure that it does not have two neighbors in the same connected component, and update the connected components as we add vertices. The cost of comp(•) will thus be 𝑂 (𝑚 + 𝑛𝛼 (𝑛)) time, obtained by the same logic as for Maximal Bipartite Subgraphs (see Section 5.2), while the rest of the operations are exactly as in the connected case, thus bear the same cost.

We can conclude that neighbors(𝑆, 𝑣) takes 𝑂 (|𝑁 (𝑣)| • (𝑚 + 𝑛𝛼 (𝑛)) time, while neighbors(𝑆) takes 𝑂 ( 𝑣 ∈𝑉 (𝐺) |𝑁 (𝑣)| • (𝑚 + 𝑛𝛼 (𝑛))) = 𝑂 (𝑚(𝑚 + 𝑛𝛼 (𝑛))).

Again, we can obtain an exponential-space algorithm using canonical reconstruction proximity search whose delay is the cost of neighbors(𝑆), and a polynomial-space algorithm using BFS-based canonical reconstruction, whose delay is given by Theorem 11.

CONCLUSIONS

We presented proximity search, a technique for the design of efficient enumeration algorithms, based on defining and traversing a solution graph with bounded out-degree. We showed several application cases, considering problems that did not allow efficient algorithms by known methods, and showing that these allow polynomial delay algorithms by proximity search.

We have provided a guideline, called canonical reconstruction, aimed at factorizing the most effective ways to apply our technique, and facilitating the design of efficient algorithms.

We have further shown a technique that, under suitable conditions, allows us to design proximity search algorithms that require only polynomial space. The results are polynomial-delay and polynomial-space algorithms for several problems whose inputrestricted problem cannot be solved in polynomial time, including non-hereditary ones.

This paper "breaks the barrier" of the input-restricted problem, showing that its complexity does not imply lower bounds in terms of time or space, nor even a trade-off between the two. This closes questions left open since [START_REF] Cohen | Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties[END_REF], furthering our understanding on the complexity of enumeration in set systems.

At the same time, this reinvigorates the open question of which listing problems allow efficient algorithms and which do not, and to define a more complete theory of enumeration complexity. On top of being a useful tool to design efficient algorithms for specific problems, we hope that this technique will be able to help us gain more insight into this general question. that any solution output by the neighboring function is maximalized, i.e., we apply a comp(•) which adds element to it until it is maximal. If we run comp(∅), we can expect to add up to 𝑠 elements, so its worst-case complexity must be Ω(𝑠) time. Binary Decision Diagram [START_REF] Donald | The art of computer programming, volume 4A: combinatorial algorithms[END_REF]. We can see it as a binary tree where leafs are all at depth | U|, and each root-to-leaf path defines a subset of U. We will have a space usage of 𝑂 (N • | U|), while the cost for addition or membership test of a solution will be 𝑂 (| U|) time. This is sufficient for the purpose of our paper as we upper bound 𝑠 by 𝑛 (or 𝑚, for edge-induced subgraphs) in the complexity results, however it is possible to further improve this using a Trie: Trie [START_REF] Donald | The art of computer programming[END_REF]. As above, a solution is represented by a root-to-leaf path. We only have nodes corresponding to including elements, so the depth will be 𝑂 (𝑠), and so the space usage 𝑂 (N • 𝑠), however a node may have 𝑂 (| U|) children. If we keep these children sorted, we can look them up by binary search and have a cost for addition and membership of 𝑂 (𝑠 log | U|); on the other hand, we can get constant time lookup using a hash table, and a cost for addition and membership of 𝑂 (𝑠) time.

3 𝑆

 3 = {2, 3, 5, 7, 8, 10, 11}, with 𝑆 0 = {2, 8, 11}, 𝑆 1 = {3, 5, 7, 10}, and 𝑣 = 12

Figure 3 :

 3 Figure 3: The steps taken by the neighboring function neighbors(𝑆, 𝑣), for a possible solution 𝑆 of the graph in Figure 2 and 𝑣 = 12. The bottom two lines correspond to the neighboring solutions produced by the function neighbors(𝑆, 12).

Definition 6 . 1 (

 61 Neighboring function for Maximal Induced 𝑘-Degenerate Subgraphs). neighbors(𝑆) = 𝑣 ∈𝑉 (𝐺) neighbors(𝑆, 𝑣) Where neighbors(𝑆, 𝑣) = {comp({𝑣 } ∪ 𝑆 \ (𝑁 (𝑣) \ 𝐾) : 𝐾 ⊆ (𝑆 ∩ 𝑁 (𝑣)) and |𝐾 | ≤ 𝑘 }

  (𝑚) time, C 𝑡 = 𝑂 (𝑚𝑛) time. Consider now neighbors(𝑆, 𝑣): firstly, we enumerate each possible 𝐾 ⊆ 𝑁 (𝑣)∩𝑆, which takes 𝑂 ( 𝑖 ∈ {1,...,𝑘 } |𝑁 (𝑣) | 𝑖 ) = 𝑂 (|𝑁 (𝑣)| 𝑘 ) time. For each, we run comp({𝑣 } ∪ (𝑆 \ 𝑁 (𝑣)) ∪ 𝐾), which takes 𝑂 (𝑚𝑛) time. The total cost is 𝑂 (𝑛 𝑘+1 𝑚) time.

Definition 6 . 3 (

 63 Neighboring function for Maximal Edge-induced 𝑘-Degenerate Subgraphs). Let 𝑆 be a maximal edge-induced 𝑘-degenerate subgraph, and 𝑒 = {𝑎, 𝑏} an edge not in 𝑆. We define: neighbors(𝑆) = 𝑒={𝑎,𝑏 } ∈𝐸\𝑆 neighbors(𝑆, 𝑎, 𝑏)∪neighbors(𝑆, 𝑏, 𝑎) Where neighbors(𝑆, 𝑎, 𝑏) = {comp({𝑒} ∪ (𝑆 \ 𝑁 𝐸 (𝑎)) ∪ 𝐾) : 𝐾 ⊆ (𝑆 ∩ 𝑁 𝐸 (𝑎)) and |𝐾 | ≤ 𝑘 -1}

Definition 7 . 2 (

 72 Neighboring function for Maximal (Connected) Induced Chordal Subgraphs). We define neighbors(𝑆) = 𝑣 ∈𝑉 (𝐺)\𝑆 neighbors(𝑆, 𝑣). For the non connected case we define neighbors(𝑆, 𝑣) = {comp(𝑆 ∪ {𝑣 } \ (𝑁 (𝑣) \ 𝑄)) : 𝑄 is a maximal clique of 𝐺 [𝑆 ∪ {𝑣 }] containing v} While for the connected case we define neighbors(𝑆, 𝑣) = {comp(cc 𝑣 (𝑆 ∪ {𝑣 } \ (𝑁 (𝑣) \ 𝑄))) : 𝑄 is a maximal clique of 𝐺 [𝑆 ∪ {𝑣 }] containing v}

  ): 𝐺 [𝑆 ∩ 𝑁 (𝑣)] has at most |𝑁 (𝑣)| vertices and 𝑂 (|𝑁 (𝑣)| 2 ) edges, so we can list all the maximal cliques of 𝐺 [𝑆 ∩ 𝑁 (𝑣)] -and thus all maximal cliques of 𝐺 [𝑆 ∪ {𝑣 }] containing 𝑣-in 𝑂 (|𝑁 (𝑣)| 2 ) time, obtaining at most |𝑁 (𝑣)| maximal cliques. The cumulative cost of listing all cliques for each 𝑣 ∈ 𝑉 (𝐺) \ 𝑆 is thus bounded by 𝑂 ( 𝑣 ∈𝑉 (𝐺)\𝑆 |𝑁 (𝑣)| 2 ) = 𝑂 (𝑚𝑛) time, and the process yields 𝑂 ( 𝑣 ∈𝑉 (𝐺)\𝑆 |𝑁 (𝑣)|) = 𝑂 (𝑚) maximal cliques. For

Figure 4 :

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

Definition 9 . 1 (

 91 Neighboring function for mocs). neighbors(𝑆) = 𝑣 ∈𝑉 (𝐺)\𝑆 neighbors(𝑆, 𝑣) Where neighbors(𝑆, 𝑣) = {comp(𝑆 𝑖 ∪ {𝑣 }) : 𝑆 𝑖 ∈ 𝜙 (𝑆, 𝑣)} Finally, for two solutions 𝑆 and 𝑆 * , we simply define 𝑆 ∩𝑆 * as the intersection 𝑆 ∩ 𝑆 * between their elements.

Definition 9 . 3 (

 93 Neighboring function for mocs).neighbors(𝑆) = 𝑣 ∈𝑉 (𝐺)\𝑆 neighbors(𝑆, 𝑣) Where neighbors(𝑆, 𝑣) = {cc 𝑣 (comp(𝑆 𝑖 ∪ {𝑣 })) : 𝑆 𝑖 ∈ 𝜙 (𝑆, 𝑣)}

Definition 10 . 4 (

 104 Neighboring Function for Maximal Connected Induced Acyclic Subgraphs). For a solution 𝑆 and a vertex 𝑣 ∈ 𝑉 (𝐺) \𝑆, we define neighbors(𝑆) = 𝑣 ∈𝑉 (𝐺)\𝑆 neighbors(𝑆, 𝑣) Where neighbors(𝑆, 𝑣) = {comp(cc 𝑣 ({𝑣 }∪𝑆\𝑁 + (𝑣))), comp(cc 𝑣 ({𝑣 }∪ 𝑆 \ 𝑁 -(𝑣)))}

  * . More formally, let 𝑆 ∩𝑆 * = {𝑠 * 1 , . . . , 𝑠 * ℎ } and 𝑣 = 𝑠 * ℎ+1 . Let 𝑆 ′ = comp(cc 𝑣 ({ 𝑣 } ∪ 𝑆 \ 𝑁 + ( 𝑣))) and 𝑆 ′′ = comp(cc 𝑣 ({ 𝑣 } ∪ 𝑆 \ 𝑁 -( 𝑣))) be the two solutions generated by neighbors(𝑆, 𝑣). By the canonical order of 𝑆 * , we have that (𝑆 ∩𝑆 * ) ∪ { 𝑣 } is connected, and either (𝑆 ∩𝑆 * ) ∩ 𝑁 + ( 𝑣) = ∅ or (𝑆 ∩𝑆 * ) ∩ 𝑁 -( 𝑣) = ∅. It follows that if (𝑆 ∩𝑆 * ) ∩ 𝑁 + ( 𝑣) = ∅, then (𝑆 ∩𝑆 * ) ∪ { 𝑣 } ⊆ cc 𝑣 ({ 𝑣 }∪𝑆 \𝑁 + ( 𝑣)) ⊆ 𝑆 ′ , and otherwise we have (𝑆 ∩𝑆 * )∩𝑁 -( 𝑣) = ∅, which means (𝑆 ∩𝑆 * ) ∪ { 𝑣 } ⊆ cc 𝑣 ({ 𝑣 } ∪ 𝑆 \ 𝑁 -( 𝑣)) ⊆ 𝑆 ′′ . We thus have that either |𝑆 ′ ∩𝑆 * | > |𝑆 ∩𝑆 * | or |𝑆 ′′ ∩𝑆 * | > |𝑆 ∩𝑆 * |, which gives us the second necessary condition of proximity search.

2 )

 2 time: Observe that the cost C 𝑡 a comp(𝑋 ) call is 𝑂 (𝑚) time. We first compute the set of vertices adjacent to 𝑋 , 𝑃 = ∪ 𝑥 ∈𝑋 𝑁 (𝑥); for each vertex 𝑣, we simply need to check that it has exactly one neighbor in 𝑋 , in 𝑂 (|𝑁 (𝑣)|) time, and discard it otherwise. Whenever we add 𝑣 vertex to 𝑋 , we add is neighbors to 𝑃 again in 𝑂 (|𝑁 (𝑣)|) time. The total cost is 𝑂 ( 𝑣 ∈𝑉 (𝐺) |𝑁 (𝑣)|) = 𝑂 (𝑚). Now consider neighbors(𝑆, 𝑣): for each 𝑤 ∈ 𝑁 (𝑣), we must compute cc 𝑣 (𝑆 \ 𝑁 (𝑣) ∪ {𝑤, 𝑣 }), which takes 𝑂 (𝑚), then apply comp(•) which has the same complexity. The cost is thus 𝑂 (|𝑁 (𝑣)| • 𝑚). In turn, this means the cost of neighbors(𝑆) is 𝑂 ( 𝑣 ∈𝑉 (𝐺) |𝑁 (𝑣)| • 𝑚) = 𝑂 (𝑚 2 ).

4 .

 4 For the latter, the costs are obtained adapting the connected version with the new cost of comp(•): U = 𝑂 (𝑛), R 𝑇 = 𝑂 ((𝑚 + 𝑛𝛼 (𝑛))Δ), R 𝑁 = 𝑂 (Δ) (but | U| • R 𝑇 can be better bounded by 𝑂 (𝑚(𝑚+𝑛𝛼 (𝑛))), and | U|•R 𝑁 can be bounded by 𝑂 (𝑚)), 𝑞 = 𝑂 (𝑛), O 𝑇 = 𝑂 (𝑚) and C 𝑡 = 𝑂 (𝑚 + 𝑛𝛼 (𝑛)). The bound of Theorem 11.4 thus resolves to 𝑂 (𝑚(𝑚 + 𝑛𝛼 (𝑛)) + 𝑚𝑞((𝑚 + 𝑛𝛼 (𝑛)) + Δ𝑚 + (𝑚 + 𝑛𝛼 (𝑛)))) = 𝑂 (𝑚𝑞(𝑛𝛼 (𝑛) + Δ𝑚)) time, which we can again upper bound by 𝑂 (𝑚 2 𝑛 2 ) time. We can thus conclude the following: Theorem 12.5. The Maximal Induced Forests of a graph 𝐺 can be enumerated in 𝑂 (𝑚 2 𝑛 2 )-time delay and 𝑂 (𝑚) space.

Algorithm 1 :

 1 Traversal of the solution graph by proximity search.

input : Graph 𝐺 = (𝑉 , 𝐸) and listing problem P output : All (maximal) solutions of P in 𝐺 global : Set S of solutions found, initially empty 1 𝑆 ← an arbitrary solution of P /* (e.g. comp(∅)) */ 2 Call enum(𝑆) 3 Function enum(𝑆) 4 Add 𝑆 to S /* Output 𝑆 if recursion depth is even */ 5 foreach 𝑆 ′ ∈ neighbors(𝑆) do 6 if 𝑆 ′ ∉ S then enum(𝑆 ′ ) /* Output 𝑆 if recursion depth is odd */

  For any fixed 𝑆 * , |𝑆 ∩𝑆 * | is maximized for (and only for) 𝑆 = 𝑆 * . Proof. We first show that if a neighbors(•) function satisfies Definition 3.1, the implicit solution graph it induces is strongly connected. Given any two distinct solutions 𝑆, 𝑆 * ∈ S, we know by Definition 3.1.(3) that there exists 𝑆 ′ ∈ neighbors(𝑆) such that |𝑆 ′ ∩𝑆 * | > |𝑆 ∩𝑆 * |. By induction on 𝑆 and 𝑆 ′ , it follows that we will eventually reach a solution 𝑆 that globally maximizes | • ∩𝑆 * |, which by Definition 3.1.(4) is precisely 𝑆 * .

	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 neighbors(•) function in Algorithm 1. Let us
	formally prove it.
	Theorem 3.2. All proximity searchable listing problems have a
	polynomial delay listing algorithm.

tween 𝑆 and 𝑆 * is the longest prefix 𝑠 * 1 , . . . , 𝑠 * 𝑖 of the canonical order of 𝑆 * whose elements are all contained in 𝑆. It should also be noted that the operation is not symmetric, i.e., we may have 𝑆 ∩𝑆 * ≠ 𝑆 * ∩𝑆. Example. Let 𝑆 be the subgraph shown in Figure 2 (b) and 𝑆 * the

  one shown in (c). Considering the canonical orders mentioned above, we can see that 𝑆 ∩𝑆 * = {2, 3, 8}, while 𝑆 * ∩𝑆 = {2, 3}. Canonical extender. The goal of a proximity search algorithm is to exploit Definition 3.1.(3): given 𝑆, for any 𝑆 * , find some 𝑆 ′ such that |𝑆 ′ ∩𝑆 * | > |𝑆 ∩𝑆 * |. Using Definition 4.1, 𝑆 ∩𝑆 * is a prefix 𝑠 * 1 , . . . , 𝑠 * Guess a removable set 𝑋 ⊆ 𝑆 from 𝑆 ∪ {𝑣 }, i.e., such that 𝑆 \ 𝑋 ∪ {𝑣 } is a solution and 𝑋 ∩ {𝑠 * 1 , . . . , 𝑠 * 𝑖 } = ∅. (3) Obtain 𝑆 ′ as the outcome of comp(𝑆 \ 𝑋 ∪ {𝑣 }).

	Definition 4.1 (proximity). Given two solutions 𝑆 and 𝑆 * , let 1 , . . . 𝑠 * 𝑠 * |𝑆 𝑖 of the canonical order of 𝑆 * , so we want to find any solution 𝑆 ′ that contains a longer prefix, i.e., 𝑠 * 1 , . . . , 𝑠 * 𝑖+1 (possibly ordered differently and interspersed in the canonical order of 𝑆 ′ ). Since we must at least add the vertex 𝑠 * 𝑖+1 , we call 𝑠 * 𝑖+1 the canonical extender of 𝑆, 𝑆 * . Armed with this notion, we want to proceed conceptually as follows for a given solution 𝑆. (1) Guess which node 𝑣 ∉ 𝑆 is the canonical extender 𝑠 * 𝑖+1 (try all possibilities, 𝑛 at most). (2) In essence, we want to add 𝑠 * 𝑖+1 to 𝑆, then turn the result back into a solution by removing some elements, but without affecting the proximity 𝑠 * 1 , . . . , 𝑠 * 𝑖 . Recalling that prefixes of a canonical order are required to be (non-maximal) solutions, indeed 𝑠 * 1 , . . . , 𝑠 * 𝑖+1 is a solution; hence, a removable set 𝑋 always exists (e.g., 𝑋 = 𝑆 \ {𝑠 * 1 , . . . , 𝑠 * 𝑖 }).

* | be the canonical order of 𝑆 * : the proximity 𝑆 ∩𝑆 * be-

  . Consider the solutions 𝐵 and 𝐵 * . Let 𝑏 * 1 , . . . , 𝑏 * |𝐵 Since all the neighbors of 𝑢 in 𝐵 * must be in its same connected component 𝐶 𝐵 * 𝑥 , and the neighbouring function (Definition 5.6) only removes neighbors of 𝑢 from 𝐵, the function may not remove from 𝐵 any vertex of 𝐵 * that is not in 𝐶. As for vertices in 𝐶, 𝐵 ∩𝐵 * 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

* | be the canonical ordering of 𝐵 * by Definition 5.6, 𝐵 ∩𝐵 * = 𝑏 * 1 , . . . , 𝑏 * 𝑖 , and 𝑢 = 𝑏 * 𝑖+1 the canonical extender for 𝐵, 𝐵 * . Let 𝐶 be the connected component of 𝐵 * containing 𝑢.

  𝑁 (𝑣) ∩ 𝑆: since we try as 𝐾 all possible subsets of 𝑁 (𝑣) ∩ 𝑆 of size at most 𝑘, we will eventually have 𝐾 = 𝑁 (𝑣) ∩ {𝑠 * 1 , . . . , 𝑠 * 𝑖-1 }. At this point the neighboring function will yield 𝑆

* , and let 𝑠 * 1 , . . . , 𝑠 * |𝑆 * | be the canonical order of 𝑆 * : if 𝑣 = 𝑠 𝑖 in this order, it follows that 𝑆 ∩𝑆 * = {𝑠 * 1 , . . . , 𝑠 * 𝑖-1 }, and |𝑁 (𝑣) ∩ {𝑠 * 1 , . . . , 𝑠 * 𝑖-1 }| ≤ 𝑘. We also have that {𝑠 * 1 , . . . , 𝑠 * 𝑖-1 } ⊆ 𝑆, so 𝑁 (𝑣) ∩ {𝑠 * 1 , . . . , 𝑠 * 𝑖-1 } ⊆

  1, |𝑆 1 | , 𝑠 2,1 , . . . , 𝑠 2, |𝑆 2 | } which respects Definition 10.1: Each vertex in 𝑠 1,1 , . . . , 𝑠 1, |𝑆 1 | has no backward outneighbor by the topological ordering of 𝑆 1 ; each 𝑠 2,1 , . . . , 𝑠 2, |𝑆 2 | has no backward in-neighbor by the reverse topological ordering of 𝑆 2 , and because vertices of 𝑆 1 can not have out-neighbors outside 𝑆 1 ; finally, every prefix of 𝑠 1,1 , . . . , 𝑠 1, |𝑆 1 | , 𝑠 2,1 , . . . , 𝑠 2,𝑗 is connected, as 𝑥, 𝑠 2,1 , . . . , 𝑠 2,𝑗 is connected, meaning that all vertices in 𝑠 2,1 , . . . , 𝑠 2,𝑗 are connected to some vertex in 𝑆 1 , that is itself connected.

  which gives us our neighboring function: Definition 10.7 (Neighboring Function for mcaes). Let 𝑆 be a mcaes and 𝑒 = (𝑣 𝑡 , 𝑣 ℎ ) a directed edge in 𝐸 (𝐺) \ 𝑆 directed from its tail 𝑣 𝑡 to its head 𝑣 ℎ . Furthermore, let 𝑁 + 𝐸 (𝑣 ℎ ) and 𝑁 - 𝐸 (𝑣 𝑡 ) be the out-edges and in-edges of 𝑣 ℎ and 𝑣 𝑡 , respectively. We define neighbors(𝑆, 𝑣 𝑡 , 𝑣 ℎ ) = {comp(cc 𝑣 𝑡 ({𝑒} ∪ (𝑆 \ 𝑒=(𝑣 𝑡 ,𝑣 ℎ ) ∈𝐸 (𝐺)\𝑆 neighbors(𝑆, 𝑣 𝑡 , 𝑣 ℎ )

	𝑁 -𝐸 (𝑣 𝑡 ))), comp(cc 𝑣 ℎ ({𝑒} ∪ (𝑆 \ 𝑁 + 𝐸 (𝑣 ℎ )))}
	And thus
	neighbors(𝑆) =

  We can observe how this canonical-BFS order Π(𝑆, 𝑣) satisfies the properties of Definition 11.2:14 (first) The first element 𝑠𝑣 1 of Π(𝑆, 𝑣) is 𝑣, as 𝑑 𝑣 (𝑣) = 0 and 𝑑 𝑣 (•) ≥ 1 for any other vertex. (prefix) Any prefix 𝑆 𝑖 = {𝑠 𝑣 1 , . . . , 𝑠 𝑣 𝑖 } of Π(𝑆, 𝑣) is connected (thus a solution), since for any 𝑠 𝑖 , the vertices on a shortest path in 𝐺 [𝑆] to 𝑠 1 are at a smaller distance from 𝑠 1 and thus occur before 𝑠 𝑖 . (greedy) For any 𝑧 ∈ 𝑆 + 𝑖 ∩ 𝑆, let 𝑘 be the distance between 𝑣 and 𝑧 in 𝐺 [𝑆 𝑖 ∪ {𝑧}]. Since 𝑧 ∈ 𝑆 +𝑖 , there must be some𝑤 ∈ 𝑆 𝑖 ∩ 𝑁 (𝑧) at distance 𝑘 -1 from 𝑣 (in 𝐺 [𝑆 𝑖 ∪ {𝑧}]). This means that the distance between 𝑣 and 𝑧 in 𝐺 [𝑆] is still 𝑘: otherwise, there would be a vertex 𝑦 ∈ 𝑆 \ 𝑆 𝑖 , i.e., after 𝑤 in the canonical order, that is a neighbor of 𝑧 and has distance ≤ 𝑘 -2 from 𝑣 in 𝐺 [𝑆]; this leads to contradiction since 𝑦 would then need to come before 𝑤 in the BFS order. It follows that the canonical-BFS order is a prefix-closed order. now straightforward to see how this order satisfies the (first), (greedy) and (prefix) properties of Definition 11.2, and essentially corresponds to the layer order defined in[START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF].Definition 11.6 (canonical-BFS order for hereditary properties). Let 𝑆 be a solution of a hereditary set system, and 𝑣 any element in 𝑆. For each connected component 𝐶 𝑖 of 𝐺 [𝑆], we say the leader of the component is 𝑣 if 𝐶 𝑖 contains 𝑣, and otherwise the vertex of smallest id in 𝐶 𝑖 .The canonical order Π(𝑆, 𝑣) = 𝑠 1 , . . . , 𝑠 |𝑆∪𝑆 + | (defined on 𝑆 ∪ 𝑆 + ) is the lexicographical order of the tuples ⟨𝑐𝑖𝑑 (𝑆, 𝑠 𝑖 ), 𝑑 𝑙 (𝑆, 𝑠 𝑖 ), 𝑠 𝑖 ⟩, where for 𝑠 𝑖 in the component 𝐶 𝑖 , 𝑐𝑖𝑑 (𝑆, 𝑠 𝑖 ) is the id of the leader of 𝐶 𝑖 , or 0 if this leader is 𝑣 (assuming wlog 0 is smaller than any other id), and 𝑑 𝑙 (𝑆, 𝑠 𝑖 ) is the distance from the leader of 𝐶 𝑖 in 𝐺 [𝐶 𝑖 ]. Observe how 𝑠 1 = 𝑣. For a vertex 𝑥 in 𝑆 + , we use as 𝑐𝑖𝑑 (𝑆, 𝑥) and 𝑑 𝑙 (𝑆, 𝑥) the values obtained in 𝐺 [𝑆 ∪ {𝑥 }].

A preliminary version of this paper has been presented in[START_REF] Conte | New polynomial delay bounds for maximal subgraph enumeration by proximity search[END_REF], containing some of the exponential-space algorithms. In this extended version, we factorize the fundamental principles of algorithms in[START_REF] Conte | New polynomial delay bounds for maximal subgraph enumeration by proximity search[END_REF] 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[START_REF] Conte | Proximity search for maximal subgraph enumeration[END_REF].

In 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.

In essence, we obtain as a special case the same solution graph as known algorithms based on the input-restricted problem[START_REF] Cohen | Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties[END_REF][START_REF] Lawler | Generating all maximal independent sets: NP-hardness and polynomial-time algorithms[END_REF][START_REF] Tsukiyama | A new algorithm for generating all the maximal independent sets[END_REF]: For a solution 𝑆 we compute neighbors(𝑆) by sequentially taking all elements 𝑣 ∈ U \ 𝑆, solving the inputrestricted problem for 𝑆 ∪ {𝑣 }, and applying comp( •) on the results.

Indeed, (𝑆 ∩𝑆 * ) ∩ 𝑋 𝑖 = ∅, i.e., 𝑋 𝑖 does not intersect the proximity, implies that 𝑆 \ 𝑋 𝑖 ∪ {𝑣 } contains (𝑆 ∩𝑆 * ) ∪ {𝑣 }, which extends the proximity with 𝑣.

For completeness, we define neighbors(𝑆, 𝑣) = {𝑆 } for 𝑣 ∈ 𝑆, as 𝑆 ∪ {𝑣 } = 𝑆 is already a solution of P.

Note that the vertices of 𝐺 [𝐵 ] are all of 𝑉 (𝐺), but to compute the canonical order we need to consider only the edges in the bipartite subgraph 𝐺 [𝐵 ].

As 𝛼 (𝑛) grows extremely slowly, we remark that 𝛼 (𝑛) is in essence 𝑂 (1) on real, finite, graphs.

To remove ambiguity, we can remove the lexicographically smallest when multiple simplicial vertices are present.

Ambiguity 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.

Note that it may not fall between 𝑣 and 𝑥 otherwise the convex hull of 𝑆 would have included 𝑥.

Note that 𝑥 1 = 𝑣 and that 𝑥 𝑖 , 𝑥 𝑖+1 ∈ 𝑋 are not necessarily consecutive in Π (𝑋 , 𝑣) as some elements from 𝑋 + can be interleaved with them.

For completeness, we could equivalently observe that 𝑑 𝑣 (𝑠) = 𝐿𝐴𝑌 𝑣 𝑆 (𝑠) according to Definition 7 in[START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF].

ACKNOWLEDGEMENTS

We wish to thank the anonymous reviewers for their thorough analysis of the paper, which helped us improve both its content and presentation. work was partially supported by JST CREST, grant number JPMJCR1401, Japan and the Italian Ministry for Education and Research, under PRIN Project n. 20174LF3T8 AHeAD.

is maximal by definition of strongly accessible set systems. We remark that this alternative definition of comp(𝑆) still returns a maximal solution containing 𝑆, and is thus with canonical reconstruction (Definition 4.2).

Finally, given the canonical ordering 𝑠 1 , . . . , 𝑠 |𝑆 | of 𝑆, the core core(𝑆) of 𝑆 is the longest prefix 𝑠 1 , . . . , 𝑠 𝑖 of this order such that comp(𝑠 1 , . . . , 𝑠 𝑖 ) ≠ 𝑆; its parent is parent(𝑆) = comp(core(𝑆)) = comp(𝑠 1 , . . . , 𝑠 𝑖 ); its parent index is pi(𝑆) = 𝑠 𝑖+1 , i.e., the element following the last one of the core. It follows by definition of parent that comp(core(𝑆) ∪ {pi(𝑆)}) = comp(𝑠 1 , . . . , 𝑠 𝑖+1 ) = 𝑆.

The function parent(𝑆) defines a forest among solutions, as every solution has a unique parent, except for the ones such that comp(seed(𝑆)) = 𝑆 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 comp({𝑢}) for any 𝑢 ∈ U. The function children(𝑃, 𝑤) lets us perform a traversal of this structure, since it will find all 𝑆 such that 𝑃 = parent(𝑆) and 𝑤 = pi(𝑆). 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 neighbors(𝑆, 𝑠) function such that together they satisfy Definition 3.1. In this section we show that we can combine proximity search and [START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF] for commutable properties, if we can produce a canonical order for the canonical reconstruction that corresponds to the solution order induced by ≺ 𝑆 .

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 neighbors(𝑆, 𝑠) function that fits canonical reconstruction (Definition 4.2), based on a canonical order defined by a prefix-closed order ⪯ 𝑆 , we define a variant of [START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF], showed in Algorithm 2.

The main idea behind this combination comes from the following observation: the parent 𝑃 = parent(𝑆) = comp(core(𝑆)) of 𝑆 is obtained from a prefix of 𝑆, and extending this prefix with pi(𝑆), then applying comp(•), gives us comp(core(𝑆) ∪ pi(𝑆)) = 𝑆 (see definitions in Section 11.1). On the other hand, we will show that applying Definition 4.1, 𝑃 ∩𝑆 is exactly core(𝑆). Relying on the neighboring function neighbors(𝑃, pi(𝑆)) of canonical reconstruction, and the core property defined in [START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF], we are able to find the set core(𝑆) ∪ pi(𝑆), and finally obtain 𝑆.

We can now state:

Theorem 11.3. Given a commutable set system ( U, F ), a prefixclosed order family ⪯ 𝑠 𝑆 for ( U, F ), and a function neighbors(𝑆, 𝑠) for canonical reconstruction (Definition 4.2) based on ⪯ 𝑠 𝑆 , Algorithm 2 enumerates all maximal solutions of ( U, F ) without duplication in polynomial delay.

Proof. To prove the correctness, we show that any 𝑆 is found in children(𝑃, 𝑤) when 𝑃 = parent(𝑆) and 𝑤 = pi(𝑆).

We will first prove that there exists a solution 𝑅 ∈ neighbors(𝑃, pi(𝑆)) (on Line 7) such that core(𝑆) ∪ {pi(𝑆)} ⊆ 𝑅.

Consider the proximity 𝑃 ∩𝑆 by Definition 4.1: the longer prefix of the solution order of 𝑆 that is completely in 𝑃 must include core(𝑆) since 𝑃 = comp(core(𝑆)). If 𝑤 ∈ 𝑃 then neighbors(𝑆, 𝑤) returns 𝑃 by Definition 4.2, and indeed 𝑃 ⊇ core(𝑆) ∪ {𝑤 }.

Otherwise, 𝑃 does not include pi(𝑆), meaning that 𝑃 ∩𝑆 = core(𝑆) and that 𝑤 is the canonical extender for 𝑃, 𝑆. Using the neighboring function neighbors(𝑃, pi(𝑆)) we obtain at least one solution 𝑅 ⊇ core(𝑆) ∪ pi(𝑆).

Using the core property defined in [START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF], we are able to use 𝑅 to retrieve 𝑆: It is proven that Lines 7-11 will find and output any solution 𝑆 such that core(𝑆) ∪ {pi(𝑆)} ⊆ 𝑅, a condition which is guaranteed by what stated above.

The if on Line 11 removes duplication: any 𝑆 is found only once out of all invocations of children(𝑃, 𝑤): when 𝑃 = parent(𝑆), 𝑤 = pi(𝑆), 𝑠 = seed(𝑆), and 𝑅 = r(𝑆). The function r(𝑆) simply aims at defining deterministically one single 𝑅 ⊇ core(𝑆) ∪ {pi(𝑆)} once the other 3 variables have been fixed. It thus follows that this check is passed exactly once out of the whole execution of the algorithm for any solution (other than the roots, found on Line 1).

Line 1 shows that, by definition, all the roots of the forest are explored by Algorithm 2. We just proved that Line 4 discovers all the children of each visited node exactly once, which concludes the proof of the fact that Algorithm 2 visits every maximal solution of ( U, F ) without duplication. □

APPENDIX A MAINTAINING THE SOLUTION SET IN PROXIMITY SEARCH

For completeness, we briefly describe how to efficiently maintain the S set with well-known data structures. In the following, let U be the ground set (e.g., 𝑉 (𝐺) for vertex-induced graph properties, or 𝐸 (𝐺) for edge-induced graph properties). Let N = |S| be the number of solutions in S, and let 𝑠 = max 𝑆 ∈S (|𝑆 |) ≤ | U| be the maximum size of a solution. Recall 𝑠 ≤ 𝑛 for vertex-induced graph properties, and 𝑠 ≤ 𝑚 for edge-induced graph properties; What we aim at showing is that the time for maintaining the solution set is negligible in all cases addressed in this paper: recall