Designing Output Sensitive Algorithms for Subgraph Enumeration

Consider the problem of enumerating all the subsets of a collection $U=\{a_1,\mathrm{\dots },a_n\}$ whose sum is less than a certain threshold $b$. By using the backtracking schema, it is possible to solve the problem as shown in Algorithm 4. Each iteration outputs a solution, and takes $O(n)$ time, so that we have $O(n)$ time per solution. It is worth observing that if we sort the elements of $U$, then each recursive call can generate a solution in $O(1)$ time, yielding $O(1)$ time per solution.

The Bron-Kerbosch algorithm is a recursive backtracking algorithm used to enumerate all maximal cliques in an undirected graph. Given a graph $G=(V,E)$, the algorithm maintains three sets:

• $\mathrm{■}$

  $R$: The current clique being constructed.

• $\mathrm{■}$

  $P$: The set of potential candidates that can be added to $R$, meaning that all the vertices in $P$ are connected to all the vertices in $R$.

• $\mathrm{■}$

  $X$: The set of already processed vertices to avoid redundant solutions.

A recursive call aims to produce all the maximal cliques containing $R$, some vertices in $P$, and no vertices in $X$. Hence, we partition the set of maximal cliques satisfying this property by analysing all the possible candidates in $P$. When considering a candidate $v\in P$, $v$ is added to the partial solution $R$, while $P$ and $X$ are reduced to include only neighbors of $v$.

We output solutions only if $P$ and $X$ are empty. If indeed $P$ contains some element, it means we can still do further recursion to enlarge $R$, as $R$ is not maximal. If $X$ is non-empty, it also means that $R$ is not maximal, as to be maximal, it should include elements of $X$. Whenever $P=\mathrm{\varnothing }$ and $X\ne \mathrm{\varnothing }$, no further addition is possible to $R$, but the clique is still not maximal, and the algorithm thus backtracks without performing any output. This is typically called a dead-end, and the presence of such events is the main reason why this algorithm is not output-sensitive.

The algorithm recursively explores the search space, ensuring that each maximal clique is output exactly once. The basic Bron-Kerbosch algorithm (Algorithm 5) recursively builds cliques and removes processed vertices to avoid duplicates. A more efficient version of the algorithm introduces a pivoting strategy [66]. Choosing a pivot vertex $u$ from $P\cup X$ helps reduce the number of recursive calls by limiting the number of candidates that need to be processed. To obtain this algorithm it is sufficient to replace line 5 with the following two lines: “Choose a pivot vertex $u$ from $P\cup X$” and “for each $v\in P\setminus N(u)$ do”. The idea of this pivoting strategy is to avoid iterating at each expansion on the $P$ set. The results will have to contain either the pivot or one of its non-neighbors, since if none of the non-neighbors of the pivot is included, then we can add the pivot itself to the result. Hence we can avoid iterating on the neighbors of the pivot at this step.

An alternative approach to enhancing the basic Bron–Kerbosch algorithm involves omitting pivoting at the outermost recursion level and instead carefully selecting the order of recursive calls to minimize the size of the candidate vertex set $P$ within each call [28]. The degeneracy of a graph $G$ is defined as the smallest integer $d$ such that every subgraph of $G$ contains at least one vertex with a degree of at most $d$. Every graph admits a degeneracy ordering, where each vertex has at most $d$ later neighbors in the sequence. This ordering can be computed in linear time by repeatedly removing the vertex with the smallest degree among the remaining ones. By processing the vertices in the Bron–Kerbosch algorithm according to a degeneracy ordering, the candidate set $P$ (i.e., the neighbors of the current vertex that appear later in the ordering) is guaranteed to have at most $d$ elements. Conversely, the exclusion set $X$, which consists of previously processed neighbors, may be significantly larger. Although pivoting is omitted at the outermost recursion level, it can still be employed in deeper recursive calls to further optimize performance.

We showcase the flashlight strategy through a binary partition algorithm for the problem of $st$-path enumeration in an undirected graph $G=(V,E)$. The partition schema chooses an arc $e=(s,r)$ incident to $s$, and partitions the set of all the $st$-paths into the ones including $e$ and the ones not including $e$. The $st$-paths including $e$ are obtained by removing all the arcs incident to $s$, and enumerating the $rt$-paths in this new graph, denoted by $G\setminus s$. The $st$-paths not including $e$ are obtained by removing $e$ and enumerating the $st$-paths in the new graph, denoted by $G\setminus e$. The corresponding pseudocode is shown by Algorithm 6. It is worth observing that if the arc $e$ is badly chosen, a subproblem could not generate any solution; in particular, the set of the $rt$-paths in the graph $G\setminus s$ is empty if $t$ is not reachable from $r$, while the set of the $st$-paths in $G\setminus e$ is empty if $t$ is not reachable from $s$. Thus, before performing the recursive call to the subproblems it could be useful to test the validity of $e$, by testing the reachability of $t$ in these modified graphs. This will be our “flashlight” indicating which partitions lead to at least one solution. Note that the height of the corresponding recursion tree is bounded by $O(|E|)$, since at every level the size of the graph is reduced by at least one arc. The cost per iteration amounts to the reachability test, so $O(|E|)$ time. Therefore, the algorithm has $O({|E|}^2)$ delay.

This problem has been studied in [63, 65, 55], and in [38], guaranteeing a linear delay. In [5], the latter algorithm has been modified in order to enumerate bubbles. In the particular case of undirected graphs, in Section 4.3.2 we will show an algorithm based on this bipartition approach having an output sensitive amortized complexity, as shown in [6]. In the particular case of shortest paths, the enumeration problem has been studied in [27]. It is worth observing that the problem of enumerating all the $st$-paths in a graph is equivalent to the problem of enumerating all the cycles passing through a vertex.

We can improve the $st$-path enumeration algorithm proposed in the previous section to achieve optimal complexity, by using a dynamic certificate based on the biconnected components of the graph [6]. Let $P_{st}(G)$ denote the set of $st$-paths in $G$ and, for an $st$-path $\pi \in P_{st}(G)$, let $|\pi |$ be the number of it edges. We note that the problem of $st$-path enumeration necessarily requires $\mathrm{\Omega }({\sum }_{\pi \in P_{st}(G)}|\pi |)$ time to just list the output. The algorithm we present here is then optimal, as it lists all the $st$-paths of $G$ in $O(m+{\sum }_{\pi \in P_{st}(G)}|\pi |)$ time, where $m$ is the number of edges of the input graph.

Assume that we are given a structural lower bounding function $L_{s,t}(\cdot )$: that is, for any biconnected graph $G$ with $s,t\in V(G)$, we have $L_{s,t}(G)\le |{𝒫}_{s,t}(G)|$. Then, if we take

we obtain that, by Corollary 8, $lbP$ is a lower bound on the total number of $st$-paths. At this point, if $lbP\ge z$, we can output $YES$. Otherwise, we need some way to expand (1). We can do so by exploiting the following disjoint union:

where $N_{B_s}(s)=\{u\in B_s|(s,u)\in E\}$ is the set of neighbors of node $s$ inside $B_s$. Note that this can be seen as exploring the binary partition tree of the previous section in a different way: given a current source $s$, we only consider what we called its “left children”, and we explore all of them at the same step (by considering all the neighbors of $s$ that lead to $t$). Note that this leads us to conceptually create “new sources” whose disjoint union covers all paths from the original source, as we now focus on $ut$-paths for each $u$ neighbor of $s$.

The latter formula, when the lower bound is applied, is translated to

We can plug this lower bound expansion in (2), improving the total bound $lbP$:

This refinement can be recursively applied again and again, by taking the reduced graph $B_s\setminus s$, recomputing its bead string, and applying Corollary 8 to the new bead string. In this way, we can proceed until either $lbP$ reaches $z$, or when we have effectively counted all $st$-paths, and their total number does not reach $z$: here we can safely output $NO$.

To be employed in such a procedure, we need a structural lower bounding function, meaning that it must satisfy the following:

1. 1.

   Given a biconnected graph $G^{\prime }$ and two nodes $s^{\prime },t^{\prime }\in V(G^{\prime })$, we have $1\le L_{s^{\prime },t^{\prime }}(G^{\prime })\le N_{s^{\prime },t^{\prime }}(G^{\prime })$.

2. 2.

   If $G^{\prime }$ is trivial (size 2), then $L_{s^{\prime },t^{\prime }}(G^{\prime })=1$.

In [54], the authors prove that the function $𝒞(G):=|E|-|V|+2$ satisfies such properties, and they employ it in the subsequent implementation.

The assessment algorithm can now follow quite immediately: start from a single bead string, and the MSTDS $𝒯$ given by the corresponding path. At each step, choose a leaf $B_u$ of $𝒯$ with source $u$, and expand it as per (3). Recompute the BCCs of $B_u\setminus u$, and add them in $𝒯$ as a subtree in place of $B_u$. Then, update the total lower bound $lbP$ accordingly. By keeping some information in the MSTDS nodes concerning the lower bounds of the paths, such bound update can be performed in $O(1)$ time.

The lower bound $lbP$ is improved by at least one every time a source with at least two neighbors is considered. We can find a source with this property in at most linear time (we traverse its unique neighbor, and thus trivial BCC, for at most $|V|$ steps). Once we find such a source, and we expand the lower bound following (3), we need $O(|E|)$ time to update the BCCs after the source removal. Thus, we spend linear time per non-trivial step where we update $lbP$. Since we stop when the lower bound reaches $z$, we do no more than $z$ such steps, leading to a time complexity of $O(|E|z)$.

In Section 4.1.1, we gave an enumeration algorithm based on a partition approach (Algorithm 4). Interestingly, this algorithm can be interpreted as a reverse search-based algorithm. Let $\text{Sol}(U)$ be the set of solutions on $U$. The root of the family tree is the empty set. Let $S$ be a non-root solution $S=\{s_{f(1)},\mathrm{\dots },s_{f(k)}\}\subseteq U$ with cardinality $k$. Here, $f:\{1,\mathrm{\dots },k\}\to \{1,\mathrm{\dots },n\}$ is an injection such that for each . Then, we can define the parent $Par(S)$ of $S$ as the set obtained by removing the element with largest index in $S$: that is, $Par(S)=\{s_{f(1)},\mathrm{\dots },s_{f(k-1)}\}$. Note that $Par(S)$ is clearly in $\text{Sol}(U)$. Now, we define the family tree $ℱ(U)$ as follows:

where $ℰ(U)=\left\{(Par(S),S)\right|S\ne \mathrm{\varnothing }\}.$

We first show that the family tree is connected and acyclic. A typical approach to show this is to use a function $g:\text{Sol}(U)\to ℝ$ such that

1. 1.

   For the root $R$, $g(R)$ has the minimum value among the solutions, and

2. 2.

   For any non-root solutions $S,S^{\prime }=Par(S)$, we have $g(S)>g(S^{\prime })$.

Here, a candidate such function is the cardinality of a solution. By using such a $g$, we can then easily obtain the following lemma:

Next, we give a (slightly) more complicated example. Recall that a clique of a graph $G=(V,E)$ is a vertex subset $C$ of the graph such that for any pair of vertices in $C$, there is an edge in $G$. Moreover, a clique $C$ is maximal if there is no clique $C^{\prime }$ such that $C⊊C^{\prime }$. Several enumeration algorithms for maximal cliques can be found in the literature [50, 40, 2]. In this section, we explain the algorithm based on reverse search by Makino and Uno [50]. As in the previous section, we need to define the root and the parent-child relation of the family tree.

First, we define the root of the family tree. Suppose that $V=\{v_1,\mathrm{\dots },v_n\}$ is a totally ordered set such that for any , . For two maximal cliques $C_1,C_2$, we say that $C_1$ is lexicographically smaller than $C_2$ if the vertex with minimum index in $(C_1\setminus C_2)\cup (C_2\setminus C_1)$ belongs to $C_1$, and write $C_1\prec C_2$. Then, let $K_0$ be the maximal clique such that it is the lexicographically smallest among all the maximal cliques in $G$. We say a maximal clique is the root if the clique is equal to $K_0$.

Next, we define the parent of a clique $K\ne K_0$. For an integer $i$, let $K_{\le i}=K\cap \left\{v_j\right|j\le i\}$, and let $C(K_{\le i})$ be the lexicographically smallest maximal clique containing $K_{\le i}$. Note that $C(K_{\le i})$ may be equal to $K$.

Thus, we define the parent index $i$ of a maximal clique $K$ as the maximum index such that $C(K_{\le i-1})\ne K$. Consequently we define the parent $Par(K)$ of $K$ as $C(K_{\le i-1})$, where $i$ is the parent index of $K$.

Clearly, $Par(K)\prec K$ holds, and there can be no cycles. It also follows that every maximal clique will have a parent index, and thus a parent, other than $K_0=C(\mathrm{\varnothing })$. Thus, the parent-child relationship derives a tree structure rooted at $K_0$.

Computing the parent of a maximal clique is easy. However, obtaining all the children of a clique $K$ is not obvious. The crucial observation for child enumeration is the following: Let $K^{\prime }$ be a child of $K$; then, for any $j$ larger than or equal to the parent index, $C(K_{\le j}^{\prime })=K^{\prime }$. Hence, children can be found by removing from $K$ a vertex $v$ and vertices having larger indices than $v$, then adding a vertex $u$ (possibly $u=v$) to the remaining of $K$, and greedily adding vertices to obtain a maximal clique. By this construction, $u$ is the vertex with the parent index in the resultant clique. In the following, we give more details. Given a maximal clique $K$ and an index $i$, let

$K[i]$ can be interpreted as follows: we first pick the vertices adjacent to $v_i$ in $K$, and then greedily add vertices to $K$. Therefore, the following lemma holds.

From the above lemma, we can obtain the children of $K$ in polynomial time, yielding a polynomial delay enumeration algorithm for maximal cliques.

The key intuition can be already found in Lawler et al. [49], generalizing algorithms by Paull and Unger [53] and by Tsukiyama et al. [67]. The idea given is the following: given a maximal solution $S$ of a given enumeration problem and some element $x\notin S$, the hardness of listing solutions maximal within $S\cup \{x\}$ is linked to the hardness of listing maximal solutions of the general problem.

This has been then formalized as the Input-Restricted problem by Cohen et al. [15], who also restrict their attention to the enumeration of maximal solutions in graphs (although the technique can potentially be applied to any enumeration problem where solutions are maximal sets of elements). Formally:

Intuitively, we can use a maximal solution $X$ of $G[S\cup \{v\}]$ to generate a new maximal solution $X^{\prime }$ of $G$. Whenever this happens, we say there is an edge from $S$ to $X^{\prime }$ in the solution graph (optionally labelled with $v$). Another significant upside of the technique is that $X^{\prime }$ can be any arbitrary solution that includes $X$. Observe that $S$ itself is always a maximal solution of $IRP(S,v)$, but we typically avoid returning it as it would only add a futile edge from $S$ to $S$.

The catch is the following: this technique assumes that the property $P$ at hand is hereditary, i.e., if $S$ is a solution, then any subset of $S$ must itself be a solution. Even if many properties respect this condition (e.g., cliques and most of their relaxations, independent sets, forests), not all properties do, and the IRP technique may not be the most suitable for the latter (e.g., cycles and spanning trees).

If the property $P$ is hereditary, then we can easily define a simple maximalization procedure $\text{complete}(X)$, which iteratively adds an arbitrary element of $V\setminus X$ to $X$ until it is no longer possible to do so without breaking $P$. With this, we have all the elements for building an enumeration algorithm, which is a DFS-like traversal of the solution graph (see Algorithm 8).

The main advantage of the technique is now clear: if we simply plug in a solver for the input-restricted problem $\text{irp}(S,v)$, the algorithm will enumerate all maximal solutions to the general problem.

The completeness of this algorithm for hereditary properties relies on the idea that the solution graph generated with the IRP is strongly connected, thus a traversal from any starting point will visit every solution. Proving this is actually quite simple. It relies on showing that if you start at $S$ and want to reach $T$, there is always a $v\in T$ and a solution $X$ of $IRP(S,v)$, such that $X$ has a larger intersection with $T$ than $S$ had: applying this repeatedly must inevitably yield $T$ in a finite amount of steps. More detailed proofs can be found in [15].

Let us then discuss the drawbacks of this approach, and how some of them can be solved.

Firstly, checking that “$X^{\prime }$ was not already found” is necessary to avoid duplication, but it is no trivial task. A way to do this is to store every solution found so far in a dictionary, and use it to check whether $X^{\prime }$ is new. This is efficient time-wise (a trie or a block tree can answer the query in linear time), but as there can be exponentially many solutions, it makes the space usage exponential. However, Cohen et al. [15] show that, for hereditary properties, we can avoid a dictionary and induce a tree-like structure based on solving the problem incrementally. Essentially, they use the solutions of $G[\{v_1,\mathrm{\dots },v_{i-1}\}]$ to generate those of $G[\{v_1,\mathrm{\dots },v_i\}]$, much like Tsukiyama et al. [67], in a DFS-like fashion. This alternative algorithm has the advantage of reducing space usage, but does not operate anymore on the solution graph, as the actual maximal solutions of $G$ correspond only to the leaves of this tree-like structure.

It is thus worth noting that Algorithm 8 has a striking similarity to reverse search, and indeed it is also possible to achieve polynomial space by inducing a parent-child relationship, identifying a parent and a parent index for $X^{\prime }$ in the same way as Section 5.1, and turning the condition in Line 8 to “if the parent of $X^{\prime }$ is $S$, and the parent index is $v$”. In this light, the Input-Restricted Problem becomes a powerful and general tool for building reverse search algorithms.

As discussed above, the Input-Restricted Problem is easy to deal with if the property $P$ at hand is hereditary (i.e., subsets of solutions are solutions). However, Cohen et al. [15] generalizes the proof of correctness of Algorithm 8 to the more general class of connected-hereditary graph properties, i.e., properties for which any connected subgraph of a solution is itself a solution.

To give an example, induced forests are a hereditary property: if a set of nodes $S$ induces a forest, any subset of $S$ induces a forest. A connected-hereditary property are instead induced trees: if $S$ induces a tree, a subset of $S$ induces a forest, but a subset of $S$ that induces a connected subgraph will induce a tree. Inducing a parent-child relationship in this class is more challenging, and Cohen et al. [15] rely on a solution dictionary for avoiding duplication. However, Conte et al. [20] proposes a general technique that allows the definition of a parent-child relationship within the structure of Algorithm 8 even for connected-hereditary properties,⁵⁵5Technically the class is the more general set of “strongly accessible and commutable” properties, whose definition can be found in [20], although most naturally defined properties in the class will typically fall inside connected-hereditary. thus allowing enumeration in polynomial space.

Finally, note that properties like induced cycles are neither hereditary nor connected-hereditary, as a subset of a cycle will never be a cycle; properties of this kind cannot be solved directly by Algorithm 8.

The final piece of the puzzle is the Input-Restricted Problem itself.

It is relatively easy to see that, in Algorithm 8, the complexity of the $IRP(S,v)$ essentially corresponds to the amount of work done per solution: every time a new solution is found, we perform $IRP(S,v)$ up to $|V|$ times (for each different $v$), and for each solutions returned we just need to apply $\text{complete}()$. This means that the cost-per-solution of the algorithm is just a polynomial multiplied by the cost of the IRP⁶⁶6The polynomial of course varies according to whether we can limit the number of $v$ considered and the cost of complete, but it is always polynomial for hereditary and connected-hereditary properties, as long as we can identify in polynomial time wherher $S$ is a solution or not, as we can then simply iteratively test every node for addition until none is possible.. While intuitively a simpler task, the IRP it does not always allow efficient resolution: the number of maximal solutions within the IRP can greatly vary from problem to problem, leading to different complexities.

One of the simpler cases are maximal cliques. Given a maximal clique $S$ and a node $v$, $G[S\cup \{v\}]$ has just two maximal cliques:

• $\mathrm{■}$

  $S$ itself ($v$ cannot be added to it, as $S$ was already maximal in $G$)

• $\mathrm{■}$

  $\{v\}\cup (S\cap N(v))$, i.e., $v$ and all its neighbors in $S$ (any other element of $S$ not adjacent to $v$ cannot extend the clique)

As it has only two solutions (and only one we care about, since $S$ was already known), $IRP(S,v)$ for maximal cliques can be solved in polynomial time. This means the total amount of work done by Algorithm 8 per solution is polynomial, i.e., we achieve polynomial amortized time.⁷⁷7In fact, we can turn this into polynomial delay with alternative output[69], that simply makes us output $S$ at the beginning of $\text{Rec}(S)$ if the recursion depth is even, and at the end of $\text{Rec}(S)$ if the recursion depth is odd. This avoids long chains of recursive calls being closed (or opened) without new outputs being produced.

This is not always the case: the Input-Restricted Problem may have an exponentially high number of solutions, meaning it cannot be solved in polynomial time. Even in this case, not all hope is lost: some properties, like Maximal Connected Induced Bipartite Subgraphs [73] or Maximal Temporal Cliques in a restricted class of temporal graphs [11] allow the IRP to be solved in polynomial delay.

More in general, we can say that whenever the IRP can be solved in Incremental Polynomial Time (which includes polynomial delay), then Algorithm 8 also runs in Incremental Polynomial Time. Intuitively, this can be proved by the fact that, if $i$ solutions were found so far, the time used by the IRP to find solutions that we already knew is polynomial in $i$ and the input size (e.g., $O(n^c\cdot i^c$)), and since we can apply the IRP only to the $i$ solutions found so far, the time required until a new solution is found is bounded by $O(i\cdot n^c\cdot i^c)$, which is also polynomial in $i$ and $n$.

Finally, there are cases where even the IRP simply cannot be solved efficiently: Lawler [49], for example, shows how to reduce an instance of SAT to a simple hereditary property on a set of $n$ elements, where $O(n)$ maximal solutions can be easily identified in polynomial time, and another solution exists if-and-only-if the input formula is satisfiable. It follows that no output-sensitive algorithm may exist for this problem, unless $𝖯=\mathrm{𝖭𝖯}$. This tells us that even an efficient solution to the IRP would imply $𝖯=\mathrm{𝖭𝖯}$, as we could use it in Algorithm 8 to obtain an efficient algorithm for the problem.

To prove strong connectivity we want to say that, starting from any solution $S$, and traversing edges of the solution graph, we will eventually find a path to any other solution $S^{\ast }$. The Input-Restricted Problem strategy, on hereditary properties, relies on intersection: for any pair $S,S^{\ast }$, there exists a $v$ for which $\text{irp}(S,v)$ finds an $S^{\prime }$ such that $|S^{\prime }\cap S^{\ast }|>|S\cap S^{\ast }|$, and this tells us $S^{\prime }$ is the next step in the path towards $S^{\ast }$.

A key step of proximity search is replacing the monotone increase in intersection with a weaker, more general, and possibly problem-specific condition, that is called proximity, and denoted as $S\tilde{\cap }{S}^{\ast }$. In essence, a proximity search algorithm requires:

• $\mathrm{■}$

  An arbitrary starting solution $S$

• $\mathrm{■}$

  A function $S\tilde{\cap }T$ to determine proximity that, for any fixed $T$, is maximized when and only when $S=T$.⁸⁸8Note that we don’t care about the efficiency of this function, as it is used in the proofs and never in the algorithm!

• $\mathrm{■}$

  A function $\text{neighbors}(S)$ such that, for any other solution $S^{\ast }$, there is $S^{\prime }\in \text{neighbors}(S)$ for which $|S^{\prime }\tilde{\cap }{S}^{\ast }|>|S\tilde{\cap }{S}^{\ast }|$.

The completeness then follows from the same logic above, as $\text{neighbors}(S)$ always has an $S^{\prime }$ that gets “one step closer” to $T$. By the same logic as Algorithm 8, if $\text{neighbors}(S)$ takes only polynomial time, then the enumeration has polynomial delay.

Just like Algorithm 8, we also need to check whether any solution was already found, to ignore duplicates, and that means again storing all solutions in a dictionary and use exponential space. We’ll see later how it is sometimes possible to overcome this.

However, rather than solving the problem, we now simply formalized the requirement. Next we introduce a useful technique to actually design proximity search algorithms.

Canonical reconstruction, formalized in [19], is an effective method to implement proximity search.

The key ingredient is defining, for each solution $S$, a solution order $s_1,s_2,\mathrm{\dots },s_{|S|}$. This order will be problem-specific, and ideally allows us to exploit the problems’ structure to our advantage. Then, canonical reconstruction defines proximity as follows:

A couple observations are in order:

• $\mathrm{■}$

  $S\tilde{\cap }S=S$, as $S$ contains all elements in its own solution order.

• $\mathrm{■}$

  $S\tilde{\cap }T\ne S\cap T$, and in particular if $t_1\notin S$, then $S\tilde{\cap }T=\mathrm{\varnothing }$. Indeed $S$ may contain several elements of $T$, but we only care about those who align into a prefix of the solution order of $T$.

• $\mathrm{■}$

  $S\tilde{\cap }T\ne T\tilde{\cap }S$, since by definition $T\tilde{\cap }S$ will instead consider the longest prefix of the solution order of $S$ that is fully contained in $T$.

Finally, given $S$ and $T$ with $S\tilde{\cap }T=\{t_1,\mathrm{\dots },t_{i-1}\}$, we call $t_i$ the canonical extender for the pair $S,T$, that is, the earliest element in the solution order of $T$ that is missing from $S$.

The directive, in canonical reconstruction, is finding a maximal solution $S^{\prime }$ in $G[S\cup \{t_i\}]$ that contains $\{t_1,\mathrm{\dots },t_{i-1},t_i\}$. $S^{\prime }$ may very well have a smaller intersection with $T$ than $S$, but its proximity will have increased by at least one.

This is by no means a conclusive guide as, again, canonical reconstruction relies on finding a problem-specific solution order and exploiting its structure. However, many graph properties are associated with specific decompositions that induce an order, and this often turns out to be a powerful way to exploit these decompositions.

For completeness, to showcase the technique, we give here the example of Maximal Induced Chordal Subgraphs. More examples can be found in [19].

A graph is chordal if it has no induced cycle longer than $3$, i.e., any longer cycle has a shortcut edge (chord). Here we want to use canonical reconstruction to enumerate all maximal $S\subseteq V$ such that $G[S]$ is chordal.

Observe that this is a hereditary property, since any induced subgraph of a chordal subgraph graph $S$ cannot introduce a new induced cycle: any shortcut edge in $S$ would be preserved in the induced subgraph. Moreover, as shown in [19], the Input-Restricted Problem for this property can have exponentially many solutions, so it cannot be used to achieve polynomial delay.

We will use two key properties of chordal graphs:

• $\mathrm{■}$

  A chordal graph $G=(V,E)$ has $O(|V|)$ maximal cliques.

• $\mathrm{■}$

  A graph is chordal if and only if it allows a perfect elimination order.

A perfect elimination order is an elimination order of the vertices obtained by iteratively removing simplicial vertices, where a vertex is simplicial if its neighbors form a clique.

Given a graph $S$, we define its solution order as a reversed perfect elimination order, that is, an order $s_1,\mathrm{\dots },s_{|S|}$ where, for each $s_i$, the neighbors of $s_i$ preceding it in the order ($N(s_i)\cap \{s_1,\mathrm{\dots },s_{i-1}\}$) form a clique.

Now, take any pair of solutions $S,T$, where $t_1,\mathrm{\dots },t_{|T|}$ is the solution order of $T$, and let $S\tilde{\cap }T=\{t_1,\mathrm{\dots },t_{i-1}\}$. As described above, we call $t_i$ the canonical extender for $S,T$, and our goal will be, given $S$, to produce a solution $S^{\prime }$ containing $\{t_1,\mathrm{\dots },t_{i-1},t_i\}$. It is crucial to observe that we do not know $T$. The $\text{neighbors}(S)$ function must be able to satisfy such a condition for any of the (exponentially many) other solutions $T$, even though $\text{neighbors}(S)$ must take polynomial time, so it is only allowed to compute polynomially many solutions. The good news is that we can simply try to use every vertex in $V$ as canonical extender, so eventually we will always consider the correct $t_i$.

This is where the structure of the problem unravels: we know that $\{t_1,\mathrm{\dots },t_{i-1}\}\subseteq S$, and crucially, we designed the solution order so that $\{t_1,\mathrm{\dots },t_{i-1}\}\cap N(t_i)$ is a clique, meaning that $\{t_1,\mathrm{\dots },t_{i-1}\}\cap N(t_i)$ is contained in a maximal clique of $S$; let this clique be $Q$. With knowledge of $t_i$ and $Q$, we can produce a suitable $S^{\prime }$ as follows:

Observe that $S^{\prime }$ must contain all of $S\tilde{\cap }T=\{t_1,\mathrm{\dots },t_{i-1}\}$ because the vertices that were not neighbors of $t_i$ were never removed from $S$, and the vertices that were neighbors of $t_i$ were added by including $Q$. Finally, applying the complete function gives us a maximal solution, but does not remove any vertex.

Moreover, observe that $S^{\prime }$ is chordal: $(S\setminus N(t_i))\cup Q$ is a subset of $S$, so it is chordal because this is a hereditary property, and the further addition of $t_i$ does not break chordality, because $t_i$ is simplicial, so $(S\setminus N(t_i))\cup Q\cup \{t_i\}$ allows a perfect elimination ordering starting from $t_i$. By definition, applying the complete function does not break chordality.

The final piece of the puzzle is the fact that, while we do not know $Q$, we know that $S$ has only $O(|S|)$ maximal cliques, so we can indeed try all possible combinations of $t_i$ and $Q$, obtaining just $O(|V|\cdot |S|)$ solutions.

Specifically, $\text{neighbors}(S)$ will produce these solutions:

• $\mathrm{■}$

  For each $v\in V\setminus S$

• $\mathrm{■}$

  For each maximal clique $Q$ of $S$

• $\mathrm{■}$

  Return $\text{complete}((S\setminus N(t_i))\cup Q\cup \{t_i\})$

From what observed above, for any possible choice of $T$, there will be one correct choice of $v$ and $Q$ such that the $S^{\prime }$ obtained has $|S^{\prime }\tilde{\cap }T|>|S\tilde{\cap }T|$. Again, observe how there are exponentially many possible $T$, and yet a polynomial number of $S^{\prime }$ is sufficient to satisfy the condition.

The result is a polynomial-delay algorithm for enumerating Maximal Induced Chordal Subgraphs.

Canonical reconstruction has one more advantage: [19] shows that it is sometimes possible to induce a parent-child relationship by adapting the parent-child relationship designed in [20] on connected-hereditary (commutable) properties. We remind the reader to [19] for the details, but it is remarkably easy to determine when this is applicable: as a rule-of-thumb, it is possible to induce a parent-child relationship and perform proximity search in polynomial space when the solution order of canonical reconstruction is defined via a breadth-first search.

This is not the case for the example shown above of chordal subgraphs, which used a reversed perfect elimination order. However, [19] shows how to apply it to several other problems such as bipartite subgraphs, induced trees, and connected acyclic subgraphs.

Moreover, [10] actually showed how to compute a suitable solution order for chordal subgraphs in a BFS-like fashion, and thus produced a proximity search algorithm for maximal chordal subgraphs with polynomial delay and polynomial space.

Finally, we remark how techniques for navigating a solution graph can get arbitrarily interesting and more complex. A great example are retaliation-free paths by Cao [12]: in essence, while canonical reconstruction finds a path from $S$ to $T$ by adding the canonical extender $t_i$ without losing $\{t_1,\mathrm{\dots },t_{i-1}\}$, retaliation-free paths work on a similar logic but with a key difference: they consider a solution order for $T$, but allow the addition of $t_i$ to remove elements from $\{t_1,\mathrm{\dots },t_{i-1}\}$, as long as we can prove that, along the path, the elements sacrificed will be added again without “retaliation”, i.e., without removing $t_i$ again. Proving the existence of retaliation-free paths is not straightforward, but [12] successfully uses them to achieve polynomial delay on multiple enumeration problems for which the input-restricted problem is not solvable in polynomial time.

We consider the problem of enumerating paths with a specified starting vertex but no specified end vertex. For this problem, we can obtain an average constant-time algorithm by using a simple partition approach. We give our algorithm in Algorithm 9. Since Algorithm 9 is a recursive algorithm, it generates a tree structure. Hereafter, we denote it as $𝒯$ and we call a vertex in $𝒯$ a recursive call.

In this algorithm, each recursive call runs in $O(\mathrm{\Delta })$ time and outputs one path starting from $s$, where $\mathrm{\Delta }$ is the maximum degree of the graph. Therefore, an immediate analysis shows that the average time complexity is $O(\mathrm{\Delta })$ time. However, using amortized analysis, we can show that this algorithm actually achieves average constant delay.

For each recursive call $X$, the running time of $X$ is $O(\mathrm{\Delta })$. More precisely, $X$ runs in $O(|N(p_k)|)$ time, where $p_k$ is the other endpoint of a current path $P$. On the other hand, the number of children of $X$ is also $|N(p_k)|$. Using this observation, we analyze the total running time $T$ of the algorithm as follows: $O({\sum }_{X\in V(𝒯)}|ch(X)|)=O(|V(𝒯)|)$, where $ch(X)$ is the set of children of a recursive call $X$. Since the number of recursive calls and the number of paths starting from $s$ are equivalent, the average time complexity is thus average constant delay.

As a next example, we propose the enumeration of all trees containing a specified vertex $s$, as shown in Algorithm 10. In this algorithm, the time complexity of each recursive call is $O({\mathrm{\Delta }}^2)$ time. More precisely, the running time is $O({\sum }_{w\in N[u]}|N(w)|)$ time. Although the notation $G/e$ is used in the algorithm, its definition is as follows. For an edge $e=(u,v)$, we denote with $G/e$ the graph obtained by contracting edge $e$, that is, by unifying vertices $u$ and $v$ into one. For a set of edges $F=\{e_1,\mathrm{\dots },e_k\}$, we write $G/F$ to denote in short $G/e_1\mathrm{\cdots }/e_k$. Since the number of recursive calls and the number of solutions are equivalent, the average time complexity boils down to $O({\mathrm{\Delta }}^2)$ time in a straightforward analysis.

We again improve the average time complexity using an amortized analysis. In Algorithm 10, the number of children of a recursive call $X$ is the degree of a given vertex $s$. Let $Y_1,\mathrm{\dots },Y_{|N(s)|}$ be the set of children of $X$. When we generate $Y_i$, contracting an edge $\{s,u\}$, we need $O(|N(u)|)$ time. On the other hand, the number of children of $Y_i$ is at least $|N(u)|$. In other words, the computation time required to generate $Y_i$ is bounded by the number of children of $Y_i$. The time complexity of each recursive call $X$ is bounded by $O(|ch(X)|+|gch(X)|)$, where $gch(X)$ is the set of grandchildren of $X$. Hence, ${\sum }_{X\in V(𝒯)}|ch(X)|+|gch(X)|=O(|V(𝒯)|)$ holds and the average time complexity is average constant delay.

Algorithm 11 shows a simple partition-based matching enumeration algorithm. In this algorithm, each recursive call requires $O(m)$ time. We note that, if the maximum degree is at most $2$, each recursive call can be done in constant time. Thus, in what follows, we consider recursive calls with the maximum degree more than $2$.

From the definition of the big $O$ notation, for each recursive call $X$, the computation time $T(X)$ is at most $cm$ for some constant $c$. Hereafter, we assume that $T(X)=cm$. This modification does not increase the time complexity of Algorithm 11. The purpose of this assumption is to simplify the analysis of a lower bound computation time. In push out amortization, a lower bound of computation time is crucial in the context of the PO condition.

We show that the tree structure $𝒯$ generated by Algorithm 11 satisfies the PO condition. Let $X$ be a recursive call and $ch(X)$ be the set of children of $X$. Since each recursive call demands $\mathrm{\Omega }(m)$ time, the sum of the computation time of children is $c\cdot (m-|N(u)|)$ for some constant $c$. We denote the child that receives $G[V\setminus \{u\}]$ as the input graph as $Y_0$. Since the number of children is $|N(u)|+1$, we obtain $T(Y_0)+\beta (|ch(X)|+1)T^{\ast }\ge c\cdot m$ for some constant $c$ by setting $\beta =c$ since $T(Y_0)\ge c\cdot (m-|N(u)|)$ and $T^{\ast }\ge 1$. We consider the remaining part of the PO condition, ${\sum }_{Y\in ch(X)\setminus \{Y_0\}}T(Y)$. We show that ${\sum }_{Y\in ch(X)\setminus \{Y_0\}}T(Y)\ge c(m-|N(u)|)$. Let $e$ be an edge in $E\setminus \delta (u)$. Since $|\delta (u)|\ge 3$, $\delta (u)$ has an edge $f$ such that $\{e,f\}$ is a matching. This implies that $ch(X)\setminus \{Y_0\}$ has a child $Y^{\prime }$ that receives a graph that has $e$. Therefore, ${\sum }_{Y\in ch(X)\setminus \{Y_0\}}T(X)\ge c(m-|N(u)|)$ holds and the PO condition holds for all recursive calls. Since $T^{\ast }$ is constant, push out amortization proves that Algorithm 11 runs in constant average delay.