# Parameterized Valiant’s classes

Markus Bläser111Computational Complexity Department, Saarlnad University,
Germany<EMAIL_ADDRESS>Christian Engels222CSE Department, IIT
Bombay, India<EMAIL_ADDRESS>
###### Abstract

We define a theory of parameterized algebraic complexity classes in analogy to
parameterized Boolean counting classes. We define the classes $\mathsf{VFPT}$
and $\mathsf{VW}[t]$, which mirror the Boolean counting classes
$\mathsf{\\#FPT}$ and $\mathsf{\\#W}[t]$, and define appropriate reductions
and completeness notions. Our main contribution is the
$\mathsf{VW}[1]$-completeness proof of the parameterized clique family. This
proof is far more complicated than in the Boolean world. It requires some new
concepts like composition theorems for bounded exponential sums and Boolean-
arithmetic formulas. In addition, we also look at two polynomials linked to
the permanent with vastly different parameterized complexity.

##  1 Introduction

When Valiant invented the theory of computational counting and
$\mathsf{\\#P}$-completeness, he also defined an algebraic model for computing
families of polynomials [Val79]. This was very natural, since many (Boolean)
counting problems are evaluations of polynomials: Counting perfect matchings
in bipartite graphs is the same as evaluating the permanent at the adjacency
matrix, counting Hamiltonian tours in directed graphs is the same as
evaluating the Hamiltonian cycle polynomial at the adjacency matrix, etc.
There is a fruitful interplay between the Boolean and the algebraic world:
algebraic methods like interpolation can be used to design counting algorithms
as well as for proving hardness results. Proving lower bounds might be easier
in the algebraic world and then we can use transfer theorems from the
algebraic world to the Boolean world [Bür00b].

Parameterized counting complexity has been very successful in the recent
years, see for instance [BHKK17, CM14, CDF+17, CDM17, JM17, Rot17].
Parameterized complexity provides a more fine-grained view on
$\mathsf{\\#P}$-complete problems. There are problems like counting vertex
covers of size $k$, which are fixed-parameter tractable, and others, which are
presumably harder, like the problem of counting cliques of size $k$. Beside
the classes $\mathsf{VP}$ and $\mathsf{VNP}$ (and subclasses of them), which
correspond to time bounded computation in the Boolean world, there have also
been definitions of algebraic classes that correspond to space bounded Boolean
computation, see [KP07b, KP07a, MR09]. However, we are not aware of any
parameterized classes in the algebraic world despite some algorithmic upper
bounds being known, see for instance [CMR01, FKL07].

###  1.1 Our Contribution

In this paper, we define a theory of parameterized algebraic complexity
classes. While some of the definitions are rather obvious modifications of the
Boolean ones and some of the basic theorems easily transfer from the Boolean
world to the algebraic world, some concepts have to be modified. For instance,
we cannot use projections to define hardness in general in the parameterized
world, since they can only decrease the degree. On the one hand, one could
choose the degree as a parameter, for instance, when computing the vertex
cover polynomial. On the other hand, one could have parameterized families
where the degree is always $n$, like the permanent on bounded genus graphs.
One cannot compare these families with projections, although both of them turn
out to be fixed parameter tractable. We could use c-reductions instead (which
are the analogue of Turing reductions). However, these seem too powerful. We
propose some intermediate concept, namely fpt-substitutions: We may replace
the variables of a polynomial by other polynomials that are computed by small
circuits (and not simply constants and variables like in the case of
projections). This mirrors what is done in parsimonious reductions: the input
is transformed by a polynomial time computable function but no post-processing
is allowed.

Our main technical contribution is the $\mathsf{VW}[1]$-completeness proof of
the parameterized clique polynomial. This proof turns out to be far more
complicated than in the Boolean world, since we are not counting satisfying
assignments to Boolean circuits but we are computing sums over algebraic
circuits. First we prove that one can combine two exponential sums into one
sum. While this is very easy in the case of $\mathsf{VNP}$, it turns out to be
quite complicated in the case of $\mathsf{VW}[1]$. Then we prove a normal form
for so-called weft 1 circuits, the defining circuits for $\mathsf{VW}[1]$. We
go on with proving that the components consisting of all monomials that depend
on a given number of variables of a polynomial computed by a weft 1 formula
can be written as a bounded exponential sum over so-called Boolean-arithmetic
expressions. We then show how to reduce such a sum to the clique problem.

In our final section, we study two polynomials based on cycle covers. The
first one consisting of one cycle of length $k$ and all other cycles being
self loops. The second is similar, but allows all other cycles to be a certain
constant. We prove that the first problem is $\mathsf{VW}[1]$ complete while
the second problem is hard for $\mathsf{VW}[t]$ for all $t$.

###  1.2 Motivation

It is an open problem in Boolean parameterized complexity theory, whether
$\mathsf{W}[t]=\mathsf{W}[t+1]$ or $\mathsf{\\#W}[t]=\mathsf{\\#W}[t+1]$
implies a collapse of the corresponding hierarchy. Here algebraic complexity
theory might shed a new light on these problems, since algebraic circuits are
much more structured than Boolean ones.

Additionally, we find the difference between the complexity of various
polynomials based on the permanent very interesting and worthy of future
studies.

We build the basic framework for the study of these questions in this paper.

##  2 Valiant’s Classes

We give a brief introduction to Valiant’s classes, for further information we
refer the reader to [Bür00a, Mah13]. Throughout the whole paper, $K$ will
denote the underlying ground field. An arithmetic circuit $C$ is an acyclic
directed graph such that every node has either indegree $0$ or indegree $2$.
Nodes with indegree $0$ are called input nodes and they are either labeled
with a constant from $K$ or with some variable. The other nodes are called
computation gates, they are either labeled with $+$ (addition gate) or $*$
(multiplication gate). Every gate computes a polynomial in the obvious way.
There is exactly one gate of outdegree $0$, the polynomial computed there is
the output of $C$. The size of a circuit is the number of edges in it. The
depth of a circuit is length of a longest path from an input node to the
output node. Later, we will also look at circuits in which the computation
gates can have arbitrary fan-in.

The objects that we study will be polynomials over $K$ in variables
$X_{1},X_{2},\dots$ (Occasionally, we will rename these variables to make the
presentation more readable.) We will denote $\\{X_{1},X_{2},\dots\\}$ by $X$.
The circuit complexity $C(f)$ of a polynomial $f$ is the size of a smallest
circuit computing $f$. We call a function $r\colon\mathbb{N}\to\mathbb{N}$ _p-
bounded_ if there is a polynomial $p$ such that $r(n)\leq p(n)$ for all $n$.

######  Definition 2.1.

A sequence of polynomials $(f_{n})\in K[X]$ is called a _p-family_ if for all
$n$,

  1. 1.

$f_{n}\in K[X_{1},\dots,X_{p(n)}]$ for some p-bounded function $p$ and

  2. 2.

$\deg f_{n}$ is p-bounded.

######  Definition 2.2.

The class $\mathsf{VP}$ consists of all p-families $(f_{n})$ such that
$C(f_{n})$ is p-bounded.

Let $f\in K[X]$ be a polynomial and $s\colon X\to K[X]$ be a mapping that maps
indeterminates to polynomials. Now, $s$ can be extended in a unique way to an
algebra endomorphism $K[X]\to K[X]$. We call $s$ a _substitution_. (Think of
the variables being replaced by polynomials.)

######  Definition 2.3.

  1. 1.

Let $f,g\in K[X]$. $f$ is called a _projection_ of $g$ if there is a
substitution $r\colon X\to X\cup K$ such that $f=r(g)$. We write $f\leq_{p}g$
in this case. (Since $g$ is a polynomial, it only depends on a finite number
of indeterminates. Therefore, we only need to specify a finite part of $r$.)

  2. 2.

Let $(f_{n})$ and $(g_{n})$ be p-families. $(f_{n})$ is a _p-projection_ of
$(g_{n})$ if there is a p-bounded function $q\colon\mathbb{N}\to\mathbb{N}$
such that $f_{n}\leq_{p}g_{q(n)}$. We write $(f_{n})\leq_{p}(g_{n})$.

Projections are very simple reductions. Therefore, we can also use them to
define hardness for “small” complexity classes like $\mathsf{VP}$. More
powerful are so-called _c-reductions_ , which are an analogue of Turing
reductions. c-reductions are strictly more powerful than p-projections [IM18].
Let $g$ be a polynomial in $s$ variables. A $g$-oracle gate is a gate of arity
$s$ that on input $t_{1},\dots,t_{s}$ outputs $g(t_{1},\dots,t_{s})$. The size
of such a gate is $s$. $C^{g}(f)$ denotes the minimum size of a circuit with
$g$-oracle gates that computes $f$. If $G$ is a set of polynomials, then
$C^{G}(f)$ is the minimum size of an arithmetic circuit that can use any
$g$-oracle gates for any $g\in G$.

######  Definition 2.4.

Let $(f_{n})$ and $(g_{n})$ be p-families. $(f_{n})$ is a _c-reduction_ of
$(g_{n})$ if there is a p-bounded function $q\colon\mathbb{N}\to\mathbb{N}$
such that $C^{G_{q(n)}}(f_{n})$ is p-bounded, where $G_{q(n)}=\\{g_{i}\mid
i\leq q(n)\\}$. We write $(f_{n})\leq_{c}(g_{n})$.

######  Definition 2.5.

A p-family $(f_{n})$ is in $\mathsf{VNP}$, if there are p-bounded functions
$p$ and $q$ and a sequence $(g_{n})\in\mathsf{VP}$ of polynomials $g_{n}\in
K[X_{1},\dots,X_{p(n)},Y_{1},\dots,Y_{q(n)}]$ such that

$f_{n}=\sum_{e\in\\{0,1\\}^{q(n)}}g_{n}(X_{1},\dots,X_{p(n)},e_{1},\dots,e_{q(n)}).$

$\mathsf{VP}$ and $\mathsf{VNP}$ are algebraic analogues of the classes
$\mathsf{P}$ and $\mathsf{\\#P}$ in the Boolean world. The permanent family
$(\operatorname{per}_{n})$ is complete for $\mathsf{VNP}$ and the problem of
computing the permanent of a given $\\{0,1\\}$-matrix is complete for
$\mathsf{\\#P}$ under p-projections.

##  3 Parameterized (Counting) Complexity

Parameterized counting complexity was introduced by Flum and Grohe [FG04]. We
give a short introduction to fixed parameterized counting complexity. For more
information on parameterized complexity, we refer the reader to [FG06, DF13].

######  Definition 3.1.

A _parameterized counting problem_ is a function
$F\colon\Sigma^{*}\times\mathbb{N}\rightarrow\mathbb{N}$.

The idea is that an input has two components $(x,k)$, $x\in\Sigma^{*}$ is the
instance and the parameter $k$ measures the “complexity” of the input.

######  Definition 3.2.

A parameterized counting problem is _fixed parameter tractable_ if there is an
algorithm computing $F(x,k)$ in time $f(k)\lvert x\rvert^{c}$ for some
computable function $f\colon\mathbb{N}\rightarrow\mathbb{N}$ and some constant
$c$. The class of all fixed parameter tractable counting problems is denoted
by $\mathsf{\\#FPT}$.

A parameterized counting problem is fixed-parameter tractable if the running
time is polynomial in the instance size. The “combinatorial explosion” is only
in the parameter $k$. In particular, the exponent of $n$ does not depend on
$k$. The classical example for a parameterized counting problem in
$\mathsf{\\#FPT}$ is the vertex cover problem: Given a graph $G$ and a natural
number $k$, count all vertex covers of $G$ of size $k$.

Fixed parameter tractable problems represent the “easy” problems in
parameterized complexity. An indication that a problem is not fixed parameter
tractable is that it is hard for the class $\mathsf{\\#W}[1]$. Reductions that
are used to define hardness are _parsimonious fpt-reductions_ : Such a
reduction maps an instance $(x,k)$ to an instance $(x^{\prime},k^{\prime})$
such that the value of the two instances is the same, the running time of the
reduction is $f(k)|x|^{c}$ for some computable function $f$ and a constant
$c$, and there is a computable function $g$ such that $k^{\prime}\leq g(k)$.
It is quite easy to see that the composition of two parsimonious fpt-
reductions is again a parsimonious fpt-reduction and that $\mathsf{\\#FPT}$ is
closed under parsimonious fpt-reductions.

We now define weft $t$ formulas inductively.333The term “weft” originates from
textile fabrication and has been used in Boolean parameterized complexity from
its very beginning.

######  Definition 3.3.

A _weft_ $0$ formula is a layered Boolean formula and the gates have fan-in
two (over the basis $\wedge$, $\vee$, and $\neg$). A weft $t$ formula is a
layered Boolean formula where the gates have fan-in two, except one layer of
gates that has unbounded fan-in. This formula has as inputs weft $t-1$
formulas.

Weft $t$ formulas have $t$ layers of unbounded fan-in gates, and all other
gate have bounded fan-in. Weft $t$ formulas are the defining machine model of
the $\mathsf{\\#W}[t]$ classes:

######  Definition 3.4.

The class $\mathsf{\\#W}[t]$ are all parameterized counting problems that are
reducible by parsimonious fpt-reductions to the following problem: Given a
weft t formula $C$ of constant depth and a parameter $k$, count all satisfying
assignments of $C$ that have exactly $k$ $1$s.

A classical example of a counting problem, that is
$\mathsf{\\#W}[1]$-complete, is counting cliques of size $k$ in a graph.
Clique is used as a major complete problem for $\mathsf{\\#W}[1]$ by Flum and
Grohe [FG04]. It is known that $\mathsf{P}=\mathsf{\\#P}$ implies
$\mathsf{\\#FPT}=\mathsf{\\#W}[1]$. Curticapean [Cur13] proves that counting
$k$-matchings, the parameterized analogue to the permanent, is
$\mathsf{\\#W}[1]$-hard (under fpt Turing reductions).

##  4 Parameterized Valiant’s Classes

We now define fixed-parameter variants of Valiant’s classes. Our families of
polynomials will now have two indices. They will be of the form $(p_{n,k})$.
Here, $n$ is the number of indeterminates and $k$ is the parameter.

######  Definition 4.1.

A parameterized p-family is a family $(p_{n,k})$ of polynomials such that

  1. 1.

$p_{n,k}\in K[X_{1},\dots,X_{q(n)}]$ for some p-bounded function $q$, and

  2. 2.

the degree of $p_{n,k}$ is p-bounded (as a function of $n+k$).

The most natural parameterization is by the degree: Let $(p_{n})$ be any
p-family then we get a parameterized family $(p_{n,k})$ by setting
$p_{n,k}=H_{k}(p_{n})$. Here $H_{k}(f)$ denotes the homogeneous part of degree
$k$ of some polynomial $f$.444I.e., the sum of all monomials of degree $k$
with their coefficients. Since $\deg(p_{n})$ is polynomially bounded,
$p_{n,k}$ is zero when $k$ is large enough. (This will usually be the case for
any parameterization.) More generally, we will also allow that
$p_{n,k}=H_{t(k)}(p_{n})$ for some function $t$ that solely depends on $k$.

Recall that a vertex cover $C$ of a graph $G=(V,E)$ is a subset of $V$ such
that for every edge $e\in E$ at least one endpoint is in $C$.

######  Example 4.2.

Let $\mathcal{G}=(G_{n})$ be a family of graphs such that $G_{n}$ has $n$
nodes. We will assume that the nodes of $G_{n}$ are $\\{1,\dots,n\\}$.

  1. 1.

The vertex cover family $(\operatorname{VC}_{n}^{\mathcal{G}})$ with respect
to $\mathcal{G}$ is defined as

$\operatorname{VC}_{n}^{\mathcal{G}}=\sum_{C\subseteq\\{1,\dots,n\\}}\prod_{i\in
C}X_{i}$

where the sum is taken over all vertex covers $C$ of $G_{n}$.

  2. 2.

The parameterized vertex cover family
$(\operatorname{VC}_{n,k}^{\mathcal{G}})$, with respect to $\mathcal{G}$, is
defined as

$\operatorname{VC}_{n,k}^{\mathcal{G}}=\sum_{{\begin{subarray}{c}C\subseteq\\{1,\dots,n\\}\\\
{\lvert C\rvert=k}\end{subarray}}}\prod_{i\in C}X_{i}$

where we now sum over all vertex covers of size $k$ of $G_{n}$. This is a
homogeneous polynomial of degree $k$. (We will call both families
$\operatorname{VC}^{\mathcal{G}}$. There is no danger of confusion, since we
mainly deal with the parameterized family.)

Every node has a label $X_{i}$ and for every vertex cover we enumerate (or
more precisely, sum up) its weight, which is the product of the labels of the
nodes in it. Above, every graph family defines a particular vertex cover
family. We can also define a unifying vertex cover family.

######  Example 4.3.

Let $E_{i,j},X_{i}$, $1\leq i,j\leq n$, $i<j$, be variables over some field
$K$. The _parameterized vertex cover polynomial_ of size $n$ is defined by

$\operatorname{VC}_{n,k}=\sum_{\begin{subarray}{c}C\subseteq\\{1,\dots,n\\}\\\
{\lvert C\rvert=k}\end{subarray}}\prod_{\begin{subarray}{c}i,j\notin C\\\
{i<j}\end{subarray}}(1-E_{i,j})\prod_{i\in C}X_{i}.$

The parameterized vertex cover family is defined as
$(\operatorname{VC}_{n,k})$.

If we set the variables $E_{i,j}$ to values $e_{i,j}\in\\{0,1\\}$ we get the
vertex cover polynomial of the graph given by the adjacency matrix
$(e_{i,j})$. The first product is $0$ if there is an uncovered edge. More
generally, if we take a family of graphs $\mathcal{G}=(G_{n})$ such that
$G_{n}$ has $n$ nodes and if we plug in the adjacency matrix of $G_{n}$ into
in each $\operatorname{VC}_{n,k}$ then we get the family
$(\operatorname{VC}^{\mathcal{G}}_{n,k})$.
$(\operatorname{VC}^{\mathcal{G}}_{n,k})$ is parameterized by the degree since
we have
$\operatorname{VC}^{\mathcal{G}}_{n,k}=H_{k}(\operatorname{VC}_{n}^{\mathcal{G}}$).
$(\operatorname{VC}_{n,k})$, however, is not parameterized by the degree as
$\operatorname{VC}_{n,k}$ contains monomials of degree polynomial in $n$
(independent of $k$).

Recall that a clique $C$ of a graph is a subset of the vertices such that for
every pair of nodes in $C$ there is an edge between them.

######  Example 4.4.

  1. 1.

Let $E_{i,j},X_{i}$, $1\leq i,j\leq n$, $i<j$, be variables over some field
$K$. The _clique polynomial_ of size $n$ is defined by

$\operatorname{Clique}_{n}=\sum_{C\subseteq\\{1,\dots,n\\}}\prod_{\begin{subarray}{c}i,j\in
C\\\ {i<j}\end{subarray}}E_{i,j}\prod_{i\in C}X_{i}.$

The clique family is defined as $(\operatorname{Clique}_{n})$.

  2. 2.

The parameterized clique family $(\operatorname{Clique}_{n,k})$ is defined by

$\operatorname{Clique}_{n,k}=\sum_{\begin{subarray}{c}C\subseteq\\{1,\dots,n\\}\\\
{\lvert C\rvert=k}\end{subarray}}\prod_{\begin{subarray}{c}i,j\in C\\\
{i<j}\end{subarray}}E_{i,j}\prod_{i\in C}X_{i}.$

(Again, we will call both families $\operatorname{Clique}$.)

If we set the variables $E_{i,j}$ to values $e_{i,j}\in\\{0,1\\}$, we get the
clique polynomial of the graph given by the adjacency matrix $(e_{i,j})$,
since the first product checks whether $C$ is a clique. For each clique, we
enumerate a monomial $\prod_{i\in C}X_{i}$. $X_{i}$ is the label of the node
$i$. $\operatorname{Clique}$ is a polynomial defined on edges and nodes. This
seems to be necessary, since the polynomial
$\sum_{C\subseteq\\{1,\dots,n\\}}\prod_{i\in
C}X_{i}=(1+X_{1})\cdots(1+X_{n})$, which is the “node-only” version of clique
polynomial of the complete graph, is easy to compute. Therefore, we cannot
expect that the “node-only” version of the clique family is hard for some
class.

Notice, that the parameterized clique family $(\operatorname{Clique}_{n,k})$
has variables standing in for vertices. These vertices seem to be necessary,
as in the counting world, counting the number of $k$ cliques and counting the
number of $k$-independent sets are tightly related. Namely, the number of
cliques is the number of independent sets on the complement graph. We want to
keep this relationship as the problem is an important member of
$\\#\mathsf{W}[1]$ and hence we incorporate the vertices.

$(\operatorname{Clique}_{n,k})$ is parameterized by the degree, since
$\operatorname{Clique}_{n,k}=H_{\binom{k}{2}+k}(\operatorname{Clique}_{n})$.
Here is another example, beside the general vertex cover family, of a family
that is parameterized by a different parameter:

######  Example 4.5.

Let $\mathcal{G}=(G_{n,k})$ be a family of bipartite graphs such that
$G_{n,k}$ has $n$ nodes on both sides and genus $k$,
$k\leq\lceil(n-2)^{2}/4\rceil$.555This is the genus of the $K_{n,n}$ [Rin65].
Let $A_{n,k}$ be the $n\times n$-matrix that has a variable $X_{i,j}$ in
position $(i,j)$ if there is an edge between $i$ and $j$ in $G_{n,k}$ and a
$0$ otherwise. The _$\mathcal{G}$ -parameterized permanent family_
$\operatorname{per}^{\mathcal{G}}=(\operatorname{per}_{n,k}^{\mathcal{G}})$ is
defined as
$\operatorname{per}_{n,k}^{\mathcal{G}}=\operatorname{per}(A_{i,j})$.

There is another natural way to parameterize the permanent:

######  Example 4.6.

Given a $k\times n$-matrix $X=(X_{i,j})$ with variables as entries, the
rectangular permanent is defined as

$\operatorname{rper}_{n,k}(X)=\sum_{\begin{subarray}{c}f\colon\\{1,\dots,k\\}\to\\{1,\dots,n\\}\\\
{\text{$f$ is injective}}\end{subarray}}\prod_{i=1}^{k}X_{i,f(i)}.$

When $k=n$ then this is the usual permanent. The _rectangular permanent
family_ is defined as $\operatorname{rper}=(\operatorname{rper}_{n,k})$.

We will give some more parameterizations of the permanent in section 8 where
we also prove some hardness results.

We now define fixed parameter variants of Valiant’s classes.

######  Definition 4.7.

  1. 1.

A parameterized p-family $(p_{n,k})$ is in the class $\mathsf{VFPT}$ if
$C(p_{n,k})$ is bounded by $f(k)p(n)$ for some p-bounded function $p$ and some
arbitrary function $f\colon\mathbb{N}\to\mathbb{N}$.666$f$ need not be
computable, since Valiant’s model is nonuniform.

  2. 2.

The subclass of $\mathsf{VFPT}$ of all parameterized p-families that are
parameterized by the degree is denoted by $\mathsf{VFPT_{\mathit{deg}}}$.

We will also say above that $C(p_{n,k})$ is _fpt-bounded_. We will see in one
of the next sections that the vertex cover family and the bounded genus
permanent are in $\mathsf{VFPT}$. We will say that a family of circuits
$(C_{n},k)$ has _fpt size_ if the size is bounded by $f(k)p(n)$ for some
function $f\colon\mathbb{N}\to\mathbb{N}$ and p-bounded function $p$.

######  Definition 4.8.

A parameterized p-family $f=(f_{n,k})$ is an _fpt-projection_ of another
parameterized p-family $g=(g_{n,k})$ if there are functions
$r,s,t\colon\mathbb{N}\to\mathbb{N}$ such that $r$ is p-bounded and $f_{n,k}$
is a projection of $g_{r(n)s(k),k^{\prime}}$ for some $k^{\prime}\leq
t(k)$.777$k^{\prime}$ might depend on $n$, but its size is bounded by a
function in $k$. There are examples in the Boolean world, where this
dependence on $n$ is used. We write $f\leq^{\mathit{fpt}}_{p}g$.

######  Lemma 4.9.

If $f\in\mathsf{VFPT}$ (or $\mathsf{VFPT_{\mathit{deg}}}$) and
$g\leq^{\mathit{fpt}}_{p}f$, then $g\in\mathsf{VFPT}$ (or
$\mathsf{VFPT_{\mathit{deg}}}$, respectively).

###### Proof.

The proof essentially follows from the fact that fpt-bounded functions are
closed under composition. Let the functions $r,s,t$ be as in the definition
above. We know that for all $n,k$,
$f_{n,k}(X_{1},\dots,X_{p(n)})=g_{r(n)s(k),k^{\prime}}(Y_{1},\dots,Y_{q(r(n)s(k))})$
where each $Y_{i}\in K\cup\\{X_{1},\dots,X_{p(n)}\\}$. Since
$(g_{n,k})\in\mathsf{VFPT}$, $C(g_{n,k})\leq u(k)m(n)$ for some p-bounded $m$
and an arbitrary function $u$. Then $C(f_{n,k})\leq
u(k^{\prime})m(r(n)s(k))\leq u(t(k))m(r(n)s(k))$. Thus $C(f_{n,k})$ is fpt-
bounded. (Note that $m(r(n)s(k))$ can be written as a product of a polynomial
in $n$ and a function depending only on $k$, since $m$ is p-bounded.) Notice,
that in the case of $\mathsf{VFPT_{\mathit{deg}}}$ the same argument holds as
the projection can only lower the degree. ∎

######  Lemma 4.10.

$\leq^{\mathit{fpt}}_{p}$ is transitive.

###### Proof.

This is essentially the same proof as for p-projections, but instead of using
that p-bounded functions are closed under composition, we use that fpt-bounded
functions are closed under composition. Let
$f\leq^{\mathit{fpt}}_{p}g\leq^{\mathit{fpt}}_{p}h$. For all $n,k$

$f_{n,k}(X_{1},\dots,X_{p_{f}(n)})=g_{r(n)s(k),k^{\prime}}(Y_{1},\ldots,Y_{p_{g}(r(n)s(k))})$

and

$g_{n,k}(X_{1},\dots,X_{p_{g}(n)})=h_{r^{\prime}(n)s^{\prime}(k),k^{\prime\prime}}(Y^{\prime}_{1},\dots,Y^{\prime}_{p_{h}(r^{\prime}(n)s^{\prime}(k))})$

with p-bounded functions $p_{f}$, $p_{g}$, $p_{h}$, $r$, and $r^{\prime}$,
$k^{\prime}\leq t(k)$ and $k^{\prime\prime}\leq t^{\prime}(k)$ for some
arbitrary functions $t$ and $t^{\prime}$, and the $Y_{i}$ and $Y^{\prime}_{i}$
being constants or variables. Now the transitivity is obvious, as we can write
$f_{n,k}$ as a projection of
$h_{r^{\prime}(r(n)s(k))s^{\prime}(k^{\prime}),k^{\prime\prime}}$ by
substituting the $Y_{i}$ into the $Y^{\prime}_{i}$, where
$k^{\prime\prime}\leq t^{\prime}(t(k))$. ∎

One can define a notion of completeness. In the case of fpt-projections, the
degree of the polynomial is the only meaningful parameter to consider: The
permanent family on bounded genus graphs $\operatorname{per}^{\mathcal{G}}$ is
in $\mathsf{VFPT}$ and so is (a variant of) the vertex cover family
$\operatorname{VC}$. However, every polynomial in the permanent family has
degree equal to the number of nodes in the graph (independent of the genus)
whereas the degree of the vertex cover polynomial depends on the degree. If a
polynomial $p$ is a projection of $q$, then $\deg p\leq\deg q$. Therefore,
$\operatorname{per}^{\mathcal{G}}$ cannot be an fpt-projection of
$\operatorname{VC}$. Now we can call a parameterized family $f$
_$\mathsf{VFPT_{\mathit{deg}}}$ -complete_ (under fpt-projections), if it is
in $\mathsf{VFPT_{\mathit{deg}}}$ and for all
$g\in\mathsf{VFPT_{\mathit{deg}}}$, $g\leq^{\mathit{fpt}}_{p}f$.

For other parameters, we need a stronger notion of reduction. There are the
so-called c-reductions, see [Bür00a], which are the analogue of Turing
reductions in Valiant’s world. This is the strongest kind of reduction one
could use. However, the p-projections in Valiant’s world seem to be weaker
than parsimonious polynomial-time reductions in the Boolean world. Therefore,
we propose an intermediate concept, which models parsimonious reductions in
the algebraic world. In parsimonious reductions, the input instance is
transformed by a polynomial time or fpt computable reduction, then the
function we reduce to is evaluated, and the result that we get shall be the
value of our given function evaluated at the original instance.

In the algebraic world, this can be modeled as follows: We call a p-family
$f=(f_{n})$ with $f_{n}\in K[X_{1},\dots,X_{p(n)}]$ a _p-substitution_ of a
p-family $g=(g_{n})$ with $g_{n}\in K[X_{1},\dots,X_{q(n)}]$ if there is a
p-bounded function $r$, and for all $n$, there are $h_{1},\dots,h_{q(r(n))}$
such that $f_{n}=g_{r(n)}(h_{1},\dots,h_{q(r(n))})$ and $\deg(h_{i})$ as well
as $C(h_{i})$ is p-bounded for all $i$. We write $f\leq_{s}g$. Compared to a
projection, we are now allowed to substitute polynomials of p-bounded
complexity. We have that $\leq_{s}$ is transitive and that $p\leq_{s}q$ and
$q\in\mathsf{VP}$ implies $p\in\mathsf{VP}$.

The parameterized analogue is defined as follows.

######  Definition 4.11.

A parameterized p-family $f=(f_{n,k})$ with $f_{n,k}\in
K[X_{1},\dots,X_{p(n)}]$ is an _fpt-substitution_ of another parameterized
p-family $g=(g_{n,k})$ with $g_{n,k}\in K[X_{1},\dots,X_{q(n)}]$ if there are
functions $r,s,t\colon\mathbb{N}\to\mathbb{N}$ such that for all $n,k$, $r$ is
p-bounded and there exists polynomials $h_{1}$,$\dots$,$h_{q(r(n)s(k))}$ $\in
K[X_{1},\dots,X_{p(n)}]$ such that

$f_{n,k}=g_{r(n)s(k),k^{\prime}}(h_{1},\dots,h_{q(r(n)s(k))})$

for some $k^{\prime}\leq t(k)$ and $\deg(h_{i})$ as well as $C(h_{i})$ is fpt-
bounded (with respect to $n$ and $k$) for all $i$. We write
$f\leq^{\mathit{fpt}}_{s}g$.

######  Lemma 4.12.

If $f\in\mathsf{VFPT}$ and $g\leq^{\mathit{fpt}}_{s}f$, then
$g\in\mathsf{VFPT}$. ∎

######  Lemma 4.13.

$\leq^{\mathit{fpt}}_{s}$ is transitive. ∎

To define an algebraic analogue of $\mathsf{\\#W}[t]$, we study unbounded fan-
in arithmetic circuits. These circuits have multiplication and addition gates
of arbitrary fan-in. A gate with fan-in $2$ will be called a gate of bounded
fan-in, any other gate is a gate of unbounded fan-in. (Instead of $2$, we can
fix any other bound $b$, and we will do this in the next sections to make the
presentation more convenient.)

######  Definition 4.14.

Let $C$ be an arithmetic circuit. The _weft_ of $C$ is the maximum number of
unbounded fan-in gates on any path from a leaf to the root.

For $s,k\in\mathbb{N}$, $\genfrac{\langle}{\rangle}{0.0pt}{}{s}{k}$ denotes
the set of all $\\{0,1\\}$-vectors of length $s$ having exactly $k$ $1$s.

######  Definition 4.15.

  1. 1.

A parameterized p-family $(f_{n,k})$ is in $\mathsf{VW}[t]$, if there is a
p-family $(g_{n})$ of polynomials $g_{n}\in
K[X_{1},\dots,X_{p(n)},Y_{1},\dots,Y_{q(n)}]$ with p-bounded $p$ and $q$ such
that $g_{n}$ is computed by a constant depth unbounded fan-in circuit of weft
$\leq t$ and polynomial size and

$(f_{n,k})\leq^{\mathit{fpt}}_{s}\Big{(}\sum_{e\in\genfrac{\langle}{\rangle}{0.0pt}{}{q(n)}{k}}g_{n}(X_{1},\dots,X_{p(n)},e_{1},\dots,e_{q(n)})\,\Big{)}.$
(1)

  2. 2.

$\mathsf{VW_{\mathit{deg}}}[t]$ is the subset of all families in
$\mathsf{VW}[t]$, that have the degree as the parameter.

In essence, we emulate the Boolean $\\#\mathsf{W}[t]$ definition. Instead of
Boolean circuits of weft $t$ we take an arithmetic circuit and instead of
counting the number of assignments, we sum over all assignments. In addition,
we only count the assignments that have weight $k$ by adjusting the vectors we
sum over, namely to $\\{0,1\\}$-vectors with exactly $k$ ones. While in the
Boolean setting the closure is taken with respect to parsimonious fpt-
reductions, in the arithmetic setting, we take fpt-substitutions. Hence, our
definition seems to be the most appropriate analogue.

The clique family is in $\mathsf{VW}[1]$, since we can write it as

$\operatorname{Clique}_{n,k}=\sum_{v\in\genfrac{\langle}{\rangle}{0.0pt}{}{n}{k}}\prod_{\begin{subarray}{c}i,j=1\\\
{i<j}\end{subarray}}^{n}(E_{i,j}v_{i}v_{j}+1-v_{i}v_{j})\prod_{i=1}^{n}(X_{i}v_{i}+1-v_{i}).$

This formula has weft 1, since there are two unbounded product gates and none
is a predecessor of the other. We replace the product over all $C$ by a
product over all vertices and use the $v$-vectors to switch variables on and
off.

Like in the Boolean case, we will show that the parameterized clique family is
complete for the class $\mathsf{VW}[1]$ (albeit for a stronger notion of
reductions, namely fpt-c-reductions). It turns out that this proof is far more
complicated than in the Boolean setting, since our circuits can compute
arbitrary polynomials and not only Boolean values. Furthermore, multiplication
and addition cannot be reduced to each other since there is no analog of de
Morgan’s law.

######  Definition 4.16.

Let $f=(f_{n,k})$ and $g=(g_{n,k})$ be parameterized p-families. $f$ _fpt-c-
reduces_ to $g$ if there is a p-bounded function
$q\colon\mathbb{N}\to\mathbb{N}$ and functions
$s,t\colon\mathbb{N}\to\mathbb{N}$ such that $C^{G_{q(n)s(k),t(k)}}(f_{n,k})$
is fpt-bounded, where $G_{q(n)s(k),t(k)}=\\{g_{i,j}\mid i\leq
q(n)s(k),\enspace j\leq t(k)\\}$. We write $f\leq^{\mathit{fpt}}_{c}g$.

The following two lemmas are proved like for $\leq_{c}$ and $\mathsf{VP}$. We
replace oracle gates by circuits and use the fact that fpt-bounded functions
are closed under composition.

######  Lemma 4.17.

If $f\in\mathsf{VFPT}$ and $g\leq^{\mathit{fpt}}_{c}f$, then
$g\in\mathsf{VFPT}$. ∎

######  Lemma 4.18.

$\leq^{\mathit{fpt}}_{c}$ is transitive. ∎

So we have two different notions to define $\mathsf{\\#W}[t]$-hardness.
Presumably, they are different, see [IM18].

##  5 $\mathsf{VFPT}$

######  Theorem 5.1.

For every family of graphs $\mathcal{G}=(G_{n})$, where $G_{n}$ has $n$ nodes,
$\operatorname{VC}_{n,k}^{\mathcal{G}}$ is in $\mathsf{VFPT_{\mathit{deg}}}$.

###### Proof.

Given $G=(V,E)$ with $V=\\{1,\dots,n\\}$ and a parameter $k$, we work in the
same way as the classical FPT algorithm. We take an arbitrary order of edges.
For every edge, we branch on which vertex we add to our cover and recurse. We
define for an edge set $E_{\setminus\\{v\\}}$ to denote the set
$\\{(u,u^{\prime})\in E\mid u\neq v\text{ and }u^{\prime}\neq v\\}$. Let
$P(G,k)$ denote the $k$-vertex cover polynomial of $G$. We write a recursive
formula for $P(G,k)$:

$P(G,k)=\begin{cases}1&\text{if $k=0$ and $E=\emptyset$},\\\ 0&\text{if $k=0$,
$E\neq\emptyset$},\\\ \sum_{i_{1}<\dots<i_{k}\in V}X_{i_{1}}\cdots
X_{i_{k}}&\text{if $k\neq 0$, $E=\emptyset$},\\\ \begin{aligned} &X_{u}\cdot
P((V\setminus\\{u\\},E_{\setminus\\{u\\}}),k-1)\\\
&\qquad+X_{v}P((V\setminus\\{v\\},E_{\setminus\\{v\\}}),k-1)\\\ &\qquad-
X_{u}X_{v}P((V\setminus\\{u,v\\},E_{\setminus\\{u,v\\}}),k-2)\end{aligned}&\text{otherwise.}\end{cases}$

The first line of the above recursive definition means that the vertex cover
polynomial of the empty graph is $1$. If there are edges left after $k$
recursive steps, we remove this computation subtree by multiplying it with
zero (second line). If the there are no edges, then the vertex cover
polynomial is the $k$th elementary symmetric polynomial on the vertex set $V$
(third line). Finally, we branch on a chosen edge $e=\\{u,v\\}$ in the fourth
line: At least one of the two nodes $u$ and $v$ has to cover the chosen edge.
We subtract the third term, since the case when both $u$ and $v$ cover the
edge is counted twice by the first two terms. It is easy to see that we always
get the same polynomial independent of the ordering of the edges. The number
of operations and hence the size of the circuit is bounded by $T(n,k)\leq
3T(n,k-1)+O(1)$ plus $\operatorname{poly}(n)$ for computing the elementary
symmetric polynomial in the third case.888The polynomial is just the
homogeneous components of $t$ of degree $n-k$ in $(t+X_{1})\cdots(t+X_{n})$.
Thus $T(n,k)$ is fpt-bounded. ∎

######  Remark 5.1.

It is unlikely that the general family $\operatorname{VC}_{n,k}$ is in
$\mathsf{VFPT}$. Take any graph $G=(V,E)$ on $n$ nodes and $m$ edges and
compute $\operatorname{VC}_{n,k}$ on this graph. Now, for $i<j$, we set

$E_{i,j}=\begin{cases}1-S&\text{if $\\{i,j\\}\in E$},\\\
0&\text{otherwise},\end{cases}$

and $X_{i}=T$ for all $i$. Then we get a bivariate polynomial. This polynomial
contains a monomial $S^{i}T^{j}$ iff there is a vertex cover of size $j$ in
$G$ not covering $i$ edges, or, equivalently, covering $m-i$ edges. Note that
since the polynomial is now bivariate, we can easily compute its coefficients
using interpolation. While the (Boolean decision version of) vertex cover is
in $\mathsf{FPT}$, it turns out [GNW07] that the more general question whether
there is a set of nodes of size $k$ covering at least $t$ edges is
$\mathsf{W}[1]$-hard (with parameter $k$). Therefore, it seems to be unlikely
that $\operatorname{VC}_{n,k}$ has circuits of fpt size.

Mahajan and Saurabh [MS16] define another variant of the vertex cover
polynomial. We multiply each cover by a product over the uncovered edges. They
multiply by a product over the covered edges. Both polynomials are essentially
equivalently, one can turn one into the other by dividing through the product
over all edges, doing a variables transform, and removing divisions.

The _sun graph_ $S_{n,k}=(V,E)$ on $n$ nodes is defined as follows: The first
$2k$ nodes form a clique. And every other node is connected to the nodes
$1,\dots,2k$, but to no other nodes, that is, the nodes $2k+1,\dots,n$ form an
independent set. Every graph $G$ with $n$ nodes that contains a vertex cover
of size $k$ is a subgraph of $S_{n,k}$. To see this, we compute a maximum
matching $M$ in $G$. This matching $M$ has size at most $k$, since at least
one endpoint of each edge in $M$ has to be in a vertex cover. There cannot be
any edge between two nodes that are not endpoints of an edge in $M$, since $M$
is maximum. Therefore, all nodes not in $M$ form an independent set. We map
the nodes in $M$ to the nodes $1,\dots,2k$ in $S_{n,k}$ and all other nodes to
the nodes $2k+1,\dots,n$.

We define $\operatorname{VC}^{s}_{n,k}$ like $\operatorname{VC}_{n,k}$ but on
the graph $S_{n,k}$ instead of $K_{n}$. The difference to $\operatorname{VC}$
is, that we now have some idea where the vertex cover is located (like it is
in the Boolean case where we can find a potential set for instance by
computing a maximum matching). Therefore, we can obtain:

######  Theorem 5.2.

$\operatorname{VC}^{s}\in\mathsf{VFPT}$.

###### Proof.

Let $C\subseteq\\{1,\dots,2k\\}$ with $\kappa\coloneqq\lvert C\rvert\leq k$.
The contribution to $\operatorname{VC}^{s}_{n,k}$ of $C$ is

$\prod_{\begin{subarray}{c}i,j\in\\{1,\dots,2k\\}\setminus C\\\
{i<j}\end{subarray}}(1-E_{i,j})\prod_{i\in C}X_{i}.$

To the set $C$, we can add $k-\kappa$ nodes from $\\{2k+1,\dots,n\\}$.
Consider the product

$\prod_{j=2k+1}^{n}\left(X_{j}+\prod_{i\notin C}(1-E_{i,j})\right).$

We go over all nodes in $\\{2k+1,\dots,n\\}$. For each node $j$, we either add
it to the cover or the edges incident with $j$ are uncovered unless they are
covered by the other node $i\in\\{1,\dots,2k\\}$. The homogeneous component of
degree $k-\kappa$ in the $X$-variables is the contribution to
$\operatorname{VC}^{s}_{n,k}$ by the outer nodes. Altogether, we have

$\operatorname{VC}^{s}_{n,k}=\sum_{\begin{subarray}{c}C\subseteq\\{1,\dots,2k\\}\\\
{\lvert C\rvert\leq
k}\end{subarray}}\left(\prod_{\begin{subarray}{c}i,j\in\\{1,\dots,2k\\}\setminus
C\\\ {i<j}\end{subarray}}(1-E_{i,j})\prod_{i\in C}X_{i}\right)\cdot
H_{k-\lvert C\rvert,X}\left(\prod_{j=2k+1}^{n}\left(X_{j}+\prod_{i\notin
C}(1-E_{i,j})\right)\right).$

Here $H_{k-\lvert C\rvert,X}$ denotes the homogeneous components of degree
$k-\lvert C\rvert$ in the $X$-variables. The number of summands is bounded by
a function $k$ and each summand can be computed by a polynomial sized circuit.
Thus $\operatorname{VC}^{s}_{n,k}\in\mathsf{VFPT}$. ∎

Both parameterized permanent families turn out to be fixed parameter
tractable.

######  Theorem 5.3.

For every family of bipartite graphs $\mathcal{G}=(G_{n,k})$ such that
$G_{n,k}$ has $n$ nodes and genus $k$, $\operatorname{per}^{\mathcal{G}}$ is
in $\mathsf{VFPT}$.

###### Proof.

Galluccio and Loebl [GL99] prove that the permanent of a bipartite graph with
genus $k$ can we written as a linear combination of $4^{k}$ determinants of
$n\times n$-matrices whose entries are linear forms. Since the determinant has
polynomial size circuits, the claim follows. ∎

######  Theorem 5.4.

$\operatorname{rper}\in\mathsf{VFPT}$.

###### Proof.

Vassilevska and Williams [VW09] construct an arithmetic circuit for
$\operatorname{per}_{n,k}$ of size $O(k2^{k}n^{3})$. ∎

Kernelization is an important concept in parameterized complexity. In the
algebraic setting, $\mathsf{VFPT}$ can also be characterized by kernels of
size $f(k)$.

###  5.1 Kernelization

In the Boolean world, a _kernelization_ is a special kind of reduction. Given
a parameterized decision problem $L:\Sigma^{*}\times\mathbb{N}\to\\{0,1\\}$, a
kernelization is a polynomial time computable mapping (reduction)
$r\colon\Sigma^{*}\times\mathbb{N}\to\Sigma^{*}\times\mathbb{N}$ such that

  * •

$(x,k)\in L$ $\iff$ $r(x,k)\eqqcolon(x^{\prime},k^{\prime})\in L$,

  * •

$\lvert x^{\prime}\rvert$ is bounded by a computable function in $k$ and
$k^{\prime}$ is bounded by a computable function in $k$.

So in polynomial time, $x$ is reduced to an instance $x^{\prime}$ the size of
which only depends on $k$. $x^{\prime}$ can be solved using brute-force and
$x^{\prime}$ is often called the problem kernel. It is know that a decision
problem is in $\mathsf{FPT}$ if and only if it is decidable and admits a
kernelization.

Kernelizations for counting problems or enumeration problems are not well
understood. Consider the vertex cover problem: A graph with $n$ nodes can have
a number of vertex covers that depends on $n$, but a kernel can only have a
number of vertex covers that depends solely on $k$. Therefore, parsimonious
reductions cannot work. See [Thu07] for some work on counting kernels and
[CMM+13] for a definition of enumeration kernels.

######  Definition 5.5.

Let $(f_{n,k})$ be a parameterized $p$-family such that $f_{n,k}\in
K[X_{1},\dots,X_{p(n)}]$. A kernelization consists of functions
$r\colon\mathbb{N}^{2}\to\mathbb{N}$ and $s,t\colon\mathbb{N}\to\mathbb{N}$
such that for all $n$ and $k$, $r(n,k)\leq s(k)$ and there are circuits
$C_{n,k,i}$ of size polynomial in $n$ computing polynomials $q_{n,k,i}$,
$1\leq i\leq p(r(n,k))$, and there is a $k^{\prime}\leq s(k)$ such that

$f_{n,k}(X_{1},\dots,X_{p(n)})=f_{r(n,k),k^{\prime}}(q_{n,k,1},\dots,q_{n,k,p(r(n,k))}).$
(2)

Essentially, this definition means that every $f_{n,k}$ is a p-substitution of
some $f_{n^{\prime},k^{\prime}}$ and $n^{\prime}$ and $k^{\prime}$ are both
bounded by a function in $k$.

We can also prove a general theorem similar to the Boolean setting:

######  Theorem 5.6.

Let $f$ be a parameterized p-family.

  1. 1.

If $f$ admits a kernelization, then $f\in\mathsf{VFPT}$.

  2. 2.

If $f\in\mathsf{VFPT}$ and there are $n_{0}$ and $k_{0}$ such that
$f_{n_{0},k_{0}}$ is linear in some variable $X_{i}$, then $f$ admits a
kernelization.

###### Proof.

For the first item, assume we are given $n$ and $k$ and let $r$, $s$, and $t$
and $q_{n,k,i}$, $1\leq i\leq p(r(n,k))$ as well as $k^{\prime}$ as in
definition 5.5. The number of variables and the degree of
$f_{r(n,k),k^{\prime}}$ only depends on $k$. Therefore, its circuit complexity
is also bounded by a function of $k$, since we can simply take the trivial
circuit that computes all monomials and sums them up. Since the $q_{n,k,i}$
have polynomial size circuits, $C(f_{n,k})$ is fpt-bounded by (2).

For the second item, let $C(f_{n,k})$ be bounded by $u(k)m(n)$ for some
p-bounded function $m$. We can assume that $m(n)\geq n$ for all $n$. By
substituting appropriate constants for all other variables, we get that
$X_{i}$ is a projection of $f_{n_{0},k_{0}}$. Now given $n$ and $k$, if
$m(n)\leq u(k)$, then $r(n,k)=n$ and $k^{\prime}=k$. Note that now
$r(n,k)=n\leq u(k)$. If $u(k)<m(n)$, then we can compute $f_{n,k}$ by a
circuit of size $u(k)m(n)\leq m^{2}(n)$, which is polynomial. Since $f_{n,k}$
trivially is a substitution of $X_{1}$, we can set $r(n,k)=n_{0}$ and
$k^{\prime}=k_{0}$, which are both constants. ∎

While the proof feels somewhat unsatisfactory, we remark that the proof in the
Boolean case works along the same lines. We can remove the degree condition in
the second item of theorem 5.6 by relaxing the notion of kernel and allowing
some postprocessing. In the general case, $X_{i}$ will have degree $d$ and we
only get that $X_{i}^{d}$ is a projection of $f_{n_{0},k_{0}}$ and therefore,
we compute $f_{n,k}^{d}$ in the second case of the case distinction. It is
however known that when a circuit of size $s$ computes some power $f^{d}$ of a
polynomial $f$, then there is a circuit of size polynomial in $s$ that
computes $f$ by using Newton iteration [BK78] (see [BES17] for an explicit
construction).

##  6 The $\mathsf{VW}$-hierarchy

We start with proving some basic facts about the $\mathsf{VW}[t]$ classes, in
analogy to the Boolean world.

######  Lemma 6.1.

$\mathsf{VFPT}=\mathsf{VW}[0]$ and
$\mathsf{VFPT_{\mathit{deg}}}=\mathsf{VW_{\mathit{deg}}}[0]$.

###### Proof.

The proof is obvious, since $\mathsf{VW}[0]$ and
$\mathsf{VW_{\mathit{deg}}}[0]$ are defined as the closure under fpt-
substitutions, so we can compute problems in $\mathsf{VFPT}$ simply by using
the reduction. ∎

The following lemma is obvious.

######  Lemma 6.2.

For every $t$, $\mathsf{VW}[t]\subseteq\mathsf{VW}[t+1]$ and
$\mathsf{VW_{\mathit{deg}}}[t]\subseteq\mathsf{VW_{\mathit{deg}}}[t+1]$.

We call a parameterized p-family $f$ _$\mathsf{VW}[t]$ -hard_ (under fpt-
substitutions), if for all $g\in\mathsf{VW}[t]$, $g\leq^{\mathit{fpt}}_{s}f$.
$f$ is called _$\mathsf{VW}[t]$ -complete_ (under fpt-substitutions) if in
addition, $f\in\mathsf{VW}[t]$. If the same way, we can also define hardness
and completeness under fpt-c-reductions.

For the classes $\mathsf{VW_{\mathit{deg}}}[t]$, it is reasonable to study
hardness and completeness under fpt-projections. We call a parameterized
p-family $f$ _$\mathsf{VW_{\mathit{deg}}}[t]$ -hard_ (under fpt-projections),
if for all $g\in\mathsf{VW}[t]$, $g\leq^{\mathit{fpt}}_{p}f$. $f$ is called
_$\mathsf{VW_{\mathit{deg}}}[t]$ -complete_ (under fpt-projections) if in
addition, $f\in\mathsf{VW}[t]$.

######  Lemma 6.3.

If $f$ is $\mathsf{VW}[t+1]$-complete under fpt-substitutions and
$f\in\mathsf{VW}[t]$, then $\mathsf{VW}[t]=\mathsf{VW}[t+1]$. In the same way,
if $f$ is $\mathsf{VW_{\mathit{deg}}}[t+1]$-complete under fpt-substitutions
or fpt-projections and $f\in\mathsf{VW_{\mathit{deg}}}[t]$, then
$\mathsf{VW_{\mathit{deg}}}[t]=\mathsf{VW_{\mathit{deg}}}[t+1]$.

###### Proof.

Let $g\in\mathsf{VW}[t+1]$ be arbitrary. By the completeness of $f$,
$g\leq^{\mathit{fpt}}_{s}f$. Since $f\in\mathsf{VW}[t]$ and
$\leq^{\mathit{fpt}}_{s}$ is transitive, $g\in\mathsf{VW}[t]$. The same proof
works for $\mathsf{VW_{\mathit{deg}}}[t]$. ∎

It is open in the Boolean case whether $\mathsf{W}[t]=\mathsf{W}[t+1]$ or
$\mathsf{\\#W}[t]=\mathsf{\\#W}[t+1]$ implies a collapse of the corresponding
hierarchy. Maybe the algebraic setting can provide more insights.

######  Theorem 6.4.

If $\mathsf{VFPT}\not=\mathsf{VW}[1]$ then $\mathsf{VP}\not=\mathsf{VNP}$.

###### Proof.

Assume that $\mathsf{VP}=\mathsf{VNP}$. Then the clique family
$(\operatorname{Clique}_{n})$ has polynomial sized circuits, since it is in
$\mathsf{VNP}$. It follows that also the parameterized clique family
$(\operatorname{Clique}_{n,k})$ has polynomial sized circuits. To see this, we
can replace the variables $X_{i}$ by $TX_{i}$ for some new variable $T$. View
the resulting polynomial as a univariate polynomial in $T$ with coefficients
being polynomials in the original variables. The coefficient of $T^{k}$ is
$\operatorname{Clique}_{n,k}$. Since interpolation can be done with polynomial
circuits, $(\operatorname{Clique}_{n,k})$ has polynomial sized circuits. We
will prove that $\operatorname{Clique}$ is $\mathsf{VW}[1]$ complete under
fpt-c-reductions (theorem 7.22). Therefore, every family in $\mathsf{VW}[1]$
has circuits of fpt size. This proves the theorem. ∎

If one takes the defining problems for $\mathsf{VW}[t]$ (sums over $\\{0,1\\}$
vectors with $k$ $1$s of weft $t$ circuits) instead of clique, one can prove
the same theorem for arbitrary classes $\mathsf{VW}[t]$ in place of
$\mathsf{VW}[1]$. The proof only get technically a little more complicated.

##  7 Hardness of Clique

Our main technical result is the $\mathsf{VW}[1]$-hardness of
$\operatorname{Clique}$. The proof is technically much more intricate than in
the Boolean setting. We will give a short outline.

  * •

First, we prove as a technical tool that two bounded exponential sums over a
weft $t$ circuit can be expressed by one exponential sum over a (different)
weft $t$ circuit. In the case of $\mathsf{VNP}$, a similar proof is easy:
Instead of summing over bit vectors of length $p$ and then of length $q$, we
can sum over bit vectors of length $p+q$ instead. If the number of ones is
however bounded, this does not work easily anymore. It turns out that for the
most interesting class $\mathsf{VW}[1]$ of the $\mathsf{VW}$-hierarchy, the
construction is astonishingly complicated. See section 7.1.

  * •

Next, we prove a normal form for weft $1$ circuits. Every weft $1$ circuit can
be replaced by an equivalent weft $1$ circuit that has five layers: The first
layer is a bounded summation gate, the second layer consist of bounded
multiplication gates, the third layer is the only layer of unbounded gates,
the fourth layer again consists of bounded addition gates and the fifth layer
of bounded multiplication gates. See section 7.2.

  * •

Then we introduce _Boolean-arithmetic formulas_ : A Boolean-arithmetic formula
is a formula of the form

$B(X_{1},\dots,X_{n})\cdot\prod_{i=1}^{n}(R_{i}X_{i}+1-X_{i})$

where $B$ is an arithmetization of some Boolean formula and the $R_{i}$ some
polynomial or even rational function (over a different set of variables). For
each satisfying $\\{0,1\\}$-assignment $e$ to $B$, that is, $B(e)=1$, the
right hand side produces one product and the $e_{i}$ (assigned to the $X_{i}$
variables) switch the factors $R_{i}$ on or off. For a polynomial $f$, the
monomials of support size $k$ are all monomials that depend on exactly $k$
variables. The sum of all these monomials is denoted by $S_{k}(f)$. A central
result for the hardness proof is that when $f$ is computed by a circuit of
weft $1$, then we can write $S_{k}(f)$ as a bounded sum over a weft $1$
Boolean arithmetic expression, that is,
$S_{k}(f)=\sum_{e\in\genfrac{\langle}{\rangle}{0.0pt}{}{p(n,k)}{q(k)}}\mathcal{B}(e)\cdot\prod_{i=1}^{p(n,k)}(R_{i}e_{i}+1-e_{i})$.
See section 7.3.

  * •

Finally, we prove in section 7.4, that $\operatorname{Clique}$ is
$\mathsf{VW}[1]$-complete under fpt-c-reductions (or under fpt-substitutions
that allow rational expressions). Given some bounded sum over a polynomial
$g_{n}(X_{1},\dots,X_{p},Y_{1}\dots,Y_{q})$ computed by a weft 1 circuit, we
view $g_{n}$ as a polynomial over the $Y$-variables, the coefficients of which
are polynomials in the $X$-variables. Then $S_{0}(g),\dots,S_{k}(g)$ are the
parts of $g_{n}$ that contribute to the sum when summing over all bit vectors
with $k$ ones. We can write this as a bounded sum over a Boolean arithmetic
formula. The concept of Boolean arithmetic formulas allows us to reuse parts
of the Boolean hardness proof.

Note that once we have the $\mathsf{VW}[1]$-hardness of
$\operatorname{Clique}$, we get further hardness results for free. In many
counting problems, we want to count subsets of some given set having a certain
property. For instance, in the clique problem, we are given a graph and count
node sets of size $k$ that form a clique. To simplify the presentation, let us
now consider such graph problems where we want to count node sets of size $k$
having a particular property. Whether a given node set has a certain property
is a Boolean function of the adjacency matrix of the graph. We get a generic
way to construct a corresponding family of polynomials by:

$V_{n,k}=\sum_{e\in\genfrac{\langle}{\rangle}{0.0pt}{}{n}{k}}P_{e}(E)X_{1}^{e_{1}}\cdots
X_{n}^{e_{n}}.$

The polynomial has edges variables $E_{1,1},\dots,E_{n,n}$ and node variables
$X_{1},\dots,X_{n}$. We sum over all node sets of size $k$ and the product
produces a label of the corresponding node set. The polynomial $P_{e}(E)$ in
the edge variables is an arithmetization of the Boolean expression that checks
whether the node set given by $e$ has indeed the required property. The
$P_{e}$ can all be different, but in most cases, they can be obtained from
each other by permuting the edge variables, like it is for $\operatorname{VC}$
or $\operatorname{Clique}$.

Another example of this kind is the grid tiling problem: Given a graph $G$ and
a parameter $k$, count the subgraphs of $G$ that are isomorphic to a $k\times
k$-grid. The corresponding family of polynomials looks as follows:

$\mathrm{GT}_{n,k}=\sum_{\begin{subarray}{c}(a_{i,j})\in\\{1,\dots,n\\}^{k\times
k}\\\ \text{$a_{i,j}$ pairwise distinct,
$a_{1,1}<a_{1,n},a_{n,1}$}\end{subarray}}\prod_{1\leq
i,j<k}E_{\\{a_{i,j},a_{i+1,j}\\}}E_{\\{a_{i,j},a_{i,j+1}\\}}\\\ \prod_{1\leq
i<k}E_{\\{a_{i,k},a_{i+1,k}\\}}E_{\\{a_{k,i},a_{k,i+1}\\}}\prod_{1\leq i,j\leq
k}X_{a_{i,j}}.$

The first two products checks whether the selected vertices indeed form a grid
in the given graph. The third product writes down a label of the grid. The
condition $a_{1,1}<a_{1,n},a_{n,1}$ is due to the fact that the grid has four
automorphisms.

######  Definition 7.1.

We call a (Boolean) parsimonious fpt-reduction between two parameterized node
counting problems $(F,k),(F^{\prime},k^{\prime})$ _witness projectable_ if all
instances $I$ with $n$ nodes are mapped to instances $I^{\prime}$ with exactly
$s(n,k)$ nodes and for every $n$, there is a mapping
$p_{n,k}\colon\\{1,\dots,n\\}\to\\{1,\dots,s(n,k)\\}$ such that for every
solution $S^{\prime}$ to $I^{\prime}$, $S=\\{u\mid p_{n,k}(u)\in
S^{\prime}\\}$ is a solution to $I$.

Witness projectable reductions have the property that we get a solution $S$ to
$F$ from a solution $S^{\prime}$ to $F^{\prime}$ by a simple projection, that
is, one can view $S$ as a subset of $S^{\prime}$. Furthermore, witness
projectable also implies that the reduction maps two instances of length $n$
to two instances having the same length $s(n,k)$. In particular, every bit of
$I^{\prime}$ (which is an entry in the adjacency matrix) is a function of the
bits of $I$. We can now prove the simple proposition.

######  Proposition 7.2.

Assume we have a witness projectable reduction from the Boolean $k$-clique
problem to a parameterized node counting problem $(F,k^{\prime})$. Then the
node counting polynomial corresponding to $F$ as defined above,

$V_{n,k}=\sum_{e\in\genfrac{\langle}{\rangle}{0.0pt}{}{n}{k}}P_{e}(E)X_{1}^{e_{1}}\cdots
X_{n}^{e_{n}}$

is $\mathsf{VW}[1]$ hard.

###### Proof.

We want to solve $(\operatorname{Clique}_{n,k})$ with $(V_{n,k})$. Let $(I,k)$
be a Boolean clique instance and $(I^{\prime},k^{\prime})$ be its image under
the reduction. Since fpt-parsimonious witness projectable reductions map
instances with $n$ nodes to instances with $s(n,k)$ many nodes, the entries of
the adjacency matrix of $I^{\prime}$ are Boolean functions in the entries of
adjacency matrix of $I$ and these expressions are independent of $I$. We
arithmetize the corresponding Boolean formulas and substitute the edge
variables of $V_{s(n,k),k^{\prime}}$ by these expressions. By the second
property of witness projectable, we get $\operatorname{Clique}_{n,k}$ by
setting some of the $X$-variables to $1$, namely, those not in the image of
$p_{n,k}$. The hardness now follows from transitivity. ∎

In particular, the family $(\mathrm{GT}_{n,k})$ is $\mathsf{VW}[1]$-hard,
since there is a witness projectable fpt-parsimonious reduction from the
Boolean clique problem to the Boolean grid tiling problem. Instead of a
$k\times k$-grid, any graph of sufficiently high tree width would work.

###  7.1 Composition of Sums

If $(f_{n}(X_{1},\dots,X_{n},Y_{1},\dots,Y_{p(n)},Z_{1},\dots,Z_{q(n)}))$ is
in $\mathsf{VP}$, then the family $(g_{n})$ given by

$g_{n}=\sum_{d\in\\{0,1\\}^{p(n)}}\sum_{e\in\\{0,1\\}^{q(n)}}f(X_{1},\dots,X_{n},d_{1},\dots,d_{p(n)},e_{1},\dots,e_{q(n)})$
(3)

is in $\mathsf{VNP}$, since we can write it as

$g_{n}=\sum_{e\in\\{0,1\\}^{p(n)+q(n)}}f(X_{1},\dots,X_{n},e_{1},\dots,e_{p(n)},e_{p(n)+1},\dots,e_{p(n)+q(n)}).$
(4)

If the family $f_{n}$ is instead computed by polynomial size constant depth
circuits of weft $t$ and we define the parameterized family $(g_{n,k})$ by

$g_{n,k}=\sum_{d\in\genfrac{\langle}{\rangle}{0.0pt}{}{p(n)}{k}}\sum_{e\in\genfrac{\langle}{\rangle}{0.0pt}{}{q(n)}{k}}f(X_{1},\dots,X_{n},d_{1},\dots,d_{p(n)},e_{1},\dots,e_{q(n)}).$
(5)

Then we cannot combine these two sums as in (4) by summing over
$e\in\genfrac{\langle}{\rangle}{0.0pt}{}{p(n)+q(n)}{2k}$, since we then also
sum over vectors that have e.g. $2k$ $1$s in the first part of $e$. We can
repair this by adding the expression

$\alpha\cdot\prod_{i=0}^{k-1}\left(i-\sum_{j=1}^{p(n)}e_{i}\right)\prod_{j=0}^{k-1}\left(j-\sum_{j=p(n)+1}^{p(n)+q(n)}e_{i}\right),$
(6)

which is nonzero if there are $k$ $1$s in the first and $k$ $1$s in the second
part and $0$ otherwise. By choosing $\alpha$ appropriately, we can achieve
that this expression is $1$ in the first case. The expression in (6) has
constant depth and weft 2, therefore, we obtain:

######  Proposition 7.3.

If $(f_{n}(X_{1},\dots,X_{n},Y_{1},\dots,Y_{p(n)},Z_{1},\dots,Z_{q(n)}))$ is
computed by polynomial size constant depth circuits of weft $t\geq 2$, then
the family $(g_{n,k})$ given by (5) is in $\mathsf{VW}[t]$.

The case $t=1$ is more complicated. We will also need these techniques later
on the $\mathsf{VW}[1]$-completeness proof of the clique family. We start with
a technical lemma.

######  Lemma 7.4.

Let $k+1$ be prime. The system of equations

$\displaystyle a\cdot b$ $\displaystyle=c$ $\displaystyle a+b+c$
$\displaystyle=k^{2}+2k$

has a unique integer solution $a,b,c\geq 1$, namely, $a=b=k$ and $c=k^{2}$.

###### Proof.

Plugging the first equation in to the second, we get

$(a+1)(b+1)=a+b+ab+1=k^{2}+2k+1=(k+1)^{2}.$

Since $a+1,b+1\geq 2$ and $k+1$ is prime, the only possible solutions are
$a=b=k$. ∎

The next construction gives a solution to the composition problem when $k+1$
is prime.

######  Lemma 7.5.

Let $n\geq k\geq 1$ be integers such that $k+1$ is prime. There is a Boolean
expression $B$ of size $\operatorname{poly}(n)$ and weft 1 on $n^{2}+2n$
variables $X_{1},\dots,X_{n}$, $Y_{1},\dots,Y_{n}$, and $Z_{i,j}$,
$i,j=1,\dots,n$ such that:

  * •

Every satisfying assignment that sets $k^{2}+2k$ variables to $1$ sets $k$
variables from $X_{1},\dots,X_{n}$ to $1$, $k$ variables of
$Y_{1},\dots,Y_{n}$ to $1$, and $k^{2}$ many variables from $Z_{i,j}$ to $1$.

  * •

For every partial assignment that sets $k$ variables of $X_{1},\dots,X_{n}$ to
$1$, and $k$ variables of $Y_{1},\dots,Y_{n}$ to $1$, there is a unique
extension of this partial assignment to a satisfying assignment of $B$. This
satisfying assignment sets $k^{2}$ variables of the $Z_{i,j}$ to $1$.

###### Proof.

Consider the complete bipartite graph with $n$ nodes on each side. The
variables $X_{1},\dots,X_{n}$ represent the nodes on the one side, the
variables $Y_{1},\dots,Y_{n}$ represent the nodes on the other side and the
variables $Z_{i,j}$ represent the edges. Setting a variable to $1$ means that
we select the corresponding node or edge.

The Boolean formula $B$ expresses the fact that we select a complete bipartite
subgraph, that is:

$B$ is given by

$\bigwedge_{i,j=1}^{n}(Z_{i,j}\leftrightarrow X_{i}\wedge
Y_{j})\wedge\bigvee_{i=1}^{n}X_{i}\wedge\bigvee_{i=1}^{n}Y_{i},$

i.e., an edge is selected if and only if both endpoints are selected. The two
ORs ensure that we select at least one node on each side. Consider an
assignment that sets in total $k^{2}+2k$ variables to $1$, $a$ variables from
$X_{1},\dots,X_{n}$ to $1$, $b$ variables from $Y_{1},\dots,Y_{n}$ to $1$, and
$c$ variables of the $Z_{i,j}$ to $1$. That is, we have $a+b+c=k^{2}+2k$. If
this assignment is satisfying, then it encodes a complete bipartite subgraph
and we therefore have $ab=c$. Since $k+1$ is prime, it follows from lemma 7.4
that $a=b=k$ and $c=k^{2}$.

For the second part, note that the partial assignment selects $k$ nodes on
both sides. If we choose the $k^{2}$ edges between these two sets, we get a
complete subgraph, and this is the only way. ∎

Lemma 7.5 can also be extended to arbitrary values of $k$. In this case, the
size of $B$ also depends on $k$ but only polynomially.

######  Lemma 7.6.

Let $n\geq k\geq 1$ be integers. There are integers $k\leq\ell\leq 2k$ and
$m\leq n+k$ and a Boolean expression $B$ of size $\operatorname{poly}(n,k)$
and weft 1 on $m^{2}+2m$ variables $X_{1},\dots,X_{m}$, $Y_{1},\dots,Y_{m}$,
and $Z_{i,j}$, $i,j=1,\dots,m$ such that:

  * •

Every satisfying assignment that sets $\ell^{2}+2\ell$ variables to $1$ sets
$k$ variables from $X_{1},\dots,X_{n}$ to $1$, $\ell-k$ variables from
$X_{n+1},\dots,X_{m}$ to $1$, $k$ variables from $Y_{1},\dots,Y_{n}$ to $1$
and $\ell-k$ variables from $Y_{n+1},\dots,Y_{m}$ to $1$, and $\ell^{2}$
variables of the $Z_{i,j}$ to $1$.

  * •

For every partial assignment that sets $k$ variables of $X_{1},\dots,X_{n}$ to
$1$, and $k$ variables of $Y_{1},\dots,Y_{n}$ to $1$, there is a unique
extension of this partial assignment to a satisfying assignment of $B$. This
satisfying assignment sets $\ell$ variables from $X_{1},\dots,X_{m}$ and
$Y_{1},\dots,Y_{m}$ to $1$, respectively, and $\ell^{2}$ variables of the
$Z_{i,j}$ to $1$.

###### Proof.

Choose the smallest prime $\ell\geq k$. By Bertrand’s postulate, $\ell\leq
2k$. Let $m=n+\ell-k$. Let $B^{\prime}$ be the expression constructed in lemma
7.5 with parameters $m$ and $\ell$ (in place of $n$ and $k$). The expression
$B$ is defined by

$B=B^{\prime}\wedge\bigwedge_{i=n+1}^{n+\ell-k}(X_{i}\wedge Y_{i}).$

The expression $B^{\prime}$ ensures that $\ell$ variables from
$X_{1},\dots,X_{m}$ and $Y_{1},\dots,Y_{m}$ are set to $1$ and the remaining
part ensures that we set exactly $k$ variables from $X_{1},\dots,X_{n}$ and
$Y_{1},\dots,Y_{n}$ to $1$.

For the second part, note that to satisfy $B$, we are forced to set
$X_{n+1},\dots,X_{m}$ and $Y_{n+1},\dots,Y_{m}$ to $1$. ∎

We will also need the following generalization of the previous lemma:

######  Lemma 7.7.

Let $n_{1}$ and $n_{2}$ be integers and $n=\max\\{n_{1},n_{2}\\}$. Let
$s\colon\mathbb{N}\to\mathbb{N}$ a function with $s(k)\geq k$ for all $k$. Let
$n\geq k\geq 1$ be an integer such that $s(k)\leq n_{2}$. There are integers
$k\leq\ell\leq 2s(k)$ and $m\leq n+2s(k)$ and a Boolean expression $B$ of size
$\operatorname{poly}(n,s(k))$ and weft 1 on $m^{2}+2m$ variables
$X_{1},\dots,X_{m}$, $Y_{1},\dots,Y_{m}$, and $Z_{i,j}$, $i,j=1,\dots,m$ such
that:

  * •

Every satisfying assignment that sets $\ell^{2}+2\ell$ variables to $1$ sets
$k$ variables from $X_{1},\dots,X_{n_{1}}$ to $1$, $\ell-k$ variables from
$X_{n_{1}+1},\dots,X_{m}$ to $1$, $s(k)$ variables from
$Y_{1},\dots,Y_{n_{2}}$ to $1$ and $\ell-s(k)$ variables from
$Y_{n_{2}+1},\dots,Y_{m}$ to $1$, and $\ell^{2}$ variables of the $Z_{i,j}$ to
$1$.

  * •

For every partial assignment that sets $k$ variables of
$X_{1},\dots,X_{n_{1}}$ to $1$, and $s(k)$ variables of
$Y_{1},\dots,Y_{n_{2}}$ to $1$, there is a unique extension of this partial
assignment to a satisfying assignment of $B$. This satisfying assignment sets
$\ell$ variables from $X_{1},\dots,X_{m}$ and $Y_{1},\dots,Y_{m}$ to $1$,
respectively and $\ell^{2}$ variables of the $Z_{i,j}$ to $1$.

###### Proof.

The construction is similar to the one of lemma 7.6. Choose the smallest prime
$\ell\geq s(k)$. By Bertrand’s postulate, $\ell\leq 2s(k)$. Let $m=n+\ell-k$.
Let $B^{\prime}$ be the expression constructed in lemma 7.5 with parameters
$m$ and $\ell$. The expression $B$ is defined by

$B=B^{\prime}\wedge\bigwedge_{i=n_{1}+1}^{n_{1}+\ell-k}X_{i}\wedge\bigwedge_{i=n_{1}+\ell-k+1}^{n+\ell-k}\neg
X_{i}\wedge\bigwedge_{i=n_{2}+1}^{n_{2}+\ell-s(k)}Y_{i}\wedge\bigwedge_{i=n_{2}+\ell-s(k)+1}^{n+\ell-k}\neg
Y_{i}.$

Now the second part of the expression $B$ ensures that $k$ variables of
$X_{1},\dots,X_{n_{1}}$ are set to $1$ and $s(k)$ of $Y_{1},\dots,Y_{n_{2}}$
are set to $1$. Since we have different values $n_{1}$ and $n_{2}$, some of
the $X_{i}$ or $Y_{i}$ will be set to $0$. ∎

Now we can also extend proposition 7.3 to $t=1$.

######  Theorem 7.8.

Let $(f_{n}(X_{1},\dots,X_{n},Y_{1},\dots,Y_{p(n)},Z_{1},\dots,Z_{q(n)}))$ be
computed by polynomial size constant depth circuits of weft $t\geq 1$ and Let
$s\colon\mathbb{N}\to\mathbb{N}$ with $s(k)\geq k$ for all $k$. Then the
family $(g_{n,k})$ defined by

$g_{n,k}=\sum_{d\in\genfrac{\langle}{\rangle}{0.0pt}{}{p(n)}{k}}\sum_{e\in\genfrac{\langle}{\rangle}{0.0pt}{}{q(n)}{s(k)}}f_{n}(X_{1},\dots,X_{n},d_{1},\dots,d_{p(n)},e_{1},\dots,e_{q(n)})$

is in $\mathsf{VW}[t]$.

###### Proof.

Let $B$ be an arithmetization999By an arithmetization of a Boolean formula we
mean an arithmetic formula that is obtained by replacing every AND-gate by a
multiplication and every negation $\neg X$ by $1-X$. OR-gates are replaced
using de Morgan’s law. When we restrict the inputs of the arithmetized formula
to $\\{0,1\\}$, then it behaves like the Boolean one. of the expression from
lemma 7.7 with $n_{1}\coloneqq p(n)$, $n_{2}\coloneqq q(n)$. $B$ has weft 1.
Let $m$ and $\ell$ be defined as in lemma 7.7, $B$ has $m^{2}+2m$ variables.
We can write

$g_{n,k}=\sum_{e\in\genfrac{\langle}{\rangle}{0.0pt}{}{m^{2}+2m}{\ell^{2}+2\ell}}B(e)f_{n}(X_{1},\dots,X_{n},e_{1},\dots,e_{p(n)},e_{m},\dots,e_{m+q(n)}).$

The properties of $B$ ensure that only the vectors $e$ survive for which
$(e_{1},\dots,e_{p(n)})$ and $(e_{m},\dots,e_{m+q(n)})$ have $k$ and $s(k)$
$1$s, respectively, and that for each such pair of vectors there is exactly
one such $e$. ∎

###  7.2 Weft 1 Arithmetic Circuits

We prove a normal form for circuits of weft 1.

######  Lemma 7.9.

Let $C$ be a circuit of depth $d$, size $s$ and weft $w$. Then there is a
formula of size $O(2^{d-w}s^{w})$ computing the same functions as $C$.

###### Proof.

We use the standard technique of duplicating gates whenever they are used more
than once: Whenever we encounter a gate $g$ that has fan-out $o>1$, then we
create a total of $o$ copies of the subcircuit induced by $g$. When this
process stops, we end up with a formula computing the same polynomial. Since
we only create copies of the subcircuits, the depth and the weft do not
change.

Any path of the resulting formula from the root to a leaf has $d-w^{\prime}$
gates of fan-in $2$ and $w^{\prime}$ gates of unbounded fan-in—which can be at
most $s$—on it for some $w^{\prime}\leq w$. From this, the size bound follows.
∎

######  Lemma 7.10.

Let $(C_{n,k})$ be a family of circuits of constant depth and fan-in $2$. Then
each $C_{n,k}$ computes a polynomial of constant degree that depends on a
constant number of variables.

###### Proof.

By lemma 7.9, we can assume that $C_{n,k}$ is a formula of constant size,
constant depth, and fan-in 2. (Note that the weft of $C_{n,k}$ is $0$.) Such
formula has a constant number of leaves and a constant number of
multiplication gates. ∎

######  Lemma 7.11.

Let $(C_{n,k})$ be a family of arithmetic circuits of fpt size, constant
depth, and weft 1. Then there is a family of arithmetic formulas $(F_{n,k})$
of fpt size and a constant $b$ such that:

  1. 1.

The top gate of $F_{n}$ is an addition gate of fan-in $\leq b$,

  2. 2.

the second layer of $F_{n}$ are multiplication gates of fan-in $\leq b$,

  3. 3.

the third layer are addition and multiplication gates of unbounded fan-in,

  4. 4.

the fourth layer are addition gates of fan-in $\leq b$, and

  5. 5.

the fifth layer are multiplication gates of fan-in $\leq b$.

Furthermore, every multiplication gate in the fifth layer has exactly one
input that is labeled with a constant and every addition gate of the fourth
layer has at most one child that computes a constant.

###### Proof.

By lemma 7.9, we can assume that $C_{n,k}$ is a formula. The subcircuit
$S_{v}$ that is induced by any child $v$ of an unbounded fan-in gate is a
formula of constant depth and bounded fan-in. By lemma 7.10, $S$ computes a
polynomial $p_{v}$ of constant degree depending on a constant number of
variables. Such a polynomial has only a constant number of monomials of
constant degree. Each monomial can be computed by a multiplication gate of
bounded fan-in and these monomials can be added by an addition gate of bounded
fan-in. Each multiplication gate has one input which is not a variable. There
might be one monomial which is a nonzero constant. For this monomial, we will
still insert a multiplication gate of fan-in $1$ for consistency reasons.

Consider the circuit $D$ that is obtained from $C_{n,k}$ by removing all
subcircuits induced by the gates of unbounded fan-in and replacing each gate
$g$ by a new indeterminate $Z_{g}$. The circuit $D$ computes a polynomial $q$
of constant degree depending on a constant number of variables. Like above,
this polynomial can be computed by a summation gate followed by a layer of
multiplication gates, all having bounded fan-in.

We get the claimed formula $F_{n,k}$ by taking the depth-2-formula computing
$q$ and then replacing every variable $Z_{g}$ by the corresponding gate $g$
and every child $v$ of $g$ by the depth-2-formula computing $p_{v}$.

There might be paths in $F_{n,k}$ from a leaf $\ell$ to the root that have
length $2$, this happens when there is no unbounded fan-in gate on the path
from $\ell$ to the root in $C_{n,k}$. We can make this path longer by adding
dummy gates of fan-in $1$ to it. ∎

###  7.3 Boolean-arithmetic Formulas

A _Boolean-arithmetic formula_ is a formula of the form

$B(X_{1},\dots,X_{n})\cdot\prod_{i=1}^{n}(R_{i}X_{i}+1-X_{i})$

where $B$ is an arithmetization of some Boolean formula and the $R_{i}$ some
polynomial or even rational function (over a different set of variables). For
each satisfying $\\{0,1\\}$-assignment $e$ to $B$, the right hand side
produces one product and the $e_{i}$ switch the factors $R_{i}$ on or off.
Boolean-arithmetic formulas will play an important role for the hardness proof
of the clique family. Note that if $B$ has weft 1, then the whole formula has
weft 1, since the right hand side has weft 1.

The _support_ of a monomial $m$ is the set of variables appearing in $m$ (with
positive degree). The _support size_ of $m$ is the number of variables in its
support. For some polynomial $f$, $S_{k}(f)$ is the sum of all monomials in
$f$ that have support size equal to $k$. Like for the homogeneous parts, we
have that $f=\sum_{i=0}^{s}S_{k}(f)$, where $s$ is the largest support size of
any monomial. Note that for any monomial, the support size is always bounded
by the degree and we have equality iff the monomial is multilinear.

The aim of this section is to prove that for a bounded depth arithmetic
circuit $C$ of weft 1 computing a polynomial $f$ in $n$ variables, we can
write the part with support size $k$ of $f$ as a bounded sum over a Boolean
arithmetic expression. In this section, $F$ is a formula as in lemma 7.11
computing the polynomial $f\in K[X_{1},\dots,X_{n}]$. For
$A\subseteq\\{X_{1},\dots,X_{n}\\}$, we consider the subtree that is obtained
from $F$ by selecting all monomials $m$ that are computed at the
multiplication gates of the fifth layer such that the support of $m$ is
contained in $A$. We denote this subformula by $F|_{A}$ and the polynomial
computed by it by $f|_{A}$.

######  Observation 1.

$f|_{A}$ is the sum of all monomials of $f$ that contain only variables from
$A$. $f|_{A}$ is obtained from $f$ by setting all variables not in $A$ to $0$.

By the last observation, we can view $|_{A}$ as an operator that can be
applied independently from a given formula $F$.

######  Observation 2.

The operator $|_{A}$ is additive and multiplicative, that is, for polynomials
$f$ and $g$, we have

  1. 1.

$(f+g)|_{A}=f|_{A}+g|_{A}$ and

  2. 2.

$(fg)|_{A}=(f|_{A})(g|_{A})$.

######  Lemma 7.12.

For any $A\subseteq\\{X_{1},\dots,X_{n}\\}$, $\lvert A\rvert=k$, we have

$S_{k}(f|_{A})=\sum_{B\subseteq A}(-1)^{k-\lvert B\rvert}f|_{B}.$

###### Proof.

Let $A=\\{X_{i_{1}},\dots,X_{i_{k}}\\}$ and let
$A_{j}=A\setminus\\{X_{i_{j}}\\}$ for all $1\leq j\leq k$. $f|_{A}$ only has
monomials with support size at most $k$. $S_{k}(f|_{A})$ are all monomials of
$f|_{A}$ that have exactly support size $k$. The monomials of smaller support
size are the monomials of $f|_{A_{1}},\dots,f|_{A_{k}}$. Now the claim follows
by the inclusion-exclusion principle. ∎

######  Lemma 7.13.

For any $0\leq k\leq n$, we have

$S_{k}(f)=\sum_{\ell=0}^{k}(-1)^{k-\ell}\binom{n-\ell}{k-\ell}\sum_{\begin{subarray}{c}A\subseteq\\{X_{1},\dots,X_{n}\\}\\\
{\lvert A\rvert=\ell}\end{subarray}}f|_{A}.$

###### Proof.

We have

$S_{k}(f)=\sum_{\begin{subarray}{c}A\subseteq\\{X_{1},\dots,X_{n}\\}\\\
{\lvert A\rvert=k}\end{subarray}}S_{k}(f|_{A}),$

since every monomial on the right hand side appears exactly once one the left
hand side and vice versa. By lemma 7.12, we get

$S_{k}(f)=\sum_{\begin{subarray}{c}A\subseteq\\{X_{1},\dots,X_{n}\\}\\\
{\lvert A\rvert=k}\end{subarray}}\sum_{B\subseteq A}(-1)^{k-\lvert
B\rvert}f|_{B}.$

If $\lvert B\rvert=\ell$, then $B$ is a subset of $\binom{n-\ell}{k-\ell}$
different $A\subseteq\\{X_{1},\dots,X_{n}\\}$ of size $k$. Therefore,

$S_{k}(f)=\sum_{\ell=0}^{k}(-1)^{k-\ell}\binom{n-\ell}{k-\ell}\sum_{\begin{subarray}{c}A\subseteq\\{X_{1},\dots,X_{n}\\}\\\
{\lvert A\rvert=\ell}\end{subarray}}f|_{A}.\qquad\qed$

∎

This means in order to compute $S_{k}(f)$, it is sufficient to compute the
sums

$\sum_{\begin{subarray}{c}A\subseteq\\{X_{1},\dots,X_{n}\\}\\\ {\lvert
A\rvert=\ell}\end{subarray}}f|_{A}.$

This is a bounded summation, so we need to understand how to compute $f|_{A}$
given some particular $A$. Let $v$ be a summation gate in the fourth layer of
$F$ computing a polynomial $p_{v}$. Let $T_{v}$ be the support of $p_{v}$,
which is the union of the supports of all monomials in $p_{v}$.

######  Observation 3.

Given some $A\subseteq\\{X_{1},\dots,X_{n}\\}$ of size $k$. Then
$p_{v}|_{A}=p_{v}|_{A\cap T_{v}}$.

######  Lemma 7.14.

Let $u$ be a multiplication gate in the third layer computing a polynomial
$q$. Then

$q|_{A}=\prod_{v}p_{v}|_{A\cap T_{v}}$

where the product is taken over all children $v$ of $u$ in the fourth layer
and $p_{v}$ is the polynomial computed at $v$.

###### Proof.

We have $q=\prod_{v}p_{v}$. Since $|_{A}$ is multiplicative,
$q|_{A}=\prod_{v}p_{v}|_{A}$. By the observation above, we can replace $A$ by
$A\cap T_{v}$. ∎

In the same way, we can prove:

######  Lemma 7.15.

Let $u$ be an addition gate in the third layer computing a polynomial $q$.
Then

$q|_{A}=\sum_{v}p_{v}|_{A\cap T_{v}}$

where the sum is taken over all children $v$ of $u$ in the fourth layer and
$p_{v}$ is the polynomial computed at $v$. ∎

Let $u$ be a multiplication gate in the second layer. There is only a constant
number of such gates, therefore, it will turn out that we can treat them
separately. We want to write the polynomial $q$ computed at $u$ as a bounded
sum over a Boolean-arithmetic formula. Let $v_{1},\dots,v_{s}$ and
$w_{1},\dots,w_{t}$ be the children of $u$, where $v_{1},\dots,v_{s}$ are
unbounded fan-in multiplication gates and $w_{1},\dots,w_{t}$ are unbounded
fan-in addition gates. The polynomial $q$ computed at $u$ is

$q=\prod_{i=1}^{s}\prod_{\text{$c$ child of
$v_{i}$}}p_{c}\cdot\prod_{i=1}^{t}\sum_{\text{$c$ child of $w_{i}$}}p_{c}.$

By lemmas 7.14 and 7.15, we have

$q|_{A}=\prod_{i=1}^{s}\,\prod_{\text{$c$ child of $v_{i}$}}p_{c}|_{A\cap
T_{c}}\cdot\prod_{i=1}^{t}\,\sum_{\text{$c$ child of $w_{i}$}}p_{c}|_{A\cap
T_{c}}.$ (7)

When we write $q|_{A}$ as a bounded sum over a Boolean-arithmetic expression,
we write it essentially as a bounded sum over a product. This means that from
the first outer product of the expression in (7), every factor can potentially
contribute and from the second outer product, we choose one summand from each
sum and sum over all possibilities. There is one complication: Since the sum
is bounded, we are only allowed to set a number of Boolean variables to $1$
that is bounded by some function in $k\coloneqq\lvert A\rvert$. For instance,
$\prod_{i=1}^{n}X_{1}$ has support size $1$, however, the degree is unbounded.

We will have $n$ Boolean variables $y_{1},\dots,y_{n}$. Setting such a
variable $y_{\nu}$ to $1$ indicates that the algebraic variable $X_{\nu}$ is
in the support $A$ that we are currently considering. In the following $a$
will be an Boolean assignment to the $y_{1},\dots,y_{n}$ such that assigns the
value $1$ to exactly $k$ variables. We will extend this assignment to further
variables. Once the values to the $y_{\nu}$ are fixed, there will only very
few ways to extend the assignment and we will have full control over it.

In our construction, we will treat the gates $v_{i}$ and $w_{j}$ differently.
From each $w_{j}$ (addition gate), only one child can contribute at a time.
For each $v_{i}$ (multiplication gate), all children can contribute
simultaneously. Let $c$ be a child of one of the $v_{i}$. For every subset $B$
of $T_{c}$, we will have a Boolean variable $x_{B}$. If a set $B$ is a subset
of more than one $T_{c}$, there will only be one variable $x_{B}$. For every
$x_{B}$, we will have a Boolean expression that sets $x_{B}$ to $1$ iff
$B\subseteq\\{X_{i}\mid a(y_{i})=1,1\leq i\leq n\\}$. We can easily express
this by a Boolean expression of weft 1:

$\mathcal{B}_{1}=\bigwedge_{B}\Bigl{(}x_{B}\leftrightarrow\bigwedge_{i:\,X_{i}\in
B}y_{i}\Bigr{)}.$ (8)

Here the first AND is over all $B$ that appear in some $T_{c}$. Note that the
inner AND gate is bounded. The number of variables that will be set to $1$ by
this expression is at most $2^{k}$.

For every $w_{j}$ and every child $c$ of $w_{j}$, we have a “switch” variable
$s_{j,c}$. For each $j$, exactly one of them shall be set to $1$. This
corresponds to choosing the corresponding summand $c$. Let $\mathcal{B}_{2}$
be a weft 1 Boolean expression realising this, that is

$\mathcal{B}_{2}=\bigwedge_{j=1}^{t}\Bigl{(}\Bigl{[}\bigvee_{\text{$c$ child
of
$w_{j}$}}s_{j,c}\Bigr{]}\wedge\neg\Bigl{[}\bigwedge_{\text{$c\not=c^{\prime}$
children of $w_{j}$}}(s_{j,c}\wedge s_{j,c^{\prime}})\Bigr{]}\Bigr{)}.$

Now let $c$ be a child of one of the $w_{j}$. For each such $c$ and every
$B\subseteq T_{c}$, we have a variable $z_{c,B}$. For every $z_{c,B}$ there
will be a Boolean expression $\mathcal{B}_{3,c,B}$ that sets $z_{c,B}$ to $1$
if $s_{j,c}$ is set to $1$ and $B\subseteq\\{X_{i}\mid a(y_{i})=1,\enspace
1\leq i\leq n\\}$. Note that $\mathcal{B}_{3,c,B}$ has constant size, since
$T_{c}$ has, and therefore

$\mathcal{B}_{3}=\bigwedge_{j=1}^{t}\bigwedge_{\text{$c$ child of
$w_{j}$}}\bigwedge_{B\subseteq T_{c}}\mathcal{B}_{3,c,B}$

has weft $1$, since the AND gate in the middle is the only one that has
unbounded fan-in. Furthermore, note that we can afford to have a separate
variable $z_{c,B}$ for every $c$, since in a summation gate, only one child is
selected and therefore, we will only set a number of variables to $1$ that is
bounded by $2^{k}$.

######  Lemma 7.16.

For any polynomial $p$ and any set $B$, let

$Q_{B}=\prod_{C\subseteq B}(p|_{C})^{{(-1)}^{\lvert B\rvert-\lvert C\rvert}},$

where we assume that all $p|_{C}$ are nonzero. (The factors are either
$p|_{C}$ or $(p|_{C})^{-1}$, depending on the parity of $\lvert B\rvert-\lvert
C\rvert$.) Then for any $A$,

$\prod_{B\subseteq A}Q_{B}=p|_{A}.$

###### Proof.

We can write

$\prod_{B\subseteq A}Q_{B}=\prod_{B\subseteq A}\prod_{C\subseteq
B}(p|_{C})^{{(-1)}^{\lvert B\rvert-\lvert C\rvert}}$

Fix a particular $C\not=A$. Let $m=\lvert A\rvert-\lvert C\rvert$. First
assume that $m$ is odd. $p|_{C}$ appears $\sum_{i=0}^{(m-1)/2}\binom{m}{2i}$
times in $\prod_{B\subseteq A}Q_{B}$ and $(p|_{C})^{-1}$ appears
$\sum_{i=0}^{(m-1)/2}\binom{m}{2i+1}$ times. Both contributions cancel. If $m$
is even, then $p|_{C}$ appear $\sum_{i=0}^{m/2}\binom{m}{2i}$ times in
$\prod_{B\subseteq A}Q_{B}$ and $(p|_{C})^{-1}$ appears
$\sum_{i=0}^{m/2-1}\binom{m}{2i+1}$ times. Again both contributions cancel.
Only $p|_{A}$ remains. ∎

######  Remark 7.1.

If some $p|_{C}$ is zero in the lemma above, then the lemma is still true when
we omit every $p|_{C}$ that is $0$ from every $Q_{B}$. The only exception is
when $p|_{A}=0$. Then the expression will be $1$.

We want to use expressions as in lemma 7.16 to design our Boolean arithmetic
formula. However, these expressions give the wrong result when $p|_{A}$ is
zero.101010Note that for a polynomial, if $p|_{B}\not=0$, then
$p|_{B^{\prime}}\not=0$ for all $B^{\prime}\supseteq B$. But we will later
consider the case when instead of $p|_{B}$, we will consider $p|_{B}$
evaluated at some point. Therefore, we will not make use out of this property.
We will have a Boolean variable $w$ that is set to $1$ when for some child $c$
of some $v_{i}$, $p_{c}|_{A}$ is $0$. This is achieved by the following
expression:

$\mathcal{B}_{4}=\left(\bigvee_{i=1}^{s}\bigvee_{\text{$c$ child of
$v_{i}$}}\bigvee_{\begin{subarray}{c}B\subseteq T_{c}\\\
{p_{c}|_{B}=0}\end{subarray}}(\bigwedge_{i\in B}y_{i}\wedge\bigwedge_{i\in
T_{c}\setminus B}\neg y_{i})\right)\leftrightarrow w.$

$\mathcal{B}_{4}$ has weft $1$, since all gates have constant fan-in except
the second one. Note that we can precompute whether $p_{c}|_{B}=0$.

Let $a$ be some assignment that sets $k$ variables $y_{1},\dots,y_{n}$ to $1$,
defining some set $A$ of size $k$. We extend $a$ to an assignment to the other
variables such that
$\mathcal{B}_{1}\wedge\mathcal{B}_{2}\wedge\mathcal{B}_{3}\wedge\mathcal{B}_{4}$
is satisfied. The number of variables set to $1$ is bounded by a function in
$k$. Note that the only degree of freedom we have is to choose which $s_{j,c}$
we set to $1$. Once this choice has been made, there is only one way to extend
the partial assignment to a satisfying one.

For some child $c$ of some $v_{i}$ and $B\subseteq T_{c}$, let

$Q_{c,B}=\prod_{C\subseteq B}(p_{c}|_{C})^{(-1)^{\lvert B\rvert-\lvert
C\rvert}}.$

If some $p_{c}|_{C}$ are zero, we simply leave them out. Consider the first
outer product of (7). We claim that

$\prod_{i=1}^{s}\,\prod_{\text{$c$ child of $v_{i}$}}p_{c}|_{A\cap
T_{c}}=(1-a(w))\prod_{\begin{subarray}{c}B:\,\text{$\exists c$ with}\\\
\text{$B\subseteq
T_{c}$}\end{subarray}}\Bigl{(}a(x_{B})\Bigl{[}\prod_{i=1}^{s}\prod_{\begin{subarray}{c}\text{$c$
child of $v_{i}$}\\\ {B\subseteq
T_{c}}\end{subarray}}Q_{c,B}\Bigr{]}+1-a(x_{B})\Bigr{)},$ (9)

where the outer product on the right-hand side is over all $B$ such that there
is a child $c$ of some $v_{i}$ and $B\subseteq T_{c}$. To see this, note that
when all $p_{c}|_{A}=p_{c}|_{T_{c}\cap A}\not=0$, then

$\displaystyle\prod_{\begin{subarray}{c}B:\,\text{$\exists c$ with}\\\
\text{$B\subseteq
T_{c}$}\end{subarray}}\Bigl{(}a(x_{B})\Bigl{[}\prod_{i=1}^{s}\prod_{\begin{subarray}{c}\text{$c$
child of $v_{i}$}\\\ {B\subseteq
T_{c}}\end{subarray}}Q_{c,B}\Bigr{]}+1-a(x_{B})\Bigr{)}$
$\displaystyle=\prod_{\begin{subarray}{c}B:\,\text{$\exists c$ with}\\\
\text{$B\subseteq T_{c}$ and $B\subseteq
A$}\end{subarray}}\prod_{i=1}^{s}\prod_{\begin{subarray}{c}\text{$c$ child of
$v_{i}$}\\\ {B\subseteq T_{c}}\end{subarray}}Q_{c,B}$
$\displaystyle=\prod_{i=1}^{s}\prod_{\text{$c$ child of
$v_{i}$}}\prod_{B\subseteq A\cap T_{c}}Q_{c,B}$
$\displaystyle=\prod_{i=1}^{s}\prod_{\text{$c$ child of $v_{i}$}}p_{c}|_{A\cap
T_{c}},$

where the last equality follows by lemma 7.16 and the remark after the lemma.
Recall that $a(x_{B})$ is true if $a$ sets all variables from $y_{\nu}$ to $1$
for which $X_{\nu}\in B$. When $p_{c}|_{A}=p_{c}|_{T_{c}\cap A}=0$ for some
$c$, then the whole product shall be zero. This is achieved by the first
factor $(1-a(w))$.

We write this rather complicated expression to get a Boolean-arithmetic
formula. Since the outer product in (9), we do not take product over all $B$,
but only over subsets of all $T_{c}$, so the product has polynomial size,
since each $T_{c}$ has constant size.

For the addition gates, we can do something similar. The construction is even
easier. We can write

$\prod_{i=1}^{t}\,\sum_{\text{$c$ child of $w_{i}$}}p_{c}|_{A\cap
T_{c}}=(1-a(w^{\prime}))\prod_{i=1}^{t}\prod_{\text{$c$ child of
$w_{i}$}}\prod_{B\subseteq
T_{c}}\Bigl{(}a(z_{c,B})Q_{c,B}+1-a(z_{c,B})\Bigr{)}.$ (10)

Here, the product is not taken over all $B$ but again only over subsets of
$T_{c}$. $w^{\prime}$ is again a new variable that checks whether one of the
chosen $p_{c}|_{A}$ is zero. The corresponding Boolean expression is given by

$\mathcal{B}_{5}=\left(\bigvee_{j=1}^{t}\bigvee_{\text{$c$ child of
$w_{j}$}}\bigvee_{\begin{subarray}{c}B\subseteq T_{c}\\\
{p_{c}|_{B}=0}\end{subarray}}\Bigl{[}z_{c,b}\wedge(\bigwedge_{i\in
B}y_{i}\wedge\bigwedge_{i\in T_{c}\setminus B}\neg
y_{i})\Bigr{]}\right)\leftrightarrow w^{\prime}.$

Now we can write

$\displaystyle\sum_{\begin{subarray}{c}A\subseteq\\{X_{1},\dots,X_{n}\\}\\\
{\lvert A\rvert=k}\end{subarray}}q|_{A}$
$\displaystyle=\sum_{a}\mathcal{B}(a)(1-a(w))\prod_{B}\Bigl{(}a(x_{B})\prod_{i=1}^{s}\prod_{\text{$c$
child of $v_{i}$}}a(x_{B})Q_{c,B}+1-a(x_{B})\Bigr{)}$
$\displaystyle\qquad\qquad\quad(1-a(w^{\prime}))\prod_{i=1}^{t}\prod_{\text{$c$
child of $w_{i}$}}\prod_{B\subseteq
T_{c}}\Bigl{(}a(z_{c,B})Q_{c,B}+1-a(z_{c,B})\Bigr{)}.$ (11)

Here the sum is taken over all $a$ that set $k$ of the $y_{i}$ to $1$ and its
extension satisfies the expression
$\mathcal{B}\coloneqq\mathcal{B}_{1}\wedge\dots\wedge\mathcal{B}_{5}$. Every
such assignment sets at most $q(k)$ other variables to $1$ for some function
$q$. To make it the same number for all assignments $a$, we add $q(k)$ dummy
variables $d_{1},\dots,d_{q(k)}$, which can always be set to $1$ (but which do
not affect the formula $\mathcal{B}$). However, there should be only one
unique way to extend a satisfying assignment of $\mathcal{B}$ to a satisfying
assignment with exactly $q(k)$ $1$s. Therefore, we add the expression
$\bigwedge_{i=1}^{q(k)}(d_{i}\geq d_{i+1})$ to $\mathcal{B}$, which has weft
1. Now the sum over all $a$ that set $k$ variables from $y_{1},\dots,y_{n}$ to
$1$ and $q(k)$ other variables is a doubly bounded sum and we can combine it
into one by lemma 7.7.

Finally, we can write $f|_{A}$ as a constant sum over constantly many
$q|_{A}$. By lemma 7.13, we can write $S_{k}(f)$ as a bounded sum over
$f|_{A}$. By applying the lemma below for a bounded number of times (in $k$),
we obtain theorem 7.18.

######  Lemma 7.17.

Let $f$ and $g$ be computed by bounded sums over Boolean-arithmetic formulas
of weft 1, that is,

$f=\sum_{d\in\genfrac{\langle}{\rangle}{0.0pt}{}{m}{k}}B(d_{1},\dots,d_{m})\prod_{i=1}^{m}(R_{i}d_{i}+1-d_{i})\quad\text{and}\quad
g=\sum_{e\in\genfrac{\langle}{\rangle}{0.0pt}{}{n}{k}}C(e_{1},\dots,e_{n})\prod_{j=1}^{n}(M_{j}e_{j}+1-e_{j}).$

Then $f+g$ can also be expressed by a bounded sum over a Boolean-arithmetic
formula of weft 1.

###### Proof.

We can write

$\displaystyle f+g$
$\displaystyle=\sum_{d\in\genfrac{\langle}{\rangle}{0.0pt}{}{n}{k}}\sum_{e\in\genfrac{\langle}{\rangle}{0.0pt}{}{m}{k}}\sum_{s\in\\{0,1\\}}\left(s\wedge\left(B(d_{1},\dots,d_{m})\wedge\bigwedge_{j=1}^{n}\neg
e_{j}\right)\vee\bar{s}\wedge\left(\bigwedge_{i=1}^{m}\neg d_{i}\wedge
C(e_{1},\dots,e_{n})\right)\right)$
$\displaystyle\qquad\quad\cdot\prod_{i=1}^{m}(R_{i}d_{i}+1-d_{i})\prod_{j=1}^{n}(M_{j}e_{j}+1-e_{j}).$

The Boolean expression is only true if the $d_{i}$ or $e_{i}$ are all $0$. In
this case, the corresponding algebraic product is $1$. The switch $s$ selects
which expression currently contributes. Now we can merge the three sums into
one by lemma 7.7. ∎

######  Theorem 7.18.

Let $C$ be a circuit of bounded depth and weft 1 computing a polynomial $f$ in
$n$ variables. Then there is a Boolean formula $\mathcal{B}$ of weft 1 and fpt
size (in $k$ and the size of $C$) having $p(n,k)$ inputs for some fpt-bounded
function $p$ and rational functions $R_{i}$ such that for all $k$,

$S_{k}(f)=\sum_{e\in\genfrac{\langle}{\rangle}{0.0pt}{}{p(n,k)}{q(k)}}\mathcal{B}(e)\cdot\prod_{i=1}^{p(n,k)}(R_{i}e_{i}+1-e_{i})$
(12)

for some function $q$.

######  Corollary 7.19.

Let $C$ be a circuit of bounded depth and weft 1 computing a polynomial $f$ in
$n$ variables. Then there is a Boolean formula $\mathcal{B}$ of weft 1 and fpt
size (in $k$ and the size of $C$) having $p(n,k)$ inputs for some fpt-bounded
function $p$ and rational functions $R_{i}$ with $R_{i}(1,\dots,1)\not=0$ such
that for all $k$,

$S_{k}(f)(1,\dots,1)=\sum_{e\in\genfrac{\langle}{\rangle}{0.0pt}{}{p(n,k)}{q(k)}}\mathcal{B}(e)\cdot\prod_{i=1}^{p(n,k)}(R_{i}(1,\dots,1)e_{i}+1-e_{i})$
(13)

for some function $q$.

###### Proof.

We have to ensure that all $R_{i}$ are defined at $(1,\dots,1)$. The $R_{i}$
are of the form $\prod_{C\subseteq B}(p_{c}|_{C})^{(-1)^{\lvert B\rvert-\lvert
C\rvert}}$. Now they are replaced by $\prod_{C\subseteq
B}(p_{c}|_{C}(1,\dots,1))^{(-1)^{\lvert B\rvert-\lvert C\rvert}}$. If one of
the $p_{c}|_{C}(1,\dots,1)$ becomes $0$, we can leave it out, as before by
remark 7.1. This can only produce a wrong result when $p|_{B}(1,\dots,1)$
becomes $0$. We can repair this as before, by an appropriate modifications of
the expression $\mathcal{B}_{4}$ and $\mathcal{B}_{5}$, namely, we replace the
condition $p_{c}|_{B}=0$ in the second OR gate by $p_{c}|_{B}(1,\dots,1)=0$. ∎

###  7.4 $\mathsf{VW}[1]$ and $\operatorname{Clique}$

In this section, we finally prove that $\operatorname{Clique}$ is
$\mathsf{VW}[1]$-complete. We first show that bounded sums over Boolean
arithmetic formulas can be written as evaluations of the clique polynomial.

######  Lemma 7.20.

Let $f$ be computed by a Boolean-arithmetic expression

$f(X_{1},\dots,X_{n})=\sum_{e\in\genfrac{\langle}{\rangle}{0.0pt}{}{p}{k}}B(e)\prod_{i=1}^{p}(R_{i}e_{i}+1-e_{i})$
(14)

where $B$ has size $s\geq p$ and weft 1. Then there is a graph $G$ with
adjacency matrix $A$ of size $a(k)q(s)$ for some p-bounded function $q$ and an
arbitrary function $a$ and some $k^{\prime}\leq b(k)$ for some arbitrary
function $b$ such that

$f(X_{1},\dots,X_{n})=\operatorname{Clique}_{a(k)q(s),k^{\prime}}(A,R_{1},\dots,R_{p},1,\dots,1).$
(15)

###### Proof.

From the $\mathsf{\\#W}[1]$-completeness proof [FG06, DF13] of the
parameterized clique problem, it follows that there is a graph $G$ with
adjacency matrix $A$ such that the satisfying assignments of $B$ with $k$ $1$s
stand in one-to-one correspondence with cliques of $G$ of size $k^{\prime}$.
Furthermore, there is an injective mapping $I$ from the variables
$x_{1},\dots,x_{p}$ of the Boolean formula $B$ to the nodes of $G$ such that
whenever a variable $x_{i}$ is set to $1$ by a satisfying assignment $e$, then
$I(x_{i})$ is contained in the clique corresponding to $e$. We give this node
the weight $R_{i}$. We order the nodes of $G$ such that these nodes are the
first $p$ nodes. All other nodes will be labeled with $1$. It follows that
(14) can be written as (15), where we substitute the values of $A$ for the
edge variables and $R_{1},\dots,R_{p},1,\dots,1$ for the node variables. ∎

######  Lemma 7.21.

Let $g\in K[Y_{1},\dots,Y_{m}]$ and let

$g_{k}=\sum_{e\in\genfrac{\langle}{\rangle}{0.0pt}{}{m}{k}}g(e).$

Then

$g_{k}=\sum_{\ell=0}^{k}\binom{m-\ell}{k-\ell}S_{\ell}(g)(1,\dots,1).$

###### Proof.

Let $\mu$ be a monomial of $g_{k}$. $\mu(e)$ contributes to $g_{k}$ if for all
$Y_{i}$ in the support of $\mu$, $e_{i}=1$. If the support size of $\mu$ is
$k$, then there is exactly one such vector $e$ and $S_{k}(g)(1,\dots,1)$ is
the sum over all $e$ of all $\mu(e)$ where $m$ has support size exactly $k$.
More general, if the support size of $\mu$ is $\ell\leq k$, then there are
$\binom{m-\ell}{k-\ell}$ such vectors. ∎

######  Theorem 7.22.

$\operatorname{Clique}_{n,k}$ is complete for $\mathsf{VW}[1]$ (under fpt-c-
reductions).

###### Proof.

Let $(f_{n,k})$ be a parameterized p-family in $\mathsf{VW}[1]$. Let $(g_{n})$
be a p-family, $g_{n}\in K[X_{1},\dots,X_{p(n)},Y_{1},\dots,Y_{q(n)}]$, such
that $g_{n}$ is computable by a constant depth unbounded fan-in circuit of
weft $1$ and $(f_{n,k})$ is an fpt-substitution of the family $(g_{n,k})$
defined by

$g_{n,k}=\sum_{e\in\genfrac{\langle}{\rangle}{0.0pt}{}{q(n)}{k}}g_{n}(X_{1},\dots,X_{p(n)},e_{1},\dots,e_{q(n)}),$
(16)

that is, there is a p-bounded function $m$, arbitrary functions $r,s$, and a
$k^{\prime}\leq s(k)$ such that

$\displaystyle f_{n,k}$
$\displaystyle=\sum_{e\in\genfrac{\langle}{\rangle}{0.0pt}{}{q(r(k)m(n))}{k^{\prime}}}g_{r(k)m(n)}(h_{1},\dots,h_{p(r(k)m(n))},e_{1},\dots,e_{q(r(k)m(n))})$
$\displaystyle=g_{r(k)m(n),k^{\prime}}(h_{1},\dots,h_{p(r(k)m(n))})$ (17)

for some polynomials $h_{1},\dots,h_{p(r(k)m(n))}$ computable by circuits of
size $r(k)m(n)$ and of degree bounded by $r(k)m(n)$.

We now want to apply corollary 7.19 to the family $g_{n,k}$. We interpret the
$g_{n}$ and $g_{n,k}$ as a polynomial in $Y_{1},\dots,Y_{q(n)}$ and treat the
other variables as constants (from the field $K(X_{1},\dots,X_{p(n)})$). By
lemma 7.21, we can write

$g_{n,k}=\sum_{\ell=0}^{k}\binom{q(n)-\ell}{k-\ell}S_{\ell}(g)(X_{1},\dots,X_{p(n)},1,\dots,1).$

By corollary 7.19, there are a Boolean expression $\mathcal{B}_{n}$ of weft 1,
an fpt-bounded function $\hat{p}$ and some function $\hat{q}$ and rational
functions $R_{n,i}$ such that

$S_{k}(g_{n})(X_{1},\dots,X_{p(n)},1,\dots,1)=\sum_{\hat{e}\in\genfrac{\langle}{\rangle}{0.0pt}{}{\hat{p}(n,k)}{\hat{q}(k)}}\mathcal{B}_{n}(\hat{e})\cdot\prod_{i=1}^{\hat{p}(n,k)}(R_{n,i}(1,\dots,1)\hat{e}_{i}+1-\hat{e}_{i}).$

$R_{n,i}(1,\dots,1)$ is a constant. But here a constant is a rational function
from $K(X_{1},\dots,X_{p(n)})$. However such a constant cannot be arbitrary.
The constants appearing in the proof of corollary 7.19 are computed by
circuits of fpt size: We start with building blocks $p_{c}|_{C}(1,\dots,1)$ or
$1/p_{c}|_{C}(1,\dots,1)$, which are computed by constant size circuits, and
each $L_{n,i}$ might be an unbounded product or sum over them. Each
$p_{c}|_{C}(1,\dots,1)$ is a sum of polynomials in $X_{1},\dots,X_{p(n)}$.
These polynomials however were created when transforming the original circuit
$C$ of bounded depth and weft 1 into the normalized formula $F$. Therefore,
they are itself computed by circuits of constant depth.

Hence, we can write

$g_{n,k}(X_{1},\dots,X_{p(n)})=\sum_{\ell=0}^{k}\binom{q(n)-\ell}{k-\ell}\sum_{\hat{e}\in\genfrac{\langle}{\rangle}{0.0pt}{}{\hat{p}(n,k)}{\hat{q}(k)}}\mathcal{B}_{n}(\hat{e})\cdot\prod_{i=1}^{\hat{p}(n,k)}(R_{n,i}(X_{1},\dots,X_{p(n)})\hat{e}_{i}+1-\hat{e}_{i}).$
(18)

By lemma 7.17, we can replace the multiple sum in (18) by one sum. Note that
the parameters in the theorem grow in such a way that the corresponding single
sum still has fpt size when we apply the theorem a number of times that is
bounded by some function in $k$. Therefore, we can interpret (18) as a Boolean
arithmetic formula of weft 1.

By lemma 7.20, we can write $g_{n,k}$ as an evaluation of
$\operatorname{Clique}_{N,k^{\prime}}$, where $N=a(k)\operatorname{poly}(n)$
and $k^{\prime}\leq b(k)$ for two functions $a,b$. The expression that we plug
into $\operatorname{Clique}_{N,k^{\prime}}$ are $0$, $1$, and the $R_{n,i}$.
The $R_{n,i}$ are rational expressions that are computable by fpt size
circuits (in $n$ and $k$) and have fpt degree (in $n$ and $k$).111111Note that
from this together with (17) it already follows that $f_{n,k}$ is an fpt-
substitution of $\operatorname{Clique}$ when we allow that we substitute
rational expression. Note that although we plug in rational functions into
$\operatorname{Clique}_{N,k^{\prime}}$, the result is still a polynomial,
namely $g_{n,k}$.

Assume for the moment that we were given a circuit computing
$\operatorname{Clique}_{N,k^{\prime}}$ evaluated at the these rational
functions. Strassen [Str73] shows that we can find a circuit without
divisions. His construction consists of the following steps:

  * •

First we perform a Taylor shift of the variables such that all denominators
have nonzero constant term, that is, are invertible as formal power series.

  * •

Then we replace the denominators by approximations of high enough degree
(still polynomial) to the corresponding formal power series.

  * •

We compute with the homogeneous components up to the desired degree.

  * •

Finally, we revert the Taylor shift from the first step.

The difference in our setting is that we do not have a circuit but we only
have a substitution of a clique polynomial. So we cannot compute in the third
step with the homogeneous components. We overcome this difficulty as follows:

  * •

After the first two steps, we replace every variable $X_{i}$ by $TX_{i}$,
where $T$ is a new variable. Let $P(T,X_{1},\dots,X_{n})$ be the resulting
polynomial. We view the polynomial as a univariate polynomial in $T$. In this
way, we group the homogeneous components of our polynomial.

  * •

Then we plug in enough (that is, fpt many) values for $T$ such that we can
recover the coefficients of $P$ by interpolation. Interpolation can be done by
polynomial sized circuits. In this way, we get the homogeneous components of
$P$ can continue like in Strassen’s construction.

In this way, we get a circuit of fpt size computing $f_{n,k}$ using
$\operatorname{Clique}$-oracle gates ∎

From the footnote to the proof of the above theorem, the following corollary
immediately follows:

######  Corollary 7.23.

$\operatorname{Clique}$ is complete for $\mathsf{VW}[1]$ under fpt-
substitutions that are allowed to substitute rational expressions.

##  8 Hardness of the Permanent and Cycle Covers

In this section we will highlight the vast difference between the provable
complexity of the following two problems. Having cycle covers where one cycle
is of length $k$ and all other cycles are self loops and the complexity of all
cycle covers where one cycle is length $k$ and all other cycle covers are of
length some fixed constant $c$. As always in this paper, we will look at
corresponding polynomials to this problem.

We will extensively use that formulas are closed under extracting of
homogeneous components. Let $K$ be a large enough field. Then given a
polynomial $f=\sum_{i=1}^{d}x^{i}p_{i}(x_{1},\dots,x_{n})$ for some variable
$x_{i}$, degree $d$ and polynomials $p_{i}\in K[x_{1},\dots,x_{n}]$, not
including the variable $x$. We can compute $p_{i}$ for any $i$ with the help
of a summation, namely

$p_{i}=\sum_{i=0}^{d}\beta_{i}f(\alpha_{i}x_{1},\dots,\alpha_{i}x_{n},\alpha_{i}x)\text{
for some constants }\alpha_{i},\beta_{i}.$

We define a transfer function between sets on graphs and polynomials. Given a
set $S$ of subgraphs of a graph $G$ we define the given polynomial
$\mathcal{P}(S)$ to be

$\mathcal{P}(S)=\sum_{G\in S}\prod_{v\in V(G)}X_{v}\prod_{e\in E(G)}E_{e}$

where $X,E$ are variables. Notice, that as expected $\mathcal{P}(C_{n,k})$
where $C_{n,k}$ is the set of all $k$-cliques on a complete graph is exactly
our previously defined clique polynomial $\operatorname{Clique}_{n,k}$.

###  8.1 Hardness of the $k$-permanent

We are adapting the proof from Curticapean and Marx [CM14] to show the
hardness of a parameterized permanent. We give most of the details in this
section but will skip correctness proofs unless they are necessary for us. In
the following, we will talk as if we were constructing graphs for clarity of
presentation but in reality, we take a large enough $n$ and set variables to
zero for edges that we did not construct.

Notice that the theorem from [CM14] is not enough for us. It is in general
unclear how and in which way the cycles transfer in the theorem while we need
an explicit fpt-projection. In essence, we can see this as the following: Our
polynomial will contain a set of all $k$-matchings which we need to be able to
transfer to a set of $k$-cliques with an fpt-projection. Transferring this
will not be difficult but certain care has to be taken in the proofs.

######  Definition 8.1 (Definition 2.4).

Let $\Gamma$ be a set of colors. A _colored graph_ is a graph $G$ together
with a coloring $c_{G}\colon V(G)\rightarrow\Gamma$. We call a graph colorful
if $c_{G}$ is bijective. Two colorful graphs $G,G^{\prime}$ are _color-
preserving_ isomorphic if there is a isomorphism $\phi$ from $H$ to
$H^{\prime}$ such that it maps every $\gamma$-colored vertex in $H$ to a
$\gamma$-colored vertex in $H^{\prime}$.

######  Definition 8.2 (Definition 2.5).

  * •

For colored graphs $H,G$ with $H$ being colorful. We define
$\texttt{PartitionedSub}(H\rightarrow G)$ to be the set of all subgraphs
$F\subseteq G$ such that $F$ is color preserving isomorphic to $H$.

  * •

For a class $\mathcal{H}$ of uncolored graphs,
$\texttt{PartitionedSub}(\mathcal{H})$ is the set of all
$\texttt{PartitionedSub}(H\rightarrow G)$ where $H$ is vertex colorful graph
whose underlying uncolored graph is in $\mathcal{H}$ and $G$ is vertex
colored. The parameter is $\lvert V(H)\rvert$.

Remember that the clique polynomial is defined by $\sum_{C\subseteq[n],\lvert
C\rvert=k}\prod_{i,j\in C,i<j}E_{i,j}\prod_{i\in C}X_{i}$.

######  Lemma 8.3 (Theorem 3.2).

$\mathcal{P}(\texttt{PartitionedSub}(\mathcal{H}_{\text{grid}}))$ is
$\mathsf{VW}[1]$ hard under fpt-c-reductions.

###### Proof.

We reduce to the parameterized clique polynomial.

  * •

For every $i\in[k]$ and every $x\in V(G)$ we introduce a vertex $v_{i,i,x,x}$
of color $(i,i)$.

  * •

For every $i,j\in[k],i\neq j$ and every $x,y\in V(G)$ such that $x\neq y$ and
$\\{x,y\\}\in E(G)$, we introduce a vertex $v_{i,j,x,y}$ of color $(i,j)$.

  * •

For every $i\in[k],j\in[k-1]$ and $x,y,y^{\prime}\in V(G)$ which are pairwise
distinct, if $v_{i,j,x,y}$ and $v_{i,j+1,x,y^{\prime}}$ both exist in
$G^{\prime}$ then we make them adjacent.

  * •

For every $i\in[k],j\in[k-1]$ and $x,x^{\prime},y\in V(G)$ which are pairwise
distinct, if $v_{i,j,x,y}$ and $v_{i,j+1,x^{\prime},y}$ both exist in
$G^{\prime}$ then we make them adjacent.

Left to show is the correctness and existence of a projection. Let
$a_{1},\dots,a_{k}$ be a $k$-clique in the complete graph. This graph is
mapped to a colorful grid in our graph $G^{\prime}$. Now, we can notice that
$h_{i,j}$ is mapped to a vertex $v_{i,j,a_{i},a_{j}}\in G^{\prime}$ and
$h_{i,j},h_{i,j+1}$ are adjacent if $v_{i,j,a_{i},a_{j}}$ and
$v_{i,j+1,a_{i},a_{j+1}}$ exist and are adjacent. Notice that vertices
$v_{i,j,a_{i},a_{j}}$ correspond to edges in our clique between $a_{i},a_{j}$
and vertices in our clique correspond to $v_{i,i,a_{i},a_{i}}$ for some $i$.
Hence, projecting to these, gives us the required polynomial.

The correctness of this mapping now follows from [CM14]. ∎

######  Lemma 8.4 (Lemma 3.1).

Let $\mathcal{H},\mathcal{H^{\prime}}$ be recursively enumerable graph classes
such that for every $H\in\mathcal{H}$ there exists some
$H^{\prime}\in\mathcal{H^{\prime}}$ with $H\preceq H^{\prime}$. Then
$\mathcal{P}(\texttt{PartitionedSub}(\mathcal{H}))\leq^{\mathit{fpt}}_{p}\mathcal{P}(\texttt{PartitionedSub}(\mathcal{H^{\prime}}))$.

###### Proof.

Let us look at $\mathcal{P}(\texttt{PartitionedSub}(\mathcal{H}\rightarrow
G))$ and $\mathcal{P}(\texttt{PartitionedSub}(\mathcal{H^{\prime}}\rightarrow
G^{\prime}))$. As in [CM14] we can transform $G$ to a $G^{\prime}$ with larger
vertex and edge set. $V(\mathcal{H^{\prime}})$, the set of vertices of
$\mathcal{H^{\prime}}$, admits a partition into so called branch sets
$B_{0},\dots,B_{k}$ such that: For $i\in[1,k]$ the induced graph of
$\mathcal{H^{\prime}}$ on $B_{i}$ is connected and deleting $B_{0}$ and
contracting each $B_{i}$ to a single vertex yields some subgraph of $H$ on the
vertex set $[k]$.

Now the following transformation will suffice by the argument in [CM14].

  1. 1.

For $i\in[1,k]$ and $v\in V_{i}(G)$, the set of vertices with color $i$:
Replace $v$ by the induced subgraph of $\mathcal{H^{\prime}}$ on $B_{i}$. Call
this graph $L_{v}$.

  2. 2.

For $\\{i,j\\}\in E(H)$, the edge set of $H$, and $u\in V_{i}(G),v\in
V_{j}(G)$: Insert all edges between $L_{u}$ and $L_{v}$ in $G^{\prime}$.

  3. 3.

For $\\{i,j\\}\not\in E(H)$ and $u\in V_{i},v\in V_{j}(G)$: Insert all edges
between $L_{u}$ and $L_{v}$ in $G^{\prime}$.

  4. 4.

Add a copy of the induced subgraph of $\mathcal{H^{\prime}}$ on $B_{0}$ to
$G^{\prime}$, connect it to all other vertices of $G^{\prime}$.

With this, we only need to make sure that for every branch set $L_{v}$ there
is only one designated vertex $v$ for which variable we project down to. As a
whole branch set will always be selected this is not a problem. A similar
argument is used for the edges. This shows that a simple projection reduction
is sufficient. ∎

######  Lemma 8.5 (Lemma 3.6).

$\mathcal{P}(\texttt{PartitionedSub}(\mathcal{H}_{\text{bicub}}))$ is
$\mathsf{VW}[1]$ hard under fpt-c-reductions.

###### Proof.

By Lemma 3.5 [CM14] every $H$ appears as the minor of some graph
$H^{\prime}\in\mathcal{H}_{\text{bicub}}$. Hence, lemma 8.4 finishes the
proof. ∎

For an edge-colored bipartite graph $G$ over the colors $\Gamma$ and
$X\subseteq\Gamma$ be a set of colors. Let $M_{X}(G)$ be the set of all
matchings in $G$ that choose exactly one edge from each color in $X$.

######  Lemma 8.6 (Theorem 4.1).

$\mathcal{P}(M_{X}(G))$ with parameter $\lvert X\rvert$ is $\mathsf{VW}[1]$
hard under fpt-c-reductions.

###### Proof.

We want to compute
$\mathcal{P}(\texttt{PartitionedSub}(\mathcal{H}_{\text{bicub}}))$ with oracle
calls to the polynomial $\mathcal{P}(M_{X}(G^{\prime}))$. Let $H,G$ be
$k$-vertex colored graphs with $H$ being 3-regular. We build the following
graph for $G$:

  1. 1.

Replace each $v\in V(G)$ by a cycle $C_{6}$ (a cycle of length 6) on the
vertices $w_{v,1}$, $z_{v,1}$, $w_{v,2}$, $z_{v,2}$, $w_{v,3}$, $z_{v,3}$ in
this order. The edges of the cycle are colored with ${i}\times[6]$.

  2. 2.

For $e\in E(H)$ with $e=\\{u,v\\}$ let $i,j\in[3]$ be such that $e$ is the
$i$th edge incident with $u$ and the $j$th edge incident with $v$. Replace
each edge $\\{u^{\prime},v^{\prime}\\}\in E(G)$ where $u^{\prime}$ is
$u$-colored and $v^{\prime}$ is $v$ colored by the edge
$\\{w_{u,a},w_{v,a}\\}$ of color $\gamma(e)$.

Assume now that for every cycle $C_{6}$, there are exactly 3 edges outgoing
matched and no edges in $C_{6}$ matched (type $(1,\dots,1)$ in the language of
Curticapean and Marx). We want to show that every such matching corresponds to
an isomorphic graph $H^{\prime}$ on the set of colors. As in Theorem 4.1
[CM14] every such matching describes a copy of $H$ and every copy of $H$
describes a unique matching of this type. Notice that the edges and vertices
are in an easily projectable relation to each other by the construction.

For each color $i\in[k]$, we define the independent set
$I(v)=\\{w_{v,1},w_{v,2},w_{v.3}\\}$ and $\mathcal{I}(i)=\bigcup_{v\in
V_{i}(G)}I(v)$ where $V_{i}(G)$ are all vertices of color $i$ in $G$. We call
two vertices $u,v\in V(M)\cap\mathcal{I}(i)$ equivalent if there exists some
$w\in V(G)$ such that $u,v\in I(w)$. In essence, this translates to that
vertices are equivalent if they originate from a single original $w\in G$.
Notice that $\lvert\mathcal{I}(i)\rvert=3$. This implies that we get a
partition that has at most 5 settings for every color $i$ where the first type
is the class of all 3 vertices being equivalent. We call these having type 1
for a color $i$ and having a type vector $(1,\dots,1)$ that describes the
types per color.

It turns out that the matchings are in a bijective relation to
$\texttt{PartitionedSub}(H\rightarrow G)$ if we restrict ourselves to
matchings having type vector $(1,\dots,1)$. Notice that here we select exactly
three vertices for every color $i\in[k]$. Now we can use simple extracting of
homogeneous components. Every extracting of homogeneous components increases
the circuit size by $O(sd^{2})$ where $d$ is the degree and $s$ the size. As
we have to iterate this, we get a overall bound of $O(sd^{2^{k}})$ as $d$ is
constant in the color variables, we get a total circuit size of $O(sc^{k})$.

Using lemma 8.5 finishes the proof. ∎

######  Lemma 8.7 (Lemma 2.7).

Let $M(G)$ be the set of all matchings in a graph $G$. Then
$\mathcal{P}(M(G))$ is $\mathsf{VW}[1]$ hard under fpt-c-reductions.

###### Proof.

We define $A_{S}$ as $\texttt{Sub}(H\rightarrow G[E_{S}])$, i.e., the set of
all graphs in $G[E_{S}]$, the induced graph of the edge set $E_{S}$, that are
isomorphic to $H$. Further notice that for $H$ being $k$ disconnected edges,
$\texttt{Sub}(H\rightarrow G)$ are exactly the $k$-matchings in $G$. By the
same argument as in Lemma 2.7 in [CM14], we only need to compute the matchings
$M$ such that

$M\in A_{X}\setminus\bigcup_{S\subsetneq X}A_{S}.$

Via an inclusion-exclusion algorithm we can achieve this. Notice, that the
monomials, resulting from $A_{S^{\prime}}$ for any $S^{\prime}$ are the same
as occurring in $A_{S}$ and hence, we do not need any projection. We need
$2^{k}$ many calls to our oracle. ∎

We define the $k$-permanent polynomial as follows. Let $S^{\prime}_{n}$ be the
set of all permutations on $n$ elements that set $n-k$ elements to the
identity. Then

$\operatorname{per}_{k}=\sum_{\sigma\in
S^{\prime}_{n}}\prod_{i\in[n]}x_{i,\sigma(i)}.$

Notice, we do not include the selected vertices, as all vertices are in the
cycle cover and hence the two problems are equivalent.

######  Corollary 8.8.

$(\operatorname{per}_{k})$ is $\mathsf{VW}[1]$ hard under fpt-c-reductions.

###### Proof.

We use the well known identity between matching on bipartite graph and the
permanent. Given a bipartite graph (given in a left $L$ and right $R$ side)
where we want to find the $k$-matching polynomial. We interpret this graph as
a directed graph with edges going from $L$ to $R$. We add self loops to every
vertex. Additionally, we connect every vertex on the right side back to all
vertices on the left side (in this direction).

Now every cycle can only form including edges going from $L$ to $R$. We
project exactly on these edges and set all other variables to zero to get the
required polynomial. The proof is obvious from this simple construction. Note
that we need to increase the $k$ to $2k$ to create the correct sized cycles.
Finishing with lemma 8.6 and lemma 8.7 shows the hardness. ∎

###  8.2 Bounded Length Cycle Covers

######  Definition 8.9.

We define $(\operatorname{per}_{\texttt{sparse},k,c})$, the bounded length
$k$-permanent, to be the polynomial of all cycle covers where one cycle has
length $k$ and all other cycles have constant length i.e., length bounded by
some constant $c$.

$(\operatorname{per}_{\texttt{sparse},k,c})=\sum_{\sigma\in
S^{\prime}_{n}}\prod_{i\in[n]}x_{i,\sigma(i)}$

where $S^{\prime}_{n}$ is the above mentioned set of permutations on $n$
elements.

By the relationship between permanent and the sum of the weighted cycle cover,
we will also speak about weighted bounded $k$-cycle cover.

$c_{2}$$c_{1}$$a$$b$$\frac{1}{2}$$-\frac{1}{2}$$-\frac{1}{2}$$\frac{1}{2}$$-1$$-\frac{1}{2}$$-\frac{1}{2}$
Figure 1: A $2$-iff coupling

We call the gadget given in fig. 1 a $2$-iff coupling. The dashed edges allow
us to splice this gadget into two given edges of some graph. We will say that
the $2$ iff coupling connects these edges. Note that all thick edges have
weight $1$. This can be easily extended to a $m$-iff coupling by having
vertices $c_{1},\dots,c_{m}$ similarly connected to $a$ and $b$. We define the
following two notions depending on edges selected in a given cycle cover and
not part of the gadget itself.

######  Definition 8.10.

We call an $m$-iff coupling _active_ if $a$ has an incoming edge, $b$ has an
outgoing edge and every $c_{i}$ has edges $(u,c_{i})$ and outgoing edge
$(c_{i},v)$ where $u\neq v$. We call it _inactive_ if all the above edges do
not exist and _borderline_ otherwise.

We will now proof that we can essentially ignore borderline states if we look
at bounded length $k$-cycle covers.

######  Lemma 8.11.

Given a directed graph $G$ let $G^{\prime}$ be a graph where some set of edges
$(u,v)$ are connected with a $m$-iff coupling, then the bounded length
$k$-cycle cover of $G^{\prime}$ is equal to the sum of the weighted bounded
length $k$-cycle cover on $G$ where in every cycle cover either all edges in
the $m$-iff coupling are active or inactive.

###### Proof.

Notice that by proof given by Buergisser [Bür00a], for every cycle cover
having self loops at $c_{1},\dots,c_{i-1},c_{i+1},\dots,c_{m}$ for some $i$
and an arbitrary cover the statement holds. Notice that the extra self-loops
only add a constant factor of weight to the cycle cover. By the construction,
every cycle cover can have at most one $c_{i}$ where the self-loop is not
taken as otherwise $a$ or $b$ would occur multiple times, The only cases left
to prove are the following two.

We define the gadget being _split_ if there exists indices $i,j$ such that
$c_{i}$ is connected in the gadget but $c_{j}$ is connected outside the
gadget, i.e., the edges $(c_{i},c_{i})$ and $(u,c_{j})$ and $(c_{j},v)$ for
$u\neq v$ are in the cycle cover, $u,v\not\in\\{a,b,c_{1},\dots,c_{m}\\}$.

The gadget is split.

If the gadget is split, we can repeat the argument by Buergisser without the
vertex $c_{j}$ as this will just add a constant factor to the sum and hence
the lemma is fulfilled.

The gadget is active.

If the gadget is active, we cannot have any additional edges, hence, the value
is $1$.∎

######  Definition 8.12.

A _parse tree_ $T$ of an arithmetic circuit is the following tree defined
iteratively.

  * •

The root is in the tree.

  * •

For every summation gate $v$, if $v\in T$ then exactly one of its children is
in $T$.

  * •

For every multiplication gate $v$, if $v\in T$ then all of $v$s children are
in $T$.

The weight of a parse tree is the product of all its leafs.

It is a well known result that the sum over the weight of all parse trees of a
formula is the polynomial computed by the formula.

With this, we can prove the following theorem.

######  Theorem 8.13.

For all $t$, there exists a constant $c$ such that
$(\operatorname{per}_{\texttt{sparse},k,c})$ is hard for $\mathsf{VW}[t]$
under fpt-c-reductions.

###### Proof.

We will show an equivalence between cycle covers of a certain kind and parse
trees of the circuit. We have a constant depth circuit $C$ for every
polynomial in $\mathsf{VW}[t]$ of weft $t$. We will reduce this circuit if
necessary to have alternating layers. We also ensure that every path from the
root has the same length by adding gates with only one input. This increases
the fan-in by at most a constant and the size by a constant factor.

We convert the circuit first into a tree. Now we set every edge $\\{u,v\\}$ in
the tree to be an edge in our directed graph $(u,v)$ where the depth of $v$ is
smaller than the depth of $u$, i.e., all edges are pointing towards the root.

We call a vertex $u$ an _additive child of $v$_ if there exists a path from
$u$ to $v$ in the above tree that does not cross any multiplication gate.

Let $G$ be a directed clique of size $n$. We split every vertex into an
incoming and outgoing vertex. Let us call this graph $G^{\prime}$. We call the
edges between $v_{\text{in}}$ and $v_{\text{out}}$ for every vertex the
selector edge. Now, our circuit has variables $Y_{1},\dots,Y_{n}$ which
outgoing edges we couple with $1$-iff couplings to the selector edges of
$G^{\prime}$.

$u$$\times$$v_{1}$$v_{2}$$\Rightarrow$$u$$\times$$v_{1}$$v^{\prime}_{1}$$v_{2}$$v^{\prime}_{2}$$2$-iff
coupling$a$$b$$c_{1}$$c_{2}$ Figure 2: Abbridged Multiplication Node Transform

Now we will construct gadgets around the above given tree. Notice that our
paths travel from leafs to roots.

Input Node

We set the weight its outgoing edge to the value in the circuit. The self loop
will have weight 1.

Addition Node

We add a self loop with weight 1.

Multiplication Node

In essence, we will do the following. We disconnect the graph, construct
separate graphs for all its children and enforce that all children will be
taken by an appropriate iff coupling. Figure 2 represents such a
transformation with the following caveats. For clarity we omit the weights and
the edges belonging to the iff coupling between $(a,c_{1})$ and $(a,c_{2})$.
Additionally, we assume that the vertex $u$ is the last vertex in this tree
and omit the loops from $v^{\prime}-1$, $v^{\prime}_{2}$ back to all additive
children in their respective subtree.

In detail: For a multiplication gate with fan-in $\ell$ we add a $\ell$-iff
coupling. This iff coupling connects the incoming edges with the outgoing
edge. Let $a,b,c_{1},\dots,c_{\ell}$ be the vertices from this $\ell$-iff
coupling. Let $v$ be the multiplication gate and the edges
$(v,u),(v_{1},v),\dots,(v_{\ell},v)$ be as expected. We splice the $\ell$-iff
coupling into this graph in the following way. Add two vertices $a,b$ between
$(v,u)$ such that $(a,u)$ and $(v,b)$ are the edges.

Add new vertices $v^{\prime}_{1},\dots,v^{\prime}_{\ell}$, add the edges
$(v_{i},v^{\prime}_{i})$. Splice between these edges $c_{i}$, i.e, replace the
edge $(v_{i},v^{\prime}_{i})$ by $(v_{i},c_{i}),(c_{i},v^{\prime}_{i})$.
Finally, add for every $v^{\prime}_{i}$ edges to all additive children of
$v^{\prime}_{i}$. We add self-loops to the vertices $v^{\prime}_{i}$ of weight
1.

Root

For the root, we construct outgoing edges to all its additive children in the
subtree. If the root is a multiplication gate, we also use the construction
for a multiplication node and add an additional vertex in a loop with the
root.

This finishes the construction of the circuit. Finally, we will require via
extracting of homogeneous components that the root is always selected, i.e.,
is not covered by only a self loop, and that $G^{\prime}$ has $k$ selector
edges selected and $2k$ edges overall.

As the polynomial computes by every formula is equal to the sum over all its
parse trees, we just need to show the equality between bounded length
$k$-cycle cover and parse trees. Notice that by construction only leafs have
weight not equal to one or zero. In the following we will ignore the factor of
$k!$ that occurs from the different possible orderings of the edges selected
in the clique $G^{\prime}$. We can easily divide by this factor.

We first prove that every parse tree has a cycle cover. All vertices not in
the parse tree can have self loops with weight 1. All vertices in the path
tree are in a cycle. Take the appropriate $k$ cycle in $G^{\prime}$. With the
iff coupling these transfer to certain input gates. Take the cycle starting
from the leafs of the parse tree. From this move up along addition gates to a
multiplication gate. Here, take the back edge and the iff coupling ensures
that we start with a new cycle from the multiplication gates output edge.
Finally, we will reach the root. As the depth is constant and every cycle
apart from the cycle in the $G^{\prime}$ is of depth at most constant, this is
a valid cycle cover. By construction the weight of this parse tree is the same
as the weight of the cycle cover.

Let us now look at a possible cycle cover. Let us start from the cycle of the
root. The cycle goes to the roots children and either hits an addition gate,
where it will take exactly one child or it hits a multiplication gate and
returns to the root. The multiplication gates iff-coupling ensures that all
the children have cycle cover. Repeat this until you have some inputs in the
cycle cover. As these are combined with $G^{\prime}$ by iff coupling, the
equivalence follows. By construction the weight of these cycle cover is the
same as the weight of the parse tree. ∎

## Acknowledgements

We thank Holger Dell for valuable comments on a first draft of this paper and
Radu Curticapean and Marc Roth for helpful discussions.

## References

  * [BES17] Markus Bläser, David Eisenbud, and Frank-Olaf Schreyer.  Ulrich complexity.  Differential Geometry and its Applications, 55:128–145, 2017.
  * [BHKK17] Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto.  Narrow sieves for parameterized paths and packings.  J. Comput. Syst. Sci., 87:119–139, 2017.  URL: https://doi.org/10.1016/j.jcss.2017.03.003, doi:10.1016/j.jcss.2017.03.003.
  * [BK78] Richard P. Brent and H. T. Kung.  Fast algorithms for manipulating formal power series.  J. ACM, 25(4):581–595, 1978.  URL: http://doi.acm.org/10.1145/322092.322099, doi:10.1145/322092.322099.
  * [Bür00a] Peter Bürgisser.  Completeness and Reduction in Algebraic Complexity Theory.  Springer, 2000.
  * [Bür00b] Peter Bürgisser.  Cook’s versus Valiant’s hypothesis.  Theor. Comput. Sci., 235(1):71–88, 2000.  URL: https://doi.org/10.1016/S0304-3975(99)00183-8, doi:10.1016/S0304-3975(99)00183-8.
  * [CDF+17] Radu Curticapean, Holger Dell, Fedor V. Fomin, Leslie Ann Goldberg, and John Lapinskas.  A fixed-parameter perspective on #BIS.  CoRR, abs/1702.05543, 2017.  URL: http://arxiv.org/abs/1702.05543, arXiv:1702.05543.
  * [CDM17] Radu Curticapean, Holger Dell, and Dániel Marx.  Homomorphisms are a good basis for counting small subgraphs.  In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 210–223. ACM, 2017.  URL: http://doi.acm.org/10.1145/3055399.3055502, doi:10.1145/3055399.3055502.
  * [CM14] Radu Curticapean and Dániel Marx.  Complexity of counting subgraphs: Only the boundedness of the vertex-cover number counts.  In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 130–139. IEEE Computer Society, 2014.  URL: https://doi.org/10.1109/FOCS.2014.22, doi:10.1109/FOCS.2014.22.
  * [CMM+13] Nadia Creignou, Arne Meier, Julian-Steffen Müller, Johannes Schmidt, and Heribert Vollmer.  Paradigms for parameterized enumeration.  In MFCS, volume 8087 of Lecture Notes in Computer Science, pages 290–301. Springer, 2013.
  * [CMR01] Bruno Courcelle, Johann A. Makowsky, and Udi Rotics.  On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic.  Discrete Applied Mathematics, 108(1-2):23–52, 2001.  URL: https://doi.org/10.1016/S0166-218X(00)00221-3, doi:10.1016/S0166-218X(00)00221-3.
  * [Cur13] Radu Curticapean.  Counting matchings of size $k$ is W[1]-hard.  In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, volume 7965 of Lecture Notes in Computer Science, pages 352–363. Springer, 2013.  URL: https://doi.org/10.1007/978-3-642-39206-1_30, doi:10.1007/978-3-642-39206-1_30.
  * [DF13] Rodney G. Downey and Michael R. Fellows.  Fundamentals of Parameterized Complexity.  Texts in Computer Science. Springer, 2013.
  * [FG04] Jörg Flum and Martin Grohe.  The parameterized complexity of counting problems.  SIAM J. Comput., 33(4):892–922, 2004.  URL: https://doi.org/10.1137/S0097539703427203, doi:10.1137/S0097539703427203.
  * [FG06] Jörg Flum and Martin Grohe.  Parameterized Complexity Theory.  Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006\.  URL: https://doi.org/10.1007/3-540-29953-X, doi:10.1007/3-540-29953-X.
  * [FKL07] Uffe Flarup, Pascal Koiran, and Laurent Lyaudet.  On the expressive power of planar perfect matching and permanents of bounded treewidth matrices.  In Takeshi Tokuyama, editor, Algorithms and Computation, 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007, Proceedings, volume 4835 of Lecture Notes in Computer Science, pages 124–136. Springer, 2007.  URL: https://doi.org/10.1007/978-3-540-77120-3_13, doi:10.1007/978-3-540-77120-3_13.
  * [GL99] Anna Galluccio and Martin Loebl.  On the theory of Pfaffian orientations. I. Perfect matchings and permanents.  Electr. J. Comb., 6, 1999.  URL: http://www.combinatorics.org/Volume_6/Abstracts/v6i1r6.html.
  * [GNW07] Jiong Guo, Rolf Niedermeier, and Sebastian Wernicke.  Parameterized complexity of vertex cover variants.  Theory Comput. Syst., 41(3):501–520, 2007.  URL: https://doi.org/10.1007/s00224-007-1309-3, doi:10.1007/s00224-007-1309-3.
  * [IM18] Christian Ikenmeyer and Stefan Mengel.  On the relative power of reduction notions in arithmetic circuit complexity.  Inf. Process. Lett., 130:7–10, 2018.  URL: https://doi.org/10.1016/j.ipl.2017.09.009, doi:10.1016/j.ipl.2017.09.009.
  * [JM17] Mark Jerrum and Kitty Meeks.  The parameterised complexity of counting even and odd induced subgraphs.  Combinatorica, 37(5):965–990, 2017.  URL: https://doi.org/10.1007/s00493-016-3338-5, doi:10.1007/s00493-016-3338-5.
  * [KP07a] Pascal Koiran and Sylvain Perifel.  VPSPACE and a transfer theorem over the complex field.  In Ludek Kucera and Antonín Kucera, editors, Mathematical Foundations of Computer Science 2007, 32nd International Symposium, MFCS 2007, Ceský Krumlov, Czech Republic, August 26-31, 2007, Proceedings, volume 4708 of Lecture Notes in Computer Science, pages 359–370. Springer, 2007.  URL: https://doi.org/10.1007/978-3-540-74456-6_33, doi:10.1007/978-3-540-74456-6_33.
  * [KP07b] Pascal Koiran and Sylvain Perifel.  VPSPACE and a transfer theorem over the reals.  In Wolfgang Thomas and Pascal Weil, editors, STACS 2007, 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007, Proceedings, volume 4393 of Lecture Notes in Computer Science, pages 417–428. Springer, 2007.  URL: https://doi.org/10.1007/978-3-540-70918-3_36, doi:10.1007/978-3-540-70918-3_36.
  * [Mah13] Meena Mahajan.  Algebraic complexity classes.  CoRR, abs/1307.3863, 2013.  URL: http://arxiv.org/abs/1307.3863, arXiv:1307.3863.
  * [MR09] Meena Mahajan and B. V. Raghavendra Rao.  Small-space analogues of Valiant’s classes.  In Miroslaw Kutylowski, Witold Charatonik, and Maciej Gebala, editors, Fundamentals of Computation Theory, 17th International Symposium, FCT 2009, Wroclaw, Poland, September 2-4, 2009. Proceedings, volume 5699 of Lecture Notes in Computer Science, pages 250–261. Springer, 2009.  URL: https://doi.org/10.1007/978-3-642-03409-1_23, doi:10.1007/978-3-642-03409-1_23.
  * [MS16] Meena Mahajan and Nitin Saurabh.  Some complete and intermediate polynomials in algebraic complexity theory.  In Alexander S. Kulikov and Gerhard J. Woeginger, editors, Computer Science - Theory and Applications - 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, Proceedings, volume 9691 of Lecture Notes in Computer Science, pages 251–265. Springer, 2016.  URL: https://doi.org/10.1007/978-3-319-34171-2_18, doi:10.1007/978-3-319-34171-2_18.
  * [Rin65] Gerhard Ringel.  Das Geschlecht des vollständigen paaren Graphen.  Abh. Math. Sem. Univ. Hamburg 28, pages 139–150, 1965.
  * [Rot17] Marc Roth.  Counting restricted homomorphisms via möbius inversion over matroid lattices.  In Kirk Pruhs and Christian Sohler, editors, 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, volume 87 of LIPIcs, pages 63:1–63:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.  URL: https://doi.org/10.4230/LIPIcs.ESA.2017.63, doi:10.4230/LIPIcs.ESA.2017.63.
  * [Str73] Volker Strassen.  Vermeidung von Divisionen.  J. Reine Angew. Math., 264:184–202, 1973.
  * [Thu07] Marc Thurley.  Kernelizations for parameterized counting problems.  In Jin-yi Cai, S. Barry Cooper, and Hong Zhu, editors, Theory and Applications of Models of Computation, 4th International Conference, TAMC 2007, Shanghai, China, May 22-25, 2007, Proceedings, volume 4484 of Lecture Notes in Computer Science, pages 703–714. Springer, 2007.  URL: https://doi.org/10.1007/978-3-540-72504-6_64, doi:10.1007/978-3-540-72504-6_64.
  * [Val79] Leslie G. Valiant.  Completeness classes in algebra.  In Michael J. Fischer, Richard A. DeMillo, Nancy A. Lynch, Walter A. Burkhard, and Alfred V. Aho, editors, Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1979, Atlanta, Georgia, USA, pages 249–261. ACM, 1979.  URL: http://doi.acm.org/10.1145/800135.804419, doi:10.1145/800135.804419.
  * [VW09] Virginia Vassilevska and Ryan Williams.  Finding, minimizing, and counting weighted subgraphs.  In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 455–464. ACM, 2009.  URL: http://doi.acm.org/10.1145/1536414.1536477, doi:10.1145/1536414.1536477.