Which Graph Motif Parameters Count?

Bläser, Markus; Curticapean, Radu; Dörfler, Julian; Ikenmeyer, Christian

doi:10.4230/LIPIcs.MFCS.2025.23

Which Graph Motif Parameters Count?

Markus Bläser

Saarland Informatics Campus (SIC), Saarland University, Saarbrücken, Germany Radu Curticapean

University of Regensburg, Germany
IT University of Copenhagen, Denmark Julian Dörfler

Saarland Informatics Campus (SIC), Saarbrücken Graduate School of Computer Science, Saarland University, Germany Christian Ikenmeyer

University of Warwick, Coventry, UK

Abstract

For a fixed graph $H$ , the function $\#\mathrm{Ind}(H\mathop{\to}\,\star\,)$ maps graphs $G$ to the count of induced $H$ -copies in $G$ ; this function obviously “counts something” in that it has a combinatorial interpretation. Linear combinations of such functions are called graph motif parameters and have recently received significant attention in counting complexity after a seminal paper by Curticapean, Dell and Marx (STOC’17). We show that, among linear combinations of functions $\#\mathrm{Ind}(H\mathop{\to}\,\star\,)$ involving only graphs $H$ without isolated vertices, precisely those with positive integer coefficients maintain a combinatorial interpretation. It is important to note that graph motif parameters can be nonnegative for all inputs $G$ , even when some coefficients are negative.

Formally, we show that evaluating any graph motif parameter with a negative coefficient is impossible in an oracle variant of #P, where an implicit graph is accessed by oracle queries. Our proof follows the classification of the relativizing closure properties of #P by Hertrampf, Vollmer, and Wagner (SCT’95) and the framework developed by Ikenmeyer and Pak (STOC’22), but our application of the required Ramsey theorem turns out to be more subtle, as graphs do not have the required Ramsey property.

Our techniques generalize from graphs to relational structures, including colored graphs. Vastly generalizing this, we introduce motif parameters over categories that count occurrences of sub-objects in the category. We then prove a general dichotomy theorem that characterizes which such parameters have a combinatorial interpretation. Using known results in Ramsey theory for categories, we obtain a dichotomy for motif parameters of finite vector spaces as well as parameter sets.

Keywords and phrases:

Graph motif parameters, Combinatorics, Combinatorial Interpretability

Funding:

Radu Curticapean: Funded by the European Union (ERC, CountHom, 101077083). Views and opinions expressed are those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency.

Christian Ikenmeyer: Supported by EPSRC grant EP/W014882/2.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Complexity theory and logic ; Mathematics of computing

\rightarrow

Combinatorics

Editors:

Paweł Gawrychowski, Filip Mazowiecki, and Michał Skrzypczak

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

1.1 Positivity in Combinatorics and #P

A fundamental task in combinatorics is to assign combinatorial meanings to quantities: For example, the binomial coefficient $\binom{n}{k}$ has the combinatorial interpretation of counting $k$ -element subsets of $\{1,\ldots,n\}$ , which may not be obvious from the algebraic formula $\frac{n!}{k!(n-k)!}$ . In fact, this is a nonnegative combinatorial interpretation, i.e., the binomial coefficient is equal to the cardinality of a naturally defined set. This is stronger than just having a signed combinatorial interpretation, such as for example the determinant of zero-one matrices $A=(a_{i,j})_{1\leq i,j\leq n}$ , which can be expressed as the difference of the number of even versus odd permutations $\pi$ with $a_{i,\pi(i)}=1$ for all $1\leq i\leq n$ . In the following, when we speak of combinatorial interpretations, we mean nonnegative ones.

In algebraic combinatorics, there are several nonnegative integer quantities for which finding such a combinatorial interpretation is a major open problem, e.g., problems 9, 10, 11, and 12 in [36]. This begs the question whether these quantities actually have combinatorial interpretations, but without a formal definition of this notion, their existence is hard to rule out. Indeed, Stanley [37, Ch. 1] writes that “only through experience does one develop an idea of what is meant by a “determination” of a counting function”. In many settings however, combinatorial interpretations of a nonnegative quantity can be defined (or at least subsumed) formally in terms of containment of the quantity in the counting complexity class #P, see [15, 29, 30]. This means that the quantity can be interpreted as counting accepting paths of some nondeterministic polynomial-time Turing machine. While “containment in #P” is a coarse over-approximation of what some mathematicians would consider “combinatorial interpretations”, this working definition is formal, robust, and arguably natural. Most importantly, it enables us to prove that some very natural quantities indeed do not have a combinatorial interpretation.

For example, if PH does not collapse, then the squares of the symmetric group characters are not in #P and hence do not have a combinatorial interpretation, see [16]. Other fruitful separations from #P are proved in [15], where the counting versions of several TFNP search problems are studied: For example, given oracle access to an exponentially large graph with degree at most two (i.e., a disjoint union of isolated vertices, paths, and cycles), and given the end of a path, it follows that there is at least one other end of a path. But the task of finding a combinatorial interpretation for the nonnegative quantity “number of other path endpoints $-1$ ” fails due to the oracle separation in [15].

1.2 Do Nonnegative Graph Motif Parameters Count?

A graph $F$ is an induced subgraph of $G$ if $F$ can be obtained from $G$ by deleting vertices. An induced copy of a graph $H$ in $G$ is an induced subgraph $F$ of $G$ that is isomorphic to $H$ . For two graphs $H$ and $G$ , write $\#\mathrm{Ind}(H\mathop{\to}G)$ for the number of induced copies of $H$ in $G$ , and when $H$ is fixed, write $\#\mathrm{Ind}(H\mathop{\to}\,\star\,)$ for the function mapping $G\mapsto\#\mathrm{Ind}(H\mathop{\to}G)$ . As defined by Curticapean, Dell, and Marx [7], a graph motif parameter is a rational linear combination of such functions. The step from individual counts to linear combinations turns graph motif parameters into a rich function space that captures interesting counting problems related to small patterns. For example, the number of (not necessarily induced) subgraphs isomorphic to a fixed $k$ -vertex graph $H$ is a nonnegative linear combination of induced subgraph counts from all $k$ -vertex supergraphs $H^{\prime}\supseteq H$ . This means that (not necessarily induced) subgraph counts from fixed graphs are graph motif parameters. The same holds for the number of homomorphisms from a fixed graph $H$ . Moreover, the coefficients of a graph motif parameter in its linear combination over $\#\mathrm{Ind}(H\mathop{\to}\,\star\,)$ are unique.

Graph motif parameters have been studied thoroughly before, mostly from a complexity-theoretic perspective [18, 19, 20, 7, 32, 33, 34, 9, 10]: Each fixed graph motif parameter $f$ can be evaluated in polynomial time on $n$ -vertex input graphs, as it involves a linear combination of induced subgraph counts from fixed graphs. Under complexity-theoretic assumptions, the above works give lower bounds on the exponent of this polynomial. We focus on the separate question which graph motif parameters have combinatorial interpretations.

For example, most of the above papers consider unweighted sums (i.e., linear combinations with coefficients $0$ or $1$ ) of induced subgraph counts from a set $X$ of $k$ -vertex graphs. This has the evident combinatorial interpretation of counting $k$ -vertex subsets $S$ of a graph $G$ that induce a graph $G[S]$ from $X$ . More generally, we can allow arbitrary integers as coefficients; as we show in Lemma 11, all integer-valued graph motif parameters $f$ can be obtained this way. In this setting, it is possible for $f$ to have negative integer coefficients but still satisfy $f(G)\geq 0$ on all graphs $G$ .

Example 1.

Consider the quantity $(|V(G)|-1)^{2}=(n-1)^{2}\geq 0$ for $n$ -vertex graphs $G$ . This is nonnegative and, in fact, a graph motif parameter: Abbreviating $\#H=\#\mathrm{Ind}(H\mathop{\to}G)$ , we have $n=\#{K_{1}}$ and $1=\#{K_{0}}$ , and $(n-1)^{2}=\#{K_{1}}^{2}-2\#{K_{1}}+\#{K_{0}}$ . Moreover, the quadratic term $\#{K_{1}}^{2}$ can be linearized¹¹1 This holds because $\#{K_{1}}^{2}$ counts the pairs $(u,v)\in V(G)^{2}$ , and so does the linear combination $2\#{K_{2}}+2\#{I_{2}}+\#{K_{1}}$ , whose summands correspond to the isomorphism type of $G[\{u,v\}]$ , which is either $K_{2}$ , $I_{2}$ , or $K_{1}$ . As we will elaborate later, graph motif parameters enjoy a general linearization property: Any polynomial combination of induced subgraph counts can be expressed as a unique linear combination. This holds even for “subobject” counts under more general notions of objects; see the full version for the details. This motivates our focus on linear combinations., i.e., expressed as the linear combination $\#{K_{1}}^{2}=2\#{K_{2}}+2\#{I_{2}}+\#{K_{1}}$ . Thus, we have

0\leq(\#K_{1}-1)^{2}=2\,\#K_{2}+2\,\#I_{2}-\#K_{1}+\#K_{0},

and have constructed a linear combination of induced subgraph counts evaluating to a nonnegative value for every graph $G$ , even though the term $\#\mathrm{Ind}(K_{1}\mathop{\to}\,\star\,)$ appears with coefficient $-1$ .

This example in fact has a very simple combinatorial interpretation for graphs $G$ with $n\geq 1$ vertices: After fixing an arbitrary vertex $z_{0}$ , the quantity $(n-1)^{2}$ simply counts the pairs $(u,v)\in V(G)^{2}$ with $u\neq z_{0}$ and $v\neq z_{0}$ . Let us consider a example where finding such an interpretation seems trickier:

Example 2.

Consider the graph motif parameter

f(G)\ =\ \#\vbox{\hbox{\leavevmode\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate\hbox{{% \leavevmode\includegraphics{}{}{dagpub-tikzpictures/p023-Blaser.latexml-figure% 0.pdf}}}}}-\#\vbox{\hbox{\leavevmode\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate\hbox{{% \leavevmode\includegraphics{}{}{dagpub-tikzpictures/p023-Blaser.latexml-figure% 1.pdf}}}}}+\#\vbox{\hbox{\leavevmode\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate\hbox{{% \leavevmode\includegraphics{}{}{dagpub-tikzpictures/p023-Blaser.latexml-figure% 2.pdf}}}}}+2\,\#\vbox{\hbox{\leavevmode\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\hbox{{\leavevmode\includegraphics{}{}{dagpub-tikzpictures/p023-Blas% er.latexml-figure3.pdf}}}}}+4\,\#\vbox{\hbox{\leavevmode\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\hbox{{\leavevmode\includegraphics{}{}{dagpub-tikzpictures% /p023-Blaser.latexml-figure4.pdf}}}}}\ \geq\ 0,

whose non-negativity is shown in the full version. Contrary to our previous example, the graphs in this linear combination feature no isolated vertices. Does $f$ have a combinatorial interpretation?

Our main result in Theorem 13 gives a formal argument against $f$ having a combinatorial interpretation: In a nutshell, a nonnegative graph motif parameter involving only patterns without isolated vertices has a combinatorial interpretation if and only if all its coefficients are nonnegative. (The “if” part of this result is trivial.) In the next section, we will give the relevant formal definitions to state our results in Section 3 and compare them to related work in Section 4.

2 Preliminaries

2.1 Type-2 Counting Complexity

We study computational problems on inputs given by concise descriptions. Such problems have been studied by Johnson, Papadimitrou, and Yanakakis [21, 31], who introduced subclasses of the complexity class TFNP, such as PLS or PPAD, to capture search problems in exponentially large objects. The problems in these subclasses of TFNP all have a similar structure: Each input $x$ implicitly encodes an exponentially large structure, e.g., a graph $G$ via a Boolean circuit $x$ that computes the edge relation of the graph $G$ . The witness sought in the search problem is however still polynomially large in $|x|$ , which is tiny compared to the size of the encoded input instance. The guiding examples in our paper are induced subgraphs $H$ of a fixed size in an exponentially large graph $G$ . In this problem, the $O(1)$ labels of the vertices in $G$ that induce $H$ constitute a witness.

A natural abstraction of this setting is obtained by providing the input as an oracle, rather than via a succinct encoding, see e.g. [2]. In this setting, which is denoted as type-2 complexity, we can only query the given structure, for instance by making queries to the edge relation of the graph, but we do not have access to a circuit computing the edge relation. Type-2 problems also arise naturally in computability and complexity studies of real functions, see e.g. [38, 22]. Since a real number is an infinite object, it is given as an oracle which one can query to get better and better rational approximations.

To define the type-2 framework formally, fix some alphabet $\Sigma$ . We assume that $0,1\in\Sigma$ , which are interpreted as false and true, respectively. An oracle is a total function of type $\Sigma^{\ast}\to\{0,1\}$ . The computational model in the type-2 framework is an oracle Turing machine, which gets an input string $x$ together with access to an oracle $O$ .

Example 3.

For a fixed graph $H$ , we consider the problem of finding an induced $H$ -copy in a large graph $G$ . The graph $G$ is given as $(x,O)$ where $O:\Sigma^{\ast}\to\{0,1\}$ is an oracle encoding the edge relation and $x$ is the number of nodes of $G$ written in binary. The nodes of $G$ are $0,\dots,x-1$ , written as bit strings of fixed length $n$ . Given two nodes $u$ and $v$ of $G$ , there is an edge between $u$ and $v$ iff $O(uv)=1$ . (Since we consider strings of fixed length $n$ , no separation symbol is needed.) In this representation, most of the information about $G$ is stored in the oracle; the input $x$ only encodes the size of the graph, and the running time of oracle Turing machines is measured in terms of $x$ .

A consistency issue can arise in this definition: Since the graph $G$ is exponentially large, the oracle Turing machine might not be able to check whether the encoding is consistent. For instance, one might wish to encode an undirected graph $G$ but have $O(uv)\neq O(vu)$ . In the case of graphs, such inconsistencies can be “repaired” by avoiding observing them, e.g., by only querying strings $u v$ with $u<v$ . In the context of TFNP and its subclasses, such issues are often elegantly repaired by interpreting any oracle as a graph with the desired properties. In general however, such a fix may not be possible for more complicated structures, in particular in the abstract setting of category theory that we will also study. Therefore, we will also resort to promise problems, in which a Turing machine is only required to work properly on inputs $(x,O)$ that are a proper encoding of an input object; see Definition 8 for more details. Note that this also encompasses the previous solutions. If we can repair the oracle or choose an interpretation such that every oracle encodes a valid instance, then we simply choose the set of “don’t care” instances to be the empty set.

A $k$ -ary type-2 relation $R$ gets a tuple of $k$ strings $x$ as an input, has access to an oracle $O$ , and outputs a value $R(x,O)\in\{0,1\}$ . Typically, we will consider unary type-2 relations, but relations with higher arity naturally occur when one considers witnesses, see below, when we define the existential and counting operators. A type-2 relation $R$ is polynomial-time computable if there is an oracle Turing machine $M$ that given input $x$ and oracle access to $O$ computes $R(x,O)$ in polynomial-time in the length of the input $x$ . Oracle queries have unit costs, but $M$ has to write the query strings on the oracle tape. Note that all time bounds we consider depend only on the length $|x|$ of $x$ , but not on $x$ itself and, more importantly, not on the oracle.

If there is a polynomial-time computable $(k+1)$ -ary type-2 relation $S$ , we define the $k$ -ary type-2 relation $\exists S$ by $\exists S(x,O)=1$ iff there is a polynomially long $y$ (in the length $|x|$ ) such that $S(x,y,O)=1$ .

Example 4.

In our example of finding an induced copy of $H$ in the graph $G$ , we start with a binary type-2 relation $\mathrm{IsIndSub}_{H}(x,y,O)$ . The relation interprets $y$ as an encoding of a set $Y$ of $k$ distinct nodes of $G$ with $k$ being the number of nodes of $H$ . The relation then queries the oracle $O$ to obtain the induced subgraph $G[Y]$ . It then checks by brute force whether $G[Y]$ and $H$ are isomorphic. If yes, it returns the value $1$ and otherwise $0$ . This is clearly polynomial-time computable in $|x|$ . The relation $\exists\mathrm{IsIndSub}_{H}(x,O)$ now returns $1$ if $G$ contains an induced copy of $H$ somewhere, and $0$ if $G$ does not contain such a copy. See also Lemma 12 for a more formal proof.

As in classical type-1 complexity, we can also introduce a counting operator $\#$ to type-2 complexity, similar to the existential operator $\exists$ : A polynomial-time computable $(k+1)$ -ary type-2 relation $S$ defines a $k$ -ary type-2 counting problem by $\#S(x,O)=\#\{y\mid S(x,y,O)=1\}$ , where $y$ is polynomially long.

Example 5.

Continuing the example above, $\#\mathrm{IsIndSub}_{H}$ now counts the number of induced subgraphs in $G$ that are isomorphic to $H$ , that is, $\#\mathrm{IsIndSub}_{H}(x,O)=\#\mathrm{Ind}(H\mathop{\to}G)$ , where $(x,O)$ is the oracle encoding of $G$ .

The goal of this paper is to characterize those integer valued nonnegative graph motif parameters that have a combinatorial interpretation. In other words, we ask which nonnegative graph motif parameters count something. The informal notion of “combinatorial interpretation” is formalized below as follows:

Definition 6.

${\textup{{{\#P}}}}^{\leavevmode\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate\hbox{{% \leavevmode\includegraphics{}{}{dagpub-tikzpictures/p023-Blaser.latexml-figure% 5.pdf}}}}=\{\#R\mid\text{$R$ is a polynomial-time computable binary type-2 % relation}\}$ .

In the notation ${\textup{{{\#P}}}}^{\leavevmode\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate\hbox{{% \leavevmode\includegraphics{}{}{dagpub-tikzpictures/p023-Blaser.latexml-figure% 6.pdf}}}}$ , the dotted circle represents a placeholder for the input oracle.

Definition 7.

For a graph motif parameter $\varphi$ , we denote by $\operatorname{Eval}_{\varphi}$ the corresponding type-2 function, which gets the graph $G$ given in the form $(x,O)$ . An integer valued nonnegative graph motif parameter $\varphi$ is called combinatorially interpretable if $\operatorname{Eval}_{\varphi}\in{\textup{{{\#P}}}}^{\leavevmode\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\hbox{{\leavevmode\includegraphics{}{}{dagpub-% tikzpictures/p023-Blaser.latexml-figure7.pdf}}}}$ (depending on context also $\operatorname{Eval}_{\varphi}\in\mathsf{Pr}\text{-}{\textup{{{\#P}}}}^{% \leavevmode\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{{\leavevmode% \includegraphics{}{}{dagpub-tikzpictures/p023-Blaser.latexml-figure8.pdf}}}}$ , see later for an explanation).

It is open for discussion whether every problem in ${\textup{{{\#P}}}}^{\leavevmode\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate\hbox{{% \leavevmode\includegraphics{}{}{dagpub-tikzpictures/p023-Blaser.latexml-figure% 9.pdf}}}}$ admits a “nonnegative combinatorial interpretation” in the informal sense used by combinatorists. If a problem is however not in ${\textup{{{\#P}}}}^{\leavevmode\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate\hbox{{% \leavevmode\includegraphics{}{}{dagpub-tikzpictures/p023-Blaser.latexml-figure% 10.pdf}}}}$ , then it cannot have a nonnegative combinatorial interpretation. Our dichotomy result for integer-valued nonnegative graph motif parameters is particularly clean-cut in this regard: Such a parameter is in ${\textup{{{\#P}}}}^{\leavevmode\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate\hbox{{% \leavevmode\includegraphics{}{}{dagpub-tikzpictures/p023-Blaser.latexml-figure% 11.pdf}}}}$ iff all its coefficients are nonnegative integers, so it indeed counts induced subgraphs.

To study more complicated structures, we consider promise problems, since the oracle TM might not be able to check whether an oracle is a legal encoding. Hence, we will have a set of “don’t care” inputs $(x,O)$ , which will correspond to illegal encodings of input objects in our setting. Our oracle TM only needs to compute the correct result on inputs which are not “don’t care” inputs. One such example are vector spaces, where we interpret the oracle as the characteristic function of the given vector space and it is not immediate how to check whether the oracle indeed describes a vector space. In this case our oracle Turing machine only has to work properly if the given oracle encodes indeed a vector space.

Definition 8.

A counting function $F$ together with a set $D$ of “don’t care” inputs is in $\mathsf{Pr}\text{-}{\textup{{{\#P}}}}^{\leavevmode\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\hbox{{\leavevmode\includegraphics{}{}{dagpub-tikzpictures% /p023-Blaser.latexml-figure12.pdf}}}}$ if there is a polynomial-time computable binary type-2 relation $R$ such that $\#R$ and $F$ coincide on all inputs outside $D$ .

Every function in ${\textup{{{\#P}}}}^{\leavevmode\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate\hbox{{% \leavevmode\includegraphics{}{}{dagpub-tikzpictures/p023-Blaser.latexml-figure% 13.pdf}}}}$ is also in $\mathsf{Pr}\text{-}{\textup{{{\#P}}}}^{\leavevmode\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\hbox{{\leavevmode\includegraphics{}{}{dagpub-tikzpictures% /p023-Blaser.latexml-figure14.pdf}}}}$ with the empty set of “don’t care” inputs.

2.2 What is a Combinatorial Interpretation – and What is Not?

While we do not have an all-encompasing answer to the first part of this question (and we do not need one in this paper), we explain why type-2 complexity gives satisfactory answers to the second part. Intuitively, a combinatorial interpretation should mean “counting something”. But that is not enough. Even the graph motif parameter $f$ from Example 2 counts something: For a given graph $G$ , we consider the set of witnesses for each pattern in $f$ . So $W(\vbox{\hbox{\leavevmode\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\hbox{{\leavevmode% \includegraphics{}{}{dagpub-tikzpictures/p023-Blaser.latexml-figure15.pdf}}}}})$ are all (induced) occurrences of an edge in $G$ , $W(\vbox{\hbox{\leavevmode\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\hbox{{\leavevmode% \includegraphics{}{}{dagpub-tikzpictures/p023-Blaser.latexml-figure16.pdf}}}}})$ are all (induced) occurrences of a triangle in $G$ and so on. The sets $W(\vbox{\hbox{\leavevmode\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\hbox{{\leavevmode% \includegraphics{}{}{dagpub-tikzpictures/p023-Blaser.latexml-figure17.pdf}}}}})$ and $W(\vbox{\hbox{\leavevmode\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\hbox{{\leavevmode% \includegraphics{}{}{dagpub-tikzpictures/p023-Blaser.latexml-figure18.pdf}}}}})$ will be multi-sets containing two and four copies of the witnesses, respectively, due to the coefficients. Let $W_{+}$ be the union of all witness sets that correspond to a term with positive coefficient and $W_{-}=W(\vbox{\hbox{\leavevmode\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate\hbox{{% \leavevmode\includegraphics{}{}{dagpub-tikzpictures/p023-Blaser.latexml-figure% 19.pdf}}}}})$ be all witnesses that correspond to a term with negative coefficient. Since $f$ is nonnegative, $|W_{+}|\geq|W_{-}|$ . Thus there is an injective map $i:W_{-}\to W_{+}$ . So we could say that $f$ counts all elements in $W_{+}$ that are not in $\textup{im}(i)$ . However, this “cheating away” of the difference $|W_{+}|-|W_{-}|$ is unsatisfactory, because it is (computationally) hard to decide whether a given element in $W_{+}$ should be counted or not.

Counting complexity gives a way to define combinatorial interpretations: We are given a set of witnesses $W\subseteq\{0,1\}^{*}$ , encoded as binary strings, and for each $x\in\{0,1\}^{*}$ we can decide in polynomial time whether it is in $W$ or not. This rules out the construction above, since constructing the embedding $i$ is infeasible. Computing the size $|W|$ is a problem in the complexity class #P: A nondeterministic Turing machine guesses a witness $x$ and then deterministically verifies whether it is in $W$ . The number of accepting paths is precisely $|W|$ . While it might be debatable whether being in #P is the right definition for a combinatorial interpretation, it appears to be at least a necessary condition. In other words, if a quantity is not in #P, then it does not admit a combinatorial interpretation.

In the case of graph motif parameters, the witnesses are given as ordered lists of nodes having constant length, say $k$ , since only the target graph $G$ varies. If $G$ has $N$ nodes, each node can be encoded by a bitstring of length $\log N$ and the total witness size is $k\log N$ . When the running time should be polynomial, then the Turing machine $M$ for checking the witness needs random access to the graph, because it cannot inspect the whole graph. This is modeled using oracles and type-2 complexity.

2.3 Induced Subgraph Numbers

Graphs in this paper are finite, undirected, and simple, i.e., they do not contain multi-edges or self-loops. Given a graph $G$ , we write $V(G)$ and $E(G)$ for its vertex and edge set, respectively. We write $\mathcal{G}$ for the class of all graphs. Towards applying a Ramsey theorem, we will also consider ordered graphs: These are graphs $G=(V,E,\leq_{G})$ where $(V,E)$ is a graph and $\leq_{G}$ is a total order on $V$ . We write $\mathcal{OG}$ for the class of these graphs. When ordered graphs are represented by an oracle, we always assume the natural lexicographic order on the vertices.

Given graphs $H$ and $G$ , we say that $H$ is a subgraph $H\subseteq G$ of $G$ if $V(H)\subseteq V(G)$ and $E(H)\subseteq E(G)$ . In the case of ordered graphs $H=(V,E,\leq_{H})$ and $G=(V^{\prime},E^{\prime},\leq_{G})$ , we additionally require that $\leq_{H}$ is the restriction of $\leq_{G}$ to $V$ . Given a vertex set $X\subseteq V(G)$ , write $G[X]=(X,\{vw\in E(G)\mid v,w\in X\})$ for the subgraph of $G$ induced by $X$ . We write $H\sqsubseteq G$ to denote that $H$ is an induced subgraph of $G$ , and we write $\mathcal{P}(G)$ for the poset of induced subgraphs of a graph $G$ , ordered by $\sqsubseteq$ . We call $H$ pure if it contains no isolated vertices, i.e., no connected components isomorphic to $K_{1}$ , and we write ${\mathcal{G}^{\text{pure}}}$ for the class of pure graphs and ${\mathcal{OG}^{\text{pure}}}$ for the pure ordered graphs.

A homomorphism from a graph $H$ into a graph $G$ is a function $f:V(H)\to V(G)$ such that $uv\in E(H)$ implies $f(u)f(v)\in E(G)$ ; we write $\#\mathrm{Hom}(H\mathop{\to}G)$ for their number. A homomorphism is an embedding if it is injective; we write $\#\mathrm{InjHom}(H\mathop{\to}G)$ for their number. A strong embedding is an embedding with the additional condition that $uv\notin E(H)$ also implies $f(u)f(v)\notin E(G)$ ; we write $\#\mathrm{StrInjHom}(H\mathop{\to}G)$ for their number. An isomorphism is a strong embedding that is bijective; two graphs $H$ and $G$ are isomorphic if there is an isomorphism from $H$ to $G$ . For isomorphic graphs $H, G$ we write $H\cong G$ . All of these definitions apply to ordered graphs as well; in this setting, homomorphisms $f$ must additionally preserve the orderings of $H$ and $G$ , i.e., if $u\leq_{H}v$ , then $f(u)\leq_{G}f(v)$ .

An automorphism of $H$ is a strong embedding from $H$ into $H$ ; we write $\#\mathrm{Aut}(H)$ for the numbers of automorphisms of $H$ . The numbers of embeddings and strong embeddings from a graph $H$ into some graph $G$ are multiples of $\#\mathrm{Aut}(H)$ . We obtain the number of subgraphs isomorphic to $H$ as $\#\mathrm{Sub}(H\mathop{\to}G)=\#\mathrm{InjHom}(H\mathop{\to}G)/\#\mathrm{Aut% }(H)$ and the number of induced subgraphs isomorphic to $H$ as $\#\mathrm{Ind}(H\mathop{\to}G)=\#\mathrm{StrInjHom}(H\mathop{\to}G)/\#\mathrm{% Aut}(H)$ . Note that for ordered graphs $H$ , we have $\#\mathrm{Aut}(H)=1$ . For a graph $H$ , we write $\#\mathrm{Ind}(H\mathop{\to}\,\star\,)$ for the function that maps $G\mapsto\#\mathrm{Ind}(H\mathop{\to}G)$ . We use that these functions are linearly independent for non-isomorphic graphs $H$ , even when restricted to particular domains:

Fact 9.

Let $\mathcal{G}^{\prime}\subseteq\mathcal{G}$ be a finite set of pairwise non-isomorphic graphs. For $H\in\mathcal{G}^{\prime}$ , write $f_{H}:\mathcal{G}^{\prime}\to\mathbb{Q}$ for the restriction of $\#\mathrm{Ind}(H\mathop{\to}\,\star\,)$ to $\mathcal{G}^{\prime}$ . Then the functions $\{f_{H}\mid H\in\mathcal{G}^{\prime}\}$ are linearly independent. The same applies for ordered graphs.

Having established that the functions $\#\mathrm{Ind}(H\mathop{\to}\,\star\,)$ are linearly independent, we consider linear combinations of these basis functions. The following term was coined in [7]:

Definition 10.

A graph motif parameter is a function $\varphi:\mathcal{G}\to\mathbb{Q}$ that admits pairwise non-isomorphic pattern graphs $H_{1},\ldots,H_{s}$ and coefficients $\alpha_{1},\ldots,\alpha_{s}\in\mathbb{Q}$ such that, for all graphs $G$ ,

\varphi(G)=\sum_{i=1}^{s}\alpha_{i}\cdot\#\mathrm{Ind}(H_{i}\mathop{\to}G).

(1)

We say that $\varphi$ is pure if every graph $H_{i}$ with non-zero coefficient is pure. An ordered graph motif parameter similarly is a linear combination of induced subgraph counts from pairwise non-isomorphic ordered graphs. The support $\textup{supp}(\varphi)$ is the set of all $H_{i}$ , s.t. $\alpha_{i}\neq 0$ .

Note that $\varphi$ being pure is well-defined, as the linear combination (1) is unique by Fact 9: The (isomorphism types of) graphs and coefficients appearing in the linear combination are uniquely determined; we therefore speak of the coefficients and the patterns of $\varphi$ . Since we investigate whether or not a graph motif parameter $\varphi$ has a combinatorial description, i.e., whether $\varphi$ counts a set of objects, we will restrict ourselves to graph motif parameters with image $\mathbb{N}$ , as all others can clearly not count anything. By the following lemma, this implies that the coefficients in the linear combination (1) can be assumed to be integers.

Lemma 11.

Let $\varphi$ be an (ordered) graph motif parameter. Then $\varphi(G)\in\mathbb{Z}$ for every (ordered) graph $G$ if and only if all coefficients of $\varphi$ are integers.

Proof.

The “if” is obvious, since $\#\mathrm{Ind}(H\mathop{\to}G)\in\mathbb{Z}$ for any $H, G$ . For the “only if”, let $H$ be a pattern in $\varphi$ with a coefficient $\alpha_{H}\in\mathbb{Q}\setminus\mathbb{Z}$ , such that $|V(H)|$ is minimal among all such patterns. Then $\#\mathrm{Ind}(H\mathop{\to}H)=1$ and $\varphi(H)=\alpha_{H}+\beta\notin\mathbb{Z}$ for some $\beta\in\mathbb{Z}$ , since all other basis functions with non-integer rational coefficients evaluate to $0$ on $H$ , as their pattern has at least $|V(H)|$ vertices and is not isomorphic to $H$ . $\hfill\blacktriangleleft$

Lemma 12.

Let $\varphi(G)=\sum_{i=1}^{s}\alpha_{i}\cdot\#\mathrm{Ind}(H_{i}\mathop{\to}G)$ with all $\alpha_{i}\in\mathbb{N}$ . Then $\operatorname{Eval}_{\varphi}\in{\textup{{{\#P}}}}^{\leavevmode\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\hbox{{\leavevmode\includegraphics{}{}{dagpub-% tikzpictures/p023-Blaser.latexml-figure20.pdf}}}}$ . This holds for unordered and ordered graph motif parameters.

3 Our Results

3.1 Graphs

We characterize the pure graph motif parameters $\varphi$ with a combinatorial interpretation as those whose coefficients are nonnegative integers. Such graph motif parameters $\varphi$ clearly have a combinatorial interpretation, as they count all induced occurrences of pattern graphs, possibly with multiplicities (see Lemma 12.) On the other hand, if $\varphi$ has a negative coefficient, then we show that $\varphi$ is not in $\mathsf{Pr}\text{-}{\textup{{{\#P}}}}^{\leavevmode\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\hbox{{\leavevmode\includegraphics{}{}{dagpub-tikzpictures% /p023-Blaser.latexml-figure21.pdf}}}}$ and thus does not admit a combinatorial interpretation. Formally we prove (recall Def. 7 about combinatorial interpretability):

Theorem 13.

Let $\varphi$ be a pure graph motif parameter, i.e., $\varphi(G)=\sum_{i=1}^{s}\alpha_{i}\cdot\#\mathrm{Ind}(H_{i}\mathop{\to}G)$ for pairwise non-isomorphic pure $H_{1},\ldots,H_{s}$ and coefficients $\alpha_{1},\ldots,\alpha_{s}\in\mathbb{Q}$ .²²2By Lemma 11 the interesting cases are those where all $\alpha_{i}\in\mathbb{Z}$ . Then $\varphi$ is combinatorially interpretable iff all $\alpha_{1},\ldots,\alpha_{s}\in\mathbb{Q}$ are nonnegative integers.

We show Theorem 13 in §5 with a delicate and technically demanding proof. The intuition is however rather easy to explain, and we illustrate it on the Example 2. An NTM $M$ is supposed to output $f(G)$ , but it can only query a small part of $G$ . Assume that $G$ is either the union of a triangle and exponentially many singletons, or the union of an edge with exponentially many singletons, or $G$ is the graph that consists of only exponentially many singletons. If $G$ is an edge and singletons, then one computation path of $M$ must accept and must have queried the oracle at the edge, because otherwise this computation path would lead to an accepting path even if $G$ has no edges, which would be the wrong answer. Now, in the case that $G$ is a triangle and singletons, it turns out (which is delicate) that such an accepting path exists for each of the triangle edges, so we get 3 accepting computation paths, but $f(G)=2$ , so the NTM has too many accepting paths.

3.2 More General Structures

The methodology used to prove Theorem 13 can be generalized to more general structures, provided that they satisfy the following conditions:

$\blacksquare$

Ramsey property: We require Ramsey-type theorems for the structures, which assert – roughly speaking – that for given objects $A, B$ , there exists an object $C$ which contains enough $B$ -copies such that, by partitioning the set of all $A$ -copies in $C$ into a small number of parts, there is some part that contains a full $B$ -copy. In the case of pure graph motif parameters, for instance, this is Lemma 20: For any ordered graphs $F, G$ , there is an ordered graph $H$ such that for any partitioning of the induced subgraphs of $H$ that are isomorphic to $F$ , we can find an induced copy of $G$ in $H$ such that all induced copies of $F$ in this copy of $G$ are in the same part.
$\blacksquare$

A neutral padding operation: We require an operation to enlarge a given object without increasing the number of induced subobjects. In the case of pure graph motif parameters, this can be achieved by adding isolated vertices, however we introduce different possible ways of achieving this for different objects, leading to different definitions of “pure”.

3.2.1 Relational Structures

For instance, we can prove results similar to Theorem 13 for various variants of relational structures, which generalize graphs. In graphs, we consider exactly one binary relation on a set $V$ , the edge relation. In a relational structure, we can have multiple relations of various arities. A relational structure $A$ is an induced substructure of another relational structure $B$ , if we can obtain $A$ by restricting the relations of $S$ to the vertices of $A$ . Similarly to graphs, we can now define motif parameters as linear combinations of induced substructure numbers. Formal definitions are given in the full version. We get the following classification for motif parameters of relational structures.

Theorem 14 (informal, see full version for a precise statement).

The evaluation function of a pure motif parameter of relational structures is combinatorially interpretable (i.e., it is in $\mathsf{Pr}\text{-}{\textup{{{\#P}}}}^{\leavevmode\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\hbox{{\leavevmode\includegraphics{}{}{dagpub-tikzpictures% /p023-Blaser.latexml-figure22.pdf}}}}$ ) iff all its coefficients are nonnegative integers.

We also consider further types of relations, namely multiset relations (each relation is a multiset and can have repetitions), and list relations (which is the equivalent to directed graphs in the relational setting) with and without repetitions. We call these relational structures mixed. Precise definitions are again given in the full version. For such mixed relational structures, we get similar dichotomies, which we first prove in the ordered setting, since the corresponding Ramsey property only holds for ordered mixed relational structures. Then we transfer this theorem to the unordered setting – a similar detour into the ordered setting is in fact already needed for the case of graphs.

An application of mixed relational structures are colored graphs, where nodes are colored and isomorphisms have to respect the colors. We show a dichotomy result for colored graphs.

Due to space constraints all these generalizations can be found in the full version.

3.2.2 Category Theory

Ramsey-type theorems have even been established within category theory [11, 26]. Since Ramsey arguments are crucial in our method, this raises the interesting question whether we can also transfer our results into this realm. Indeed, we achieve this in the full version. Our objects of consideration are now objects of some category $C$ , and the subobjects we consider are now specified using a class of morphisms $\mathcal{M}$ from $C$ . For two objects $a$ and $b$ of $C$ , we call the morphisms $a\to b$ in $\mathcal{M}$ , identified if they only differ by an isomorphism of $a$ , the $\mathcal{M}$ -subobjects of $a$ under $b$ . In the case of undirected graphs, we choose $\mathcal{M}$ to be the class of all strong graph embeddings. An important concept in our construction will be so-called factorization systems, used also by Lagodzinski [24] and Isbell [17] in the context of counting problems. We have a second class of morphisms $\mathcal{E}$ and we require that every morphism $f:a\to b$ factors (essentially uniquely) as $f=me$ with $m\in\mathcal{M}$ and $e\in\mathcal{E}$ . In our running example of unordered graphs, we can take $\mathcal{E}$ to be the class of surjective graph homomorphisms and $\mathcal{M}$ the above class of strong graph embeddings. Then every graph homomorphism $f:H\to G$ factors through the subgraph $G[f(V(H))]$ of $G$ that is induced by the image of $V(H)$ .

Recall that for graph motif parameters, we had a notion of pure graphs. We will have the same here, we will have two categories, a category $C$ of objects that we consider and category $P$ of pure objects that we want to count. In the full version, we collect a number of natural and rather mild requirements on $C$ and $P$ (maybe except for the property of being Ramsey) in order to prove our main result that $P$ -pure motif parameters can only have a combinatorial interpretation if the coefficients are all nonnegative.

Theorem 15 (informal, see full version for the precise statement).

Let $\varphi$ be a $P$ -pure motif parameter. Then under some mild conditions, we have $\operatorname{Eval}_{\varphi}\notin\mathsf{Pr}\text{-}{\textup{{{\#P}}}}^{% \leavevmode\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{{\leavevmode% \includegraphics{}{}{dagpub-tikzpictures/p023-Blaser.latexml-figure23.pdf}}}}$ unless all its coefficients are nonnegative integers.

The theorem does not automatically give a dichotomy, since we do not have a corresponding upper bound when the coefficients are all nonnegative integers. However, our concrete applications in fact do admit corresponding upper bounds (all details can be found in the full version):

$\blacksquare$

First we consider finite dimensional vector spaces over finite fields, which were shown to have the Ramsey property in [11] using methods from category theory. In particular, we show that the evaluation function of a motif parameter over a finite vector space is in $\mathsf{Pr}\text{-}{\textup{{{\#P}}}}^{\leavevmode\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\hbox{{\leavevmode\includegraphics{}{}{dagpub-tikzpictures% /p023-Blaser.latexml-figure24.pdf}}}}$ iff all its coefficients are nonnegative integers.
$\blacksquare$

Then we consider so-called parameter sets, which are subsets of $A^{n}$ for some fixed alphabet $A$ where we may set a coordinate to constant or identify any number of coordinates. They are also known to satisfy a Ramsey property, see [25, Theorem 10.4]. As a consequence of our general theorem, a motif parameter over parameter sets is in $\mathsf{Pr}\text{-}{\textup{{{\#P}}}}^{\leavevmode\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\hbox{{\leavevmode\includegraphics{}{}{dagpub-tikzpictures% /p023-Blaser.latexml-figure25.pdf}}}}$ iff all its coefficients are nonnegative integers.

3.3 Linearization

As shown examplarily on the first pages, graph motif parameters enjoy a useful linearization property: Any polynomial in induced subgraph counts is a graph motif parameter, that is, a linear combination of induced subgraph numbers. Among other applications, this universality of linear combinations can be used to show that induced subgraph counts are algebraically independent, as any annihilating polynomial would in fact translate to a linear combination that always evaluates to zero, thus contradicting linear independence. Linearization also motivates our focus on linear combinations of subobject counts.

In the full version, we establish conditions for subobject numbers of a category $C$ to enjoy similar linearization properties. We obtain that the coefficients in the linearized version are positive and have a combinatorial interpretation if the polynomial we started with has positive coefficients in the binomial basis; see the next section.

4 Related Work

Searching for combinatorial interpretations for nonnegative integer quantities has a long tradition in combinatorics dating back to Cayley, Littlewood, Richardson, Schützenberger, Macdonald, Schensted, Knuth, Stanley, and others, e.g., [23, 35, 36], and has recently been studied from the perspective of #P containment and functional #P closure properties [28, 15, 16, 5]. The univariate relativizing functional closure properties of #P have been characterized in [4, Thm 3.1.1(b)]: Consider the binomial coefficient $\binom{x}{i}=\frac{1}{i!}x(x-1)(x-2)\cdots(x-i+1)$ for $i\in\mathbb{N}$ as a polynomial in $x$ , and let $\varphi:\mathbb{N}\to\mathbb{N}$ be a univariate polynomial with expansion $\varphi(x)=\sum_{i=1}^{k}\alpha_{i}\binom{x}{i}$ for $\alpha_{i}\in\mathbb{Q}$ . This expansion is called the binomial basis expansion of $\varphi$ . It is known that $\varphi({\textup{{{\#P}}}}^{\leavevmode\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\hbox{{\leavevmode\includegraphics{}{}{dagpub-tikzpictures/p023-Blas% er.latexml-figure26.pdf}}}})\subseteq{\textup{{{\#P}}}}^{\leavevmode\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\hbox{{\leavevmode\includegraphics{}{}{dagpub-% tikzpictures/p023-Blaser.latexml-figure27.pdf}}}}$ iff all $\alpha_{i}\in\mathbb{N}$ (see [15] for a proof). The connection between combinatorial interpretations and functional closure properties of #P is very recent [15].

In the language of graphs, the construction in [4] can be phrased as follows. Let $\mathcal{G}^{\prime}$ denote the graphs on $\{1,2,\ldots,3k\}$ whose vertices $\{3i,3i+1,3i+2\}$ either form a triangle or a path on 3 vertices. Consider graph motif parameters for which all patterns are disjoint unions of triangles, i.e., $\varphi(G)=\sum_{i}\alpha_{i}\#\mathrm{Ind}(H_{i}\mathop{\to}G)$ , where $H_{i}$ is a union of $i$ disjoint triangles. For $G\in\mathcal{G}^{\prime}$ with $x$ many triangles, we have $\varphi(G)=\sum_{i}\alpha_{i}\binom{x}{i}$ . Their construction can be interpreted as oracle graphs $G\in\mathcal{G}^{\prime}$ showing that $\varphi$ is not combinatorial.

The non-oracle implications in the univariate case were studied in [27, p. 307], which shows that $\textup{{{GapP}}}\cap\{f:\{0,1\}^{*}\to\mathbb{N}\mid\forall w:f(w)\geq 0\}=% \textup{{{\#P}}}$ implies $\textup{{{C}}}_{=}\textup{{{P}}}=\textup{{{coNP}}}$ and $\textup{{{SPP}}}=\textup{{{UP}}}$ (see [12] for an overview over these classes.) The multivariate case was resolved in [14, Thm 3.14], cf. [13, Thm 23], based on a Ramsey theorem [13, Thm 12]. As in the univariate case, one gets small variants of our main theorem, whereas we consider a larger set of non-isomorphic graphs of the same cardinality, each without isolated vertices. The functional closure properties of other counting classes are mainly unknown, with the exception of GapP [3, Thm 6] and finite automata [8].

While search versions of type-2 problems have been studied already in [1] and later works on TFNP, the counting versions have only recently been studied to understand whether their nonnegative transformations still have combinatorial interpretations [15]. We improve on the work [15] in various ways. First, we show much more general results due to our general theorem in the categorial framework. Second, our results are also valid for unordered objects, like unordered graphs, which do not have the required Ramsey property per se. We overcome this technical difficulty by carefully reducing the unordered case to the ordered one. All graph problems in [15] are on ordered graphs only.

5 Results for Graphs

5.1 Reduction to Ordered Graphs

To prove Theorem 13, we first prove the following stronger result about ordered graphs:

Theorem 16.

Let $\varphi:\mathcal{OG}\to\mathbb{N}$ be a pure ordered graph motif parameter. Then $\operatorname{Eval}_{\varphi}\in\mathsf{Pr}\text{-}{\textup{{{\#P}}}}^{% \leavevmode\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{{\leavevmode% \includegraphics{}{}{dagpub-tikzpictures/p023-Blaser.latexml-figure29.pdf}}}}$ iff all coefficients of $\varphi$ are nonnegative integers.

Theorem 13 then follows by the simple observation that

\displaystyle\#\mathrm{Ind}((V_{i},E_{i})\mathop{\to}(V,E))

\displaystyle=\sum_{\leq_{V_{i}}}\#\mathrm{Ind}((V_{i},E_{i},\leq_{V_{i}})% \mathop{\to}(V,E,\leq_{V}))

(2)

where $\leq_{V}$ is any arbitrary linear ordering of $V$ and $\leq_{V_{i}}$ sums over all linear orders of $V_{i}$ that result in non-isomorphic ordered graphs. Note that all the pattern graphs occurring on the right-hand side are non-isomorphic pure ordered graphs. Even more, for different patterns on the left hand side, all possible occuring patterns on the right hand side are non-isomorphic. Now let $\varphi:\mathcal{G}\to\mathbb{N}$ be a pure graph motif parameter with a negative coefficient. Then the pure ordered graph motif parameter $\varphi^{\prime}:\mathcal{OG}\to\mathbb{N}$ obtained by applying (2) to each of the basis functions has a negative coefficient and thus $\operatorname{Eval}_{\varphi^{\prime}}\notin\mathsf{Pr}\text{-}{\textup{{{\#P}% }}}^{\leavevmode\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{{\leavevmode% \includegraphics{}{}{dagpub-tikzpictures/p023-Blaser.latexml-figure30.pdf}}}}$ by Theorem 16. Assume for the sake of contradiction that $\operatorname{Eval}_{\varphi}\in\mathsf{Pr}\text{-}{\textup{{{\#P}}}}^{% \leavevmode\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{{\leavevmode% \includegraphics{}{}{dagpub-tikzpictures/p023-Blaser.latexml-figure31.pdf}}}}$ , then we can compute $\operatorname{Eval}_{\varphi^{\prime}}$ by simulating the ordered oracle in polynomial time and running the corresponding NTM computing $\operatorname{Eval}_{\varphi}$ . This places $\operatorname{Eval}_{\varphi^{\prime}}$ in $\mathsf{Pr}\text{-}{\textup{{{\#P}}}}^{\leavevmode\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\hbox{{\leavevmode\includegraphics{}{}{dagpub-tikzpictures% /p023-Blaser.latexml-figure32.pdf}}}}$ , a contradiction.

While this only proves that pure graph motif parameters with some negative coefficients are not combinatorially interpretable, Lemmas 11 and 12 complete the proof by proving the reverse direction.

5.2 Ordered Graphs

The proof of the hardness in Theorem 16 now proceeds in two parts:

First we show how to instantiate any ordered graph and all its induced subgraphs as oracle graphs. Here it is important that the instantiations all have the same size; otherwise, the Turing machine could infer (through the number of vertices) possibly useful information about an instantiation without explicitly querying the oracle. For this purpose, for some subset $D\subseteq\mathcal{OG}$ , we say that an ordered graph motif parameter $\Psi:D\to\mathbb{N}$ is $D$ -good if all its coefficients are nonnegative integers and all its patterns are from $D$ . If any such coefficient is negative, it is instead called $D$ -bad. If the domain $D$ is clear from the context, we will also simply call them good and bad respectively.

The second part of the proof finds a target graph $G$ such that, if there is any counterexample where any (restricted) good function would disagree with our bad $\varphi$ , it must already occur on some induced subgraph of $G$ . For a fixed bad pure ordered graph motif parameter $\varphi:\mathcal{OG}\to\mathbb{N}$ such a counterexample will always exist. We then instantiate precisely $\mathcal{P}(G)$ as oracle graphs.

Simply padding all graphs of $\mathcal{P}(G)$ to the same size however is not enough. The main goal here is that acceptance of a computation path is monotone relative to which part of the graph is observed by a computation, i.e., if we embed $H\sqsubseteq G$ , then all previously accepting paths that accept on oracle input $H$ should still be accepting when the oracle input is $G$ .

Our proof follows the structure of [15]. We start by formalizing computation paths:

Definition 17.

A computation path $\tau$ of a nondeterministic Turing machine on some input is defined as the sequence of its nondeterministic choice bits and the answers to its oracle queries (both types of bits appear in the same list, ordered chronologically). Formally, it is an element of $\{0,1\}^{*}$ .

The same Turing machine can yield the same computation path on different inputs, for example, when not the whole input is read, or when having access to different oracles, because the oracles can differ in positions that are not queried.

Given a nondeterministic Turing machine $M$ and an oracle graph $G$ , we are interested in the number of accepting paths of $M$ when given oracle access to $G$ . We define the number of accepting paths of $M$ on input $j\in\mathbb{N}$ (given in binary) with oracle access to $G$ as $\#\textup{{{acc}}}_{M^{G}}(j)$ . (This notation highlights that $G$ is given as an oracle while the number of vertices $j$ is a classical input.) Further we will also call $\#\textup{{{acc}}}_{M^{G}}(j)$ a computation. In the following, write ${\mathcal{OG}_{=j}}$ to denote those graphs in $\mathcal{OG}$ that contain exactly $j$ vertices, $0,\ldots,j-1$ with the natural order on them, for $j\in\mathbb{N}$ .

Definition 18 (Set-instantiator against $(M,G,\varphi)$ ).

Let $M$ be a nondeterministic Turing machine, let $G\in\mathcal{OG}$ and let $\varphi$ be an ordered pure graph motif parameter. Let $\top$ be a symbolic top element above the induced subgraph poset $\mathcal{P}(G)$ , i.e., $\top\not\sqsubseteq H$ for all induced subgraphs $H\sqsubseteq G$ . A set-instantiator $\mathcal{S}\!I$ is a triple of

$\circ$ some $j\in\mathbb{N}$ ,

$\circ$ an instantiation function $\textup{{{inst}}}_{\textup{{$\mathcal{S}\!I$}}}:\mathcal{P}(G)\to{\mathcal{OG}% _{=j}}$ , and

$\circ$ a perception function $\textup{{{perc}}}_{\textup{{$\mathcal{S}\!I$}}}:\{0,1\}^{*}\to\mathcal{P}(G)% \cup\{\top\}$ ,
such that both of the following properties hold for all induced subgraphs $H\sqsubseteq G$ :

$\bullet$ $\tau\in\{0,1\}^{*}$ is an accepting path in computation $\#\textup{{{acc}}}_{M^{\textup{{{inst}}}_{\textup{{$\mathcal{S}\!I$}}}(H)}}(j)$ iff $\textup{{{perc}}}_{\textup{{$\mathcal{S}\!I$}}}(\tau)\sqsubseteq H$ ,

$\bullet$ $\varphi(\textup{{{inst}}}_{\textup{{$\mathcal{S}\!I$}}}(H)))=\varphi(H)$ .

In the above definition, we think of the perception of an accepting computation path of $M$ to be the induced subgraph of $G$ that is observed by $M$ through oracle queries, while computation paths that do not accept are given perception $\top$ .

We can now prove by a randomized construction that set-instantiators always exist for polynomial-time NTMs:

Lemma 19.

Let $\varphi:\mathcal{OG}\to\mathbb{N}$ be a pure ordered graph motif parameter, let $M$ be a polynomial-time NTM computing $\operatorname{Eval}_{\varphi}$ and let $G\in\mathcal{OG}$ . Then there is a set-instantiator against $(M,G,\varphi)$ .

Proof.

For now let $n\in\mathbb{N}$ be undetermined, we will choose it accordingly later. Uniformly at random choose a function $\hat{\xi}:V(G)\to\{0,\ldots,n-1\}$ and let it induce a monotone function $\xi:V(G)\to\{0,\ldots,|V(G)|\cdot n-1\}$ by mapping the $i$ -th smallest vertex $v\in V(G)$ to $(i-1)\cdot n+\hat{\xi}(v)$ . We then set $j=|V(G)|\cdot n$ .

For an ordered graph $H\sqsubseteq G$ , we denote by $\xi(H)$ the graph on the vertices $\{0,\ldots,|V(G)|\cdot n-1\}$ , where the edges are given as the images of the edges of $H$ under $\xi$ . Any vertex that is not in the image of $\xi(V(H))$ is thus an isolated vertex. We are trying to find some $\xi$ , s.t. for all $H\sqsubseteq G$ , all accepting paths of the computation $\#\textup{{{acc}}}_{M^{\xi(H)}}(j)$ do not access the oracle for any edges incident to vertices in $\xi(V(G))\setminus\xi(V(H))$ . By the union bound, if we can show this happening with high probability for each of the finitely many individual $H\sqsubseteq G$ , then there is such a $\xi$ , so for now fix some $H\sqsubseteq G$ .

Now group the functions $\xi$ by their image of $V(H)$ and fix one such group $I$ . Note that the image of the remaining vertices $V(G)\setminus V(H)$ under $\xi$ is still independently and uniformly distributed from $n$ possible choices each by the choice of $\hat{\xi}$ . Consider the set $S_{I}$ of all vertices queried by all accepting paths of the computation $\#\textup{{{acc}}}_{M^{\xi(H)}}(j)$ . Let $t_{M}(j)$ be the worst-case running-time of $M$ on input $j$ . Each oracle query can query at most two vertices, there are at most $\varphi(H)$ many accepting paths and each accepting path can query the oracle at most $t_{M}(j)$ many times and as such the size $|S_{I}|$ is bounded by $2\cdot\varphi(H)\cdot t_{M}(j)$ , which is polynomial in $\log(j)$ due to $M$ being polynomial-time and $H$ being fixed. As a rough estimate using the Bernoulli inequality, this means that for a fraction of at least $\left(1-\frac{|S_{I}|}{n}\right)^{|V(G)|}\geq 1-\frac{|S_{I}|\cdot|V(G)|}{n}$ choices of $\hat{\xi}$ resulting in $\xi\in I$ , none of the accepting paths queries any edges incident to vertices in $\xi(V(G))\setminus\xi(V(H))$ . By averaging across all possible $\hat{\xi}$ (no longer restricted to $I$ ), we see that a fraction of $1-\frac{\mathrm{polylog}(j)\cdot|V(G)|}{n}$ choices have our desired property.

Using the union bound over all $H\sqsubseteq G$ , we get that a fraction of $1-\frac{\mathrm{polylog}(j)\cdot|V(G)|\cdot 2^{|V(G)|}}{n}$ choices of $\hat{\xi}$ lead to the desired property for all $H\sqsubseteq G$ simultaneously. By choosing $n$ large enough (remember that $j$ and $n$ are polynomially related, so this is always possible), this guarantees the existence of our desired $\xi$ , s.t. for all $H\sqsubseteq G$ , all accepting paths of the computation $\#\textup{{{acc}}}_{M^{\xi(H)}}(j)$ do not access the oracle for any edges incident to vertices in $\xi(V(G))\setminus\xi(V(H))$ .

We can now construct our set-instantiator with $j$ chosen as above. The instantiation function for $H\sqsubseteq G$ is $\textup{{{inst}}}_{\textup{{$\mathcal{S}\!I$}}}(H)=\xi(H)$ . For any computation path $\tau\in\{0,1\}^{\star}$ of a computation $\#\textup{{{acc}}}_{M^{\xi(H)}}(j)$ , denote by $S_{\tau}\subseteq\{0,\ldots,j-1\}$ the set of vertices that are queried by the computation. We set

\displaystyle\textup{{{perc}}}_{\textup{{$\mathcal{S}\!I$}}}(\tau):=\begin{% cases}G[\xi^{-1}(S_{\tau})]&\text{if $\tau$ is an accepting path of the % computation $\#\textup{{{acc}}}_{M^{\xi(G)}}(j)$,}\\ \top&\text{otherwise}\end{cases}

Note that the preimage $\xi^{-1}(S_{\tau})$ is defined to be simply the set $\{v\in V(G)\mid\xi(v)\in S_{\tau}\}$ , even if $S_{\tau}$ is not entirely contained in the image of $\xi$ .

We check the properties of a set-instantiator. Clearly $\varphi(\textup{{{inst}}}_{\textup{{$\mathcal{S}\!I$}}}(H))=\varphi(H)$ for all $H\sqsubseteq G$ , since the two graphs are identical except isolated vertices and no pattern in $\varphi$ contains any isolated vertices. Further we need that for all $H\sqsubseteq G$ we have that $\tau\in\{0,1\}^{\star}$ is an accepting path for the computation $\#\textup{{{acc}}}_{M^{\textup{{{inst}}}_{\textup{{$\mathcal{S}\!I$}}}(H)}}(j)$ iff $\textup{{{perc}}}_{\textup{{$\mathcal{S}\!I$}}}(\tau)\sqsubseteq H$ . For this fix $H\sqsubseteq G$ and let $\tau$ be an accepting path for the computation $\#\textup{{{acc}}}_{M^{\textup{{{inst}}}_{\textup{{$\mathcal{S}\!I$}}}(H)}}(j)$ . By our choice of $\xi$ we know that no other vertices of $\xi(V(G))\setminus\xi(V(H))$ are queried, or in other words, $\xi^{-1}(S_{\tau})\subseteq V(H)$ and thus $\tau$ is also an accepting path for the computation $\#\textup{{{acc}}}_{M^{\textup{{{inst}}}_{\textup{{$\mathcal{S}\!I$}}}(G)}}(j)$ . This directly implies $\textup{{{perc}}}_{\textup{{$\mathcal{S}\!I$}}}(\tau)=G[\xi^{-1}(S_{\tau})]\sqsubseteq H$ . On the other hand, let $\textup{{{perc}}}_{\textup{{$\mathcal{S}\!I$}}}(\tau)\sqsubseteq H$ , then $\textup{{{perc}}}_{\textup{{$\mathcal{S}\!I$}}}(\tau)\neq\top$ and $\tau$ is an accepting path of the computation $\#\textup{{{acc}}}_{M^{\textup{{{inst}}}_{\textup{{$\mathcal{S}\!I$}}}(G)}}(j)$ , since $\textup{{{perc}}}_{\textup{{$\mathcal{S}\!I$}}}(\tau)=G[\xi^{-1}(S_{\tau})]\sqsubseteq H$ , $\tau$ is also an accepting path of the computation $\#\textup{{{acc}}}_{M^{\textup{{{inst}}}_{\textup{{$\mathcal{S}\!I$}}}(H)}}(j)$ . $\hfill\blacktriangleleft$

If $H_{1}$ and $H_{2}$ are isomorphic, then it can still be the case that $\#\textup{{{acc}}}_{M^{\textup{{{inst}}}_{\textup{{$\mathcal{S}\!I$}}}(H_{1})}% }(j)\neq\#\textup{{{acc}}}_{M^{\textup{{{inst}}}_{\textup{{$\mathcal{S}\!I$}}}% (H_{2})}}(j)$ , which we do not want to happen in a good function. For example if $G$ is any graph containing some triangles, then we want the instantiation of every induced triangle of $G$ to have the same number of accepting paths. We thus want to construct an instantiation function that no longer has this problem. We achieve this by creating a very large set-instantiator and then restricting ourselves to some small part of the set-instantiator where we can enforce this property.

Ensuring this structure is achieved by usage of a Ramsey theorem. For two graphs $H$ and $G$ we denote by $\binom{G}{H}$ the subset of induced subgraphs of $G$ that are isomorphic to $H$ .

Lemma 20 (Main Theorem in [26]).

Let $F,G\in\mathcal{OG}$ and let $t\in\mathbb{N}$ be fixed. Then there is a $H\in\mathcal{OG}$ , such that for every $\Phi:\binom{H}{F}\to\{0,\ldots,t\}$ , there is a $G_{\Phi}\sqsubseteq H$ with $G_{\Phi}\cong G$ with the property that $|\Phi(\binom{G_{\Phi}}{F})|=1$ .

Note that Lemma 20 is the reason why we need to generalize our result to ordered graphs first instead of being able to prove it directly for unordered graphs. It is known that this type of Ramsey theorem does not hold for unordered graphs [25, Theorem 5.1].

By repeatedly applying Lemma 20 we get

Proposition 21 (Ramsey Theorem).

Let $G\in\mathcal{OG}$ and let $t\in\mathbb{N}$ be fixed. Then there is an $H\in\mathcal{OG}$ , such that for every $\Phi:\mathcal{P}(H)\to\{0,\ldots,t\}$ there is a $G_{\Phi}\sqsubseteq H$ with $G_{\Phi}\cong G$ with the property, if $A,B\sqsubseteq G_{\Phi}$ with $A\cong B$ , then $\Phi(A)=\Phi(B)$ .

This theorem can now be used to ensure that for every polynomial-time NTM there must be some small set of inputs where the NTM behaves like a good function.

Lemma 22.

Let $\varphi$ be a pure ordered graph motif parameter, let $M$ be any nondeterministic polynomial-time Turing machine computing $\operatorname{Eval}_{\varphi}$ and let $G\in\mathcal{OG}$ . Then there is some $j\in\mathbb{N}$ , a function $\textup{{{inst}}}:\mathcal{P}(G)\to{\mathcal{OG}_{=j}}$ and a $\mathcal{P}(G)$ -good function $\Psi$ with $\#\textup{{{acc}}}_{M^{\textup{{{inst}}}(F)}}(j)=\Psi(F)$ and $\varphi(\textup{{{inst}}}(F))=\varphi(F)$ for every $F\sqsubseteq G$ .

Proof.

We invoke Proposition 21 for $G$ and $t:=\max\{\varphi(H)\,:\,H\sqsubseteq G\}$ to obtain $\widetilde{G}\in\mathcal{OG}$ . We now want to color $\mathcal{P}(\widetilde{G})$ according to the behaviour of $M$ on the elements of it, in particular how many accepting paths query each specific induced subgraph of $\widetilde{G}$ . Before we can do this we have to first embed all potential elements of $\mathcal{P}(\widetilde{G})$ as oracles. In order to do this we use Lemma 19 to construct a set-instantiator $\mathcal{S}\!I$ against $(M,\widetilde{G},\varphi)$ to obtain a $j\in\mathbb{N}$ , $\textup{{{inst}}}_{\textup{{$\mathcal{S}\!I$}}}$ and $\textup{{{perc}}}_{\textup{{$\mathcal{S}\!I$}}}$ as in Definition 18.

For $H\in\mathcal{P}(\widetilde{G})$ define $\Phi(H):=\#\textup{{{acc}}}_{M^{\textup{{{inst}}}_{\textup{{$\mathcal{S}\!I$}}% }(H)}}(j)$ . Note that

\Phi(H)\ =\ \bigl{|}\bigl{\{}\tau\in\{0,1\}^{*}\,:\,\textup{{{perc}}}_{\textup% {{$\mathcal{S}\!I$}}}(\tau)\sqsubseteq H\bigr{\}}\bigr{|}=\sum_{F\sqsubseteq H% }\,\bigl{|}\big{\{}\tau\in\{0,1\}^{*}\,:\,\textup{{perc}}_{\textup{{$\mathcal{% S}\!I$}}}(\tau)=F\big{\}}\bigr{|}.

(3)

Using $\Phi$ as a coloring for Proposition 21, we obtain $G_{\Phi}$ . Note that $\Phi(H)$ now only depends on the isomorphism type $[H]$ of $H$ for all $H\sqsubseteq G_{\Phi}$ . By induction we see that the number $\big{|}\big{\{}\tau\in\{0,1\}^{*}\,:\,\textup{{perc}}_{\textup{{$\mathcal{S}\!% I$}}}(\tau)=H\big{\}}\big{|}$ also depends only on the isomorphism type of $H$ , whenever $H\sqsubseteq G_{\Phi}$ . Denote this number by $\alpha_{[H]}$ and set $\Psi([H]):=\Phi(H)$ . This is only well-defined for $H\sqsubseteq G_{\Phi}$ , thus we consider the domain of $\Psi$ to be $\mathcal{P}([G_{\Phi}])=\mathcal{P}([G])$ . This means that (3) simplifies:

\Psi([H])\ =\ \sum_{[F]}\#\mathrm{Ind}([F]\to[H])\alpha_{[F]}

(4)

where the sum is over all isomorphism classes $[F]$ of induced subgraphs $F\sqsubseteq H$ . This implies that $\Phi$ is $\mathcal{P}(G)$ -good.

It remains to define the function $\textup{{{inst}}}:\mathcal{P}(G)\to{\mathcal{OG}_{=j}}$ . Let $H\sqsubseteq G$ , then $\textup{{{inst}}}(H):=\textup{{{inst}}}_{\textup{{$\mathcal{S}\!I$}}}(H_{\Phi})$ for some $H_{\Phi}\sqsubseteq G_{\Phi}$ with $H\cong H_{\Phi}$ . The property $\varphi(\textup{{{inst}}}(H))=\varphi(H)$ now directly follows from $\mathcal{S}\!I$ being a set-instantiator. $\hfill\blacktriangleleft$

Note that Lemma 22 only guarantees the local behaviour of $M$ to be $\mathcal{P}(G)$ -good. This leaves two possibilities for contradictions: Either the local behaviour is even $(\mathcal{P}(G)\cap{\mathcal{OG}^{\text{pure}}})$ -good, or the function grows too quickly for inputs with many isolated vertices. This next Witness Theorem shows that in the first case we can always find an ordered graph that proves that $M$ does not compute the correct function using a simple linear algebra argument.

Theorem 23 (The Witness Theorem).

Fix a bad $\varphi:{\mathcal{OG}^{\text{pure}}}\to\mathbb{N}$ . Then there exists $G\in{\mathcal{OG}^{\text{pure}}}$ such that for every $(\mathcal{P}(G)\cap{\mathcal{OG}^{\text{pure}}})$ -good function $\Psi:(\mathcal{P}(G)\cap{\mathcal{OG}^{\text{pure}}})\to\mathbb{N}$ , there exists $W\in\mathcal{P}(G)\cap{\mathcal{OG}^{\text{pure}}}$ with $\Psi(W)\neq\varphi(W)$ .

Proof.

Choose $G$ to be the disjoint union of the graphs in $\textup{supp}(\varphi)$ and let $\mathcal{OG}^{\prime}:=\mathcal{P}(G)\cap{\mathcal{OG}^{\text{pure}}}$ , keeping only one representative per isomorphism class. By Fact 9, the functions $\#\mathrm{Ind}(H\to\,\star\,)$ for $H\in\mathcal{OG}^{\prime}$ are linearly independent. Thus the patterns and coefficients of any function $\Psi$ with support $\textup{supp}(\Psi)\subseteq\mathcal{P}(G)\cap{\mathcal{OG}^{\text{pure}}}$ are uniquely determined by the evaluations $\Psi$ on $\mathcal{P}(G)\cap{\mathcal{OG}^{\text{pure}}}$ , and there exists a witness $W\in\mathcal{P}(G)\cap{\mathcal{OG}^{\text{pure}}}$ with $\Psi(W)\neq\varphi(W)$ , since $\Psi$ is good while $\varphi$ is bad (thus, $\Psi$ and $\varphi$ are not the same function). $\hfill\blacktriangleleft$

With this last tool we are finally able to lead the existence of polynomial-time NTMs computing bad ordered graph motif parameters to a contradiction.

Lemma 24.

Let $M$ be any nondeterministic polynomial-time Turing machine computing $\operatorname{Eval}_{\varphi}$ for some bad pure ordered graph motif parameter $\varphi$ . Then there is a $j\in\mathbb{N}$ and $W\in{\mathcal{OG}_{=j}}$ such that $\#\textup{{{acc}}}_{M^{W}}(j)\neq\varphi(W)$ .

Proof.

We invoke the Witness Theorem 23 with our $\varphi$ to obtain an $G_{1}\in{\mathcal{OG}^{\text{pure}}}$ as in the theorem. Construct $G_{2}$ such that

	$\displaystyle\#\mathrm{Ind}(H\to G_{2})$	$\displaystyle>\max\big{\{}\varphi(F)\,:\,F\in\mathcal{P}(G_{1})\cap{\mathcal{% OG}^{\text{pure}}}\big{\}}$	for all $H\in\mathcal{P}(G_{1})\setminus{\mathcal{OG}^{\text{pure}}}$		(5)
	$\displaystyle\#\mathrm{Ind}(H\to G_{2})$	$\displaystyle=\#\mathrm{Ind}(H\to G_{1})$	for all $H\in{\mathcal{OG}^{\text{pure}}}$		(6)

by adding sufficiently many isolated vertices to $G_{1}$ . For this it is sufficient to add $1+\max\big{\{}\varphi(F)\,:\,F\in\mathcal{P}(G_{1})\cap{\mathcal{OG}^{\text{% pure}}}\big{\}}$ isolated vertices in between every pair of adjacent vertices in $G_{1}$ , relative to $\leq_{G_{1}}$ .

We now use Lemma 22 to obtain $j\in\mathbb{N}$ , a function $\textup{{{inst}}}:\mathcal{P}(G_{2})\to{\mathcal{OG}_{=j}}$ and a $\mathcal{P}(G_{2})$ -good function $\Psi$ with $\#\textup{{{acc}}}_{M^{\textup{{{inst}}}(H)}}(j)=\Psi(H)$ and $\varphi(\textup{{{inst}}}(H))=\varphi(H)$ for every $H\sqsubseteq G_{2}$ . There are now two possibilities to find the required counterexample $W$ : If there are no basis functions present in $\Psi$ with a pattern in $\mathcal{P}(G_{1})\setminus{\mathcal{OG}^{\text{pure}}}$ , we can invoke the Witness Theorem again. If any of these basis functions are present we can construct a direct counterexample.

We first handle the case where such a basis function is present, so let the coefficient of $\#\mathrm{Ind}(H\to\,\star\,)$ in $\Psi$ be positive for some $H\in\mathcal{P}(G_{1})\setminus{\mathcal{OG}^{\text{pure}}}$ . Then

\Psi(G_{2})\geq\#\mathrm{Ind}(H\to G_{2})>\max\big{\{}\varphi(F)\,:\,F\in% \mathcal{P}(G_{1})\cap{\mathcal{OG}^{\text{pure}}}\big{\}}\geq\varphi(G_{1})=% \varphi(G_{2})

by (5) and (6), combined with the fact that $\varphi$ is pure, and our counterexample is $W:=G_{2}$ .

Otherwise assume that no such basis function is present. Then $\widetilde{\Psi}$ obtained from $\Psi$ by restricting to $\mathcal{P}(G_{1})$ (i.e. setting all coefficients of $\mathcal{P}(G_{2})\setminus\mathcal{P}(G_{1})$ to zero), is $(\mathcal{P}(G_{1})\cap{\mathcal{OG}^{\text{pure}}})$ -good, which is a requirement for the second part of the Witness Theorem 23 (we already used it to obtain $G_{1}$ ). Furthermore $\widetilde{\Psi}_{|\mathcal{P}(G_{1})}=\Psi_{|\mathcal{P}(G_{1})}$ . We invoke the second part of the Witness Theorem 23 to find a point $W\in\mathcal{P}(G_{1})\cap{\mathcal{OG}^{\text{pure}}}$ with $\Psi(W)=\widetilde{\Psi}(W)\neq\varphi(W)$ which is our counterexample.

Independent of how we have obtained our $W$ we observe $\#\textup{{{acc}}}_{M^{\textup{{{inst}}}(W)}}(j)=\Psi(W)\neq\varphi(W)=\varphi% (\textup{{{inst}}}(W))$ , which completes the proof for $W^{\prime}=\textup{{{inst}}}(W)$ . $\hfill\blacktriangleleft$

This proves the separation in Theorem 16, which together with Lemmas 11 and 12 finishes the proof of the theorem.

6 Overview of Results for Relational Structures and Categories

Induced subgraph counts can also be considered in a colored setting, where each vertex has a color and colored graphs are considered isomorphic if the colors of the vertices that are mapped to each other by the isomorphism have to agree. Such colored patterns occur, e.g., within the proofs of some parameterized hardness results [9, 6], as access to vertex-colors gives more versatility in the reduction. It is natural to ask whether our main theorem generalizes from graphs to colored graphs and to other more general versions of graphs, such as hypergraphs of bounded edge-cardinality. We answer this question positively for general relational structures; due to space limitations, this part only appears in the full version. The proof proceeds along the same lines as Theorem 13, our main theorem about graphs.

Generalizing further from relational structures, we consider the vastly more general setting of category theory in the full version and show a variant of Theorem 13 for motif parameters defined over categories. It turns out that the arguments from the main proof can be adapted for this purpose, but only after significant technical effort: While homomorphisms and embeddings naturally generalize from graphs to categories, nontrivial concepts from category theory are needed to formulate the proper requirements on categories that allow us to handle subobjects similarly to induced subgraphs. Among other such requirements, we require well-powered categories (where every subobject itself has only finitely many isomorphism types of subobjects) and proper factorization systems (that decompose morphisms into compositions of epimorphisms and monomorphisms). We then use the general category-theoretic framework to study combinatorial interpretations of counting problems related to finite vector spaces and to so-called parameter sets, which play a role in enumerative combinatorics.

References

[1] Paul Beame, Stephen Cook, Jeff Edmonds, Russell Impagliazzo, and Toniann Pitassi. The relative complexity of NP search problems. In Proceedings of the twenty-seventh annual ACM Symposium on Theory of Computing, pages 303–314, 1995. doi:10.1145/225058.225147.
[2] Paul Beame, Russell Impagliazzo, and Toniann Pitassi. Improved depth lower bounds for small distance connectivity. In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pages 692–701. IEEE Computer Society, 1995. doi:10.1109/SFCS.1995.492671.
[3] Richard Beigel. Closure properties of GapP and #P. In Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems, pages 144–146. IEEE, 1997. doi:10.1109/ISTCS.1997.595166.
[4] Jin-Yi Cai, Thomas Gundermann, Juris Hartmanis, Lane A Hemachandra, Vivian Sewelson, Klaus Wagner, and Gerd Wechsung. The boolean hierarchy II: Applications. SIAM Journal on Computing, 18(1):95–111, 1989. doi:10.1137/0218007.
[5] Swee Hong Chan and Igor Pak. Computational complexity of counting coincidences. Theoretical Computer Science, 1015:114776, 2024. doi:10.1016/j.tcs.2024.114776.
[6] Radu Curticapean. Count on CFI graphs for #P-hardness. In Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 1854–1871. SIAM, 2024. doi:10.1137/1.9781611977912.74.
[7] Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, pages 210–223, 2017. doi:10.1145/3055399.3055502.
[8] Julian Dörfler and Christian Ikenmeyer. Functional closure properties of finite $\mathbb{n}$ -weighted automata. In 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia, volume 297 of LIPIcs, pages 134:1–134:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.ICALP.2024.134.
[9] Julian Dörfler, Marc Roth, Johannes Schmitt, and Philip Wellnitz. Counting induced subgraphs: An algebraic approach to #W[1]-hardness. Algorithmica, 84(2):379–404, 2022. doi:10.1007/s00453-021-00894-9.
[10] Simon Döring, Dániel Marx, and Philip Wellnitz. Counting small induced subgraphs with edge-monotone properties. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 1517–1525. ACM, 2024. doi:10.1145/3618260.3649644.
[11] RL Graham, K Leeb, and BL Rothschild. Ramsey’s theorem for a class of categories. Advances in Mathematics, 8(3):417–433, 1972.
[12] Lane A. Hemaspaandra and Mitsunori Ogihara. The Complexity Theory Companion. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2002. doi:10.1007/978-3-662-04880-1.
[13] Ulrich Hertrampf. Classes of bounded counting type and their inclusion relations. In STACS 95: 12th Annual Symposium on Theoretical Aspects of Computer Science Munich, Germany, March 2–4, 1995 Proceedings 12, pages 60–70. Springer, 1995. doi:10.1007/3-540-59042-0_62.
[14] Ulrich Hertrampf, Heribert Vollmer, and Klaus W. Wagner. On the power of number-theoretic operations with respect to counting. In Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference, pages 299–314, 1995. doi:10.1109/SCT.1995.514868.
[15] Christian Ikenmeyer and Igor Pak. What is in #P and what is not? In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 860–871, 2022. doi:10.1109/FOCS54457.2022.00087.
[16] Christian Ikenmeyer, Igor Pak, and Greta Panova. Positivity of the symmetric group characters is as hard as the polynomial time hierarchy. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3573–3586, 2023. doi:10.1137/1.9781611977554.ch136.
[17] John Isbell. Some inequalities in hom sets. Journal of Pure and Applied Algebra, 76(1):87–110, 1991. doi:10.1016/0022-4049(91)90099-N.
[18] Mark Jerrum and Kitty Meeks. The parameterised complexity of counting connected subgraphs and graph motifs. J. Comput. Syst. Sci., 81(4):702–716, 2015. doi:10.1016/j.jcss.2014.11.015.
[19] Mark Jerrum and Kitty Meeks. Some hard families of parameterized counting problems. ACM Trans. Comput. Theory, 7(3):11:1–11:18, 2015. doi:10.1145/2786017.
[20] Mark Jerrum and Kitty Meeks. The parameterised complexity of counting even and odd induced subgraphs. Comb., 37(5):965–990, 2017. doi:10.1007/s00493-016-3338-5.
[21] David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. How easy is local search? J. Comput. Syst. Sci., 37(1):79–100, 1988. doi:10.1016/0022-0000(88)90046-3.
[22] Ker-I Ko. Complexity Theory of Real Functions. Birkhäuser / Springer, 1991. doi:10.1007/978-1-4684-6802-1.
[23] Carl Kostka. Über den Zusammenhang zwischen einigen Formen von symmetrischen Functionen. Walter de Gruyter, Berlin/New York Berlin, New York, 1882.
[24] Gregor Lagodzinski. Counting homomorphisms over fields of prime order (Zählen von Homomorphismen über Körper mit Primzahlordnung). PhD thesis, University of Potsdam, Germany, 2024. doi:10.25932/PUBLISHUP-64603.
[25] Jaroslav Nešetřil. Ramsey theory. In Handbook of Combinatorics, volume 2, pages 1331–1403. Elsevier Science B.V., Amsterdam, 1995.
[26] Jaroslav Nešetřil and Vojtech Rödl. Partitions of finite relational and set systems. J. Comb. Theory A, 22(3):289–312, 1977. doi:10.1016/0097-3165(77)90004-8.
[27] Mitsunori Ogiwara and Lane A Hemachandra. A complexity theory for feasible closure properties. Journal of Computer and System Sciences, 46(3):295–325, 1993. doi:10.1016/0022-0000(93)90006-I.
[28] Igor Pak. Short stories: Combinatorial inequalities. Notices of the American Mathematical Society, 66(7):1109–1112, 2019.
[29] Igor Pak. What is a combinatorial interpretation? CoRR, abs/2209.06142, 2022. doi:10.48550/arXiv.2209.06142.
[30] Greta Panova. Computational complexity in algebraic combinatorics. arXiv:2306.17511, 2023. doi:10.48550/arXiv.2306.17511.
[31] Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci., 48(3):498–532, 1994. doi:10.1016/S0022-0000(05)80063-7.
[32] Marc Roth. Counting problems on quantum graphs. PhD thesis, Saarland University, Germany, 2019. doi:10.22028/D291-28348.
[33] Marc Roth, Johannes Schmitt, and Philip Wellnitz. Counting small induced subgraphs satisfying monotone properties. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1356–1367. IEEE, 2020. doi:10.1109/FOCS46700.2020.00128.
[34] Marc Roth, Johannes Schmitt, and Philip Wellnitz. Detecting and counting small subgraphs, and evaluating a parameterized tutte polynomial: Lower bounds via toroidal grids and cayley graph expanders. In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 108:1–108:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ICALP.2021.108.
[35] M.-P. Schützenberger. La correspondance de Robinson. In Combinatoire et Représentation du Groupe Symétrique, pages 59–113, Berlin, Heidelberg, 1977. Springer Berlin Heidelberg.
[36] Richard P Stanley. Positivity problems and conjectures in algebraic combinatorics. Mathematics: frontiers and perspectives, 295:319, 2000.
[37] Richard P. Stanley. Enumerative Combinatorics, Volume 1, volume 49 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, second edition, 2011.
[38] Klaus Weihrauch. Computable Analysis - An Introduction. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2000. doi:10.1007/978-3-642-56999-9.

[bib.bib1] [1] Paul Beame, Stephen Cook, Jeff Edmonds, Russell Impagliazzo, and Toniann Pitassi. The relative complexity of NP search problems. In Proceedings of the twenty-seventh annual ACM Symposium on Theory of Computing, pages 303–314, 1995. doi:10.1145/225058.225147.

[bib.bib2] [2] Paul Beame, Russell Impagliazzo, and Toniann Pitassi. Improved depth lower bounds for small distance connectivity. In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pages 692–701. IEEE Computer Society, 1995. doi:10.1109/SFCS.1995.492671.

[bib.bib3] [3] Richard Beigel. Closure properties of GapP and #P. In Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems, pages 144–146. IEEE, 1997. doi:10.1109/ISTCS.1997.595166.

[bib.bib4] [4] Jin-Yi Cai, Thomas Gundermann, Juris Hartmanis, Lane A Hemachandra, Vivian Sewelson, Klaus Wagner, and Gerd Wechsung. The boolean hierarchy II: Applications. SIAM Journal on Computing, 18(1):95–111, 1989. doi:10.1137/0218007.

[bib.bib5] [5] Swee Hong Chan and Igor Pak. Computational complexity of counting coincidences. Theoretical Computer Science, 1015:114776, 2024. doi:10.1016/j.tcs.2024.114776.

[bib.bib6] [6] Radu Curticapean. Count on CFI graphs for #P-hardness. In Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 1854–1871. SIAM, 2024. doi:10.1137/1.9781611977912.74.

[bib.bib7] [7] Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, pages 210–223, 2017. doi:10.1145/3055399.3055502.

[bib.bib8] [8] Julian Dörfler and Christian Ikenmeyer. Functional closure properties of finite $\mathbb{n}$ -weighted automata. In 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia, volume 297 of LIPIcs, pages 134:1–134:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.ICALP.2024.134.

[bib.bib9] [9] Julian Dörfler, Marc Roth, Johannes Schmitt, and Philip Wellnitz. Counting induced subgraphs: An algebraic approach to #W[1]-hardness. Algorithmica, 84(2):379–404, 2022. doi:10.1007/s00453-021-00894-9.

[bib.bib10] [10] Simon Döring, Dániel Marx, and Philip Wellnitz. Counting small induced subgraphs with edge-monotone properties. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 1517–1525. ACM, 2024. doi:10.1145/3618260.3649644.

[bib.bib11] [11] RL Graham, K Leeb, and BL Rothschild. Ramsey’s theorem for a class of categories. Advances in Mathematics, 8(3):417–433, 1972.

[bib.bib12] [12] Lane A. Hemaspaandra and Mitsunori Ogihara. The Complexity Theory Companion. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2002. doi:10.1007/978-3-662-04880-1.

[bib.bib13] [13] Ulrich Hertrampf. Classes of bounded counting type and their inclusion relations. In STACS 95: 12th Annual Symposium on Theoretical Aspects of Computer Science Munich, Germany, March 2–4, 1995 Proceedings 12, pages 60–70. Springer, 1995. doi:10.1007/3-540-59042-0_62.

[bib.bib14] [14] Ulrich Hertrampf, Heribert Vollmer, and Klaus W. Wagner. On the power of number-theoretic operations with respect to counting. In Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference, pages 299–314, 1995. doi:10.1109/SCT.1995.514868.

[bib.bib15] [15] Christian Ikenmeyer and Igor Pak. What is in #P and what is not? In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 860–871, 2022. doi:10.1109/FOCS54457.2022.00087.

[bib.bib16] [16] Christian Ikenmeyer, Igor Pak, and Greta Panova. Positivity of the symmetric group characters is as hard as the polynomial time hierarchy. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3573–3586, 2023. doi:10.1137/1.9781611977554.ch136.

[bib.bib17] [17] John Isbell. Some inequalities in hom sets. Journal of Pure and Applied Algebra, 76(1):87–110, 1991. doi:10.1016/0022-4049(91)90099-N.

[bib.bib18] [18] Mark Jerrum and Kitty Meeks. The parameterised complexity of counting connected subgraphs and graph motifs. J. Comput. Syst. Sci., 81(4):702–716, 2015. doi:10.1016/j.jcss.2014.11.015.

[bib.bib19] [19] Mark Jerrum and Kitty Meeks. Some hard families of parameterized counting problems. ACM Trans. Comput. Theory, 7(3):11:1–11:18, 2015. doi:10.1145/2786017.

[bib.bib20] [20] Mark Jerrum and Kitty Meeks. The parameterised complexity of counting even and odd induced subgraphs. Comb., 37(5):965–990, 2017. doi:10.1007/s00493-016-3338-5.

[bib.bib21] [21] David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. How easy is local search? J. Comput. Syst. Sci., 37(1):79–100, 1988. doi:10.1016/0022-0000(88)90046-3.

[bib.bib22] [22] Ker-I Ko. Complexity Theory of Real Functions. Birkhäuser / Springer, 1991. doi:10.1007/978-1-4684-6802-1.

[bib.bib23] [23] Carl Kostka. Über den Zusammenhang zwischen einigen Formen von symmetrischen Functionen. Walter de Gruyter, Berlin/New York Berlin, New York, 1882.

[bib.bib24] [24] Gregor Lagodzinski. Counting homomorphisms over fields of prime order (Zählen von Homomorphismen über Körper mit Primzahlordnung). PhD thesis, University of Potsdam, Germany, 2024. doi:10.25932/PUBLISHUP-64603.

[bib.bib25] [25] Jaroslav Nešetřil. Ramsey theory. In Handbook of Combinatorics, volume 2, pages 1331–1403. Elsevier Science B.V., Amsterdam, 1995.

[bib.bib26] [26] Jaroslav Nešetřil and Vojtech Rödl. Partitions of finite relational and set systems. J. Comb. Theory A, 22(3):289–312, 1977. doi:10.1016/0097-3165(77)90004-8.

[bib.bib27] [27] Mitsunori Ogiwara and Lane A Hemachandra. A complexity theory for feasible closure properties. Journal of Computer and System Sciences, 46(3):295–325, 1993. doi:10.1016/0022-0000(93)90006-I.

[bib.bib28] [28] Igor Pak. Short stories: Combinatorial inequalities. Notices of the American Mathematical Society, 66(7):1109–1112, 2019.

[bib.bib29] [29] Igor Pak. What is a combinatorial interpretation? CoRR, abs/2209.06142, 2022. doi:10.48550/arXiv.2209.06142.

[bib.bib30] [30] Greta Panova. Computational complexity in algebraic combinatorics. arXiv:2306.17511, 2023. doi:10.48550/arXiv.2306.17511.

[bib.bib31] [31] Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci., 48(3):498–532, 1994. doi:10.1016/S0022-0000(05)80063-7.

[bib.bib32] [32] Marc Roth. Counting problems on quantum graphs. PhD thesis, Saarland University, Germany, 2019. doi:10.22028/D291-28348.

[bib.bib33] [33] Marc Roth, Johannes Schmitt, and Philip Wellnitz. Counting small induced subgraphs satisfying monotone properties. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1356–1367. IEEE, 2020. doi:10.1109/FOCS46700.2020.00128.

[bib.bib34] [34] Marc Roth, Johannes Schmitt, and Philip Wellnitz. Detecting and counting small subgraphs, and evaluating a parameterized tutte polynomial: Lower bounds via toroidal grids and cayley graph expanders. In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 108:1–108:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ICALP.2021.108.

[bib.bib35] [35] M.-P. Schützenberger. La correspondance de Robinson. In Combinatoire et Représentation du Groupe Symétrique, pages 59–113, Berlin, Heidelberg, 1977. Springer Berlin Heidelberg.

[bib.bib36] [36] Richard P Stanley. Positivity problems and conjectures in algebraic combinatorics. Mathematics: frontiers and perspectives, 295:319, 2000.

[bib.bib37] [37] Richard P. Stanley. Enumerative Combinatorics, Volume 1, volume 49 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, second edition, 2011.

[bib.bib38] [38] Klaus Weihrauch. Computable Analysis - An Introduction. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2000. doi:10.1007/978-3-642-56999-9.

Which Graph Motif Parameters Count?

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Positivity in Combinatorics and #P

1.2 Do Nonnegative Graph Motif Parameters Count?

Example 1.

Example 2.

2 Preliminaries

2.1 Type-2 Counting Complexity

Example 3.

Example 4.

Example 5.

Definition 6.

Definition 7.

Definition 8.

2.2 What is a Combinatorial Interpretation – and What is Not?

2.3 Induced Subgraph Numbers

Fact 9.

Definition 10.

Lemma 11.

Proof.

Lemma 12.

3 Our Results

3.1 Graphs

Theorem 13.

3.2 More General Structures

3.2.1 Relational Structures

Theorem 14 (informal, see full version for a precise statement).

3.2.2 Category Theory

Theorem 15 (informal, see full version for the precise statement).

3.3 Linearization

4 Related Work

5 Results for Graphs

5.1 Reduction to Ordered Graphs

Theorem 16.

5.2 Ordered Graphs

Definition 17.

Definition 18 (Set-instantiator against (M,G,φ)).

Lemma 19.

Proof.

Lemma 20 (Main Theorem in [26]).

Proposition 21 (Ramsey Theorem).

Lemma 22.

Proof.

Theorem 23 (The Witness Theorem).

Proof.

Lemma 24.

Proof.

6 Overview of Results for Relational Structures and Categories

References

Definition 18 (Set-instantiator against $(M,G,\varphi)$ ).