Contracting a Single Element in a Transversal Matroid

Transversal matroids are an important class of matroids. In introductory texts to matroid theory the theory of transversal matroids is often well developed [welsh], and they are regularly given as an example of naturally arising matroids alongside the original classes, representable and graphic matroids [oxley]. However, there are some key differences that separate transversal matroids from these other two fundamental classes. Firstly, representable and graphic matroids are closed under minors while transversal matroids are not. Furthermore, obtaining representations of minors of representable or graphic matroids can be done in polynomial time while no polynomial-time algorithm is known that determines if a minor of a transversal matroid is even transversal or not, nevermind one that obtains a representation. Secondly, representable matroids are closed under duality and representations of their duals can, once again, be found in polynomial time. Graphic matroids are not closed under duality, however, the class of graphic matroids which are also co-graphic is well understood and such matroids can be recognised, and representations of their duals found, in polynomial time. Currently there is very little understanding of which transversal matroids are also co-transversal and of course there does not exist a polynomial-time algorithm to find transversal representations of duals of transversal matroids.

These ideas immediately give rise to the following natural problems. In all such problems where our problem instance contains a transversal matroid we will assume that the transversal matroid is represented by a bipartite graph in the usual way.

Transversal Contraction
Instance: A transversal matroid $M$ and a subset $X\subseteq E(M)$.
Question: Is $M/X$ transversal?


Transversal Dual
Instance: A transversal matroid $M$.
Question: Is $M^{*}$ transversal?

These are questions that have remained unresolved for a long time: Welsh asked in 1971 [DominicProblems, Problem 29] for a characterisation of the matroids that are both transversal and co-transversal; while Bonin, in 2010, asked the same thing [jobonotes, Open Problem 6.1]. We are interested in a slightly different, but related question: whether there even exists a polynomial-time algorithm for determining if a matroid is transversal and co-transversal. As we explain in Section 4 a polynomial-time algorithm that solves Transversal Contraction would provide a polynomial-time algorithm that solves Transversal Dual.

We work toward answering these questions by addressing the simplest case of Transversal Contraction, when $X$ consists of a single element.

Single Element Transversal Contraction
Instance: A transversal matroid $M$ and an element $e\in E(M)$.
Question: Is $M/e$ transversal?

We provide a polynomial-time algorithm that solves this problem and, if $M/e$ is determined to be transversal, our algorithm provides a bipartite graph representation. Therefore we obtain the following theorem.

We will discuss the underlying complexity theory of the problem in more detail in Section 2 but we give a brief description here to show that this problem is in $\Sigma_{2}$. We assume that $e$ is not a loop of $M$ as then $M/e=M\backslash e$ which is trivially transversal. We are able to check, in polynomial time, if a set $B\subseteq E(M)-e$ is a basis of $M/e$ by simply checking if $B\cup e$ is a basis of $M$. Similarly for any transversal matroid, $M_{T}$, with a transversal representation, we can check if $B$ is a basis of $M_{T}$. This means that if we are given a transversal matroid, $M_{T}$, on the same ground set as $M/X$ we can check in polynomial time whether a basis of one is a basis of the other. In order for us to obtain a positive answer to Transversal Contraction there must exist a matroid, $M_{T}$, such that for all $B$ we have that $B$ is not a basis of exactly one of $M/X$ or $M_{T}$. This alternation of quantifiers puts Transversal Contraction into $\Sigma_{2}$ [npcompleteness]. Whether the problem is in fact in $NP$, or perhaps even in $P$, remains open.

Our approach to obtaining a polynomial time algorithm will examine the duals of transversal matroids. The class of co-transversal matroids is exactly the class of strict gammoids [INGLETON197351]. Strict gammoids have their own graphical representation [mason] which we shall discuss in Section 2.

Instead of working directly with transversal representations we will work with strict gammoids. This allows us to examine restrictions of strict gammoids instead of contractions of transversal matroids. Restrictions of strict gammoids are called gammoids and they have their own graphical representation. This allows us to quickly determine any matroid properties such as independence or closure that we might need from the restricted matroid for our algorithm.

Gammoids are interesting in their own right as they are closed under minors and since any transversal matroid is also a gammoid [oxley] they are a minor closed class containing transversal matroids. In fact they are exactly the class of transversal matroids and their minors [oxley]. Representing gammoids graphically can be a challenge though as it was only recently that a bound was put on the size of a graphic representation of a gammoid [6375323]. Our work approaches this problem from another direction, assuming that we already have a small representation of a gammoid and finding a representation that is one vertex smaller or determining that no such representation exists.

Since we are working in the dual picture we obtain a solution to the dual of Single Element Transversal Contraction where our strict gammoid is represented by a directed graph in the usual way.

Single Element Strict Gammoid Deletion
Instance: A strict gammoid $M$ and an element $e\in E(M)$.
Question: Is $M\backslash e$ a strict gammoid?

That is, we provide a proof for the following theorem which, through duality, also proves Theorem 1.

One might wonder why a polynomial-time algorithm for a single-element contraction does not lead to a polynomial-time algorithm for a many-element contraction. As it turns out, it is possible that for a transversal matroid, $M$, there are distinct elements $e$ and $f$ such that neither $M/e$ nor $M/f$ is transversal, but $M/\{e,f\}$ is transversal. Note that, in this case, our algorithm can determine that $M/e$ and $M/f$ are not transversal, but then cannot be used to determine anything about $M/\{e,f\}$.

In general, even our most fundamental results do not apply when contracting more than one element. However, there is a specific case in which some of our results do apply. A fundamental basis of a matroid, $M$, is a basis, $B_{F}$, of $M$ such that for any cyclic flat $Z$ of $M$ we have that $B_{F}\cap Z$ spans $Z$. As we explain in Section 4, if a polynomial-time algorithm existed that could solve Transversal Contraction in polynomial time in the case when $X$ is a fundamental basis of $M$, then a polynomial time algorithm for Transversal Dual would also exist. Therefore, while we can currently only contract a single element in polynomial time, if our methods can be built upon, we may be able to provide the first real progress toward the questions in [DominicProblems] and [jobonotes] in over 50 years.

Also in Section 4 we explain that while many of our important results for a single element contraction do not carry over to the general case, some of them do transfer to the case when $X$ is a fundamental basis. This provides hope that perhaps our technique, or a similar technique can solve this problem and therefore provide a polynomial-time algorithm that solves Transversal Dual.

The remainder of this paper is organised as follows. In Section 2 we introduce some basic concepts in matroid theory and the theory of transversal matroids. In Section 3 we develop the necessary theory and then prove Theorem 2 which of course also proves Theorem 1. In Section 4 we then examine the potential of extending our ideas toward obtaining a polynomial-time algorithm to determine if a transversal matroid is co-transversal. Then in Section 5 we conclude the paper with some conjectures about extensions of our results.

If $S$ is a set we let $S+x$ be $S\cup\{x\}$. We use $[n]$ to denote the set $\{0,1,2...,n\}$. For sets $S$ and $S^{\prime}$ we use $S\subseteq S^{\prime}$ to denote that $S$ is a subset of $S^{\prime}$ and $S\subset S^{\prime}$ to denote that $S$ is a proper subset of $S^{\prime}$. If $M$ is a matroid and $X$ is a subset of $M$ we use $M|X$ to represent $M\backslash(M-X)$, that is, $M$ restricted to $X$.

Let $E$ be a finite set. We define a set system $(E,\mathcal{A})$ to be $E$ along with a multiset $\mathcal{A}=(A_{j}:j\in[n])$ of subsets of $E$ where $n=|\mathcal{A}|$. Thus the same set may appear multiple times in $\mathcal{A}$, indexed by different elements of $[n]$.

A set system $(E,\mathcal{A})$ can be represented by a bipartite graph whose vertex set is $\mathcal{A}\cup E$; an edge connects $A_{j}\in\mathcal{A}$ with $e\in E$ if and only if $e\in A_{j}$. Similarly each bipartite graph can be seen as representing a set system.

A transversal of the set system $(E,\mathcal{A})$ is a subset $T$ of $E$ for which there is a bijection $\phi:E\rightarrow[n]$ with $e\in\phi(e)$ for all $e\in E$. We refer to the bijection, $\phi$, as a matching.

A well known theorem of Hall determines necessary and sufficient conditions for when a set system has a transversal [hall1987representatives].

If $T$ is a transversal of set system $(E,\mathcal{A})$ and $T^{\prime}$ is a proper subset of $T$ then we say $T^{\prime}$ is a partial transversal of the system $(E,\mathcal{A})$.

A lattice is a set, $L$, with a partial order such that any two elements, $e_{0}$ and $e_{1}$ have a unique least upper bound, called the join of $e_{0}$ and $e_{1}$, denoted $e_{0}\lor e_{1}$, and a unique greatest lower bound, called the meet of $e_{0}$ and $e_{1}$, denoted $e_{0}\land e_{1}$. We will only consider finite lattices. Such a lattice will have both a minimum element, $0_{L}$ and a maximum element $1_{L}$.

We say a set system is a lattice under inclusion if the partial ordering imposed on the sets in the system by containment gives rise to a lattice.

We will use the terms; independent sets, dependent sets, loops, coloops, bases, circuits, cyclic sets, rank, closure, flats, cyclic flats, span, contraction, deletion, minors, and duality without providing definitions. We refer the reader to [oxley] for details on matroids.

We have from [bonin2008lattice] that it is possible to define a matroid from its set of cyclic flats and their ranks in the following way:

We let $\mathcal{Z}(M)$ be the collection of all cyclic flats of a matroid $M$. We will also define the nullity function, $n:2^{E(M)}\rightarrow\mathbb{N}$ as $n(X)=|X|-r(X)$. Therefore we see that we can equivalently define a matroid using its set of cyclic flats and their nullities. We also have from [oxley]*Chapter 2.1 Exercise 13a that a set is a cyclic flat of a matroid, $M$, if and only if its complement is a cyclic flat of, $M^{*}$, the dual of $M$. We will also make use of the following equation for the dual rank function [oxley]:

Now let $(E(M),\mathcal{A})$ be a set system and let $\mathcal{I}$ be the set of partial transversals on $(E(M),\mathcal{A})$. Then $(E(M),\mathcal{I})$ is a matroid [jobonotes]. We call any matroid arising in this way a transversal matroid. We define an important function called the $\beta$ function recursively on all subsets of a matroid

Though they did not formulate their theorem in this way we have the following theorem from [ingletoninequality] and [masoninequality] (the proof that this is equivalent to the formulations of [ingletoninequality] and [masoninequality] can be found in [jobonotes]).

Next let $D$ be a directed graph with $E$ and $S$ each being subsets of $V(D)$, we do not require that $E$ and $S$ are disjoint. We say that a set $I\subseteq E$ is linked into $S$ if there exist $|I|$ disjoint directed paths each starting at a vertex in $I$ and ending at a vertex in $S$. The set system $(E,\mathcal{I})$ where $\mathcal{I}$ is the collection of sets with linkings into $S$ is a matroid [oxley]. We denote this particular matroid as $M(D,E,S)$ and we call any matroid arising in this way a gammoid. If $M$ is a gammoid such that $M=M(D,V(D),S)$ for some directed graph $D$ then we say that $M$ is a strict gammoid.

It is not difficult to see that gammoids are the restrictions of strict gammoids. Strict gammoids, and as an extension, gammoids, are of interest to us due to the following theorem [INGLETON197351].

Let $S$ be a set of characters. We call a sequence of characters from $S$ a word. We call a set of words, $L$, a language. Complexity theory examines the complexity of algorithms that determine if a given word belongs to a given language. For our purposes we can imagine our words as inputs to a Turing Machine coded with an algorithm that will eventually accept the word if it belongs to the language and reject it otherwise. If we can bound the number of steps the Turing Machine will take by some polynomial function, $n^{k}$, where $n$ is the size of the word and $k$ is some constant then we say that the algorithm runs in polynomial time.

We classify languages based on their complexity and thus build a structure known as the polynomial hierarchy. The first level of the polynomial hierarchy is $P$. A language, $L$, is in $P$ if there exists an algorithm which will determine that a word belongs to $L$ in polynomial time.

The next level of the polynomial hierarchy is best viewed through an example. Let $L_{S}$ be the language of satisfiable boolean formulae. We let $L_{S}^{\prime}$ be the language consisting of words of the form $(F,A)$ where $F$ is a boolean formula and $A$ is an assignment of the variables of $F$ such that $F$ evaluates to true. Clearly a word, $F$, belongs to $L_{S}$ if and only if there exists a word, $(F,A)$, belonging to $L_{S}^{\prime}$. A polynomial-time algorithm for determining whether a word belongs to $L_{S}$ does not exist as far as we know, however, a polynomial-time algorithm for determining whether a word belongs to $L_{S}^{\prime}$ does exist, one simply needs to evaluate $F$ with $A$ to ensure that $F$ evaluates to true.

This example gives us our definition of the next set of the polynomial hierarchy we are examining, $\Sigma_{1}$, also known as NP. A language, $L$, of words, $W$, is in $\Sigma_{1}$ if and only if there exists some language, $L^{\prime}\in P$, of pairs, $(W,V)$, where a word, $W$ is in $L$ if and only if there exists some $V$ such that $(W,V)\in L^{\prime}$. Therefore, since $L_{S}^{\prime}$ is in $P$ we see that $L_{S}$ is in $\Sigma_{1}$.

Of course “there exists” is not the only quantifier we can consider. Our next example will be the language of tautological formulae, $L_{T}$, that is, those logical formulae for which every assignment of boolean variables results in the formula evaluating to true. Here we let $L_{T}^{\prime}$ be the language consisting of words of the form $(F,A)$ where $F$ is a logical formula and $A$ can be anything except an assignment of variables to $F$ such that $F$ evaluates to false. Clearly a word, $F$, belongs to $L_{T}$ if and only if “for all” $A$ we have that $(F,A)\in L_{T}^{\prime}$. Once again we have that $L_{T}^{\prime}$ is in $P$ but there exists no known polynomial-time algorithm to verify that a formula belongs to $L_{T}$.

This example gives us our definition of the next set that we are examining, $\Pi_{1}$ (or co-NP), which can be thought of as being at the same level of the hierarchy as $\Sigma_{1}$ but distinct from it. A language, $L$, of words, $W$, is in $\Pi_{1}$ if and only if there exists some language, $L^{\prime}\in P$, of pairs $(W,V)$, where a word, $W$ is in $L$ if and only if for all $V$ we have that $(W,V)\in L^{\prime}$. Therefore, since $L_{T}^{\prime}$ is in $P$ we see that $L_{T}$ is in $\Pi_{1}$.

We can construct further levels of the polynomial hierarchy by alternating quantifiers. For our purposes we need only construct one more set, $\Sigma_{2}$. A language, $L$, of words, $W$, is in $\Sigma_{2}$ if and only if there exists some language, $L^{\prime}\in\Pi_{1}$, of pairs, $(W,V)$, where a word $W$ belongs to $L$ if and only if there exists a $V$ such that $(W,V)\in L^{\prime}$.

We will now show that both Transversal Contraction and Transversal Dual are in $\Sigma_{2}$. To see this we first have the fact that if given the associated bipartite graph for a set system $(E,\mathcal{A})$, we may determine whether a subset of $E$ is a transversal or not in polynomial time [oxley].

We first examine Transversal Contraction. Let $M_{T}$ be a transversal matroid on the same ground set as $M/X$ for which we have the transversal representation. Let $L_{T}$ be the language of triples of the form $(M/X,M_{T},B)$ where $B$ can be anything except a set which is a basis in one of $M/X$ or $M_{T}$ but not the other. Since we can check in polynomial time if $B$ is a basis in $M/X$ or $M_{T}$ we have that $L_{T}\in P$.

Now let $L_{X}$ be the language of pairs of the form $(M/X,M_{T})$ where $M/X\cong M_{T}$. We have that a word, $(M/X,M_{T})$ is in $L_{X}$ if and only if for all $B$ we have that $(M/X,M_{T},B)\in L_{T}$. Therefore $L_{X}$ is in $\Pi_{1}$.

Finally we have the language, $L$, with words of the form $M/X$ where $M/X$ is a transversal matroid. We see that determining whether a word is in $L$ is equivalent to solving Transversal Contraction. A word, $M/X$, is in $L$ if and only if there exists some transversal matroid $M_{T}$ such that $M/X\cong M_{T}$, that is if $(M/X,M_{T})\in L_{X}$. Since $L_{X}\in\Pi_{1}$ this means that $L\in\Sigma_{2}$.

For Transversal Dual the argument is the same except that instead of $M/X$ we use $M^{*}$. That is, for a given transversal matroid $M_{T}$ with representation, the language of triples of the form $(M^{*},M_{T},B)$ where $B$ is not a basis of only one of $M^{*}$ or $M_{T}$, is in $P$. Therefore, the language of pairs of the form $(M^{*},M_{T})$ where $M^{*}\cong M_{T}$, is in $\Pi_{1}$. Therefore, the language of words, $M^{*}$, for which an $M_{T}$ exists such that $M^{*}\cong M_{T}$, is in $\Sigma_{2}$.

This means that determining if a dual or minor of a transversal matroid is also transversal is in $\Sigma_{2}$, even if we are only contracting a single element. One might suspect that $L$ should be at least in $\Pi_{1}$ given Equation 2, as all one has to do to verify that $M$ is not a transversal matroid is to find a set, $X$, for which $\beta(X)<0$, however, even if such an $X$ is found there could be exponentially many cyclic flats that strictly contain $X$ and so verifying the $\beta$ value of $X$ in polynomial time is likely to require some other technique, leaving the problem in $\Sigma_{2}$.

We begin this section by calculating the dual of (2). That is, we wish to obtain a function which will be non-zero on all sets of a matroid if and only if that matroid is co-transversal.

At first, we have

We can use (1) to get

We may cancel the $r(M)$ terms and combine the cardinality terms

We wish to replace $Y$ with $\overline{Y}$ in the range of the summation. To do this note that if $Y\subset Z$ then $\overline{Z}\subset\overline{Y}$, this gives us

The first two terms in the sum are of course the nullity of $\overline{Y}$ which is defined as $n(\overline{Y})=|\overline{Y}|-r(\overline{Y})$, while in the summation term it would help if we just examined $\overline{Z}$ directly. This is fortunately, quite easy, as the cyclic flats of $M$ are exactly the complements of cyclic flats of $M^{*}$, hence we have

We now relable $\overline{Y}$ to be $X$ and then we have

Now we define a new function $\gamma(X)$ which is simply $\beta^{*}(\overline{X})$, we can then replace both of our $\beta^{*}$ terms as follows

and so we obtain our $\gamma$ function. Since the $\gamma$ function checks the same sets as the $\beta^{*}$ function we obtain the following Corollary.

Combining this result with Theorem 6 implies the following:

The proof of Theorem 5, which can be found in [jobonotes], takes the cyclic flats with nonzero $\beta$ values and constructs a transversal representation. A similar construction can be obtained in the dual case for strict gammoids.

For this construction we define a few terms. If $M=M(D,V(D),S)$ is a strict gammoid we call $(D,V(D),S)$ a representation of $M$. We say that a representation is maximal if $(D+a,V(D),S)$ is not a representation of $M$ for any arc $a\notin A(D)$. If $v$ is a vertex of $V(D)-S$ then the set of vertices, $u$ for which the arc $(v,u)\in A(D)$ is called the forward neighbourhood of $v$, denoted $N_{D}^{+}(v)$. The closed forward neighbourhood of $v$, denoted $N_{D}^{+}[v]$, is $N_{D}^{+}(v)+v$. If $X$ is a set of vertices of $D$ then the set $N(X)$ is the set of vertices, $v$ such that $N^{+}_{D}[v]=X$.

Our version of the proof of Theorem 9 is quite detailed and involves many results about strict gammoids that are not used in this paper. For this reason the proof is ommitted and will be available in the author’s thesis. We justify this with the fact that the dual result exists for transversal matroids as can be found in [jobonotes] and the fact that we will not use Theorem 9 directly.

What this Theorem tells us is that we can simply read off the $\gamma$ values of cyclic flats with nonzero $\gamma$ values from the maximal directed graph representation. Similarly if we have these particular $\gamma$ values we can construct the maximal directed graph representation. This does not directly follow from the result, however, this is something that is also proved in the author’s thesis. The full result is as follows:

Note that if $M$ is not a strict gammoid, $M^{\prime}$ may still exist, in which case $M$ is not equal to $M^{\prime}$. This will cause difficulties for our algorithm as we will construct such an $M^{\prime}$ and then have to verify that $M=M^{\prime}$, however, we are able to do so in polynomial time.

Since any representation obtained from Lemma 10 has $|E(M)|$ vertices there are at most $|E(M)|$ closed forward neighbourhoods and so viewing a strict gammoid as a directed graph is equivalent (for the purposes of polynomial-time algorithms) to viewing the set of cyclic flats with nonzero $\gamma$ values and their $\gamma$ values. Therefore we use Theorem 9 to justify viewing strict gammoids by their collections of cyclic flats with nonzero $\gamma$ values rather than as directed graph representations.

To do this in general we need one more result which allows us to obtain a maximal representation of a strict gammoid from a general representation of a strict gammoid. Once again, the dual of this result exists for transversal matroids and can be found in [jobonotes]. Therefore we will not provide a proof here and instead refer the reader to the author’s thesis for details.

Finally we also explicitly state the result we proved and used above about the bound on the number of cyclic flats of a strict gammoid with nonzero $\gamma$ values.

We require some results concerning flats of matroids. Some of these results pertain to general matroids rather than simply strict gammoids.

We can use Proposition 13 to see that in a strict gammoid, $M$, we have

Which we can see by letting $Z_{\omega}$ be the maximum cyclic flat contained in $E(M)$ described by Proposition 13, then

but by Proposition 13 we see that $n(Z_{\omega})=n(M)$ and so rearranging gives the result. This gives another proof of Corollary 12. Next we have two results about the $\gamma$ function that we will use later.

Note that if $X$ in Lemma 14 is a flat then we have from Proposition 13 that $X-L^{*}$ will be a cyclic flat and so we obtain the following corollary:

By Definition 4 we see that the collection of cyclic flats of a matroid forms a lattice under inclusion. Specifically if $Z_{0}$ and $Z_{1}$ are cyclic flats then their join, $Z_{0}\lor Z_{1}$, is the closure of their union, and their meet, $Z_{0}\land Z_{1}$ is the union of all circuits contained in their intersection. Note that the set of all loops of a matroid is a cyclic flat even if it is empty. If given a set of cyclic flats $\mathcal{Z}=\{Z_{0},Z_{1},\ldots,Z_{n}\}$ we define $\lor\mathcal{Z}$ to be $Z_{0}\lor Z_{1}\lor\dots\lor Z_{n}$ and $\land\mathcal{Z}$ to be $Z_{0}\land Z_{1}\land\dots\land Z_{n}$. It is clear that given any pair of cyclic flats in a gammoid their join and meet can be obtained in polynomial time, however, there may be exponentially many cyclic flats in the matroid and so it is not feasible to examine all of them in polynomial time.

Our goal is to examine a single-element deletion from a strict gammoid and determine if the resulting gammoid remains a strict gammoid. Naively in order to do this we would have to check the $\gamma$ values of every subset of the ground set of the resulting matroid which clearly could not be done in polynomial time. In fact, even checking all the cyclic flats could not be done in polynomial time. However, recall that by Corollary 12 the number of cyclic flats with nonzero $\gamma$ values in the original matroid is bounded by the size of the ground set. While that may not be true for our new matroid we can use this information to help us obtain information about it in polynomial time. As such we first examine the relationship between the lattices of cyclic flats for each matroid.

Let $M^{+}$ be a matroid with $e\in E(M^{+})$, let $M=M^{+}\backslash e$. We obtain a function $f:\mathcal{Z}(M^{+})\rightarrow 2^{E(M)}$ which is defined as $f(Z)=Z-e$. Note that $f(Z)$ may or may not be a cyclic flat in $M$. We now prove the following properties about $f$.

Let $\mathcal{L}^{+}$ be the lattice of cyclic flats of $M^{+}$ and let $\mathcal{L}$ be the lattice of cyclic flats of $M$. Lemma 17 tells us that $f$ is almost an isomorphism from $\mathcal{L}^{+}$ and $\mathcal{L}$. The ‘almost’ coming from the fact that sometimes $f$ sends cyclic flats to sets that are not cyclic flats and we have $f(Z_{0})\land f(Z_{1})\subseteq f(Z_{0}\land Z_{1})$ rather than $f(Z_{0})\land f(Z_{1})=f(Z_{0}\land Z_{1})$. We will use this near-isomorphic structure to obtain the results we need.