# The Complexity of the Greedoid Tutte Polynomial

Christopher Knapp
Brunel University
Kingston Lane
Uxbridge, UK
<EMAIL_ADDRESS>Steven Noble
Birkbeck, University of London
Malet Street
London, UK
<EMAIL_ADDRESS>
###### Abstract

We consider the Tutte polynomial of three classes of greedoids: those arising
from rooted graphs, rooted digraphs and binary matrices. We establish the
computational complexity of evaluating each of these polynomials at each fixed
rational point $(x,y)$. In each case we show that evaluation is $\\#$P-hard
except for a small number of exceptional cases when there is a polynomial time
algorithm. In the binary case, establishing $\\#$P-hardness along one line
relies on Vertigan’s unpublished result on the complexity of counting bases of
a matroid. For completeness, we include an appendix providing a proof of this
result.

Mathematics Subject Classifications: 05C31, 68Q17, 05B35

##  1 Introduction

Tutte’s eponymous polynomial is perhaps the most widely studied two-variable
graph and matroid polynomial due to its many specializations, their vast
breadth and the richness of the underlying theory. Discussion of the Tutte
polynomial and closely related polynomials fills an entire handbook [13].
Tutte first introduced the Tutte polynomial of a graph, as the _dichromate_ in
[37]. It is closely related to Whitney’s rank generating function [43] which
Tutte extended from graphs to matroids in his PhD thesis [38]. Crapo [10]
later extended the definition of the Tutte polynomial to matroids. See Farr
[14] for more on the early history of the Tutte polynomial.

The simplest definition of the Tutte polynomial $T(G;x,y)$ of a graph $G$ is
probably in terms of the rank function $r$. Given a graph $G$ and set $A$ of
its edges, we have $r(A)=|V(G)|-k(G|A)$, where $k(G|A)$ is the number of
connected components of the graph obtained from $A$ by deleting the edges in
$E(G)-A$ (and keeping all the vertices).

######  Definition 1.

For a graph $G$ with edge set $E$, we have

$T(G;x,y)=\sum_{A\subseteq E}(x-1)^{r(E)-r(A)}(y-1)^{|A|-r(A)}.$

By making appropriate substitutions for $x$ and $y$, a huge number of graph
invariants with connections to diverse areas of mathematics may be obtained.
We summarise just a few of these evaluations that are particularly relevant
later in this paper. A _spanning subgraph_ of a graph $G$ is a subgraph
including all the vertices of $G$.

  * •

$T(G;1,1)$ is the number of maximal spanning forests of $G$. (If $G$ is
connected, then this is the number of spanning trees.)

  * •

$T(G;2,1)$ is the number of spanning forests of $G$.

  * •

$T(G;1,2)$ is the number of spanning subgraphs of $G$ having the same number
of components as $G$.

  * •

$T(G;1,0)$ is the number of acyclic orientations of $G$ with one predefined
source vertex per component of $G$ [21].

Other evaluations (up to a simple pre-factor) include the reliability
polynomial, chromatic polynomial and partition function of the $q$-state Potts
model. For a full list of evaluations see [8, 12, 13].

Given a graph polynomial of this type, a natural question is to determine its
complexity, that is to classify the points $(a,b)$ according to whether there
is a polynomial time algorithm to evaluate the polynomial at $(a,b)$ or
whether the evaluation is computationally intractable. Because of the inherent
difficulties of measuring the complexity of algorithms involving arbitrary
real numbers, we restrict $a$ and $b$ to being rational. This question was
completely resolved in a groundbreaking paper by Jaeger, Vertigan and Welsh
[23]. A stronger result was obtained by Vertigan and Welsh [41], who proved
the theorem below. For $\alpha$ in $\mathbb{Q}-\\{0\\}$, let
$H_{\alpha}=\\{(x,y)\in\mathbb{Q}^{2}:(x-1)(y-1)=\alpha\\}$, and let
$H_{0}^{x}=\\{(1,y):y\in\mathbb{Q}\\}$ and
$H_{0}^{y}=\\{(x,1):x\in\mathbb{Q}\\}$. This family of hyperbolae seems to
play a special role in the theory of the Tutte polynomial, both in terms of
its evaluations and its complexity.

######  Theorem 2 (Vertigan, Welsh).

Evaluating the Tutte polynomial of a bipartite planar graph at any fixed point
$(a,b)$ in the rational plane is $\\#$P-hard apart from when $(a,b)$ lies on
$H_{1}$ or $H_{2}$, or when $(a,b)$ equals $(-1,-1)$ or $(1,1)$, when there
exists a polynomial-time algorithm.

Roughly speaking, the proof of the hardness part of this result (at least
without the planar bipartite restriction) proceeds as follows. By exploiting a
result of Brylawski [7], one first shows that for most points $(a,b)$, the
existence of a polynomial time algorithm to evaluate $T(G;a,b)$ for every
graph $G$ would imply the existence of a polynomial time algorithm to evaluate
$T(G;x,y)$ at every point $(x,y)$ in $H_{\alpha}$, where $\alpha=(a-1)(b-1)$.
Given a graph $G$, let $G^{k}$ and $G_{k}$ denote, respectively, the graph
obtained by replacing every edge of $G$ by $k$ parallel edges and the graph
obtained by replacing every non-loop of $G$ by a path comprising $k$ edges and
every loop by a circuit comprising $k$ edges. The former is known as the _$k$
-thickening_ of $G$ and the latter as the _$k$ -stretch_ of $G$. Brylawski
gave expressions for the Tutte polynomials of $G^{k}$ and $G_{k}$ in terms of
the Tutte polynomial of $G$. By varying $k$, one may obtain expressions for
$T(G;a_{k},b_{k})$ at a sequence $\\{(a_{k},b_{k})\\}$ of points on
$H_{\alpha}$, and then solve for the coefficients of the one-variable
polynomial obtained by restricting the domain of $T$ to $H_{\alpha}$. There
remain several special cases because the sequence $\\{(a_{k},b_{k})\\}$
sometimes contains only a small number of distinct points. The second step
proceeds by determining a $\\#$P-hard point on each curve $H_{\alpha}$. Many
of these come from evaluations of the chromatic polynomial.

The Tutte polynomial is essentially a generating function for the number of
subsets of the edges of a graph according to their rank and size. Following
the work of Jaeger, Vertigan and Welsh, many authors have established
corresponding results for a variety of graph polynomials defined in a similar
way but using different notions of rank. These include the cover polynomial
[3], the Bollobás–Riordan polynomial [4], the interlace polynomial [5], the
rank generating function of a graphic $2$-polymatroid [32] and the Tutte
polynomial of a bicircular matroid [16]. In each case, the proof techniques
have some similarities: the bulk of the work is done using a graph operation
analogous to the thickening, but there are considerable technical difficulties
required to deal with the special cases and to complete the proof. These
results provide evidence for Makowsky’s Difficult Point Conjecture which
states that for an $n$-variable graph polynomial $P$ that may be defined in
monadic second order logic, there is a set $S$ of points with the following
properties:

  1. 1.

For every $\mathbf{x}\in S$, there is a polynomial time algorithm to evaluate
$P(\mathbf{x})$;

  2. 2.

For every $\mathbf{x}\notin S$, it is $\\#$P-hard to evaluate $P(\mathbf{x})$;

  3. 3.

The set $S$ is the finite union of algebraic sets in $\mathbb{C}^{n}$ each
having dimension strictly less than $n$.

For full details see [30].

In this paper we prove results analogous to Theorem 2 for two graph
polynomials, the Tutte polynomials of a rooted graph and a rooted digraph, and
a polynomial of binary matrices, the Tutte polynomial of a binary greedoid.
Each of these polynomials is a special case of the Tutte polynomial of a
greedoid introduced by Gordon and McMahon [18] and the proofs have
considerable commonality. (All the necessary definitions are provided in the
next sections.) The graph polynomials are the analogue of the Tutte polynomial
for rooted graphs and rooted digraphs, and our results provide further
evidence for Makowsky’s Difficult Point Conjecture.

An overview of the paper is as follows. In Section 2 we provide necessary
background on rooted graphs, rooted digraphs, greedoids and computational
complexity. In the following section we describe the Tutte polynomial of a
greedoid and list some of its evaluations for each of the three classes of
greedoid that we work with. Within our hardness proofs we require an analogue
of the thickening operation and various other constructions which can be
defined for arbitrary greedoids, and may be of independent interest. We
describe these in Section 4 and provide analogues of Brylawski’s results [7]
expressing the Tutte polynomial for these constructions in terms of the Tutte
polynomials of their constituent greedoids.

In Section 5, we prove the following result completely determining the
complexity of evaluating the Tutte polynomial of a rooted graph at a rational
point.

######  Theorem 3.

Evaluating the Tutte polynomial of a connected, rooted, planar, bipartite
graph at any fixed point $(a,b)$ in the rational $xy$-plane is $\\#$P-hard
apart from when $(a,b)$ equals $(1,1)$ or when $(a,b)$ lies on $H_{1}$.

There are polynomial time algorithms to evaluate the Tutte polynomial of a
rooted graph at $(1,1)$ and at any point lying on $H_{1}$.

In Section 6, we prove the equivalent result for the Tutte polynomial of a
rooted digraph.

######  Theorem 4.

Evaluating the Tutte polynomial of a root-connected, rooted digraph at any
fixed point $(a,b)$ in the rational $xy$-plane is $\\#$P-hard apart from when
$(a,b)$ equals $(1,1)$, when $(a,b)$ lies on $H_{1}$, or when $b=0$.

There are polynomial time algorithms to evaluate the Tutte polynomial of a
rooted digraph at $(1,1)$, at any point lying on $H_{1}$ and at any point
$(a,0)$.

We then determine the complexity of evaluating the Tutte polynomial of a
binary greedoid.

######  Theorem 5.

Evaluating the Tutte polynomial of a binary greedoid at any fixed point
$(a,b)$ in the rational $xy$-plane is $\\#$P-hard apart from when $(a,b)$ lies
on $H_{1}$.

There is a polynomial time algorithm to evaluate the Tutte polynomial of a
binary greedoid at any point lying on $H_{1}$.

One special case of this theorem depends on a special case of an unpublished
result of Vertigan, who proved that the problem of counting bases of a binary
matroid is $\\#$P-complete. For completeness, in Appendix A, we provide a
proof of this result for all fields.

##  2 Preliminaries

###  2.1 Rooted graphs and digraphs

All our graphs are allowed to have loops and multiple edges. A _rooted graph_
is a graph with a distinguished vertex called the _root_. Most of the graphs
we work with will be rooted but occasionally we will work with a graph without
a root. For complete clarity, we will sometimes refer to such graphs as
_unrooted graphs_. We denote a rooted graph $G$ with vertex set $V(G)$, edge
set $E(G)$ and root $r(G)$ by a triple $(V(G),E(G),r(G))$. We omit the
arguments when there is no fear of ambiguity. Many of the standard definitions
for graphs can be applied to rooted graphs in the natural way. Two rooted
graphs $(V,E,r)$ and $(V^{\prime},E^{\prime},r^{\prime})$ are _isomorphic_ if
the unrooted graphs $(V,E)$ and $(V^{\prime},E^{\prime})$ are isomorphic via
an isomorphism mapping $r$ to $r^{\prime}$. For a subset $A$ of $E$, the
_rooted spanning subgraph_ $G|A$ is formed from $G$ by deleting all the edges
in $E-A$ (and keeping all the vertices). The _root component_ of $G$ is the
connected component of $G$ containing the root. A set $A$ of edges of $G$ is
_feasible_ if the root component of $G|A$ is a tree and contains every edge of
$A$. We define the _rank_ $\rho_{G}(A)$ of $A$ to be

$\rho_{G}(A)=\max\\{|A^{\prime}|:A^{\prime}\subseteq A,A\text{ is
feasible}\\}.$

We omit the subscript when the context is clear. We let $\rho(G)=\rho(E)$.
Observe that a set $A$ of edges is feasible if and only if $\rho(A)=|A|$. A
feasible set is a _basis_ if $\rho(A)=\rho(G)$. So $A$ is a basis of $G$ if
and only if it is the edge set of a spanning tree of the root component of
$G$.

A _rooted digraph_ is a digraph with a distinguished vertex called the _root_.
We denote a rooted digraph $D$ with vertex set $V(D)$, edge set $E(D)$ and
root $r(D)$ by a triple $(V(D),E(D),r(D))$. Once again we omit the arguments
when there is no chance of ambiguity. Two rooted digraphs $(V,E,r)$ and
$(V^{\prime},E^{\prime},r^{\prime})$ are _isomorphic_ if the unrooted digraphs
$(V,E)$ and $(V^{\prime},E^{\prime})$ are isomorphic via an isomorphism
mapping $r$ to $r^{\prime}$. We say that the _underlying rooted graph_ of a
rooted digraph is the rooted graph we get when we remove all the directions on
the edges. For a subset $A$ of $E$, the _rooted spanning subdigraph_ $D|A$ is
formed from $D$ by deleting all the edges in $E-A$. The _root component_ of
$D$ is formed by deleting every vertex $v$ to which there is no directed path
from $r$ in $D$, together with its incident edges. The rooted digraph is
_root-connected_ if there is a directed path from the root to every other
vertex. The rooted digraph $D$ is an _arborescence rooted at $r$_ if $D$ is
root-connected and its underlying rooted graph is a tree. Observe that a set
$A$ of edges of $D$ is _feasible_ if and only if the root component of $D|A$
is an arborescence rooted at $r$ and contains every edge of $A$. The _rank_
$\rho_{D}(A)$ of $A$ is defined by

$\rho_{D}(A)=\max\\{|A^{\prime}|:A^{\prime}\subseteq A,D|A^{\prime}\text{ is
feasible}\\}.$

We can omit the subscript when the context is clear. We let $\rho(D)=\rho(E)$.
A set $A$ of edges is feasible if and only if $\rho(A)=|A|$. A feasible set is
a _basis_ if $\rho(A)=\rho(D)$. So $A$ is a basis of $D$ if and only if it is
the edge set of an arborescence rooted at $r$ that includes every vertex of
the root component of $D$.

###  2.2 Greedoids

Greedoids are generalizations of matroids, first introduced by Korte and
Lovász in 1981 in [26]. The aim was to generalize the characterization of
matroids as hereditary set systems on which the greedy algorithm is guaranteed
to determine the optimal member of the set system, according to an arbitrary
weighting. Most of the information about greedoids which we summarise below
can be found in [2] or [29].

######  Definition 6.

A _greedoid_ $\Gamma$ is an ordered pair $(E,\mathcal{F})$ consisting of a
finite set $E$ and a non-empty collection $\mathcal{F}$ of subsets of $E$
satisfying the following axioms:

  1. (G1)

$\emptyset\in\mathcal{F}$.

  2. (G2)

For all $F$ and $F^{\prime}$ in $\mathcal{F}$ with $|F^{\prime}|<|F|$ there
exists some $x\in F-F^{\prime}$ such that $F^{\prime}\cup x\in\mathcal{F}$.

The set $E$ is _ground set_ of $\Gamma$ and the members of $\mathcal{F}$ are
the _feasible sets_ of $\Gamma$. The axioms are the first and third of the
usual axioms specifying a matroid in terms of its independent sets, so clearly
every matroid is a greedoid, but a greedoid does not necessarily satisfy the
hereditary property satisfied by the independent sets of a matroid requiring
that the collection of independent sets is closed under taking subsets. The
_rank_ $\rho_{\Gamma}(A)$ of a subset $A$ of $E$ is given by

$\rho_{\Gamma}(A)=\max\\{|A^{\prime}|:A^{\prime}\subseteq
A,A^{\prime}\in\mathcal{F}\\}$

and we let $\rho(\Gamma)=\rho_{\Gamma}(E)$. We omit the subscript when the
context is clear. Notice that a set $A$ is feasible if and only if
$\rho(A)=|A|$. A feasible set is a _basis_ if $\rho(A)=\rho(\Gamma)$. We
denote the collection of bases of $\Gamma$ by $\mathcal{B}(\Gamma)$. Axiom
(G2) implies that every basis has the same cardinality. Note that the rank
function determines $\Gamma$ but the collection of bases does not. For
example, suppose that a greedoid has ground set $\\{1,2\\}$ and unique basis
$\\{1,2\\}$. Then its collection of feasible sets could either be
$\\{\emptyset,\\{1\\},\\{1,2\\}\\}$, $\\{\emptyset,\\{2\\},\\{1,2\\}\\}$ or
$\\{\emptyset,\\{1\\},\\{2\\},\\{1,2\\}\\}$.

The rank function of a greedoid can be characterized in a similar way to the
rank function of a matroid [27].

######  Proposition 7.

The rank function $\rho$ of a greedoid with ground set $E$ takes integer
values and satisfies each of the following.

  1. (GR1)

For every subset $A$ of $E$, $0\leq\rho(A)\leq|A|$;

  2. (GR2)

For all subsets $A$ and $B$ of $E$ with $A\subseteq B$, $\rho(A)\leq\rho(B)$;

  3. (GR3)

For every subset $A$ of $E$, and elements $e$ and $f$, if $\rho(A)=\rho(A\cup
e)=\rho(A\cup f)$, then $\rho(A)=\rho(A\cup e\cup f)$.

Moreover if $E$ is a finite set and $\rho$ is a function from the subsets of
$E$ to the integers, then $\rho$ is the rank function of a greedoid with
ground set $E$ if and only if $\rho$ satisfies conditions (GR1)–(GR3) above.

The following lemma is easily proved using induction on $|B|$ and will be
useful later.

######  Lemma 8.

Let $(E,\rho)$ be a greedoid specified by its rank function and let $A$ and
$B$ be subsets of $E$ such that for all $b\in B$, $\rho(A\cup b)=\rho(A)$.
Then $\rho(A\cup B)=\rho(A)$.

Two greedoids $\Gamma_{1}=(E_{1},\mathcal{F}_{1})$ and
$\Gamma_{2}=(E_{2},\mathcal{F}_{2})$ are _isomorphic_ , denoted by
$\Gamma_{1}\cong\Gamma_{2}$, if there exists a bijection $f:E_{1}\rightarrow
E_{2}$ that preserves the feasible sets.

The following two examples of greedoids were introduced in [28]. Let $G$ be a
rooted graph. Take $\Gamma=(E,\mathcal{F})$ so that $E=E(G)$ and a subset $A$
of $E$ is in $\mathcal{F}$ if and only if the root component of $G|A$ is a
tree containing every edge of $A$. Then $\Gamma$ is a greedoid. Any greedoid
which is isomorphic to a greedoid arising from a rooted graph in this way is
called a _branching greedoid_. The branching greedoid of a rooted graph $G$ is
denoted by $\Gamma(G)$.

Similarly suppose we have a rooted digraph $D$ and take
$\Gamma=(E,\mathcal{F})$ so that $E={E}(D)$ and a subset $A$ of $E$ is in
$\mathcal{F}$ if and only if the root component of $D|A$ is an arborescence
rooted at $r$ and contains every edge of $A$. Then $\Gamma$ is a greedoid. Any
greedoid which is isomorphic to a greedoid arising from a rooted digraph in
this way is called a _directed branching greedoid_. The directed branching
greedoid of a rooted digraph $D$ is denoted by $\Gamma(D)$. (There should be
no ambiguity with the overload of notation for a branching greedoid and a
directed branching greedoid.)

Notice that for both rooted graphs and digraphs, the concepts of feasible set,
basis and rank are compatible with their definitions for the associated
branching greedoid or directed branching greedoid in the sense that a set $A$
of edges is feasible in a rooted graph $G$ if and only if it is feasible in
$\Gamma(G)$, and similarly for the other concepts.

We now define the class of _binary greedoids_. These are a special case of a
much broader class, the _Gaussian elimination greedoids_ , introduced by
Goecke in [17], motivated by the Gaussian elimination algorithm. Let $M$ be an
$m\times n$ binary matrix. It is useful to think of the rows and columns of
$M$ as being labelled by the elements of $[m]$ and $[n]$ respectively, where
$[n]=\\{1,\ldots,n\\}$. If $X$ is a subset of $[m]$ and $Y$ is a subset of
$[n]$, then $M_{X,Y}$ denotes the matrix obtained from $M$ by deleting all the
rows except those with labels in $X$ and all the columns except those with
labels in $Y$. Take $\Gamma=([n],\mathcal{F})$, so that

$\mathcal{F}=\\{A\subseteq[n]:\text{ the submatrix $M_{[|A|],A}$ is non-
singular}\\}.$

By convention, the empty matrix is considered to be non-singular. Then
$\Gamma$ is a greedoid. Any greedoid which is isomorphic to a greedoid arising
from a binary matrix in this way is called a _binary greedoid_. The binary
greedoid of a binary matrix $M$ is denoted by $\Gamma(M)$.

######  Example 9.

Let

$M=\bordermatrix{~{}&1&2&3&4\cr~{}&1&0&0&1\cr~{}&1&0&1&0\cr~{}&0&1&1&1\cr}.$

The binary greedoid $\Gamma(M)$ has ground set $\\{1,2,3,4\\}$ and feasible
sets

$\\{\emptyset,\\{1\\},\\{4\\},\\{1,3\\},\\{1,4\\},\\{3,4\\},\\{1,2,3\\},\\{1,2,4\\},\\{2,3,4\\}\\}.$

The following lemma is clear.

######  Lemma 10.

Let $E=[n]$, let $M$ be an $m\times n$ binary matrix with columns labelled by
$E$ and let $M^{\prime}$ be obtained from $M$ by adding row $i$ to row $j$,
where $i<j$. Then $\Gamma(M^{\prime})\cong\Gamma(M)$.

A consequence of this lemma is that if $\Gamma$ is a binary greedoid, then
there is a binary matrix $M$ with linearly independent rows so that
$\Gamma=\Gamma(M)$. With this in mind we easily obtain the following result
which will be useful later.

######  Lemma 11.

Let $\Gamma$ be a binary greedoid. Then there is a binary matroid $M$ so that
$\mathcal{B}(M)=\mathcal{B}(\Gamma)$.

In contrast with the situation in matroids, where every graphic matroid is
binary, it is not the case that every branching greedoid is binary. For
example, take $G$ to be the star with four vertices in which the central
vertex is the root. Then $\Gamma(G)$ is not binary. The same example but with
the edges directed away from the root demonstrates that not every directed
branching greedoid is binary.

An element of a greedoid is a _loop_ if it does not belong to any feasible
set. So if $G$ is a rooted graph then an edge $e$ is a loop of $\Gamma(G)$ if
it does not lie on any path from the root and if $G$ is connected then it is
just a loop in the normal graph-theoretic sense. Similarly if $D$ is a
directed rooted graph then an edge $e$ is a loop of $\Gamma(D)$ if it does not
lie on any directed path from the root. As the concepts of loops in greedoids
and in rooted graphs and digraphs do not completely coincide, we use the term
_greedoid loop_ whenever there is potential for confusion.

Let $\Gamma$ be a greedoid with ground set $E$ and rank function $\rho$.
Elements $e$ and $f$ of $E$ are said to be _parallel_ in $\Gamma$ if for all
subsets $A$ of $E$,

$\rho(A\cup e)=\rho(A\cup f)=\rho(A\cup e\cup f).$

As far as we are aware, the following elementary lemma does not seem to have
been stated before.

######  Lemma 12.

Let $\Gamma$ be a greedoid. Define a relation $\bowtie$ on the ground set of
$\Gamma$ by $e\bowtie f$ if $e$ and $f$ are parallel in $\Gamma$. Then
$\bowtie$ is an equivalence relation and if $\Gamma$ has at least one loop,
then one of the equivalence classes of $\bowtie$ comprises the set of loops.

###### Proof.

The only part of the lemma that is not immediately obvious is that $\bowtie$
is transitive. Let $\rho$ be the rank function of $\Gamma$ and $e$, $f$ and
$g$ be elements of $\Gamma$, so that $e\bowtie f$ and $f\bowtie g$. Then for
any subset $A$ of elements of $\Gamma$, we have $\rho(A\cup e)=\rho(A\cup
f)=\rho(A\cup e\cup f)$ and $\rho(A\cup f)=\rho(A\cup g)=\rho(A\cup f\cup g)$.
Thus $\rho(A\cup e)=\rho(A\cup g)$. By applying Lemma 8 to $A\cup f$ and
elements $e$ and $g$, we see that $\rho(A\cup e\cup f\cup g)=\rho(A\cup f)$.
Thus, by (GR2), $\rho(A\cup f)=\rho(A\cup e\cup f\cup g)\geq\rho(A\cup e\cup
g)\geq\rho(A\cup e)$. But as $\rho(A\cup e)=\rho(A\cup f)$, equality must hold
throughout, so $\rho(A\cup e\cup g)=\rho(A\cup e)=\rho(A\cup g)$, as required.
∎

###  2.3 Complexity

We assume some familiarity with computational complexity and refer the reader
to one of the standard texts such as [15] or [34] for more background. Given
two computational problems $\pi_{1}$ and $\pi_{2}$, we say that $\pi_{2}$ is
_Turing reducible_ to $\pi_{1}$ if there exists a deterministic Turing machine
solving $\pi_{2}$ in polynomial time using an oracle for $\pi_{1}$, that is a
subroutine returning an answer to an instance of $\pi_{1}$ in constant-time.
When $\pi_{2}$ is Turing reducible to $\pi_{1}$ we write
$\pi_{2}\propto_{T}\pi_{1}$ and we say that solving problem $\pi_{1}$ is at
least as hard as solving problem $\pi_{2}$. The relation $\propto_{T}$ is
transitive.

Informally, the class $\\#$P is the counting analogue of NP, that is, the
class of all counting problems corresponding to decision problems in NP.
Slightly more precisely, a problem is in $\\#$P if it counts the number of
accepting computations or “witnesses” of a problem in NP. Consider the
decision problem of determining whether a graph has a proper vertex
$3$-colouring. The obvious non-deterministic algorithm for this problem
interprets a “witness” as a colouring of the vertices with $3$ colours and
verifies that it is a proper colouring. So the corresponding problem in $\\#$P
would be to determine the number of proper vertex $3$-colourings. A
computational problem $\pi$ is said to be _$\\#$ P-hard_ if
$\pi^{\prime}\propto_{T}\pi$ for all $\pi^{\prime}\in\\#\text{P}$, and _$\\#$
P-complete_ if, in addition, $\pi\in\\#\text{P}$. Counting the number of
vertex $3$-colourings of a graph is an example of an $\\#$P-complete problem.

The following lemma is crucial in many of our proofs.

######  Lemma 13.

There is an algorithm which when given a non-singular integer $n\times n$
matrix $A$ and an integer $n$-vector $b$ such that the absolute value of every
entry of $A$ and $b$ is at most $2^{l}$, outputs the vector $x$ so that
$Ax=b$, running in time bounded by a polynomial in $n$ and $l$.

One algorithm to do this is a variant of Gaussian elimination known as the
Bareiss algorithm [1]. Similar ideas were presented by Edmonds [11]. See also
[22].

##  3 The Tutte Polynomial of a Greedoid

Extending the definition of the Tutte polynomial of a matroid, McMahon and
Gordon defined the Tutte polynomial of a greedoid in [18]. The _Tutte
polynomial_ of a greedoid $\Gamma$ with ground set $E$ and rank function
$\rho$ is given by

$T(\Gamma;x,y)=\sum_{A\subseteq
E}(x-1)^{\rho(\Gamma)-\rho(A)}(y-1)^{|A|-\rho(A)}.$

When $\Gamma$ is a matroid, this reduces to the usual definition of the Tutte
polynomial of a matroid. For a rooted graph $G$ we let
$T(G;x,y)=T(\Gamma(G);x,y)$, for a rooted digraph $D$ we let
$T(D;x,y)=T(\Gamma(D);x,y)$ and for a binary matrix $M$ we let
$T(M;x,y)=T(\Gamma(M);x,y)$.

######  Example 14.

  1. 1.

Let $P_{k}$ be the rooted (undirected) path with $k$ edges in which the root
is one of the leaves. Then

$T(P_{k};x,y)=1+\sum_{i=1}^{k}(x-1)^{i}y^{i-1}.$

  2. 2.

Let $S_{k}$ be the rooted (undirected) star with $k$ edges in which the root
is the central vertex. Then

$T(S_{k};x,y)=x^{k}.$

The Tutte polynomial of a greedoid retains many of the properties of the Tutte
polynomial of a matroid, for example, it has a delete–contract recurrence,
although its form is not as simple as that of the Tutte polynomial of a
matroid [18]. Moreover, for a greedoid $\Gamma$:

  * •

$T(\Gamma;1,1)$ is the number of bases of $\Gamma$;

  * •

$T(\Gamma;2,1)$ is the number of feasible sets of $\Gamma$;

  * •

$T(\Gamma;1,2)$ is the number of subsets $A$ of elements of $\Gamma$ so that
$\rho(A)=\rho(\Gamma)$.

  * •

$T(\Gamma;2,2)=2^{|E(\Gamma)|}$.

But the Tutte polynomial of a greedoid also differs fundamentally from the
Tutte polynomial of a matroid, for instance, unlike the Tutte polynomial of a
matroid, the Tutte polynomial of a greedoid can have negative coefficents. For
example, $T(\Gamma(P_{2});x,y)=x^{2}y-2xy+x+y$.

The Tutte polynomial of a rooted graph has some of the same evaluations as the
Tutte polynomial of a unrooted graph. Let $G$ be a rooted graph with edge set
$E$.

  * •

$T(G;1,1)$ is the number of spanning trees of the root component of $G$. (When
$G$ is connected, this is just the number of spanning trees of $G$.)

  * •

$T(G;2,1)$ is the number of subsets $A$ of $E$, so that the root component of
$G|A$ is a tree containing all the edges of $A$.

  * •

$T(G;1,2)$ is the number of subsets $A$ of $E$ so that the root component of
$G|A$ includes every vertex of the root component of $G$. (When $G$ is
connected, this is just the number of subsets $A$ so that $G|A$ is connected.)

  * •

If no component of $G$ other than the root component has edges, then
$T(G;1,0)$ is the number of acyclic orientations of $G$ with a unique source.
Otherwise $T(G;1,0)=0$.

We record the following proposition stating that the Tutte polynomial of a
connected rooted graph $G$ coincides with the Tutte polynomial of the
corresponding unrooted graph $G^{\prime}$ along the line $x=1$. This is easy
to prove by noting that $\rho(G)=r(G^{\prime})$ and a subset $A$ of the edges
of $G$ satisfies $\rho(A)=\rho(G)$ if and only if $r(A)=r(G^{\prime})$.

######  Proposition 15.

Let $G=(V,E,r)$ be a connected rooted graph and let $G^{\prime}=(V,E)$ be the
corresponding unrooted graph. Then

$T(G;1,y)=T(G^{\prime};1,y).$

We list some evaluations of the Tutte polynomial of a digraph. Let $D$ be a
rooted digraph with edge set $E$ and root $r$.

  * •

$T(D;1,1)$ is the number of spanning arborescences of the root component of
$D$ rooted at $r$. (When $D$ is root-connected, this is just its number of
spanning arborescences rooted at $r$.)

  * •

$T(D;2,1)$ is the number of subsets $A$ of $E$, so that the root component of
$D|A$ is an arborescence rooted at $r$ containing every edge of $A$.

  * •

$T(D;1,2)$ is the number of subsets $A$ of $E$, so that the root component of
$D|A$ includes every vertex of the root component of $D$. (When $D$ is
connected, this is just the number of subsets $A$ so that $D|A$ is root-
connected.)

  * •

$T(D;1,0)=1$ if $D$ is acyclic and root-connected, and $0$ otherwise.

The last evaluation will be discussed in more detail in Section 6.

Gordon and McMahon [18] proved that if $T_{1}$ and $T_{2}$ are rooted
arborescences, then $T(T_{1};x,y)=T(T_{2};x,y)$ if and only if $T_{1}\cong
T_{2}$.

We list some evaluations of the Tutte polynomial of a binary matroid. Let $M$
be an $m\times n$ binary matrix with linearly independent rows.

  * •

$T(M;1,1)$ is the number of subsets $A$ of the columns of $M$ so that the
submatrix of $M$ corresponding to the columns in $A$ is non-singular.

  * •

$T(M;2,1)$ is the number of subsets $A$ of the columns of $M$ so that the
submatrix $M_{[|A|],A}$ is non-singular.

  * •

$T(M;1,2)$ is the number of subsets $A$ of the columns of $M$ containing a
subset $A^{\prime}$ so that the submatrix of $M$ corresponding to the columns
in $A^{\prime}$ is non-singular.

If a point $(a,b)$ lies on the hyperbola $H_{1}$ then we have $(a-1)(b-1)=1$
by definition. Thus the Tutte polynomial of a greedoid $\Gamma$ evaluated at
such a point is given by

$\displaystyle T(\Gamma;a,b)$ $\displaystyle=\sum_{A\subseteq
E(\Gamma)}(a-1)^{\rho(\Gamma)-\rho(A)}(b-1)^{|A|-\rho(A)}$
$\displaystyle=(a-1)^{\rho(\Gamma)}\sum_{A\subseteq
E(\Gamma)}\left(\frac{1}{a-1}\right)^{|A|}=(a-1)^{\rho(\Gamma)-|E(\Gamma)|}a^{|E(\Gamma)|}.$

Therefore, given $|E(\Gamma)|$ and $\rho(\Gamma)$, it is easy to compute
$T(\Gamma;a,b)$ in polynomial time. For all of the greedoids that we consider,
both $|E(\Gamma)|$ and $\rho(\Gamma)$ will be either known or easily computed.

The _characteristic polynomial_ of a greedoid was first introduced by Gordon
and McMahon in [19] and is a generalization of the characteristic or chromatic
polynomial of a matroid. For a greedoid $\Gamma$, the _characteristic
polynomial_ $p(\Gamma;\lambda)$ is defined by

$p(\Gamma;\lambda)=(-1)^{\rho(\Gamma)}T(\Gamma;1-\lambda,0).$ (1)

##  4 Greedoid Constructions

In this section we introduce three greedoid constructions and give expressions
for the Tutte polynomial of greedoids resulting from these constructions.

The first construction is just the generalization of the $k$-thickening
operation introduced by Brylawski [7] from matroids to greedoids. Given a
greedoid $\Gamma=(E,\mathcal{F})$, its $k$-thickening is the greedoid
$\Gamma^{k}$ that, informally speaking, is formed from $\Gamma$ by replacing
each element by $k$ parallel elements. More precisely, $\Gamma^{k}$ has ground
set $E^{\prime}=E\times[k]$ and collection $\mathcal{F}^{\prime}$ of feasible
sets as follows. Define $\mu$ to be the projection operator
$\mu:2^{E\times[k]}\rightarrow 2^{E}$ so that element $e\in\mu(A)$ if and only
if $(e,i)\in A$ for some $i$. Now a subset $A$ is feasible in $\Gamma^{k}$ if
and only if $\mu(A)$ is feasible in $\Gamma$ and $|\mu(A)|=|A|$. The latter
condition ensures that $A$ does not contain more than one element replacing a
particular element of $\Gamma$.

It is clear that $\Gamma^{k}$ is a greedoid and moreover
$\rho_{\Gamma^{k}}(A)=\rho_{\Gamma}(\mu(A))$. In particular
$\rho(\Gamma^{k})=\rho(\Gamma)$. For any element $e$ of $\Gamma$ the elements
$(e,i)$ and $(e,j)$ are parallel. The effect of the $k$-thickening operation
on the Tutte polynomial of a greedoid is given in the following theorem,
generalizing the expression for the $k$-thickening of the Tutte polynomial
given by Brylawski [7].

######  Theorem 16.

Let $\Gamma$ be a greedoid. The Tutte polynomial of the $k$-thickening
$\Gamma^{k}$ of $\Gamma$ when $y\neq-1$ is given by

$T(\Gamma^{k};x,y)=(1+y+\cdots+y^{k-1})^{\rho_{G}(\Gamma)}T\left(\Gamma;\frac{x+y+\cdots+y^{k-1}}{1+y+\cdots+y^{k-1}},y^{k}\right).$
(2)

When $y=-1$ we have

$T(\Gamma^{k};x,-1)=\begin{cases}(x-1)^{\rho_{G}(\Gamma)}&\text{if $k$ is
even; }\\\ T(\Gamma;x,-1)&\text{if $k$ is odd. }\end{cases}$

###### Proof.

Let $\Gamma^{k}$ be the $k$-thickened greedoid, let $E^{\prime}$ denote its
ground set and let $E$ be the ground set of $\Gamma$. Then
$E^{\prime}=E\times[k]$. Let $\mu$ be the mapping defined in the discussion at
the beginning of this section. To ensure that we do not divide by zero in our
calculations, we prove the case when $y=1$ separately.

For each $A^{\prime}\subseteq E^{\prime}$ we have
$\rho_{\Gamma^{k}}(A^{\prime})=\rho_{\Gamma}(\mu(A^{\prime}))$ and furthermore
$\rho(\Gamma^{k})=\rho(\Gamma)$. The Tutte polynomial of $\Gamma^{k}$ when
$y\notin\\{-1,1\\}$ is thus given by

$\displaystyle T(\Gamma^{k};x,y)$ $\displaystyle=\sum_{A^{\prime}\subseteq
E^{\prime}}(x-1)^{\rho(\Gamma^{k})-\rho_{\Gamma^{k}}(A^{\prime})}(y-1)^{|A^{\prime}|-\rho_{\Gamma^{k}}(A^{\prime})}$
$\displaystyle=\sum_{A\subseteq E}\sum_{\begin{subarray}{c}A^{\prime}\subseteq
E^{\prime}:\\\
\mu(A^{\prime})=A\end{subarray}}(x-1)^{\rho(\Gamma)-\rho_{\Gamma}(\mu(A^{\prime}))}(y-1)^{|A^{\prime}|-\rho_{\Gamma}(\mu(A^{\prime}))}$
(3) $\displaystyle=\sum_{A\subseteq
E}(x-1)^{\rho(\Gamma)-\rho_{\Gamma}(A)}(y-1)^{-\rho_{\Gamma}(A)}\sum_{\begin{subarray}{c}A^{\prime}\subseteq
E^{\prime}:\\\ \mu(A^{\prime})=A\end{subarray}}(y-1)^{|A^{\prime}|}$
$\displaystyle=\sum_{A\subseteq
E}(x-1)^{\rho(\Gamma)-\rho_{\Gamma}(A)}(y-1)^{-\rho_{\Gamma}(A)}(y^{k}-1)^{|A|}$
$\displaystyle=(1+y+\cdots+y^{k-1})^{\rho(\Gamma)}\sum_{A\subseteq
E}\left(\frac{(x-1)(y-1)}{y^{k}-1}\right)^{\rho(\Gamma)-\rho_{\Gamma}(A)}(y^{k}-1)^{|A|-\rho_{\Gamma}(A)}$
$\displaystyle=(1+y+\cdots+y^{k-1})^{\rho(\Gamma)}T\left(\Gamma;\frac{x+y+\cdots+y^{k-1}}{1+y+\cdots+y^{k-1}},y^{k}\right).$

When $y=1$ we get non-zero terms in Equation 3 if and only if
$|A^{\prime}|=\rho_{\Gamma}(\mu(A^{\prime}))$, which implies that
$|A^{\prime}|=|A|$. For each $A\subseteq E$ there are $k^{|A|}$ choices for
$A^{\prime}$ such that $\mu(A^{\prime})=A$ and $|A^{\prime}|=|A|$. Therefore
we have

$\displaystyle T(\Gamma^{k};x,1)$
$\displaystyle=\sum_{\begin{subarray}{c}A\subseteq E:\\\
\rho_{\Gamma}(A)=|A|\end{subarray}}(x-1)^{\rho(\Gamma)-\rho_{\Gamma}(A)}\sum_{\begin{subarray}{c}A^{\prime}\subseteq
E^{\prime}:\\\ \mu(A^{\prime})=A,\\\
|A^{\prime}|=|A|\end{subarray}}1=\sum_{\begin{subarray}{c}A\subseteq E:\\\
\rho_{\Gamma}(A)=|A|\end{subarray}}(x-1)^{\rho(\Gamma)-\rho_{\Gamma}(A)}k^{\rho_{\Gamma}(A)}$
$\displaystyle=\sum_{\begin{subarray}{c}A\subseteq E:\\\
\rho_{\Gamma}(A)=|A|\end{subarray}}\left(\frac{x-1}{k}\right)^{\rho(\Gamma)-\rho_{\Gamma}(A)}k^{\rho(\Gamma)}=k^{\rho(\Gamma)}T\left(\Gamma;\frac{x+k-1}{k},1\right)$

which agrees with Equation 2 when $y=1$.

When $y=-1$ we have

$\displaystyle T(\Gamma^{k};x,-1)$ $\displaystyle=\sum_{A\subseteq
E}\sum_{\begin{subarray}{c}A^{\prime}\subseteq E^{\prime}:\\\
\mu(A^{\prime})=A\end{subarray}}(x-1)^{\rho(\Gamma)-\rho_{\Gamma}(\mu(A^{\prime}))}(-2)^{|A^{\prime}|-\rho_{\Gamma}(\mu(A^{\prime}))}$
$\displaystyle=\sum_{A\subseteq
E}(x-1)^{\rho(\Gamma)-\rho_{\Gamma}(A)}(-2)^{-\rho_{\Gamma}(A)}\sum_{\begin{subarray}{c}A^{\prime}\subseteq
E^{\prime}:\\\ \mu(A^{\prime})=A\end{subarray}}(-2)^{|A^{\prime}|}$
$\displaystyle=\sum_{A\subseteq
E}(x-1)^{\rho(\Gamma)-\rho_{\Gamma}(A)}(-2)^{-\rho_{\Gamma}(A)}((-1)^{k}-1)^{|A|}$
$\displaystyle=\left\\{\begin{array}[]{ll}(x-1)^{\rho(\Gamma)}&\text{if $k$ is
even};\\\ T(\Gamma;x,-1)&\text{if $k$ is odd.}\end{array}\right.$ (6)

Note that the only contribution to $T(\Gamma^{k};x,-1)$ when $k$ is even is
from the empty set. ∎

The second construction is a little more involved. To motivate it we first
describe a natural construction operation on rooted graphs. Let $G$ and $H$ be
disjoint rooted graphs with $G$ being connected. Then the _$H$ -attachment_ of
$G$, denoted by $G\sim H$, is formed by taking $G$ and $\rho(G)$ disjoint
copies of $H$, and identifying each vertex of $G$ other than the root with the
root vertex of one of the copies of $H$. The root of $G\sim H$ is the root of
$G$. See Figure 1 for an illustration of the attachment operation.

$r_{G\sim H}$$G\sim H$$r_{G}$$G$$r_{H}$$H$ Figure 1: An example of the
attachment operation.

Suppose that $V(G)=\\{r,v_{1},\ldots,v_{\rho(G)}\\}$, where $r$ is the root of
$G$, let $E_{0}$ be the edge set of $G$ and let $E_{i}$ be the edge set of the
copy of $H$ attached at $v_{i}$. A set $F$ is feasible in $\Gamma(G\sim H)$ if
and only if each of the following conditions holds.

  1. 1.

$F\cap E_{0}$ is feasible in $\Gamma(G)$.

  2. 2.

For all $i$ with $1\leq i\leq\rho(G)$, $F\cap E_{i}$ is feasible in
$\Gamma(H)$.

  3. 3.

For all $i$ with $1\leq i\leq\rho(G)$, if $v_{i}$ is not in the root component
of $G|(F\cap E_{0})$, then $F\cap E_{i}=\emptyset$.

In order to extend these ideas to general greedoids, we begin by describing
the notion of a closed set, which was first defined for greedoids by Korte and
Lovasz [26]. Let $\Gamma$ be a greedoid with ground set $E$ and rank function
$\rho$. Given a subset $A$ of $E$, its _closure_ $\sigma_{\Gamma}(A)$ is
defined by $\sigma_{\Gamma}(A)=\\{e:\rho(A\cup e)=\rho(A)\\}$. We will drop
the dependence on $\Gamma$ whenever the context is clear. Note that it follows
from the definition that $A\subseteq\sigma(A)$. Moreover Lemma 8 implies that
$\rho(\sigma(A))=\rho(A)$. Furthermore if $e\notin\sigma(A)$, then $\rho(A\cup
e)>\rho(A)$, so axiom (GR2) implies that $\rho(\sigma(A)\cup
e)>\rho(\sigma(A))$ and hence $\sigma(\sigma(A))=\sigma(A)$. A subset $A$ of
$E$ satisfying $A=\sigma(A)$ is said to be _closed_. Every subset of $E$ of
the form $\sigma(X)$ for some $X$ is closed.

We now introduce what we call an attachment function. Let $\Gamma$ be a
greedoid with rank function $\rho$. A function $f:\mathcal{F}\rightarrow
2^{[\rho(\Gamma)]}$ is called a _$\Gamma$ -attachment function_ if it
satisfies both of the following.

  1. 1.

For each feasible set $F$, we have $|f(F)|=\rho(F)$.

  2. 2.

If $F_{1}$ and $F_{2}$ are feasible sets and $F_{1}\subseteq\sigma(F_{2})$
then $f(F_{1})\subseteq f(F_{2})$.

The following property of attachment functions is needed later.

######  Lemma 17.

Let $\Gamma$ be a greedoid and $f$ be a $\Gamma$-attachment function. Let $A$
be a subset of the elements of $\Gamma$ and let $F_{1}$ and $F_{2}$ be maximal
feasible subsets of $A$. Then $f(F_{1})=f(F_{2})$.

###### Proof.

It follows from the axioms for the feasible sets of a greedoid that all
maximal feasible subsets of $A$ have the same size. Thus
$\rho(F_{1})=\rho(F_{2})=\rho(A)$. For every element $e$ of $A$,
$\rho(F_{1})\leq\rho(F_{1}\cup e)\leq\rho(A)$. As $\rho(F_{1})=\rho(A)$,
equality must hold throughout. Thus $e\in\sigma(F_{1})$. Hence
$A\subseteq\sigma(F_{1})$, so $F_{2}\subseteq\sigma(F_{1})$. By symmetry,
$F_{1}\subseteq\sigma(F_{2})$. The result then follows from the second
condition satisfied by a $\Gamma$-attachment function. ∎

Given greedoids $\Gamma_{1}$ and $\Gamma_{2}$ with disjoint ground sets, and
$\Gamma_{1}$-attachment function $f$, we define the _$\Gamma_{2}$ -attachment
of $\Gamma_{1}$_, denoted by $\Gamma_{1}\sim_{f}\Gamma_{2}$ as follows. The
ground set $E$ is the union of the ground set $E_{0}$ of $\Gamma_{1}$ together
with $\rho=\rho(\Gamma_{1})$ disjoint copies $E_{1},\ldots,E_{\rho}$ of the
ground set of $\Gamma_{2}$. In the following we abuse notation slightly by
saying that for $i>0$, a subset of $E_{i}$ is feasible in $\Gamma_{2}$ if the
corresponding subset of the elements of $\Gamma_{2}$ is feasible. A subset $F$
of $E$ is feasible if and only if each of the following conditions holds.

  1. 1.

$F\cap E_{0}$ is feasible in $\Gamma_{1}$.

  2. 2.

For all $i$ with $1\leq i\leq\rho$, $F\cap E_{i}$ is feasible in $\Gamma_{2}$.

  3. 3.

For all $i$ with $1\leq i\leq\rho$, if $i\notin f(F\cap E_{0})$ then $F\cap
E_{i}=\emptyset$.

######  Proposition 18.

For any greedoids $\Gamma_{1}$ and $\Gamma_{2}$, and $\Gamma_{1}$-attachment
function $f$, the _$\Gamma_{2}$ -attachment of $\Gamma_{1}$_ is a greedoid.

###### Proof.

We use the notation defined above to describe the ground set of
$\Gamma_{1}\sim_{f}\Gamma_{2}$. Clearly the empty set is feasible in
$\Gamma_{1}\sim_{f}\Gamma_{2}$. Suppose that $F_{1}$ and $F_{2}$ are feasible
sets in $\Gamma_{1}\sim_{f}\Gamma_{2}$ with $|F_{2}|>|F_{1}|$. If there is an
element $e$ of $F_{2}\cap E_{0}$ which is not in
$\sigma_{\Gamma_{1}}(F_{1}\cap E_{0})$ then $(F_{1}\cap E_{0})\cup e$ is
feasible in $\Gamma_{1}$. Moreover $F_{1}\cap
E_{0}\subseteq\sigma_{\Gamma_{1}}((F_{1}\cap E_{0})\cup e)$, so $f(F_{1}\cap
E_{0})\subseteq f((F_{1}\cap E_{0})\cup e)$. Consequently $F_{1}\cup e$ is
feasible in $\Gamma_{1}\sim_{f}\Gamma_{2}$.

On the other hand, suppose that $F_{2}\cap
E_{0}\subseteq\sigma_{\Gamma_{1}}(F_{1}\cap E_{0})$. Then $f(F_{2}\cap
E_{0})\subseteq f(F_{1}\cap E_{0})$. Moreover, as there is no element $e$ of
$(F_{2}\cap E_{0})-(F_{1}\cap E_{0})$ such that $(F_{1}\cap E_{0})\cup e$ is
feasible, we have $|F_{2}\cap E_{0}|\leq|F_{1}\cap E_{0}|$. So for some $i$ in
$f(F_{2}\cap E_{0})$, we have $|F_{2}\cap E_{i}|>|F_{1}\cap E_{i}|$. Thus
there exists $e\in(F_{2}-F_{1})\cap E_{i}$ such that $(F_{1}\cap E_{i})\cup e$
is feasible in $\Gamma_{2}$. As $i\in f(F_{2}\cap E_{0})$, we have $i\in
f(F_{1}\cap E_{0})$. Hence $F_{1}\cup e$ is feasible in
$\Gamma_{1}\sim_{f}\Gamma_{2}$. ∎

Every greedoid $\Gamma$ has an attachment function formed by setting
$f(F)=[|F|]$ for each feasible set $F$. However there are other examples of
attachment functions. Let $G$ be a connected rooted graph in which the
vertices other than the root are labelled $v_{1},\ldots,v_{\rho}$. There is an
attachment function $f$ defined on $\Gamma(G)$ as follows. For every feasible
set $F$, define $f(F)$ so that $i\in f(F)$ if and only if $v_{i}$ is in the
root component of $G|F$. It is straightforward to verify that $f$ is indeed an
attachment function. Furthermore if $H$ is another rooted graph then
$\Gamma(G\sim H)=\Gamma(G)\sim_{f}\Gamma(H)$.

We now consider the rank function of $\Gamma=\Gamma_{1}\sim_{f}\Gamma_{2}$. We
keep the same notation as above for the elements of $\Gamma$. Let $A$ be a
subset of $E(\Gamma)$ and let $F$ be a maximal feasible subset of $A\cap
E_{0}$. Then

$\rho_{\Gamma}(A)=\rho_{\Gamma_{1}}(A\cap E_{0})+\sum_{i\in
f(F)}\rho_{\Gamma_{2}}(A\cap E_{i}).$ (7)

Observe that the number of subsets of $E(\Gamma)$ with specified rank, size
and intersection with $E_{0}$ does not depend on the choice of $f$.
Consequently the Tutte polynomial of $\Gamma_{1}\sim_{f}\Gamma_{2}$ does not
depend on $f$. We now make this idea more precise by establishing an
expression for the Tutte polynomial of an attachment.

######  Theorem 19.

Let $\Gamma_{1}$ and $\Gamma_{2}$ be greedoids, and let $f$ be an attachment
function for $\Gamma_{1}$. Then the Tutte polynomial of
$\Gamma_{1}\sim_{f}\Gamma_{2}$ is given by

$T(\Gamma_{1}\sim_{f}\Gamma_{2};x,y)=T(\Gamma_{2};x,y)^{\rho(\Gamma_{1})}T\Big{(}\Gamma_{1};\frac{(x-1)^{\rho(\Gamma_{2})+1}y^{|E(\Gamma_{2})|}}{T(\Gamma_{2};x,y)}+1,y\Big{)},$

providing $T(\Gamma_{2};x,y)\neq 0$.

###### Proof.

Let $\Gamma=\Gamma_{1}\sim_{f}\Gamma_{2}$. We use the notation defined above
to describe the ground set of $\Gamma$. It is useful to extend the definition
of the attachment function $f$ to all subsets of $E_{0}$ by setting $f(A)$ to
be equal to $f(F)$ where $F$ is a maximal feasible set of $A$. Lemma 17
ensures that extending $f$ in this way is well-defined. It follows from
Equation 7 that $\rho(\Gamma)=\rho(\Gamma_{1})(\rho(\Gamma_{2})+1)$. We have

$\displaystyle T(\Gamma;x,y)$ $\displaystyle=\sum_{A\subseteq
E(\Gamma)}(x-1)^{\rho(\Gamma)-\rho_{\Gamma}(A)}(y-1)^{|A|-\rho(A)}$
$\displaystyle=\sum_{A_{0}\subseteq
E_{0}}(x-1)^{\rho(\Gamma_{1})-\rho_{\Gamma_{1}}(A_{0})}(y-1)^{|A_{0}|-\rho_{\Gamma_{1}}(A_{0})}\cdot\prod_{i\notin
f(A_{0})}\sum_{A_{i}\subseteq E_{i}}(x-1)^{\rho(\Gamma_{2})}(y-1)^{|A_{i}|}$
$\displaystyle\phantom{=}\ \cdot\prod_{i\in f(A_{0})}\sum_{A_{i}\subseteq
E_{i}}(x-1)^{\rho(\Gamma_{2})-\rho_{\Gamma_{2}}(A_{i})}(y-1)^{|A_{i}|-\rho_{\Gamma_{2}}(A_{i})}$
$\displaystyle=\sum_{A_{0}\subseteq
E_{0}}(x-1)^{\rho(\Gamma_{1})-\rho_{\Gamma_{1}}(A_{0})}(T(\Gamma_{2};x,y))^{\rho_{\Gamma_{1}}(A_{0})}$
$\displaystyle\phantom{=}\
\cdot\big{(}(x-1)^{\rho(\Gamma_{2})}y^{|E(\Gamma_{2})|}\big{)}^{\rho(\Gamma_{1})-\rho_{\Gamma_{1}}(A_{0})}(y-1)^{|A_{0}|-\rho_{\Gamma_{1}}(A_{0})}$
$\displaystyle=(T(\Gamma_{2};x,y))^{\rho(\Gamma_{1})}\sum_{A_{0}\subseteq
E_{0}}(y-1)^{|A_{0}|-\rho_{\Gamma_{1}}(A_{0})}\Big{(}\frac{(x-1)^{\rho(\Gamma_{2})+1}y^{|E(\Gamma_{2})|}}{T(\Gamma_{2};x,y)}\Big{)}^{\rho(\Gamma_{1})-\rho_{\Gamma_{1}}(A_{0})}$
$\displaystyle=T(\Gamma_{2};x,y)^{\rho(\Gamma_{1})}T\Big{(}\Gamma_{1};\frac{(x-1)^{\rho(\Gamma_{2})+1}y^{|E(\Gamma_{2})|}}{T(\Gamma_{2};x,y)}+1,y\Big{)}.$

∎

The third construction is called the full rank attachment. Given greedoids
$\Gamma_{1}=(E_{1},\mathcal{F}_{1})$ and $\Gamma_{2}=(E_{2},\mathcal{F}_{2})$
with disjoint ground sets, the _full rank attachment of $\Gamma_{2}$ to
$\Gamma_{1}$_ denoted by $\Gamma_{1}\approx\Gamma_{2}$ has ground set
$E_{1}\cup E_{2}$ and a set $F$ of elements is feasible if either of the two
following conditions holds.

  1. 1.

$F\in\mathcal{F}_{1}$;

  2. 2.

$F\cap E_{1}\in\mathcal{F}_{1}$, $F\cap E_{2}\in\mathcal{F}_{2}$ and
$\rho_{\Gamma_{1}}(F\cap E_{1})=\rho(\Gamma_{1})$.

It is straightforward to prove that $\Gamma_{1}\approx\Gamma_{2}$ is a
greedoid.

Suppose that $\Gamma=\Gamma_{1}\approx\Gamma_{2}$ and that $A$ is a subset of
$E(\Gamma)$. Then

$\rho(A)=\begin{cases}\rho(A\cap E_{1})&\text{if $\rho(A\cap
E_{1})<\rho(\Gamma_{1})$,}\\\ \rho(A\cap E_{1})+\rho(A\cap E_{2})&\text{if
$\rho(A\cap E_{1})=\rho(\Gamma_{1})$.}\end{cases}$

This observation enables us to prove the following identity for the Tutte
polynomial.

######  Theorem 20.

Let $\Gamma_{1}$ and $\Gamma_{2}$ be greedoids, and let
$\Gamma=\Gamma_{1}\approx\Gamma_{2}$. Let $E$, $E_{1}$ and $E_{2}$ denote the
ground sets of $\Gamma$, $\Gamma_{1}$ and $\Gamma_{2}$ respectively. Then

$T(\Gamma_{1}\approx\Gamma_{2};x,y)\\\
=T(\Gamma_{1};x,y)(x-1)^{\rho(\Gamma_{2})}y^{|E_{2}|}+T(\Gamma_{1};1,y)(T(\Gamma_{2};x,y)-(x-1)^{\rho(\Gamma_{2})}y^{|E_{2}|}).$

###### Proof.

We have

$\displaystyle{T(\Gamma_{1}\approx\Gamma_{2};x,y)}$
$\displaystyle=\sum_{A\subseteq
E}(x-1)^{\rho(\Gamma)-\rho_{\Gamma}(A)}(y-1)^{|A|-\rho_{\Gamma}(A)}$
$\displaystyle=\sum_{\begin{subarray}{c}A_{1}\subseteq E_{1}:\\\
\rho_{\Gamma_{1}}(A_{1})<\rho(\Gamma_{1})\end{subarray}}(x-1)^{\rho(\Gamma_{1})-\rho_{\Gamma_{1}}(A_{1})}(y-1)^{|A_{1}|-\rho_{\Gamma_{1}}(A_{1})}\sum_{A_{2}\subseteq
E_{2}}(x-1)^{\rho(\Gamma_{2})}(y-1)^{|A_{2}|}$ $\displaystyle\phantom{=}\
{}+\sum_{\begin{subarray}{c}A_{1}\subseteq E_{1}:\\\
\rho_{\Gamma_{1}}(A_{1})=\rho(\Gamma_{1})\end{subarray}}(y-1)^{|A_{1}|-\rho_{\Gamma_{1}}(A_{1})}\sum_{A_{2}\subseteq
E_{2}}(x-1)^{\rho(\Gamma_{2})-\rho_{\Gamma_{2}}(A_{2})}(y-1)^{|A_{2}|-\rho_{\Gamma_{2}}(A_{2})}$
$\displaystyle=\sum_{A_{1}\subseteq
E_{1}}(x-1)^{\rho(\Gamma_{1})-\rho_{\Gamma_{1}}(A_{1})}(y-1)^{|A_{1}|-\rho_{\Gamma_{1}}(A_{1})}(x-1)^{\rho(\Gamma_{2})}y^{|E_{2}|}$
$\displaystyle\phantom{=}\ {}+\sum_{\begin{subarray}{c}A_{1}\subseteq
E_{1}:\\\
\rho_{\Gamma_{1}}(A_{1})=\rho(\Gamma_{1})\end{subarray}}(y-1)^{|A_{1}|-\rho_{\Gamma_{1}}(A_{1})}$
$\displaystyle\phantom{=}\ \cdot\Big{(}\sum_{A_{2}\subseteq
E_{2}}(x-1)^{\rho(\Gamma_{2})-\rho_{\Gamma_{2}}(A_{2})}(y-1)^{|A_{2}|-\rho_{\Gamma_{2}}(A_{2})}-(x-1)^{\rho(\Gamma_{2})}y^{|E_{2}|}\Big{)}$
$\displaystyle=T(\Gamma_{1};x,y)(x-1)^{\rho(\Gamma_{2})}y^{|E_{2}|}+T(\Gamma_{1};1,y)\big{(}T(\Gamma_{2};x,y)-(x-1)^{\rho(\Gamma_{2})}y^{|E_{2}|}\big{)}.$

∎

This construction will be useful later in Section 7 when $\Gamma_{1}$ and
$\Gamma_{2}$ are binary greedoids with $\Gamma_{1}=\Gamma(M_{1})$ and
$\Gamma_{2}=\Gamma(M_{2})$, where $M_{1}$ has full row rank. Then
$\Gamma_{1}\approx\Gamma_{2}=\Gamma(M)$ where $M$ has the form

$M=\left(\begin{array}[]{c|c}M_{1}&0\\\ \hline\cr 0&M_{2}\end{array}\right).$

##  5 Rooted Graphs

Throughout the remainder of the paper we focus on three computational
problems. Let $\mathbb{G}$ denote either the class of branching greedoids,
directed branching greedoids or binary greedoids. Our first problem is
computing all the coefficients of the Tutte polynomial for a greedoid in the
class $\mathbb{G}$.

  * $\pi_{1}[\mathbb{G}]$ : $\\#$Rooted Tutte Polynomial
Input: $\Gamma\in\mathbb{G}$.
Output: The coefficients of $T(\Gamma;x,y)$.

The second problem involves computing the Tutte polynomial along a plane
algebraic curve $L$. We restrict our attention to the case where $L$ is a
rational curve given by the parametric equations

$x(t)=\frac{p(t)}{q(t)}\quad\text{ and }\quad y(t)=\frac{r(t)}{s(t)},$

where $p$, $q$, $r$ and $s$ are polynomials over $\mathbb{Q}$. More precisely,
we compute the coefficients of the one-variable polynomial obtained by
restricting $T$ to the curve $L$.

  * $\pi_{2}[\mathbb{G},L]$ : $\\#$Rooted Tutte Polynomial Along $L$
Input: $\Gamma\in\mathbb{G}$.
Output: The coefficients of the rational function of $t$ given by evaluating
$T(\Gamma;x(t),y(t))$ along $L$.

Most of the time, $L$ will be one of the hyperbolae $H_{\alpha}$. We will
frequently make a slight abuse of notation by writing $L=H_{\alpha}$.

The final problem is the evaluation of the Tutte polynomial at a fixed
rational point $(a,b)$.

  * $\pi_{3}[\mathbb{G},a,b]$ : $\\#$Rooted Tutte Polynomial At $(a,b)$
Input: $\Gamma\in\mathbb{G}$.
Output: $T(\Gamma;a,b)$.

It is straightforward to see that for each possibility for $\mathbb{G}$, we
have

$\pi_{3}[\mathbb{G},a,b]\propto_{T}\pi_{2}[\mathbb{G},H_{(a-1)(b-1)}]\propto_{T}\pi_{1}[\mathbb{G}].$

Our results in the remainder of the paper will determine when the opposite
reductions hold.

In this section we prove Theorem 3. We let $\mathcal{G}$ be the class of
branching greedoids of connected, rooted, planar, bipartite graphs and take
$\mathbb{G}=\mathcal{G}$. It is, however, more convenient to take the input to
each problem to be a connected, rooted, planar, bipartite graph rather than
its branching greedoid.

We begin by reviewing the exceptional points of Theorem 3. If a point $(a,b)$
lies on the hyperbola $H_{1}$ then, following the remarks at the end of
Section 3, $T(G;a,b)$ is easily computed. We noted in Section 3 that for a
connected rooted graph $G$, $T(G;1,1)$ is equal to the number of spanning
trees of $G$. That this can be evaluated in polynomial time follows from
Kirchhoff’s Matrix–Tree theorem [25]. Hence there are polynomial time
algorithms to evaluate the Tutte polynomial of a connected rooted graph at
$(1,1)$ and at any point lying on $H_{1}$. It is easy to extend this to all
rooted graphs because every edge belonging to a component that does not
include the root is a loop in the corresponding branching greedoid.

We will now review the hard points of Theorem 3. A key step in establishing
the hardness part of Theorem 3 for points lying on the line $y=1$ is to
strengthen a result of Jerrum [24]. Given an unrooted graph $G=(V,E)$, a
_subtree_ of $G$ is a subgraph of $G$ which is a tree. (We emphasize that the
subgraph does not have to be an induced subgraph.) Jerrum [24] showed that the
following problem is $\\#$P-complete.

  * $\\#$Subtrees
Input: Planar unrooted graph $G$.
Output: The number of subtrees of $G$.

Consider the restriction of this problem to bipartite planar graphs.

  * $\\#$Bisubtrees
Input: Bipartite, planar unrooted graph $G$.
Output: The number of subtrees of $G$.

We shall show that $\\#$Bisubtrees is $\\#$P-complete. We say that an edge of
a graph $G$ is _external_ in a subtree $T$ of $G$ if it is not contained in
$E(T)$. Let $t_{i,j}(G)$ be the number of subtrees of $G$ with $i$ external
edges having precisely one endvertex in $T$ and $j$ external edges having both
endvertices in $T$.

Recall that the $k$-stretch of an unrooted graph $G$ is obtained by replacing
each loop by a circuit with $k$ edges and every other edge by a path of length
$k$. Let $t(G)$ denote the number of subtrees of $G$.

######  Proposition 21.

For every unrooted graph $G$, the number of subtrees of the $k$-stretch
$G_{k}$ of $G$ is given by

$t(G_{k})=\left(\sum_{i,j\geq
0}t_{i,j}(G)k^{i}\binom{k+1}{2}^{j}\right)+\frac{k(k-1)|E|}{2}.$

###### Proof.

Let $E(G)=\\{e_{1},e_{2},\ldots,e_{m}\\}$ and let $E_{t}$ be the set of edges
replacing $e_{t}$ in $G_{k}$ for $1\leq t\leq m$. Thus
$E(G_{k})=\bigcup_{t=1}^{m}E_{t}$. We can think of the vertices of $G_{k}$ as
being of two types: those corresponding to the vertices of $G$ and the extra
ones added when $G_{k}$ is formed. We construct a function $f$ that maps every
subtree $T$ of $G_{k}$ to a graph $T^{\prime}$ which is either a subtree of
$G$ or an empty graph with no vertices or edges. We let $V(T^{\prime})$
comprise all the vertices of $V(T)$ corresponding to vertices in $G$. The edge
set $E(T^{\prime})$ is defined so that $e_{t}\in E(T^{\prime})$ if and only if
$E_{t}\subseteq E(T)$.

Let $T^{\prime}$ be a subtree of $G$ with at least one vertex, $i$ external
edges having precisely one endvertex in $T^{\prime}$ and $j$ external edges
having both endvertices in $T^{\prime}$.

If $T\in f^{-1}(T^{\prime})$ then it must contain all of the edges in $G_{k}$
that replace the edges in $E(T^{\prime})$. Suppose there is an edge
$e=v_{1}v_{2}$ in $G$ that is external in $T^{\prime}$ with $v_{1}\in
V(T^{\prime})$ and $v_{2}\notin V(T^{\prime})$. Then there are $k$
possibilities for the subset of $E_{t}$ appearing in $T$. Now suppose there
exists an edge $e_{t}=v_{1}v_{2}$ in $G$ that is external in $T^{\prime}$ with
$v_{1},v_{2}\in V^{\prime}$. Then there are $\binom{k+1}{2}$ choices for the
subset of $E_{t}$ appearing in $T$. Therefore,

$|f^{-1}(T_{i,j}^{\prime})|=k^{i}\binom{k+1}{2}^{j}.$

It remains to count the subtrees of $G_{k}$ mapped by $f$ to a graph with no
vertices. Such a subtree does not contain any vertices corresponding to
vertices in $G$. There are $(k-1)|E(G)|$ subtrees of $G_{k}$ comprising a
single vertex not in $V(G)$ and no edges, and $\binom{k-1}{2}|E(G)|$ subtrees
of $G_{k}$ with at least one edge but not containing any vertex in $V(G)$.
Hence

$t(G_{k})=\left(\sum_{i,j\geq
0}t_{i,j}(G)k^{i}\binom{k+1}{2}^{j}\right)+\frac{k(k-1)}{2}|E(G)|.$

∎

We can now show that Bisubtrees is $\\#$P-complete.

######  Proposition 22.

The problem Bisubtrees is $\\#$P-complete.

###### Proof.

It is clear that Bisubtrees belongs to $\\#$P. To establish hardness, first
note that $G_{2},\ldots,G_{4|E(G)|+2}$ are all bipartite and may be
constructed from $G$ in polynomial time. We have $\max_{i,j\geq
0}\\{i+2j:t_{i,j}(G)>0\\}\leq\max_{i,j\geq
0}\\{i+2j:i+j\leq|E(G)|\\}=2{|E(G)|}$. Therefore, by Proposition 21,
$t(G_{k})$ is a polynomial in $k$ of degree at most $2|E(G)|$. So we can write

$t(G_{k})=\sum_{p=0}^{2|E(G)|}a_{p}k^{p}.$

Thus, if we compute $t(G_{k})$ for $k=2,\ldots,4|E(G)|+2$, then we can apply
Lemma 13 to recover $a_{i}$ for all $i$ and then determine $t(G)=t(G_{1})$ in
polynomial time. Therefore we have shown that Subtrees $\propto_{T}$
Bisubtrees. ∎

We now present three propositions which together show that at most fixed
rational points $(a,b)$, evaluating the Tutte polynomial of a connected,
bipartite, planar, rooted graph at $(a,b)$ is just as hard as evaluating it
along the curve $H_{(a-1)(b-1)}$. The $k$-thickening operation is crucial.
Notice that $\Gamma(G^{k})\cong(\Gamma(G))^{k}$, so we may apply Theorem 16 to
obtain an expression for $T(G^{k})$. The first proposition deals with the case
when $a\neq 1$ and $b\notin\\{-1,0,1\\}$.

######  Proposition 23.

Let $L=H_{\alpha}$ for some $\alpha\in\mathbb{Q}-\\{0\\}$. Let $(a,b)$ be a
point on $L$ such that $b\notin\\{-1,0\\}$. Then

$\pi_{2}[\mathcal{G},L]\propto_{T}\pi_{3}[\mathcal{G},a,b].$

###### Proof.

For a point $(x,y)$ on $L$ we have $y\neq 1$. Therefore $z=y-1\neq 0$ and so
$\alpha/z=x-1$. Let $G$ be in $\mathcal{G}$. Along $L$ the Tutte polynomial of
$G$ has the form

$T(G;x,y)=T(G;1+\alpha/z,1+z)=\sum_{A\subseteq
E(G)}\left(\frac{\alpha}{z}\right)^{\rho(G)-\rho(A)}z^{|A|-\rho(A)}=\sum_{i=-\rho(G)}^{|E(G)|}t_{i}z^{i},$

for some $t_{-\rho(G)},\ldots,t_{|E(G)|}$.

We now show that we can determine all of the coefficients $t_{i}$ from the
evaluations $T(G^{k};a,b)$ for $k=1,\ldots,|E(G)|+\rho(G)+1$ in time
polynomial in $|E(G)|$. For each such $k$, $G^{k}$ may be constructed from $G$
in time polynomial in $|E(G)|$ and is bipartite, planar and connected. By
Theorem 16, we have

$T(G^{k};a,b)=(1+b+\ldots+b^{k-1})^{\rho(G)}T\left(G;\frac{a+b+\ldots+b^{k-1}}{1+b+\ldots+b^{k-1}},b^{k}\right).$

Since $b\neq-1$, we have $1+b+\ldots+b^{k-1}\neq 0$. Therefore we may compute

$T\left(G;\frac{a+b+\ldots+b^{k-1}}{1+b+\ldots+b^{k-1}},b^{k}\right)$

from $T(G^{k};a,b)$. The point
$\left(\frac{a+b+\ldots+b^{k-1}}{1+b+\ldots+b^{k-1}},b^{k}\right)$ will also
be on the curve $L$ since

$\left(\frac{a+b+\ldots+b^{k-1}}{1+b+\ldots+b^{k-1}}-1\right)(b^{k}-1)=(a-1)(b-1).$

As $b\notin\\{-1,0,1\\}$, for $k=1,2,\ldots,|E(G)|+\rho(G)+1$, the points
$\left(\frac{a+b+\ldots+b^{k-1}}{1+b+\ldots+b^{k-1}},b^{k}\right)$ are
pairwise distinct. Therefore by evaluating $T(G^{k};a,b)$ for
$k=1,\ldots,|E(G)|+\rho(G)+1$, we obtain
$\sum_{i=-\rho(G)}^{|E(G)|}t_{i}z^{i}$ for $|E(G)|+\rho(G)+1$ distinct values
of $z$. This gives us $|E(G)|+\rho(G)+1$ linear equations for the coefficients
$t_{i}$. The matrix of the equations is a Vandermonde matrix and clearly non-
singular. So, we may apply Lemma 13 to compute $t_{i}$ for all $i$ in time
polynomial in $|E(G)|$. ∎

The next proposition deals with the case when $a=1$. Recall
$H_{0}^{x}=\\{(1,y):y\in\mathbb{Q}\\}$ and
$H_{0}^{y}=\\{(x,1):x\in\mathbb{Q}\\}$.

######  Proposition 24.

Let $L=H_{0}^{x}$ and let $b\in\mathbb{Q}-\\{-1,0,1\\}$. Then

$\pi_{2}[\mathcal{G},L]\propto_{T}\pi_{3}[\mathcal{G},1,b].$

###### Proof.

Let $G$ be in $\mathcal{G}$. Along $L$ the Tutte polynomial of $G$ has the
form

$T(G;1,y)=\sum_{\begin{subarray}{c}A\subseteq E(G):\\\
\rho(A)=\rho(G)\end{subarray}}(y-1)^{|A|-\rho(G)}=\sum_{i=-\rho(G)}^{|E(G)|}t_{i}y^{i},$

for some $t_{-\rho(G)},\ldots,t_{|E(G)|}$.

The proof now follows in a similar way to that of Proposition 23 by computing
$T(G^{k};1,b)$ for $k=1,\ldots,|E(G)|+\rho(G)+1$ and then determining each
coefficient $t_{i}$ in time polynomial in $|E(G)|$. ∎

The following proposition deals with the case when $b=1$.

######  Proposition 25.

Let $L=H_{0}^{y}$ and $a\in\mathbb{Q}-\\{1\\}$. Then

$\pi_{2}[\mathcal{G},L]\propto_{T}\pi_{3}[\mathcal{G},a,1].$

###### Proof.

Let $G$ be in $\mathcal{G}$. Along $L$ the Tutte polynomial of $G$ has the
form

$T(G;x,1)=\sum_{\begin{subarray}{c}A\subseteq E(G):\\\
\rho(A)=|A|\end{subarray}}(x-1)^{\rho(G)-\rho(A)}=\sum_{i=0}^{\rho(G)}t_{i}x^{i},$

for some $t_{0},\ldots,t_{\rho(G)}$.

We now show that we can determine all of the coefficients $t_{i}$ from the
evaluations $T(G^{k};a,1)$ for $k=1,\ldots,\rho(G)+1$ in time polynomial in
$|E(G)|$. For each such $k$, $G^{k}$ may be constructed from $G$ in time
polynomial in $|E(G)|$ and is bipartite, planar and connected. By Theorem 16,
we have

$T(G^{k};a,1)=k^{\rho(G)}T\left(G;\frac{a+k-1}{k},1\right).$

Therefore we may compute $T\left(G;\frac{a+k-1}{k},1\right)$ from
$T(G^{k};a,1)$. Clearly $\left(\frac{a+k-1}{k},1\right)$ lies on $H_{0}^{y}$.
Since $a\neq 1$, the points $\left(\frac{a+k-1}{k},1\right)$ are pairwise
distinct for $k=1,2,\ldots,\rho(G)+1$. Therefore by evaluating $T(G^{k};a,1)$
for $k=1,\ldots,\rho(G)+1$, we obtain $\sum_{i=0}^{|\rho(G)|}t_{i}z^{i}$ for
$\rho(G)+1$ distinct values of $z$. This gives us $\rho(G)+1$ linear equations
for the coefficients $t_{i}$. Again the matrix of the equations is a
Vandermonde matrix and clearly non-singular. So, we may apply Lemma 13 to
compute $t_{i}$ for all $i$ in time polynomial in $|E(G)|$. ∎

We now summarize the three preceding propositions.

######  Proposition 26.

Let $L$ be either $H_{0}^{x}$, $H_{0}^{y}$, or $H_{\alpha}$ for
$\alpha\in\mathbb{Q}-\\{0\\}$. Let $(a,b)$ be a point on $L$ such that
$(a,b)\neq(1,1)$ and $b\notin\\{-1,0\\}$. Then

$\pi_{2}[\mathcal{G},L]\propto_{T}\pi_{3}[\mathcal{G},a,b].$

We now consider the exceptional case when $b=-1$. For reasons that will soon
become apparent, we recall from Example 14 that $T(P_{2};x,y)=x^{2}y-2xy+x+y$
and $T(S_{k};x,y)=x^{k}$.

######  Proposition 27.

Let $L$ be the line $y=-1$. For $a\notin\\{\frac{1}{2},1\\}$ we have

$\pi_{2}[\mathcal{G},L]\propto_{T}\pi_{3}[\mathcal{G},a,-1].$

###### Proof.

Let $G$ be in $\mathcal{G}$ and let $z=x-1$. Along $L$ the Tutte polynomial of
$G$ has the form

$T(G;x,-1)=\sum_{A\subseteq
E(G)}z^{\rho(G)-\rho(A)}(-2)^{|A|-\rho(A)}=\sum^{\rho(G)}_{i=0}t_{i}z^{i}$

for some $t_{0},\ldots,t_{\rho(G)}$.

We now show that, apart from a few exceptional values of $a$, we can determine
all of the coefficients $t_{i}$ in polynomial time from $T(G\sim S_{k};a,-1)$,
for $k=0,1,\ldots,\rho(G)$, in time polynomial in $|E(G)|$. For each such $k$,
$G\sim S_{k}$ may be constructed from $G$ in time polynomial in $|E(G)|$ and
is bipartite, planar and connected.

By Theorem 19 we have

$T(G\sim
S_{k};a,-1)=a^{k\rho(G)}T\left(G;\frac{(a-1)^{k+1}(-1)^{k}}{a^{k}}+1,-1\right).$

Providing $a\neq 0$ we may compute
$T\left(G;\frac{(a-1)^{k+1}(-1)^{k}}{a^{k}}+1,-1\right)$ from $T(G\sim
S_{k};a,-1)$. For $a\notin\\{\frac{1}{2},1\\}$ the points
$\left(\frac{(a-1)^{k+1}(-1)^{k}}{a^{k}}+1,-1\right)$ are pairwise distinct
for $k=0,1,2,\ldots,\rho(G)$. Therefore by evaluating $T(G\sim S_{k};a,-1)$
for $k=0,1,2,\ldots,\rho(G)$ where $a\notin\\{0,\frac{1}{2},1\\}$, we obtain
$\sum_{i=0}^{\rho(G)}t_{i}z^{i}$ for $\rho(G)+1$ distinct values of $z$. This
gives us $\rho(G)+1$ linear equations for the coefficients $t_{i}$. Again the
matrix corresponding to these equations is a Vandermonde matrix and clearly
non-singular. So, we may apply Lemma 13 to compute $t_{i}$ for all $i$ in time
polynomial in $|E(G)|$. Hence for $a\notin\\{0,\frac{1}{2},1\\}$,
$\pi_{2}[\mathcal{G},L]\propto\pi_{3}[\mathcal{G},a,-1]$.

We now look at the case when $a=0$. Note that $T(P_{2};0,-1)=-1$. Applying
Theorem 19 to $G$ and $P_{2}$ gives

$T(G\sim
P_{2};0,-1)=(-1)^{\rho(G)}T\left(G;\frac{(-1)^{3}(-1)^{2}}{-1}+1,-1\right)=(-1)^{\rho(G)}T(G;2,-1).$

Therefore we have the reductions

$\pi_{2}[\mathcal{G},L]\propto_{T}\pi_{3}[\mathcal{G},2,-1]\propto_{T}\pi_{3}[\mathcal{G},0,-1].$

Since the Turing reduction relation is transitive, this implies that
evaluating the Tutte polynomial at the point $(0,-1)$ is at least as hard as
evaluating it along the line $y=-1$. This completes the proof. ∎

We now begin to classify the complexity of $\pi_{3}$. The next results will
establish hardness for a few special cases, namely when $b\in\\{-1,0,1\\}$.

######  Proposition 28.

The problem $\pi_{3}[\mathcal{G},1,b]$ is $\\#$P-hard apart from when $b=1$,
in which case it has a polynomial time algorithm.

###### Proof.

The hardness part follows directly from Theorem 2 and Proposition 15. We have
already noted the existence of a polynomial time algorithm to solve
$\pi_{3}[\mathcal{G},1,1]$. ∎

######  Proposition 29.

The problem $\pi_{3}[\mathcal{G},a,-1]$ is $\\#$P-hard apart from when
$a=1/2$, in which case it has a polynomial time algorithm.

###### Proof.

First note that there is a polynomial time algorithm for
$\pi_{3}[\mathcal{G},a,-1]$ because $(\frac{1}{2},-1)$ lies on $H_{1}$. Now
let $L$ be the line $y=-1$. By Proposition 27 we have

$\pi_{2}[\mathcal{G},L]\propto_{T}\pi_{3}[\mathcal{G},a,-1]$

for $a\notin\\{\frac{1}{2},1\\}$. So

$\pi_{3}[\mathcal{G},1,-1]\propto_{T}\pi_{3}[\mathcal{G},a,-1]$

for $a\neq 1/2$. By Proposition 28 we know that $\pi_{3}[\mathcal{G},1,-1]$ is
$\\#$P-hard. So the result follows. ∎

######  Proposition 30.

The problem $\pi_{3}[\mathcal{G},a,0]$ is $\\#$P-hard apart from when $a=0$,
in which case it has a polynomial time algorithm.

###### Proof.

Let $G$ be in $\mathcal{G}$. First note that evaluating the Tutte polynomial
of $G$ at the point $(0,0)$ is easy since $(0,0)$ lies on the hyperbola
$H_{1}$.

The rooted graph $G\sim S_{1}$ may be constructed from $G$ in time polynomial
in $|E(G)|$ and is bipartite, planar and connected. Applying Theorem 19 to $G$
and $S_{1}$ gives

$T(G\sim S_{1};a,0)=a^{\rho(G)}T(G;1,0).$

Since $a\neq 0$ we may compute $T(G;1,0)$ from $T(G\sim S_{1};a,0)$. Therefore
$\pi_{3}[\mathcal{G},1,0]\propto\pi_{3}[\mathcal{G},a,0]$. By Proposition 28,
$\pi_{3}[\mathcal{G},1,0]$ is $\\#$P-hard, and the result follows. ∎

Recall from Equation 1 that along $y=0$ the Tutte polynomial of a rooted graph
specializes to the characteristic polynomial. Therefore we have the following
corollary.

######  Corollary 31.

Computing the characteristic polynomial $p(G;k)$ of a connected rooted graph
$G$ is $\\#$P-hard for all $k\in\mathbb{Q}-\\{1\\}$. When $k=1$, there is a
polynomial time algorithm.

###### Proof.

Let $k$ be in $\mathbb{Q}$. We have

$p(G;k)=(-1)^{\rho(G)}T(G;1-k,0).$

By Proposition 30 evaluating $T(G;1-k,0)$ is $\\#$P-hard providing $k\neq 1$.
Furthermore when $k=1$ we have

$p(G;1)=(-1)^{\rho(G)}T(G;0,0)=\left\\{\begin{array}[]{ll}1&\text{ if $G$ is
edgeless; }\\\ 0&\text{ otherwise, }\\\ \end{array}\right.$

and so it is easy to compute (as expected since $(0,0)$ lies on $H_{1}$). ∎

We now consider points along the line $y=1$.

######  Proposition 32.

The problem $\pi_{2}[\mathcal{G},a,1]$ is $\\#$P-hard when $a\neq 1$.

###### Proof.

Let $G$ be a connected, planar, bipartite, unrooted graph with
$V(G)=\\{v_{1},\ldots,v_{n}\\}$. Now for $1\leq j\leq n$, let $G_{j}$ be the
graph in $\mathcal{G}$ obtained from $G$ by choosing $v_{j}$ to be the root.
Let $\rho_{j}$ denote the rank function of $G_{j}$ and $a_{i}(G_{j})$ be the
number of subsets $A$ of the edges of $G_{j}$ having size $i$ so that the root
component of $G|A$ is a tree. Then

$T(G_{j};x,1)=\sum_{\begin{subarray}{c}A\subseteq E:\\\
\rho_{j}(A)=|A|\end{subarray}}(x-1)^{\rho(G_{j})-|A|}=\sum_{i=0}^{\rho(G_{j})}a_{i}(G_{j})(x-1)^{\rho(G_{j})-i}.$

Let $a_{i}(G)$ denote the number of subtrees of $G$ with $i$ edges. Then

$a_{i}(G)=\sum_{j=1}^{n}\frac{a_{i}(G_{j})}{i+1}.$

This is because every subtree $T$ of $G$ with $i$ edges has $i+1$ vertices and
its edge set is one of the sets $A$ contributing to $a_{i}(G_{j})$ for the
$i+1$ choices of $j$ corresponding to its vertices.

Given an oracle for $\pi_{2}[\mathcal{G},H_{0}^{y}]$, we can compute
$a_{i}(G_{j})$ for $i=0,\ldots,|E(G)|$ and $1\leq j\leq n$ in time polynomial
in $|E(G)|$. So we can compute $a_{i}(G)$ and consequently the number of trees
of $G$ in time polynomial in $|E(G)|$. Thus

$\\#\text{SUBTREES}\propto_{T}\pi_{3}[\mathcal{G},H_{0}^{y}].$

By Proposition 26 we have

$\\#\text{SUBTREES}\propto_{T}\pi_{3}[\mathcal{G},H_{0}^{y}]\propto_{T}\pi_{2}[\mathcal{G},a,1]$

for $a\neq 1$. The result now follows from Proposition 22. ∎

We now summarize our results and prove Theorem 3.

###### Proof of Theorem 3.

Let $(a,b)$ be a point on $H_{\alpha}$ for some $\alpha$ in
$\mathbb{Q}-\\{0,1\\}$. By Proposition 26 we have
$\pi_{2}[\mathcal{G},H_{\alpha}]\propto_{T}\pi_{3}[\mathcal{G},a,b]$ providing
$b\notin\\{-1,0\\}$. The hyperbola $H_{\alpha}$ crosses the $x$-axis at the
point $(1-\alpha,0)$. By Proposition 30 the problem
$\pi_{3}[\mathcal{G},1-\alpha,0]$ is $\\#$P-hard since $\alpha\neq 1$. This
gives us a $\\#$P-hard point on each of these curves and therefore implies
$\pi_{2}[\mathcal{G},H_{\alpha}]$ is $\\#$P-hard for
$\alpha\in\mathbb{Q}-\\{0,1\\}$. Hence $\pi_{3}[\mathcal{G},a,b]$ is
$\\#$P-hard for $(a,b)\in H_{\alpha}$ with $\alpha\in\mathbb{Q}-\\{0,1\\}$ and
$b\neq-1$. The rest of the proof now follows directly by Propositions 28, 29
and 32, and the discussion concerning the easy points at the beginning of the
section. ∎

##  6 Rooted Digraphs

In this section we let $\mathbb{G}$ be the class of directed branching
greedoids of root-connected rooted digraphs, a class we denote by
$\mathcal{D}$. We consider the same three problems as in the previous section.
Again, it is more convenient to think of the input as being a root-connected
rooted digraph rather than its directed branching greedoid. We present
analogous results to those in the previous section by finding the
computational complexity of evaluating the Tutte polynomial of a root-
connected digraph at a fixed rational point, eventually proving Theorem 4.

We begin the proof by examining the easy points. Let $D$ be a rooted digraph
with edge set $E$ and rank function $\rho$. If a point $(a,b)$ lies on the
hyperbola $H_{1}$ then, following the remarks at the end of Section 3,
$T(D;a,b)$ is easily computed. We now show that evaluating $T(D;a,0)$ is easy
for all $a\in\mathbb{Q}$. A _sink_ in a digraph is a non-isolated vertex with
no outgoing edges. Suppose that $D$ is a root-connected, rooted digraph with
$s$ sinks. Then Gordon and McMahon [20] have shown that its characteristic
polynomial $p$ satisfies the following.

$p(D;\lambda)=\begin{cases}(-1)^{\rho(D)}(1-\lambda)^{s}&\text{if $D$ is
acyclic;}\\\ 0&\text{if $D$ has a directed cycle.}\end{cases}$

Using the relation $T(D;1-\lambda,0)=(-1)^{\rho(D)}p(D;\lambda)$ we see that

$T(D;x,0)=\begin{cases}x^{s}&\text{if $D$ is acyclic;}\\\ 0&\text{if $D$ has a
directed cycle.}\end{cases}$

It is easy to count the sinks in a digraph so the problem
$\pi_{3}[\mathcal{D},a,0]$ can be solved in polynomial time for any
$a\in\mathbb{Q}$. Every edge of a component of a rooted digraph other than the
root component is a greedoid loop, so if $D$ has such an edge then
$T(D;1-\lambda,0)=0$. Furthermore, the addition or removal of isolated
vertices makes no difference to $T(D)$. So $T(D;a,0)$ can be computed in
polynomial time for the class of all rooted digraphs.

We noted in Section 3 that $T(D;1,1)$ is the number of spanning arborescences
of the root component of $D$ rooted at $r$. This can be computed in polynomial
time using the Matrix–Tree theorem for directed graphs [6, 36].

We now move on to consider the hard points. The $k$-thickening operation will
again be crucial: the _$k$ -thickening_ $D^{k}$ of a root-connected digraph
$D$ is obtained by replacing every edge $e$ in $D$ by $k$ parallel edges that
have the same direction as $e$. We have $\Gamma(D^{k})\cong(\Gamma(D))^{k}$,
so Theorem 16 can be applied to give an expression for $T(D^{k})$.

The proof of the following proposition is omitted as it is analogous to that
of Proposition 26.

######  Proposition 33.

Let $L$ be either $H_{0}^{x},H_{0}^{y}$, or $H_{\alpha}$ for
$\alpha\in\mathbb{Q}-\\{0\\}$. Let $(a,b)$ be a point on $L$ such that
$(a,b)\neq(1,1)$ and $b\notin\\{-1,0\\}$. Then

$\pi_{2}[\mathcal{D},L]\propto_{T}\pi_{3}[\mathcal{D},a,b].$

We let $\overrightarrow{P_{k}}$ be the root-connected directed path of length
$k$ with the root being one of the leaves and $\overrightarrow{S_{k}}$ be the
root-connected directed star with $k$ edges emanating from the root. Then
$T(\overrightarrow{P_{k}};x,y)=1+\sum_{i=1}^{k}(x-1)^{i}y^{i-1}$ and
$T(\overrightarrow{S_{k}};x,y)=x^{k}$. The proof of the following proposition
is analogous to that of Proposition 27 with $\overrightarrow{P_{k}}$ and
$\overrightarrow{S_{k}}$ playing the roles of $P_{k}$ and $S_{k}$.

######  Proposition 34.

Let $L$ be the line $y=-1$. For $a\notin\\{\frac{1}{2},1\\}$ we have

$\pi_{2}[\mathcal{D},L]\propto_{T}\pi_{3}[\mathcal{D},a,-1].$

Next we classify the complexity of $\pi_{3}[\mathcal{D},1,b]$ for
$b\notin\\{0,1\\}$. Suppose we have a root-connected digraph $D$ and generate
a random subgraph $(D,p)$ of $D$ by deleting each edge with probability $p$
independently of all the other edges. Let $g(D;p)$ denote the probability that
$(D,p)$ is root-connected and let $g_{j}$ be the number of subsets $A$ of
$E(D)$ with size $j$ so that $D|A$ is root-connected. Notice that $g_{j}$ is
equal to the number of subsets $A$ of $E$ with $|A|=j$ and $\rho(A)=\rho(E)$.
Then

$g(D;p)=\sum_{j=0}^{|E(D)|}g_{j}p^{|E(D)|-j}(1-p)^{j}.$

Provan and Ball [35] showed that the following problem is $\\#$P-complete for
each rational $p$ with $0<p<1$, and computable in polynomial time when $p=0$
or $p=1$.

  * $\\#$Connectedness Reliability
Input: $D\in\mathcal{D}$.
Output: $g(D;p)$.

Note that we have restricted the input digraph to being root-connected which
Provan and Ball did not, but this does not make a difference to the
complexity, because if $D$ is not root-connected then clearly $g(D;p)=0$. We
now use this result to classify the complexity of points along the line $x=1$.

######  Proposition 35.

The computational problem $\pi_{3}[\mathcal{D},1,b]$ is $\\#$P-hard for $b>1$.

###### Proof.

Let $D$ be a root-connected digraph with edge set $E$ and rank function
$\rho$. Then for $0<p<1$ we have

$\displaystyle g(D;p)$ $\displaystyle=\sum_{\begin{subarray}{c}A\subseteq
E(D):\\\
\rho(A)=\rho(D)\end{subarray}}p^{|E(D)|-|A|}(1-p)^{|A|}=p^{|E(D)|-\rho(D)}(1-p)^{\rho(D)}\sum_{\begin{subarray}{c}A\subseteq
E(D):\\\
\rho(A)=\rho(D)\end{subarray}}\left(\frac{1-p}{p}\right)^{|A|-\rho(A)}$
$\displaystyle=p^{|E(D)|-\rho(D)}(1-p)^{\rho(D)}T\left(D;1,\frac{1}{p}\right).$

Evaluating $g(D;p)$ is therefore Turing-reducible to evaluating
$T(D;1,\frac{1}{p})$ for $0<p<1$. Therefore, $\pi_{3}[\mathcal{D},1,b]$ is
$\\#$P-hard for $b>1$. ∎

In order to determine the complexity of the point $\pi_{3}[\mathcal{D},1,-1]$,
we introduce a new operation on root-connected digraphs which we call the _$k$
-digon-stretch_. We define a _tailed $k$-digon_ from $u$ to $v$ to be the
digraph defined as follows. The vertex set is
$\\{w_{0}=u,w_{1},\ldots,w_{k},w_{k+1}=v\\}$. There is an edge $w_{0}w_{1}$
and a directed cycle of length $2$ on $w_{i}$ and $w_{i+1}$ for each $i$ with
$1\leq i\leq k$. An example of a tailed $k$-digon is shown in Figure 2. (The
labelling of the edges will be needed later.) For a root-connected digraph
$D$, the $k$-digon-stretch of $D$ is constructed by replacing every directed
edge $uv$ in $D$ by a tailed $k$-digon from $u$ to $v$. We denote the
$k$-digon-stretch of $D$ by $D_{k}$.

$w_{0}$$w_{1}$$w_{2}$$w_{3}$$w_{k}$$w_{k+1}$$\ldots$$p_{0}$$p_{1}$$q_{1}$$p_{2}$$q_{2}$$p_{k}$$q_{k}$
Figure 2: A tailed $k$-digon.

######  Theorem 36.

Let $D$ be a root-connected digraph. Then

$T(D_{k};1,y)=(k+1)^{|E(D)|-\rho(D)}y^{k|E(D)|}T\left(D;1,\frac{k+y}{k+1}\right).$

###### Proof.

Let $S$ be a subset of edges of a tailed $k$-digon from $u$ to $v$. If $S$
contains all the edges on the unique directed $uv$-path through the $k$-tailed
digon, then $S$ is said to _admit a $uv$-dipath_. Let $A$ be a subset of
$E(D_{k})$ and $P(A)$ be the set of edges $uv$ in $D$ for which $A$ admits a
$uv$-dipath.

We have $\rho(A)=\rho(D_{k})$ if and only if

  1. (i)

for each directed edge $uv$ of $D$ and each vertex $w$ of the corresponding
tailed $k$-digon from $u$ to $v$ in $D_{k}$, $A$ includes the edges of a path
in the $k$-tailed digon from either $u$ or $v$ to $w$, and

  2. (ii)

$\rho(P(A))=\rho(D)$.

Note that $\rho(D_{k})=k|E(D)|+\rho(D)$. We can write $A$ as the disjoint
union $A=\bigcup_{e\in E(D)}A_{e}$ where $A_{e}$ is the set of edges of $A$
belonging to the tailed $k$-digon corresponding to $e$. The Tutte polynomial
of $D_{k}$ along the line $x=1$ is given by

$\displaystyle T(D_{k};1,y)=\sum_{\begin{subarray}{c}A\subseteq E(D_{k}):\\\
\rho(A)=\rho(D_{k})\end{subarray}}(y-1)^{|A|-\rho(D_{k})}=\sum_{\begin{subarray}{c}B\subseteq
E(D):\\\ \rho(B)=\rho(D)\end{subarray}}\sum_{\begin{subarray}{c}A\subseteq
E(D_{k}):\\\ \rho(A)=\rho(D_{k})\\\
P(A)=B\end{subarray}}(y-1)^{|A|-\rho(D_{k})}$
$\displaystyle=\sum_{\begin{subarray}{c}B\subseteq E(D):\\\
\rho(B)=\rho(D)\end{subarray}}\sum_{\begin{subarray}{c}A\subseteq E(D_{k}):\\\
\rho(A)=\rho(D_{k}),\\\
P(A)=B\end{subarray}}\underbrace{\left(\prod_{\begin{subarray}{c}e\in E(D):\\\
e\notin
P(A)\end{subarray}}(y-1)^{|A_{e}|-k}\right)}_{(1)}\underbrace{\left(\prod_{\begin{subarray}{c}e\in
E(D):\\\ e\in
P(A)\end{subarray}}(y-1)^{|A_{e}|-(k+1)}\right)}_{(2)}(y-1)^{|P(A)|-\rho(D)}.$
(8)

Consider a tailed $k$-digon from $u$ to $v$ with vertex set labelled as
described just before the statement of the theorem. For $0\leq i\leq k$, let
$p_{i}$ denote the edge $w_{i}w_{i+1}$; for $1\leq i\leq k$, let $q_{i}$
denote the edge $w_{i+1}w_{i}$.

In the first product above we are considering edges $e=uv$ for which $e\notin
P(A)$. Thus $A_{e}$ does not contain all of $p_{0}$, …, $p_{k}$. Let $j$ be
the smallest integer such that $p_{j}\notin A_{e}$. As we are only interested
in sets $A$ with $\rho(A)=\rho(D_{k})$, each of $q_{j+1}$, …, $q_{k}$ belongs
to $A_{e}$. Thus $|A_{e}|\geq k$. Moreover each of $p_{j+1}$, …, $p_{k}$ and
$q_{1}$, …, $q_{j}$ may or may not belong to $A_{e}$. As there are $k+1$
possibilities for $j$, summing

$\prod_{\begin{subarray}{c}e\in E(D):\\\ e\notin
P(A)\end{subarray}}(y-1)^{|A_{e}|-k}$

over all possible choices of $A_{e}$ for $e\notin P(A)$ gives
$\left((k+1)y^{k}\right)^{|E(D)|-|P(A)|}$.

In the second product above we are considering edges $e=uv$ for which $e\in
P(A)$. Thus $A_{e}$ contains all of $p_{0}$, …, $p_{k}$. So $|A_{e}|\geq k+1$.
Moreover each of $q_{1}$, …, $q_{k}$ may or may not belong to $A_{e}$. Summing

$\prod_{\begin{subarray}{c}e\in E(D):\\\ e\in
P(A)\end{subarray}}(y-1)^{|A_{e}|-(k+1)}$

over all possible choices of $A_{e}$ for $e\in P(A)$ gives $y^{k|P(A)|}$.

Thus the right side of Equation 8 becomes

$\displaystyle{\sum_{\begin{subarray}{c}B\subseteq E(D):\\\
\rho(B)=\rho(D)\end{subarray}}y^{k|B|}\left((k+1)y^{k}\right)^{|{E(D)}|-|B|}(y-1)^{|B|-\rho(D)}}$
$\displaystyle=y^{k|E(D)|}\sum_{\begin{subarray}{c}B\subseteq E(D):\\\
\rho(B)=\rho(D)\end{subarray}}(k+1)^{\rho(B)-|B|+|E(D)|-\rho(D)}(y-1)^{|B|-\rho(B)}$
$\displaystyle=y^{k|E(D)|}(k+1)^{|E(D)|-\rho(D)}T\left(D;1,\frac{y+k}{k+1}\right).$

∎

We now complete the classification of complexity for points on the line
$H_{0}^{x}$.

######  Proposition 37.

The problem $\pi_{3}[\mathcal{D},1,b]$ is $\\#$P-hard for $b\notin\\{0,1\\}$.

###### Proof.

For $b\notin\\{-1,0,1\\}$ the result follows immediately from Propositions 33
and 35. By Theorem 36, if $D$ is root-connected, then

$T(D_{2};1,-1)=3^{|E(D)|-\rho(D)}T\left(D;1,\frac{1}{3}\right).$

As $D_{2}$ is root-connected and can be constructed from $D$ in polynomial
time, $\pi_{3}(\mathcal{D},1,\frac{1}{3})\propto\pi_{3}(\mathcal{D},1,-1)$, so
$\pi_{3}(\mathcal{D},1,-1)$ is $\\#$P-hard. ∎

We now show that evaluating the Tutte polynomial of a root-connected digraph
at most points on the hyperbola $H_{\alpha}$ for $\alpha\neq 0$ is at least as
hard as evaluating it at the point $(1+\alpha,2)$.

######  Proposition 38.

Let $\alpha$ be in $\mathbb{Q}-\\{0\\}$ and $(a,b)$ be a point on $H_{\alpha}$
with $b\notin\\{-1,0\\}$, then

$\pi_{3}[\mathcal{D},1+\alpha,2]\propto_{T}\pi_{3}[\mathcal{D},a,b].$

###### Proof.

For $\alpha$ in $\mathbb{Q}-\\{0\\}$, the hyperbola $H_{\alpha}$ crosses the
line $y=2$ at the point $(1+\alpha,2)$. By Proposition 33, we know that for
any point $(a,b)$ on $H_{\alpha}$ with $b\notin\\{-1,0\\}$ we have
$\pi_{3}[\mathcal{D},1+\alpha,2]\propto_{T}\pi_{2}[\mathcal{D},H_{\alpha}]\propto_{T}\pi_{3}[\mathcal{D},a,b]$.
∎

We will now show that evaluating the Tutte polynomial of a root-connected
digraph at most of the points on the line $y=2$ is $\\#$P-hard. This will
enable us to classify the complexity of most points lying on the hyperbola
$H_{\alpha}$ for all $\alpha\in\mathbb{Q}-\\{0\\}$.

######  Proposition 39.

The problem $\pi_{3}[\mathcal{D},a,2]$ is $\\#$P-hard for $a\neq 2$.

###### Proof.

We begin by proving that when $L$ is the line $y=2$ we have

$\pi_{2}[\mathcal{D},L]\propto_{T}\pi_{3}[\mathcal{D},a,2]$

for $a\notin\\{1,2\\}$. Let $D$ be a root-connected digraph and let $z=x-1$.
Along $L$ the Tutte polynomial of $D$ has the form

$T(D;x,2)=\sum_{A\subseteq
E(D)}z^{\rho(D)-\rho(A)}=\sum_{i=0}^{\rho(D)}t_{i}z^{i}$

for some $t_{0},t_{1},\ldots,t_{\rho(D)}$. We will now show that for most
values of $a$, we may determine all of the coefficients $t_{i}$ in polynomial
time from $T(D\sim\overrightarrow{S_{k}};a,2)$ for $k=0,1,\ldots,\rho(D)$. For
each such $k$, $D\sim\overrightarrow{S_{k}}$ is root-connected and can be
constructed in polynomial time. By Theorem 19, we have

$T(D\sim\overrightarrow{S_{k}};a,2)=a^{k\rho(D)}T\left(D;\frac{2^{k}(a-1)^{k+1}}{a^{k}}+1,2\right).$

Therefore we may compute $T\left(D;\frac{2^{k}(a-1)^{k+1}}{a^{k}}+1,2\right)$
from $T(D\sim\overrightarrow{S_{k}};a,2)$ when $a\neq 0$. For
$a\notin\\{0,\frac{2}{3},1,2\\}$ the values of
$\left(\frac{2^{k}(a-1)^{k+1}}{a^{k}}+1,2\right)$ are pairwise distinct for
$k=0,1,\ldots,\rho(D)$. Therefore by evaluating
$T(D\sim\overrightarrow{S_{k}};a,2)$ for $k=0,1,\ldots,\rho(D)$ where
$a\notin\\{0,\frac{2}{3},1,2\\}$, we obtain $\sum_{i=0}^{\rho(D)}t_{i}z^{i}$
for $\rho(D)+1$ distinct values of $z$. This gives us $\rho(D)+1$ linear
equations for the coefficients $t_{i}$, and so by Lemma 13, they may be
recovered in polynomial time. Hence evaluating the Tutte polynomial of a root-
connected digraph along the line $y=2$ is Turing-reducible to evaluating it at
the point $(a,2)$ for $a\notin\\{0,\frac{2}{3},1,2\\}$.

We now consider the cases where $a=0$ or $a=\frac{2}{3}$. The digraph
$D\sim\overrightarrow{P_{2}}$ is root-connected and may be constructed in
polynomial time. By Theorem 19, we have

$T(D\sim\overrightarrow{P_{2}};0,2)=2^{\rho(D)}T\left(D;\frac{(-1)^{3}2^{2}}{2}+1,2\right)\\\
=2^{\rho(D)}T(D;-1,2).$

Therefore $\pi_{3}[\mathcal{D},-1,2]\propto_{T}\pi_{3}[\mathcal{D},0,2]$.
Similarly we have

$T\left(D\sim\overrightarrow{P_{2}};\frac{2}{3},2\right)=2^{\rho(D)}T\left(D;\frac{(-\frac{1}{3})^{3}2^{2}}{2}+1,2\right)=2^{\rho(D)}T\left(D;\frac{25}{27},2\right).$

Therefore $\pi_{3}[\mathcal{D},25/27,2]\propto_{T}\pi_{3}[\mathcal{D},2/3,2]$.
Putting all this together we get
$\pi_{2}[\mathcal{D},L]\propto_{T}\pi_{3}[\mathcal{D},a,2]$ for all $a$ in
$\mathbb{Q}-\\{1,2\\}$. Consequently
$\pi_{3}[\mathcal{D},1,2]\propto_{T}\pi_{3}[\mathcal{D},a,2]$, for all $a$ in
$\mathbb{Q}-\\{2\\}$.

By Proposition 37, we know that $\pi_{3}[\mathcal{D},1,2]$ is $\\#$P-hard.
This completes the proof. ∎

######  Theorem 40.

Let $\alpha$ be in $\mathbb{Q}-\\{0,1\\}$ and $(a,b)$ be a point on
$H_{\alpha}$ with $b\neq 0$. Then $\pi_{3}[\mathcal{D},a,b]$ is $\\#$P-hard.

###### Proof.

Suppose first that $b\neq-1$. By Proposition 38,
$\pi_{3}[\mathcal{D},1+\alpha,2]\propto_{T}\pi_{3}[\mathcal{D},a,b]$. As
$\alpha\neq 1$, Proposition 39, implies $\pi_{3}[\mathcal{D},a,b]$ is
$\\#$P-hard.

Now suppose that $b=-1$. As $(a,b)\notin H_{1}$, we have $a\neq\frac{1}{2}$.
So by Proposition 34,
$\pi_{3}[\mathcal{D},1,-1]\propto_{T}\pi_{3}[\mathcal{D},a,-1]$. By
Proposition 37, $\pi_{3}[\mathcal{D},1,-1]$ is $\\#$P-hard. Therefore
$\pi_{3}[\mathcal{D},a,-1]$ is $\\#$P-hard. ∎

The only remaining points we need to classify are those lying on the line
$y=1$. To do this we prove that the problem of evaluating the Tutte polynomial
of a root-connected digraph at most fixed points along this line is at least
as hard as the analogous problem for rooted graphs.

######  Theorem 41.

The problem $\pi_{3}[\mathcal{D},a,1]$ is $\\#$P-hard for $a$ in
$\mathbb{Q}-\\{1\\}$.

###### Proof.

Let $G$ be a connected rooted graph with root $r$. Construct a rooted graph
$D$ with root $r$ by replacing every edge of $G$ by a pair of oppositely
directed edges. Then $D$ is root-connected and can be constructed from $G$ in
polynomial time. We can define a natural map $f:2^{E(D)}\rightarrow 2^{E(G)}$
so that $f(A)$ is the set of edges of $G$ for which at least one corresponding
directed edge is included in $A$.

If $\rho_{G}(A)=|A|$ then the root component of $G|A$ is a tree and includes
all the edges of $A$. Similarly if $\rho_{D}(A^{\prime})=|A^{\prime}|$ then
the root component of $D|A^{\prime}$ is an arborescence rooted at $r$ and
includes all the edges of $A^{\prime}$. For every subset $A$ of $E$ with
$\rho_{G}(A)=|A|$, there is precisely one choice of $A^{\prime}$ with
$\rho_{D}(A^{\prime})=|A^{\prime}|$ and $f(A^{\prime})=A$, obtained by
directing all the edges of $A$ away from $r$. Thus there is a one-to-one
correspondence between subsets $A$ of $E$ with $\rho_{G}(A)=|A|$ and subsets
$A^{\prime}$ of $E(D)$ with $\rho_{D}(A^{\prime})=|A^{\prime}|$, and this
correspondence preserves the sizes of the sets. Therefore we have

$T(D;x,1)=\sum_{\begin{subarray}{c}A^{\prime}\subseteq E(D):\\\
|A^{\prime}|=\rho_{D}(A^{\prime})\end{subarray}}(x-1)^{\rho(D)-|A^{\prime}|}=\sum_{\begin{subarray}{c}A\subseteq
E:\\\ |A|=\rho_{G}(A)\end{subarray}}(x-1)^{\rho(G)-|A|}=T(G;x,1).$

So $\pi_{3}[\mathcal{G},a,1]\propto_{T}\pi_{3}[\mathcal{D},a,1]$. So by
Proposition 32, we deduce that $\pi_{3}[\mathcal{D},a,1]$ is $\\#$P-hard for
$a\neq 1$. ∎

##  7 Binary Greedoids

In our final section we let $\mathbb{G}$ be the class of binary greedoids. We
present analogous results to those in the previous section by finding the
computational complexity of evaluating the Tutte polynomial of a binary
greedoid at a fixed rational point, eventually proving Theorem 5. As before,
it is convenient to think of the input as being a binary matrix rather than
its binary greedoid.

We begin by examining the easy points of Theorem 5. Let $\Gamma$ be a binary
greedoid with element set $E$ and rank function $\rho$. If a point $(a,b)$
lies on the hyperbola $H_{1}$ then, following the remarks at the end of
Section 3 $T(\Gamma;a,b)$ is easily computed.

We now focus on the hard points. The $k$-thickening operation will again be
crucial. Given a binary matrix $M$, the $k$-thickening $M^{k}$ of $M$ is
obtained by replacing each column of $M$ by $k$ copies of the column. We have
$\Gamma(M^{k})=(\Gamma(M))^{k}$, so Theorem 16 can be applied to compute the
$T(M^{k})$ in terms of $T(M)$. Let $I_{k}$ denote the $k\times k$ identity
matrix. Then $\Gamma(I_{k})\cong\Gamma(P_{k})$, so
$T(I_{k})=T(P_{k})=1+\sum_{j=1}^{k}(x-1)^{j}y^{j-1}$.

The proof of the following proposition is analogous to that of Proposition 26,
thus we omit it.

######  Proposition 42.

Let $L$ be either $H_{0}^{x},H_{0}^{y}$, or $H_{\alpha}$ for
$\alpha\in\mathbb{Q}-\\{0\\}$. Let $(a,b)$ be a point on $L$ such that
$(a,b)\neq(1,1)$ and $b\notin\\{-1,0\\}$. Then

$\pi_{2}[\mathcal{B},L]\propto_{T}\pi_{3}[\mathcal{B},a,b].$

A binary matroid is a matroid that can be represented over the finite field
$\mathbb{Z}_{2}$. Every graphic matroid is also binary, so Theorem 2 and Lemma
11 imply that $\pi_{2}[\mathcal{B},1,b]$ is $\\#$P-hard providing $b\neq 1$.
This immediately gives the following.

######  Proposition 43.

The problem $\pi_{3}[\mathcal{B},1,b]$ is $\\#$P-hard for all $b$ in
$\mathbb{Q}-\\{1\\}$.

The following result has been announced by Vertigan in [9] and slightly later
in [42], but up until now no written proof has been published. For
completeness, we provide a proof in Appendix A.

######  Theorem 44 (Vertigan).

Evaluating the Tutte polynomial of a binary matroid is $\\#$P-hard at the
point $(1,1)$.

Using this result, we are able to fill in the missing point $(1,1)$ from the
previous result and also establish hardness along the line $y=1$.

######  Proposition 45.

The problem $\pi_{3}[\mathcal{B},a,1]$ is $\\#$P-hard for all $a$.

###### Proof.

By Proposition 42 we have
$\pi_{2}[\mathcal{B},H_{0}^{y}]\propto_{T}\pi_{3}[\mathcal{B},a,1]$ for $a\neq
1$. The result now follows Theorem 44. ∎

######  Proposition 46.

Let $\Gamma$ be a binary greedoid and let $\Gamma^{\prime}=\Gamma(I_{k})$.
Then

$T(\Gamma\approx\Gamma^{\prime};x,y)=T(\Gamma;x,y)(x-1)^{k}y^{k}+T(\Gamma;1,y)\Big{(}1+\sum_{j=1}^{k}(x-1)^{j}y^{j-1}-(x-1)^{k}y^{k}\Big{)}.$

###### Proof.

The proof follows immediately from Theorem 20. ∎

We now classify the complexity of $\pi_{3}[\mathcal{B},a,b]$ when $b=0$ or
$b=-1$.

######  Proposition 47.

The problem $\pi_{3}[\mathcal{B},a,0]$ is $\\#$P-hard for all $a\neq 0$.

###### Proof.

Let $M$ be a binary matrix with linearly independent rows. Then from Theorem
20, we have $T(M\approx I_{1};a,0)=aT(M;1,0)$. Therefore when $a\neq 0$ we
have $\pi_{2}[\mathcal{B},1,0]\propto_{T}\pi_{2}[\mathcal{B},a,0]$. The result
now follows from Proposition 43. ∎

######  Proposition 48.

The problem $\pi_{3}[\mathcal{B},a,-1]$ is $\\#P$-hard for all
$a\neq\frac{1}{2}$.

###### Proof.

Let $M$ be a binary matrix with linearly independent rows. We have

$(2a-1)T(M;1,-1)=T(M\approx I_{1};a,-1)+(a-1)T(M;a,-1).$

Thus, $\pi_{3}[\mathcal{B},1,-1]\propto_{T}\pi_{3}[\mathcal{B},a,-1]$. By
using Proposition 43, we deduce that $\pi_{0}[\mathcal{B},a,-1]$ is
$\\#$P-hard. ∎

Our final result completes the proof of Theorem 5.

######  Theorem 49.

Let $(a,b)$ be a point in $H_{\alpha}$ for $\alpha\in\mathbb{Q}-\\{0,1\\}$
with $b\neq-1$. Then $\pi_{3}[\mathcal{B},a,b]$ is $\\#$P-hard.

###### Proof.

For $\alpha\in\mathbb{Q}-\\{0,1\\}$, the hyperbola $H_{\alpha}$ crosses the
$x$-axis at the point $(1-\alpha,0)$. By Proposition 42 since $b\neq-1$ and
$(a,b)\neq(1,1)$ we have
$\pi_{3}[\mathcal{B},1-\alpha,0]\propto_{T}\pi_{3}[\mathcal{B},a,b]$. The
result now follows from Proposition 47. ∎

##  Appendix A Counting bases in a represented matroid

In this appendix, we present a proof that counting the number of bases of a
represented matroid is $\\#$P-complete. More precisely, we consider the
following family of counting problems. Let $\mathbb{F}$ be a field.

  * Counting Bases of $\mathbb{F}$-Represented Matroids
Input: A $(0,1)$-matrix $A$.
Output: The number of bases of $M(A)$, the matroid represented by $A$ over the
field $\mathbb{F}$.

######  Theorem 50.

For every field $\mathbb{F}$, Counting Bases of $\mathbb{F}$-Represented
Matroids is $\\#$P-complete.

A proof of this result was announced nearly 30 years ago by Dirk Vertigan — it
first seems to have been referred to in [9] and slightly later in [42], where
it is described as an unpublished manuscript — but no written proof has been
circulated. Sketches of the proof have been presented by Vertigan in talks,
for example, at the Conference for James Oxley in 2019 [40]. The second author
was present at this meeting and the material in this section has been produced
from his incomplete recollection of the talk. All the key ideas are due to
Vertigan but the details including any errors, omissions or unnecessary
complications are due to the authors. As pointed out to us by Dillon Mayhew
[31], Vertigan’s proof presented in [40] introduced an intermediate step
involving weighted bases; our proof does not require this intermediate step
but this comes at the cost of introducing a larger matrix in the reduction. We
provide the proof, partly as a service to the community because we know of
several colleagues who have tried to recreate it, but primarily because a
referee has pointed out the undesirability of relying on an unpublished
result. Although our original aim was only to establish the special case of
Theorem 50 relevant for our work, it turns out that little extra effort is
required to prove Theorem 50 in full generality.

We require very little matroid theory other than basic notions such as rank,
circuits and the closure operator. As we work exclusively with matroids having
representations drawn from a specific family of matrices considered over
different fields, the claims we make about the associated matroids can easily
be checked by considering the representing matrices. For background on
matroids see [33].

A graph is _simple_ if it has no loops or parallel edges. To prove hardness,
we give a reduction from counting perfect matchings in a simple graph, a
problem which is well-known to be $\\#$P-complete [39]. Clearly, it makes no
difference to the complexity of counting perfect matchings if we forbid our
graphs from having isolated vertices. Given such a graph $G$ with $n$
vertices, we construct a family of matrices $\\{A_{i}:1\leq i\leq\lfloor
n/2\rfloor+1\\}$ with entries in $\\{0,1\\}$. By considering these matrices as
being defined over different fields, we obtain two corresponding families of
matroids. Which family arises depends on whether the field has characteristic
two. Thus the proof of Theorem 50 splits into two parts depending on whether
the characteristic of the underlying field is two.

We shall generally think of matrices as coming with sets indexing their rows
and columns. If $A$ is a matrix with sets $X$ and $Y$ indexing its rows and
columns respectively, then we say that $A$ is an $X\times Y$ matrix. For non-
empty subsets $X^{\prime}$ and $Y^{\prime}$ of $X$ and $Y$, respectively,
$A[X^{\prime},Y^{\prime}]$ is the submatrix of $A$ obtained by deleting the
rows indexed by elements of $X-X^{\prime}$ and the columns indexed by elements
of $Y-Y^{\prime}$.

Suppose that $G$ is a simple graph without isolated vertices having vertex set
$\\{v_{1},\ldots,v_{n}\\}$ and edge set $\\{e_{1},\ldots,e_{m}\\}$. Let $k$ be
a strictly positive integer. Let

$\displaystyle X$
$\displaystyle=\\{v_{1},\ldots,v_{n},e_{1},\ldots,e_{m}\\}\cup\\{f_{i,j}:1\leq
i\leq m,1\leq j\leq k\\}$ and $\displaystyle Y$
$\displaystyle=\\{v_{1},\ldots,v_{n},e_{1},\ldots,e_{m}\\}\cup\\{w_{i,j},x_{i,j},y_{i,j},z_{i,j}:1\leq
i\leq m,1\leq j\leq k\\}.$

Here both $X$ and $Y$ include all the vertices and edges of $G$, together with
several new elements. The matrix $A_{k}$ is an $X\times Y$ matrix. To specify
its entries suppose that $e_{i}$ has endvertices $v_{a}$ and $v_{b}$ with
$a<b$. Then for each $j$ with $1\leq j\leq k$, taking
$X^{\prime}=\\{v_{a},v_{b},f_{i,j}\\}$ and
$Y^{\prime}=\\{v_{a},v_{b},e_{i},w_{i,j},x_{i,j},y_{i,j},z_{i,j}\\}$, we let

${A_{k}}[X^{\prime},Y^{\prime}]=\bNiceMatrix[first-row,first-
col]&v_{a}v_{b}e_{i}w_{i,j}x_{i,j}y_{i,j}z_{i,j}\\\ v_{a}1010101\\\
v_{b}0110011\\\ f_{i,j}0001111.$

We complete the definition of $A_{k}$ by setting every as yet unspecified
entry to zero.

Fix $\mathbb{F}$ and let $N_{k}=M(A_{k})$, that is, the matroid with element
set $Y$ represented by $A_{k}$ considered over $\mathbb{F}$. Taking
$Y^{\prime}$ as in the previous paragraph, if $\mathbb{F}$ has characteristic
two, then $N_{k}|Y^{\prime}$ is isomorphic to the Fano matroid $F_{7}$ and
otherwise $N_{k}|Y^{\prime}$ is isomorphic to the non-Fano matroid $F_{7}^{-}$
obtained from $F_{7}$ by relaxing the circuit-hyperplane
$\\{e_{i},x_{i,j},y_{i,j}\\}$. Now let $M_{k}=N_{k}\setminus(V\cup E)$. Note
that $r(M_{k})=r(N_{k})=|V|+|E|k$ and that for each vertex $v$ and edge $e$ of
$G$, $N_{k}$ contains elements $e$ and $v$, but $M_{k}$ contains neither.

We shall show that for each $k$, every basis of $M_{k}$ corresponds to what we
call a _feasible template_ of $G$, that is, a subgraph of $G$ in which some
edges are directed (possibly in both directions) and some are labelled,
satisfying certain properties which we describe below. In particular, we will
see that the bidirected edges in a feasible template form a matching in $G$.
Furthermore, the number of bases of $M_{k}$ corresponding to each feasible
template depends only on $k$ and the numbers of edges directed and labelled in
each possible way, and is easily computed. By varying $k$ and counting the
number of bases of $M_{k}$, we can recover the number of feasible templates
with each possible number of bidirected edges. The number of feasible
templates with $n/2$ bidirected edges is equal to the number of perfect
matchings of $G$.

Let $G$ be a simple graph without isolated vertices, having vertex set
$V=\\{v_{1},\ldots,v_{n}\\}$ and edge set $E=\\{e_{1},\ldots,e_{m}\\}$. A
_template_ of $G$ is a spanning subgraph of $G$ in which edges may be
bidirected, that is, two arrows are affixed one pointing to each endvertex,
(uni)directed or undirected, and are labelled according to the following
rules.

  * •

Every bidirected edge is unlabelled.

  * •

A (uni)directed edge $e=v_{a}v_{b}$ with $a<b$ is labelled either $wx$ or $yz$
if $e$ is directed towards $a$ and is labelled either $wy$ or $xz$ if $e$ is
directed towards $b$.

  * •

An undirected edge is labelled either $wz$ or $xy$.

Even though the matroid $M_{k}$ itself depends on whether $\mathbb{F}$ has
characteristic two, the proofs of the two cases have a great deal in common.
To prevent repetition we describe the common material here, before finishing
the two cases separately. For $1\leq i\leq m$ and $1\leq j\leq k$, let
$F_{i,j}=\\{w_{i,j},x_{i,j},y_{i,j},z_{i,j}\\}$ and for $1\leq i\leq m$, let
$F_{i}=\bigcup_{1\leq j\leq k}F_{i,j}$. For all $i$ and $j$, the set $F_{i,j}$
is a circuit and $r(M_{k}\setminus F_{i,j})<r(M_{k})$. Let $B$ be a basis of
$M_{k}$. Then $1\leq|B\cap F_{i,j}|\leq 3$. Moreover, for all $i$,
$r(F_{i})=k+2$ and $r(M_{k}\setminus F_{i})\leq r(M_{k})-k$, so $k\leq|B\cap
F_{i}|\leq k+2$. The main idea in the proof is to use templates to classify
each basis $B$ of $M_{k}$ by specifying $|B\cap F_{i}|$ for each $i$ and when
$|B\cap F_{i}|=k+1$, implying that $|B\cap F_{i,j}|=2$ for precisely one value
$j^{*}$ of $j$, additionally specifying $B\cap F_{i,j^{*}}$.

Suppose edge $e_{i}$ joins vertices $v_{a}$ and $v_{b}$ in $G$ and $a<b$. If
$|B\cap F_{i}|=k$, then $\operatorname{cl}_{N_{k}}(B\cap
F_{i})-E(M_{k})=\emptyset$, and if $|B\cap F_{i}|=k+2$, then
$\operatorname{cl}_{N_{k}}(B\cap F_{i})-E(M_{k})=\\{v_{a},v_{b},e_{i}\\}$. If
$|B\cap F_{i}|=k+1$, then $|B\cap F_{i,j}|=2$ for precisely one value $j^{*}$
of $j$ and $\operatorname{cl}_{N_{k}}(B\cap F_{i})-E(M_{k})$ depends on $B\cap
F_{i,j^{*}}$.

  * •

If $B\cap F_{i,j^{*}}$ is $\\{w,x\\}$ or $\\{y,z\\}$, then
$\operatorname{cl}_{N_{k}}(B\cap F_{i})-E(M_{k})=\\{v_{a}\\}$.

  * •

If $B\cap F_{i,j^{*}}$ is $\\{w,y\\}$ or $\\{x,z\\}$, then
$\operatorname{cl}_{N_{k}}(B\cap F_{i})-E(M_{k})=\\{v_{b}\\}$.

  * •

If $B\cap F_{i,j^{*}}$ is $\\{w,z\\}$, then $\operatorname{cl}_{N_{k}}(B\cap
F_{i})-E(M_{k})=\\{e_{i}\\}$.

  * •

If $B\cap F_{i,j^{*}}$ is $\\{x,y\\}$, then $\operatorname{cl}_{N_{k}}(B\cap
F_{i})-E(M_{k})$ is $\\{e_{i}\\}$ when $\mathbb{F}$ has characteristic two and
is empty otherwise.

To each subset $S$ of $E(M_{k})$, such that for all $i$, $S\cap F_{i}$ is
independent and for all $i$ and $j$, $|S\cap F_{i,j}|\geq 1$, we associate a
template $T(S)$ of $G$, by starting with an edgeless graph with vertex set
$V(G)$ and doing the following for each edge $e_{i}$ of $G$ such that $|S\cap
F_{i,j}|>1$ for some $j$. Suppose that $e_{i}=v_{a}v_{b}$ with $a<b$. We first
consider whether to add $e_{i}$ to $T(S)$ and whether to direct it.

  * •

If $\operatorname{cl}_{N_{k}}(S\cap F_{i})-E(M_{k})=\\{v_{a},v_{b},e_{i}\\}$,
then add $e_{i}$ to $T(S)$ and bidirect it.

  * •

If $\operatorname{cl}_{N_{k}}(S\cap F_{i})-E(M_{k})=\\{v_{a}\\}$, then add
$e_{i}$ to $T(S)$ and direct it from $v_{b}$ to $v_{a}$.

  * •

If $\operatorname{cl}_{N_{k}}(S\cap F_{i})-E(M_{k})=\\{v_{b}\\}$, then add
$e_{i}$ to $T(S)$ and direct it from $v_{a}$ to $v_{b}$.

  * •

If $\operatorname{cl}_{N_{k}}(S\cap F_{i})-E(M_{k})\subseteq\\{e_{i}\\}$, then
add $e_{i}$ to $T(S)$ (and do not direct it).

In the last three cases above, we also label $e_{i}$. To do this let $j^{*}$
be the unique value of $j$ such that $|S\cap F_{i,j}|=2$. Then label $e_{i}$
with the elements of $S\cap F_{i,j^{*}}$, but with their subscripts omitted.
In this way the edge $e_{i}$ is given two labels from the set $\\{w,x,y,z\\}$.

###  A.1 $\mathbb{F}$ has characteristic two

We now focus on the case when $\mathbb{F}$ has characteristic two. The
following result is the key step in the proof.

######  Proposition 51.

A subset $B$ of $E(M_{k})$ is a basis of $M_{k}$ if and only if all of the
following conditions hold.

  1. 1.

For all $i$, $B\cap F_{i}$ is independent.

  2. 2.

For all $i$ and $j$, $|B\cap F_{i,j}|\geq 1$.

  3. 3.

The subgraph of $T(B)$ induced by its undirected edges is acyclic.

  4. 4.

It is possible to direct the undirected edges of $T(B)$ so that every vertex
has indegree one.

###### Proof.

We first show that the conditions are collectively sufficient. Suppose that
$B$ satisfies each of the conditions and that $T(B)$ has $b$ bidirected edges,
$r$ (uni)directed edges and $u$ undirected edges. Then the last condition
implies that $2b+r+u=n$. Combining this with the first two conditions gives
$|B|=km+2b+r+u=km+n=r(M_{k})$. So, it is sufficient to prove that
$r(B)=r(M_{k})$. We will show that the last two conditions imply that
$v_{i}\in\operatorname{cl}_{N_{k}}(B)$ for $i=1,\ldots,n$. Then the second
condition ensures that $\operatorname{cl}_{N_{k}}(B)=E(N_{k})$ and
consequently $r(B)=r(N_{k})=r(M_{k})$ as required.

Consider a vertex $v$ of $G$. The last two conditions imply that there is a
(possibly empty) path $P$ in $T(B)$ between $v$ and a vertex $v^{\prime}$
having indegree one and comprising only undirected edges. Suppose that the
vertices of $P$ in order are
$v_{j_{1}}=v^{\prime},v_{j_{2}},\ldots,v_{j_{l}}=v$ and that for $1\leq h\leq
l-1$, the edge joining $v_{j_{h}}$ and $v_{j_{h+1}}$ in $P$ is $e_{i_{h}}$.
Then
$\\{v_{j_{1}},e_{i_{1}},\ldots,e_{i_{l-1}}\\}\subseteq\operatorname{cl}_{N_{k}}(B)$.
As $v_{j_{h}}\in\operatorname{cl}_{N_{k}}(\\{v_{j_{h-1}},e_{i_{h-1}}\\})$ for
$h=2,\ldots,l$, we see that $v=v_{j_{l}}\in\operatorname{cl}_{N_{k}}(B)$, as
required. Thus the conditions are sufficient.

To show that each condition is necessary we suppose that $B$ is a basis of
$M_{k}$. Clearly the first condition is necessary. We observed earlier that
for all $i$ and $j$, $r(E(M_{k})-F_{i,j})<r(M_{k})$, so the second condition
is also necessary. Suppose, without loss of generality, that edges
$e_{1},\ldots,e_{l}$ are undirected and form a circuit in $T(B)$. Then the
corresponding elements $e_{1},\ldots,e_{l}$ form a circuit in $N_{k}$. Because
each of $e_{1},\ldots,e_{l}$ is undirected,
$e_{i}\in\operatorname{cl}_{N_{k}}(B\cap F_{i})$ for $i=1,\ldots,l$. Thus

$e_{l}\in\operatorname{cl}_{N_{k}}(\\{e_{1},\ldots,e_{l-1}\\})\subseteq\operatorname{cl}_{N_{k}}\Bigg{(}\bigcup_{i=1}^{l-1}(B\cap
F_{i})\Bigg{)}.$

So there is a circuit of $N_{k}$ contained in $\\{e_{l}\\}\cup(B\cap F_{l})$
and another contained in $\\{e_{l}\\}\cup\bigcup_{i=1}^{l-1}(B\cap F_{i})$.
Hence there is a circuit of $N_{k}$ and consequently of $M_{k}$ contained in
$\bigcup_{i=1}^{l}(B\cap F_{i})$, contradicting the fact that $B$ is a basis.
Thus the third condition is necessary.

Finally, suppose that $T(B)$ has $b$ bidirected edges, $r$ (uni)directed edges
and $u$ undirected edges. Then, as $km+2b+r+u=|B|=r(M_{k})=km+n$, we have
$2b+r+u=n$. Observe that if the undirected edges are assigned a direction,
then the sum of the indegrees of the vertices will become $n$. Suppose that it
is impossible to direct the undirected edges of $T(B)$ so that each vertex has
indegree one. Then, before directing the undirected edges, there must either
be a vertex $z$ with indegree at least two, or two vertices $x$ and $y$ both
having indegree at least one and joined by a path $P$ of undirected edges.

In either case the aim is to establish a contradiction by showing that there
is some vertex $v$ such that $B\cup\\{v\\}$ contains two distinct circuits in
$N_{k}$. Then $B$ contains a circuit of $N_{k}$ and consequently of $M_{k}$.
In the former case there are distinct edges $e_{i}$ and $e_{j}$ directed
towards (and possibly away from as well) $z$ in $T(B)$. So
$z\in\operatorname{cl}_{N_{k}}(B\cap F_{i})\cap\operatorname{cl}_{N_{k}}(B\cap
F_{j})$ implying that $(B\cap F_{i})\cup\\{z\\}$ and $(B\cap
F_{j})\cup\\{z\\}$ both contain circuits of $N_{k}$ including $z$. But then
$(B\cap F_{i})\cup(B\cap F_{j})=B\cap(F_{i}\cap F_{j})$ contains a circuit of
$N_{k}$ and consequently of $M_{k}$, contradicting the fact that $B$ is a
basis of $M_{k}$. So we may assume that the latter case holds. Suppose that,
without loss of generality, the vertices of $P$ in order are
$v_{1}=x,v_{2},\ldots,v_{l}=y$. Suppose, again without loss of generality,
that for $i=2,\ldots,l$, the edge joining $v_{i-1}$ and $v_{i}$ in $P$ is
$e_{i}$, that $e_{1}$ is directed towards $x=v_{1}$ in $T(B)$ and $e_{l+1}$ is
directed towards $y=v_{l}$ in $T(B)$. Then
$y\in\operatorname{cl}_{N_{k}}(B\cap F_{l+1})$ and
$x\in\operatorname{cl}_{N_{k}}(B\cap F_{1})$. Furthermore, for each
$i=2,\ldots,l$, $e_{i}\in\operatorname{cl}_{N_{k}}(B\cap F_{i})$, so
$v_{i}\in\operatorname{cl}_{N_{k}}\Big{(}\bigcup_{j=1}^{i}(B\cap
F_{j})\Big{)}$. In particular,
$y\in\operatorname{cl}_{N_{k}}\Big{(}\bigcup_{j=1}^{l}(B\cap F_{j})\Big{)}$.
So, there is a circuit of $N_{k}$ contained in $\\{y\\}\cup\\{B\cap
F_{l+1}\\}$ and another contained in $\\{y\\}\cup\bigcup_{j=1}^{l}(B\cap
F_{j})$. Hence there is a circuit of $N_{k}$ and consequently of $M_{k}$
contained in $\bigcup_{j=1}^{l+1}(B\cap F_{j})$, contradicting the fact that
$B$ is a basis. It follows that it possible to direct the undirected edges of
each component of $T(B)$ so that every vertex has indegree one, establishing
the necessity of the final condition. ∎

We say that a template $T$ is _feasible_ if it satisfies the last two
conditions in the previous result, that is, if the subgraph induced by its
undirected edges is acyclic and every vertex of the graph obtained from $T$ by
contracting the undirected edges has indegree equal to one.

######  Proposition 52.

Let $G$ be a simple graph without isolated vertices and let $T$ be a feasible
template of $G$ with $b$ bidirected edges. Then the number of bases of $M_{k}$
with template $T$ is

$4^{km}\Big{(}\frac{k}{4}\Big{)}^{n}\Big{(}\frac{4}{k}+12\Big{)}^{b}.$

###### Proof.

If follows from the definition of feasibility that if a feasible template
contains $b$ bidirected edges, then it has $n-2b$ edges which are either
(uni)directed or undirected. Furthermore $G$ has $m-n+b$ edges which are not
in $T$. Suppose that $B$ is a basis with template $T$. We count the number of
choices for $B$. Suppose that $e_{i}$ is an edge of $G$ which is not present
in $T$. Then for $j=1,\ldots,k$, we have $|F_{i,j}\cap B|=1$, so there are
$4^{k}$ choices for $B\cap F_{i}$. Now suppose that $e_{i}$ is either
(uni)directed or undirected in $T$. Then for all but one choice of $j$ in
$1,\ldots,k$, we have $|F_{i,j}\cap B|=1$ and for the remaining possibility
for $j$, $|F_{i,j}\cap B|=2$, with the choice of elements of $F_{i,j}$
specified by the labelling of the edge $e_{i}$. Thus there are $k\cdot
4^{k-1}$ choices for $B\cap F_{i}$. Finally suppose that $e_{i}$ is a
bidirected edge. Then there are two subcases to consider. Either $|F_{i,j}\cap
B|=3$ for one value of $j$ and $|F_{i,j}\cap B|=1$ for all other values of
$j$, or $|F_{i,j}\cap B|=2$ for two values of $j$ and $|F_{i,j}\cap B|=1$ for
all other values of $j$. Suppose that $|F_{i,j^{\prime}}\cap
B|=|F_{i,j^{\prime\prime}}\cap B|=2$ for $j^{\prime}\neq j^{\prime\prime}$.
Then we also require that $\operatorname{cl}_{N_{k}}(B\cap
F_{i,j^{\prime}})-F_{i}\neq\operatorname{cl}_{N_{k}}(B\cap
F_{i,j^{\prime}})-F_{i}$. Thus there are $k\cdot 4^{k}+\binom{k}{2}\cdot
6\cdot 4\cdot 4^{k-2}$ choices for $B\cap F_{i}$.

So the number of bases of $M_{k}$ with template $T$ is

$(4^{k})^{m-n+b}(k\cdot 4^{k-1})^{n-2b}(k\cdot 4^{k}+\binom{k}{2}\cdot 6\cdot
4\cdot
4^{k-2})^{b}=4^{km}\Big{(}\frac{k}{4}\Big{)}^{n}\Big{(}\frac{4}{k}+12\Big{)}^{b}.$

∎

######  Theorem 53.

If $\mathbb{F}$ is a field with characteristic two, then the problem Counting
Bases of $\mathbb{F}$-Represented Matroids is $\\#$P-complete.

###### Proof.

It is clear that Counting Bases of $\mathbb{F}$-Represented Matroids belongs
to $\\#$P. To prove hardness, we give a reduction from counting perfect
matchings. Let $G$ be a simple graph with $n$ vertices and $m$ edges. We may
assume that $G$ has no isolated vertices and $n$ is even. We can construct
representations of the matroids $M_{1},\ldots,M_{n/2+1}$ in time polynomial in
$n$ and $m$. For $k=1,\ldots,n/2+1$, let $b_{k}$ denote the number of bases of
$M_{k}$ and for $j=0,\ldots,n/2$, let $t_{j}$ denote the number of feasible
templates of $G$ with $j$ bidirected edges. Then for $k=1,\ldots,n/2+1$, by
Proposition 52, we have

$b_{k}=\sum_{j=0}^{n/2}4^{km}\Big{(}\frac{k}{4}\Big{)}^{n}\Big{(}\frac{4}{k}+12\Big{)}^{j}t_{j}.$

Given $b_{1},\ldots,b_{n/2+1}$, we may recover $t_{0},\ldots,t_{n/2}$ in time
polynomial in $n$ and $m$. In particular, we may recover $t_{n/2}$. But
feasible templates with $n/2$ bidirected edges are in one-to-one
correspondence with perfect matchings of $G$. As counting perfect matching is
$\\#$P-complete by [39], we deduce that when $\mathbb{F}$ has characteristic
two, Counting Bases of $\mathbb{F}$-Represented Matroids is $\\#$P-complete. ∎

###  A.2 $\mathbb{F}$ does not have characteristic two

When $\mathbb{F}$ does not have characteristic two, we can proceed in a
similar way, but the proof is a little more complicated, as we need to
consider more carefully circuits of undirected edges in a template. We say
that a circuit of a template comprising only undirected edges is _good_ if it
has an odd number of edges labelled $wz$. The following lemma gives us the key
property of circuits of undirected edges in the template of a basis.

######  Lemma 54.

Let $G$ be a simple graph without isolated vertices and let $M_{k}$ and
$N_{k}$ be the associated matrices. Let $C$ be a circuit of $G$ and select a
set $Z$ of $2|C|$ elements of $M_{k}$ as follows. For each $i$ such that
$e_{i}$ is an edge of $C$, choose $j$ with $1\leq j\leq k$ and add either
$w_{i,j}$ and $z_{i,j}$, or $x_{i,j}$ and $y_{i,j}$ to $Z$. To simplify
notation we omit the second subscript and for each $i$ denote the elements
added to $Z$ by either $w_{i}$ and $z_{i}$, or $x_{i}$ and $y_{i}$. Then both
of the following hold.

  1. 1.

If $|\\{i:\\{w_{i},z_{i}\\}\subseteq Z\\}|$ is odd then $Z$ is independent in
$M_{k}$ (and $N_{k}$) and for each vertex $v$ of $C$,
$v\in\operatorname{cl}_{N_{k}}(Z)$.

  2. 2.

If $|\\{i:\\{w_{i},z_{i}\\}\subseteq Z\\}|$ is even then $Z$ is a circuit in
$M_{k}$ (and $N_{k}$).

###### Proof.

For an edge $e_{i}$ of $C$, we say that $e_{i}$ is a $wz$-edge if
$\\{w_{i},z_{i}\\}\subseteq Z$, and otherwise we say that it is an $xy$-edge.
We first prove that $Z$ is either independent or a circuit, depending on the
parity of $|\\{i:\\{w_{i},z_{i}\\}\subseteq Z\\}|$. Consider the submatrix $A$
of $A_{k}$ containing just the columns indexed by members of $Z$ and consider
the coefficients of a non-trivial linear combination of these columns summing
to zero. As each row of $A$ is either zero or contains two non-zero entries,
both equal to one, we may assume that the non-zero coefficients are all $\pm
1$. Furthermore, for every $wz$-edge $e_{i}$, the coefficients of $w_{i}$ and
$z_{i}$ must sum to zero, and similarly for every $xy$-edge $e_{i}$, the
coefficients of $x_{i}$ and $y_{i}$ must sum to zero. Now consider two
adjacent edges $e_{i}$ and $e_{j}$ in $C$, and let $v$ be their common
endvertex. As the row indexed by $v$ contains one non-zero entry in a column
indexed by an element of $\\{w_{i},x_{i},y_{i},z_{i}\\}\cap Z$ and also one in
a column indexed by an element of $\\{w_{j},x_{j},y_{j},z_{j}\\}\cap Z$, we
deduce that the coefficients of $\\{w_{i},x_{i},y_{i},z_{i}\\}\cap Z$ are non-
zero if and only those of $\\{w_{j},x_{j},y_{j},z_{j}\\}\cap Z$ are non-zero.
Consequently all the coefficients in a non-trivial linear combination of the
columns of $A$ are non-zero. Now imagine traversing $C$ in $G$ and suppose
that $e_{i}$ and $e_{j}$ are consecutive (not necessarily adjacent)
$wz$-edges. Then it is not difficult to see that the coefficients of $w_{i}$
and $w_{j}$ (and of $z_{i}$ and $z_{j}$) have opposite signs. Thus, if there
is an odd number of $wz$-edges, then no non-trivial linear combination of the
columns of $A$ sums to zero and $Z$ is independent. Alternatively, if there is
an even number of $wz$-edges, then one can assign coefficients $\pm 1$ to
columns indexed by $w_{i}$ or $z_{i}$ meeting the necessary conditions we have
established, and then it is not difficult to check that non-zero coefficients
may be assigned to all the remaining columns in order to give a non-trivial
linear combination of the columns of $A$ summing to zero. Thus $Z$ is
dependent, and as we have shown that all coefficients of a non-trivial linear
combination of the columns of $A$ summing to zero must be non-zero, we deduce
that $Z$ is a circuit.

Finally, suppose that there is an odd number of $wz$-edges and let $V(C)$
denote the vertex set of $C$. Then $r_{N_{k}}(Z\cup V(C))=2|C|=r_{N_{k}}(Z)$,
so for each vertex $v$ of $C$, $v\in\operatorname{cl}_{N_{k}}(Z)$. ∎

The analogue of Proposition 51 is as follows.

######  Proposition 55.

A subset $B$ of $E(M_{k})$ is a basis of $M_{k}$ if and only if all of the
following conditions hold.

  * •

For all $i$, $B\cap F_{i}$ is independent.

  * •

For all $i$ and $j$, $|B\cap F_{i,j}|\geq 1$.

  * •

Every circuit of $T(B)$ comprising only undirected edges is good.

  * •

It is possible to direct the undirected edges of $T(B)$ so that every vertex
has indegree one.

###### Proof.

Most of the proof follows that of Proposition 51. The main difference concerns
circuits of $T(B)$ comprising undirected edges. To prove the sufficiency of
the conditions we modify the last part of the sufficiency argument of
Proposition 51. Suppose that $B$ satisfies each of the conditions. The key
step involves showing that for every vertex $v$ in $G$, we have
$v\in\operatorname{cl}_{N_{k}}(B)$. The last two conditions imply that for a
vertex $v$ of $G$, there is a (possibly empty) path $P$ in $T(B)$, comprising
only undirected edges, between $v$ and a vertex $v^{\prime}$, which either has
indegree one or belongs to a good circuit. Using Lemma 54 for the latter case,
we see that in either case $v^{\prime}\in\operatorname{cl}_{N_{k}}(B)$ and the
proof may continue in the same way as that of Proposition 51.

To show that each condition is necessary we suppose that $B$ is a basis of
$M_{k}$. The necessity of the first two conditions follows in the same way as
in the proof of Proposition 51 and the necessity of the third follows from
Lemma 54. The necessity of the final condition follows from a similar argument
to that used in the proof of Proposition 51, but there are more cases to
consider. Notice that the necessity of the third condition implies that every
undirected edge of $T(B)$ belongs to at most one circuit comprising only
undirected edges. If it is not possible to direct the undirected edges of
$T(B)$ so that each edge has indegree one, then before directing the
undirected edges one of the following must occur.

  1. 1.

There is a vertex $z$ of $T(B)$ with indegree at least two.

  2. 2.

There is a vertex $z$ belonging to two edge-disjoint good circuits.

  3. 3.

There is a vertex $z$ of $T(B)$ with indegree one which belongs to a good
circuit.

  4. 4.

There are vertices $x$ and $y$ of $T(B)$ not belonging to the same good
circuit and joined by a path $P$ comprising undirected edges and so that each
of $x$ and $y$ either has indegree one or belongs to a good circuit.

To show that each possibility leads to a contradiction, the aim is again to
show that there is a vertex $v$ of $B$ such that $B\cup\\{v\\}$ contains two
distinct circuits of $N_{k}$. The first case is the same as in the proof of
Proposition 51. The second and third follow similarly with the aid of Lemma 54
and the final one follows in a similar way to the analogous case in
Proposition 51, noting first that by Lemma 54, if necessary, there are
disjoint subsets $B_{x}$ and $B_{y}$ of $B$ with
$x\in\operatorname{cl}_{N_{k}}(B_{x})$ and
$y\in\operatorname{cl}_{N_{k}}(B_{y})$ and then deducing that $y$ (and in fact
every vertex of $P$) belongs to $\operatorname{cl}_{N_{k}}(B_{x})$. ∎

We amend the definition of feasibility to say that a template $T$ is
_feasible_ if it satisfies the last two conditions in the previous result,
that is, if the subgraph induced by its undirected edges contains no circuits
including an even number of edges labelled $wz$ and it is possible to direct
the undirected edges of $T(B)$ so that every vertex has indegree one.

######  Proposition 56.

Let $G$ be a simple graph without isolated vertices and let $T$ be a feasible
template of $G$ with $b$ bidirected edges. Then the number of bases of $M_{k}$
with template $T$ is

$4^{km}\Big{(}\frac{k}{4}\Big{)}^{n}\Big{(}\frac{3}{k}+13\Big{)}^{b}.$

###### Proof.

The proof is very similar to that of Proposition 52. The key difference is
counting the number of choices for $F_{i}$ when $i$ is a bidirected edge and
$|F_{i,j^{\prime}}\cap B|=|F_{i,j^{\prime\prime}}\cap B|=2$ for
$j^{\prime}\neq j^{\prime\prime}$. There are now $26$ ways to choose
$F_{i,j^{\prime}}$ and $F_{i,j^{\prime\prime}}$ compared with $24$ when
$\mathbb{F}$ has characteristic two.

So the number of bases of $M_{k}$ with template $T$ is

$(4^{k})^{m-n+b}(k\cdot 4^{k-1})^{n-2b}(k\cdot 4^{k}+\binom{k}{2}\cdot 26\cdot
4^{k-2})^{b}=4^{km}\Big{(}\frac{k}{4}\Big{)}^{n}\Big{(}\frac{3}{k}+13\Big{)}^{b}.$

∎

######  Theorem 57.

If $\mathbb{F}$ is a field with characteristic other than two, then the
problem Counting Bases of $\mathbb{F}$-Represented Matroids is
$\\#$P-complete.

The proof is identical to that of Theorem 53.

## Acknowledgement

We thank Mark Jerrum and Dillon Mayhew for helpful suggestions concerning
Appendix A.

## References

  * [1] Erwin H. Bareiss.  Sylvester’s identity and multistep integer-preserving Gaussian elimination.  Math. Comput., 22:565–578, 1968.
  * [2] Anders Björner and Günter M. Ziegler.  Introduction to greedoids.  In Matroid applications, pages 284–357. Cambridge: Cambridge University Press, 1992.
  * [3] Markus Bläser, Holger Dell, and Mahmoud Fouz.  Complexity and approximability of the cover polynomial.  Comput. Complexity, 21(3):359–419, 2012.
  * [4] Markus Bläser, Holger Dell, and Johann A. Makowsky.  Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions.  Theory Comput. Syst., 46(4):690–706, 2010.
  * [5] Markus Bläser and Christian Hoffmann.  Fast evaluation of interlace polynomials on graphs of bounded treewidth.  In Algorithms – ESA 2009. 17th annual European symposium, Copenhagen, Denmark, September 7–9, 2009. Proceedings, pages 623–634. Berlin: Springer, 2009.
  * [6] C. W. Borchardt.  Ueber eine der Interpolation entsprechende Darstellung der Eliminations-Resultante.  J. Reine Angew. Math., 57:111–121, 1860.
  * [7] T. Brylawski.  The Tutte polynomial part I: General theory.  In A. Barlotti, editor, Matroid Theory and its Applications. Proceedings of the Third International Mathematical Summer Center (C.I.M.E. 1980), 1982.
  * [8] T. Brylawski and J. Oxley.  The Tutte polynomial and its applications.  In N. White, editor, Matroid Applications. Cambridge University Press, 1992.
  * [9] Charles J. Colbourn, J. Scott Provan, and Dirk Vertigan.  The complexity of computing the Tutte polynomial on transversal matroids.  Combinatorica, 15(1):1–10, 1995.
  * [10] Henry H. Crapo.  The Tutte polynomial.  Aequationes Math., 3:211–229, 1969.
  * [11] J. Edmonds.  Systems of distinct representatives and linear algebra.  Journal of Research of the National Bureau of Standards, B 71(4):241–241, 1967.
  * [12] J. Ellis-Monaghan and C. Merino.  Graph polynomials and their applications I: The Tutte polynomial.  In M. Dehmer, editor, Structural analysis of complex networks. Birkhäuser Boston, 2011.
  * [13] Joanna A. Ellis-Monaghan and Iain Moffatt, editors.  Handbook of the Tutte polynomial and related topics.  Boca Raton, FL: CRC Press, 2022.
  * [14] Graham Farr.  Handbook of the Tutte polynomial and related topics, chapter The history of Tutte–Whitney polynomials, page 46 pages.  Boca Raton, FL: CRC Press, 2022.
  * [15] M. R. Garey and D. S. Johnson.  Computers and Intractability: a Guide to the Theory of NP-Completeness.  W. H. Freeman, 1979.
  * [16] Omer Giménez and Marc Noy.  On the complexity of computing the Tutte polynomial of bicircular matroids.  Comb. Probab. Comput., 15(3):385–395, 2006.
  * [17] O. Goecke.  A greedy algorithm for hereditary set systems and a generalization of the Rado–Edmonds characterization of matroids.  Discrete Applied Mathematics, 20(1):39 – 49, 1988.
  * [18] G. Gordon and E. McMahon.  A greedoid polynomial which distinguishes rooted arborescences.  Proceedings of the American Mathematical Society, 107(2):287–298, 1989.
  * [19] G. Gordon and E. McMahon.  A greedoid characteristic polynomial.  Contemporary Mathematics, 197:343–351, 1996.
  * [20] G. Gordon and E. McMahon.  A characteristic polynomial for rooted graphs and rooted digraphs.  Discrete Mathematics, 232(1):19–33, 2001.
  * [21] C. Greene and T. Zaslavsky.  On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-radon partitions, and orientations of graphs.  Transactions of the American Mathematical Society, 280(1):97–126, 1983.
  * [22] Martin Grötschel, László Lovász, and Alexander Schrijver.  Geometric algorithms and combinatorial optimization., volume 2 of Algorithms Comb. Berlin: Springer-Verlag, 2. corr. ed. edition, 1993.
  * [23] François Jaeger, D. L. Vertigan, and D. J. A. Welsh.  On the computational complexity of the Jones and Tutte polynomials.  Math. Proc. Camb. Philos. Soc., 108(1):35–53, 1990.
  * [24] M. Jerrum.  Counting trees in a graph is $\\#$P-complete.  Information Processing Letters, 51(3):111–116, 1994.
  * [25] G. Kirchhoff.  Ueber die Auflösung der Gleichungen, auf welche man bei der untersuchung der linearen verteilung galvanischer Ströme geführt wird.  Annalen der Physik und Chemie, 72(12):497–508, 1847.
  * [26] B. Korte and L. Lovász.  Mathematical structures underlying greedy algorithms.  In Ferenc Gécseg, editor, Fundamentals of Computation Theory: Proceedings of the 1981 International FCT-Conference, pages 205–209. Springer Berlin Heidelberg, 1981.
  * [27] B. Korte and L. Lovász.  Shelling structures, convexity and a happy end.  Inst. für Ökonometrie u. Operations-Research, 1983.
  * [28] Bernhard Korte and László Lovász.  Greedoids - A structural framework for the greedy algorithm.  Progress in combinatorial optimization, Conf. Waterloo/Ont. 1982, 221-243 (1984)., 1984.
  * [29] Bernhard Korte, László Lovász, and Rainer Schrader.  Greedoids, volume 4 of Algorithms Comb. Springer, Berlin, 1991.
  * [30] J. A. Makowsky.  From a zoo to a zoology: Towards a general theory of graph polynomials.  Theory Comput. Syst., 43(3-4):542–562, 2008.
  * [31] D. Mayhew.  Private Communication, 2023.
  * [32] S. D. Noble.  Evaluating the rank generating function of a graphic 2-polymatroid.  Comb. Probab. Comput., 15(3):449–461, 2006.
  * [33] J. G. Oxley.  Matroid Theory.  Oxford University Press, 1992.
  * [34] C. H. Papadimitriou.  Computational Complexity.  Addison-Wesley, 1994.
  * [35] J. S. Provan and M. O. Ball.  The complexity of counting cuts and of computing the probability that a graph is connected.  SIAM Journal on Computing, 12(4):777–788, 1983.
  * [36] W. T. Tutte.  The dissection of equilateral triangles into equilateral triangles.  Proc. Cambridge Philos. Soc., 44:463–482, 1948.
  * [37] W. T. Tutte.  A contribution to the theory of chromatic polynomials.  Can. J. Math., 6:80–91, 1954.
  * [38] W.T. Tutte.  An Algebraic Theory of Graphs.  Ph.D. thesis, Cambridge University, 1948.
  * [39] L. G. Valiant.  The complexity of computing the permanent.  Theor. Comput. Sci., 8:189–201, 1979.
  * [40] D. Vertigan.  Counting bases in matroids.  Unpublished manuscript, presented at the Conference for James Oxley, Louisiana State University, (2019).
  * [41] D. L. Vertigan and D. J. A. Welsh.  The computational complexity of the Tutte plane: The bipartite case.  Comb. Probab. Comput., 1(2):181–187, 1992.
  * [42] Dirk Vertigan.  Bicycle dimension and special points of the Tutte polynomial.  J. Comb. Theory, Ser. B, 74(2):378–396, 1998.
  * [43] Hassler Whitney.  The coloring of graphs.  Ann. of Math. (2), 33(4):688–718, 1932.