Counting Small Induced Subgraphs:
Scorpions Are Easy but Not Trivial

The starting point of our investigation is the problem of counting induced $H$-copies for a fixed individual graph $H$. Formally, this problem asks for the number of sets $X\subseteq V(G)$ such that the induced subgraph $G[X]$ is isomorphic to $H$. We stress that $H$ is considered fixed in this problem, and only $G$ is the input. In particular, each such problem can be solved in time $O(n^k)$, which is polynomial in $n$ for fixed $k$.

Some improvements over the trivial $O(n^k)$ running time are known: For example, triangles can be counted in $O(n^{\omega })$ time [21], where is the optimal exponent of $n\times n$ matrix multiplication [1]. This improvement can be lifted to cliques beyond $K_3$: Denoting by $C(K_k)$ the optimal exponent for counting $k$-cliques in $n$-vertex graphs, similar to the exponent of matrix multiplication, we have $C(K_k)\le \omega \cdot \lceil k/3\rceil$ (see [30]). Under the Exponential-Time Hypothesis ETH, there exists a fixed constant $\alpha$ such that $C(K_k)\ge \alpha \cdot k$ (see [4]).

Writing $C_{\mathrm{ind}}(H)$ to denote the optimal exponent of counting induced $H$-subgraphs [5] for fixed $H$, a straightforward reduction shows that $C_{\mathrm{ind}}(H)=C(K_k)$ for all $k$-vertex graphs $H$. In other words, for fixed $k$, all induced $H$-counting problems with $k$-vertex $H$ are equally hard, and they require an exponent of $\mathrm{\Omega }(k)$ under ETH. Compare this to counting not necessarily induced subgraphs, where different patterns can yield different complexity exponents: The number of subgraph copies of the edgeless $k$-vertex graph ${\mathrm{IS}}_k$ in an $n$-vertex graph is $\left(\genfrac{}{}{0pt}{}{n}{k}\right)$ and can thus be computed in linear time, while counting $k$-cliques is hard.

In recent years, counting occurrences of individual $k$-vertex patterns $H$ has been generalized to counting pattern occurrences from a fixed set of patterns [22, 23]. In this setting, we fix a number $k\in \mathbb{N}$ and a set $\mathscr{H}$ of $k$-vertex graphs. On input $G$, we wish to count the induced $k$-vertex subgraphs of $G$ isomorphic to some $H\in \mathscr{H}$. This subsumes the problem of counting induced $H$-copies, but also allows us to address, e.g., the problem of counting connected $k$-vertex graphs [22].

Of course, for every set $\mathscr{H}$, this problem can be solved by counting induced $H$-copies for the individual graphs $H\in \mathscr{H}$, which readily implies an $O(n^{C(K_k)})$ time algorithm. Significantly faster algorithms were only known for trivial pattern sets $\mathscr{H}$, i.e., if the pattern set $\mathscr{H}$ is empty or contains all $k$-vertex graphs. In these cases, the output is just $0$ or $\left(\genfrac{}{}{0pt}{}{n}{k}\right)$, respectively. Also, for some pattern sets $\mathscr{H}$, slight improvements can be obtained over the $O(n^{C(K_k)})$ time algorithm [9], but no nontrivial set $\mathscr{H}$ of $k$-vertex graphs with exponent strictly less than $C(K_{\lfloor k/2\rfloor })$ was known. In other words, counting induced patterns from a fixed set $\mathscr{H}$ of $k$-vertex graphs appeared to be either trivial or very hard.

In the literature, pattern counting is often phrased in terms of graph properties $\mathrm{\Phi }$ that may hold on infinitely many graphs rather than finite sets $\mathscr{H}$. More specifically, in the problem $\mathrm{\#}\text{IndSub}(\mathrm{\Phi })$ for a fixed graph property $\mathrm{\Phi }$, the input is a graph $G$ and $k\in \mathbb{N}$, and we ask to count the induced $k$-vertex subgraphs of $G$ satisfying $\mathrm{\Phi }$. Compared to the previous setting, the pattern size $k$ is now part of the input rather than a fixed constant, so the problem $\mathrm{\#}\text{IndSub}(\mathrm{\Phi })$ may not be polynomial-time solvable. We say that $\mathrm{\#}\text{IndSub}(\mathrm{\Phi })$ is fixed-parameter tractable if it can be solved in time $f(k)\cdot n^{O(1)}$ for a computable function $f$, and we would like to understand which properties $\mathrm{\Phi }$ render $\mathrm{\#}\text{IndSub}(\mathrm{\Phi })$ fixed-parameter tractable.

In prior literature, all known properties $\mathrm{\Phi }$ with fixed-parameter tractable $\mathrm{\#}\text{IndSub}(\mathrm{\Phi })$ are essentially trivial: Formally, we call $\mathrm{\Phi }$ meager if the restriction ${\mathrm{\Phi }}^{(k)}$ of $\mathrm{\Phi }$ to $k$-vertex graphs (i.e., the $k$-th slice of $\mathrm{\Phi }$) is trivial for all but finitely many $k\in \mathbb{N}$. Meager computable properties $\mathrm{\Phi }$ trivially render $\mathrm{\#}\text{IndSub}(\mathrm{\Phi })$ fixed-parameter tractable. Complementing this, the problem $\mathrm{\#}\text{IndSub}(\mathrm{\Phi })$ was conjectured to be #W[1]-hard for all other computable properties $\mathrm{\Phi }$. Here, #W[1] is the parameterized analogue of #P; it is known that ETH rules out fixed-parameter tractable algorithms for all #W[1]-hard problems (see, e.g., [15]).

This conjecture has been verified for general classes of properties $\mathrm{\Phi }$, e.g., properties that are closed under deleting edges [9, 13, 14] or deleting vertices [16], and other natural classes of properties [9, 22, 23, 35, 37]. This made it a plausible working hypothesis in the area.

We show that Conjecture 1 fails. That is, we exhibit non-meager properties $\mathrm{\Phi }$ such that $\mathrm{\#}\text{IndSub}(\mathrm{\Phi })$ is fixed-parameter tractable – in fact, even polynomial-time solvable.

These counterexamples are derived from simple constructions that were introduced 50 years ago in the context of the evasiveness conjecture [27, 33, 26], a major open problem about the worst-case query complexity of graph properties. In the setting of the evasiveness conjecture, we are given a fixed graph property $\mathrm{\Phi }$, and we wish to decide whether an unknown $k$-vertex graph $G$ is contained in $\mathrm{\Phi }$, where $G$ can only be accessed via edge queries. More precisely, the vertex set $V(G)$ is known, and for two vertices $v,w$, we can query whether $vw$ is an edge of $G$. Clearly, every property can be decided by querying all $\left(\genfrac{}{}{0pt}{}{k}{2}\right)$ pairs of vertices, and the evasiveness conjecture postulates that this trivial worst-case upper bound is optimal for all (edge-)monotone properties.

However, when we drop the monotonicity requirement, properties $\mathrm{\Phi }$ with linear query complexity $O(k)$ are known [27, 33], and it turns out that those examples can be used to refute Conjecture 1.

• $\mathrm{■}$

  As a simple counterexample, the property ${\mathrm{\Psi }}_{\mathrm{sink}}$ of having a sink in a directed graph is nontrivial on graphs of fixed size $k\ge 2$, and hence not meager. Here, a graph $D$ satisfies ${\mathrm{\Psi }}_{\mathrm{sink}}$ if there is a vertex $s\in V(D)$ with $(v,s)\in E(D)$ for all $v\ne s$.¹¹1Contrary to contemporary notation, in which a sink is a vertex of out-degree $0$, we use the term sink to refer to a vertex $s\in V(D)$ such that $(v,s)\in E(D)$ for all $v\ne s$. This follows the terminology of the original paper [33], which is still common in the context of the evasiveness conjecture. Nevertheless, $\mathrm{\#}\text{IndSub}({\mathrm{\Psi }}_{\mathrm{sink}})$ can be solved in linear time on directed graphs without antiparallel edges. We invite the reader to discover the algorithm themselves before proceeding to Section 3.1. This property actually presented the first counterexample to a (too strong) version of the evasiveness conjecture on directed graphs [33].

• $\mathrm{■}$

  A marginally more involved construction also works for undirected graphs: The scorpion property $\mathrm{\Psi }$ is a non-meager property of undirected graphs such that $\mathrm{\#}\text{IndSub}(\mathrm{\Psi })$ can be solved in $O(n^4)$ time on general undirected graphs. Scorpions were the first counterexample to a (too strong) variant of the evasiveness conjecture for undirected graphs [27], prompting the restriction of this conjecture to monotone properties.

• $\mathrm{■}$

  We show more generally that $\mathrm{\#}\text{IndSub}(\mathrm{\Psi })$ can be made gradually harder: For every $\mathrm{\ell }\in \mathbb{N}$, we construct a generalized scorpion property ${\mathrm{\Psi }}_{\mathrm{\ell }}$ such that $\mathrm{\#}\text{IndSub}({\mathrm{\Psi }}_{\mathrm{\ell }})$ can be solved in $O(n^{\mathrm{\ell }+3})$ time, while ETH rules out $O(n^{\alpha \cdot \mathrm{\ell }})$ time algorithms for a fixed constant $\alpha >0$. Our construction also allows for $\mathrm{\ell }$ to be a function in $k$. Under the Strong Exponential-Time Hypothesis SETH, we rule out $O(n^{\mathrm{\ell }+2-\epsilon })$ time algorithms.

Finally, informed by these counterexamples, we formulate a new hypothesis on the computational complexity of $\mathrm{\#}\text{IndSub}(\mathrm{\Phi })$ for properties $\mathrm{\Phi }$. This new hypothesis is more technical and explained in Section 4. In a nutshell, it is based around the well-established fact that sums of induced pattern counts like the $k$-th slices $\mathrm{\#}\mathrm{IndSub}({\mathrm{\Phi }}^{(k)}\to G)$ can be expressed as linear combinations of (not necessarily induced) subgraph counts [5], and that such basis changes may help in understanding the complexity of a problem [5, 6, 9, 12, 13, 14, 16, 17, 24, 35, 37, 36].

More specifically, the new hypothesis postulates that a useful phenomenon occurs when expressing the graph parameter $\mathrm{\#}\mathrm{IndSub}({\mathrm{\Phi }}^{(k)}\to G)$ as a linear combination of subgraph counts: Any hard term in such a linear combination ensures hardness of the entire linear combination. General linear combinations of $k$-vertex subgraph counts do not enjoy this useful phenomenon. We demonstrate in Section 4 that our conjecture would imply useful new ways of proving hardness of $\mathrm{\#}\mathrm{IndSub}({\mathrm{\Phi }}^{(k)}\to G)$.

Notably, this work is not the first to draw connections between the evasiveness conjecture and the computational complexity of $\mathrm{\#}\text{IndSub}(\mathrm{\Phi })$. Indeed, this connection was already made by Roth and Schmitt [35], who adapted the topological approach to the evasiveness conjecture, dating back to Kahn, Saks and Sturtevant [25], to prove lower bounds for $\mathrm{\#}\text{IndSub}(\mathrm{\Phi })$ for certain graph properties $\mathrm{\Phi }$. In a similar spirit, [9] adapts a lower bound of $\mathrm{\Omega }(k^2)$ on the query complexity of monotone graph properties due to Rivest and Vuillemin [32] to obtain hardness of $\mathrm{\#}\text{IndSub}(\mathrm{\Phi })$ for monotone properties $\mathrm{\Phi }$. The present work complements these connections on the upper-bound side: We observe that standard examples of properties $\mathrm{\Phi }$ with linear query complexity admit efficient algorithms for $\mathrm{\#}\text{IndSub}(\mathrm{\Phi })$.

Currently, these connections seem to be restricted to specific examples and proof techniques. We believe that it is an interesting open question whether a general connection can be established in either direction. Without going into details, we point out that the Fourier degree of a property $\mathrm{\Phi }$ (when $\mathrm{\Phi }$ is restricted to a slice and viewed as a Boolean function) provides a lower bound both for the query complexity of $\mathrm{\Phi }$ [31], and for the computational complexity of $\mathrm{\#}\text{IndSub}(\mathrm{\Phi })$ [9]. However, in both cases, large Fourier degree is only known to give a sufficient criterion for hardness, so it does not establish a direct link between the query complexity of $\mathrm{\Phi }$ and the complexity of $\mathrm{\#}\text{IndSub}(\mathrm{\Phi })$.

We follow standard textbooks [11] for graph-theoretic notation. Unless stated otherwise, graphs are simple (i.e., without multiedges or self-loops) and undirected. We write $V(G)$ and $E(G)$ for the vertex and edge set of $G$, respectively, and we write $N_G(v)≔\{u\mid uv\in E(G)\}$ for the neighborhood of $v\in V(G)$ in $G$.

A graph $H$ is a subgraph of $G$, written $H\subseteq G$, if it can be obtained by deleting vertices and edges from $G$. For $X\subseteq V(G)$, we write $G[X]$ to denote the induced subgraph on $X$. For $S\subseteq E(G)$, we write $G[S]$ for the subgraph with vertex set $V(G)$ and edge set $S$. For $k,\mathrm{\ell }\in \mathbb{N}$, we write $K_{\mathrm{\ell }}$ for the complete $\mathrm{\ell }$-vertex graph, ${\mathrm{IS}}_{\mathrm{\ell }}$ for the edgeless $\mathrm{\ell }$-vertex graph, and $K_{\mathrm{\ell },k}$ for the complete bipartite graph on $\mathrm{\ell }+k$ vertices.

A graph property $\mathrm{\Phi }$ is a function that maps each graph $G$ to $\{0,1\}$ and is invariant under isomorphisms, i.e., $\mathrm{\Phi }(G)=\mathrm{\Phi }(H)$ for all isomorphic graphs $G,H$. For $k\in \mathbb{N}$, the $k$-th slice of $\mathrm{\Phi }$, denoted by ${\mathrm{\Phi }}^{(k)}$, is the restriction of $\mathrm{\Phi }$ to $k$-vertex graphs. We implicitly identify ${\mathrm{\Phi }}^{(k)}$ with the set of all $k$-vertex graphs $G$ satisfying $\mathrm{\Phi }(G)=1$, and we use graph properties and sets of graphs interchangeably. For $k\in \mathbb{N}$ and a graph $G$, the number of $k$-vertex induced subgraphs $G[X]$ satisfying $\mathrm{\Phi }$ will be denoted by

Moreover, we write $\mathrm{\#}\mathrm{IndSub}({\mathrm{\Phi }}^{(k)}\to \star )$ for the map $G\mapsto \mathrm{\#}\mathrm{IndSub}({\mathrm{\Phi }}^{(k)}\to G)$.

A parameterized problem consists of a function $P:{\mathrm{\Sigma }}^{\ast }\to \mathbb{N}$ and a computable parameterization $\kappa :{\mathrm{\Sigma }}^{\ast }\to \mathbb{N}$. It is fixed-parameter tractable (FPT) if there is a computable function $f$, a constant $c\in \mathbb{N}$, and a deterministic algorithm $𝔸$ that computes $P(x)$ in time $O(f(\kappa (x))\cdot {|x|}^c)$ for all $x\in {\mathrm{\Sigma }}^{\ast }$. We write $\mathrm{\#}\text{IndSub}(\mathrm{\Phi })$ for the parametrized problem that gets as input a graph $G$ and a parameter $k$, and computes $\mathrm{\#}\mathrm{IndSub}({\mathrm{\Phi }}^{(k)}\to G)$.

For lower bounds, we rely on the Exponential-Time Hypothesis (ETH) [20], which asserts the existence of some $\epsilon >0$ such that the Boolean satisfiability problem on $n$-variable $3$-CNF formulas cannot be solved in time $O(2^{\epsilon \cdot n})$ (see also [10, Conjecture 14.1]). The Strong Exponential-Time Hypothesis (SETH) [19] states that for all $\epsilon >0$, there is a $k\ge 3$ such that Boolean Satisfiability on $k$-CNF formulas cannot be solved in $O(2^{(1-\epsilon )\cdot n})$ (see also [10, Conjecture 14.2]).