Representative set statements for delta-matroids and the Mader delta-matroid

The representative sets lemma for linear matroids has many powerful surprising applications in parameterized complexity, including improved FPT dynamic programming algorithms (Fomin et al., JACM 2016) and polynomial kernelization and sparsification results for graph separation problems (Kratsch and Wahlström, JACM 2020). However, its application can be sporadic, as it presupposes the existence of a linear matroid encoding a property relevant to the problem at hand. Correspondingly, although its application led to several new kernelizations (e.g., Almost 2-SAT and restricted variants of Multiway Cut), there are also several problems left open (e.g., the general case of Multiway Cut).

We present representative sets-style statements for linear delta-matroids, which are set systems that generalize matroids, with important connections to matching theory and graph embeddings. Furthermore, our proof uses a new approach of sieving polynomial families, which generalizes the linear algebra approach of the representative sets lemma to a setting of bounded-degree polynomials. The representative sets statements for linear delta-matroids then follow by analyzing the Pfaffian of the skew-symmetric matrix representing the delta-matroid. Applying the same framework to the determinant instead of the Pfaffian recovers the representative sets lemma for linear matroids. Altogether, this significantly extends the toolbox available for kernelization.

As an application, we show an exact sparsification result for Mader networks: Let G = (V, E) be a graph and T a partition of a set of terminals T ⊆ V (G), |T | = k. A T -path in G is a path with endpoints in distinct parts of T and internal vertices disjoint from T . In polynomial time, we can derive a graph G ′ = (V ′ , E ′ ) with T ⊆ V (G ′ ), such that for every subset S ⊆ T there is a packing of T -paths with endpoints S in G if and only if there is one in G ′ , and |V (G ′ )| = O(k 3 ). This generalizes the (undirected version of the) cut-covering lemma, which corresponds to the case that T contains only two blocks.

To prove the Mader network sparsification result, we furthermore define the class of Mader delta-matroids, and show that they have linear representations. This should be of independent interest.

A particularly interesting outlier here is the problem T -Cycle: Given a graph G = (V, E) and a set of vertices T ⊆ V , is there a simple cycle in G that visits every vertex in T ? This problem is FPT under parameter k = |T | [4], but more unexpectedly there is a polynomial-time compression of (G, T ): There is a process that takes (G, k) as input and in polynomial time produces an annotated matrix A of Õ(k 3 ) bits as output, such that (G, T ) is positive if and only if det A contains a particular term [62]. Note that |V (G)| and the length of the cycle can be unbounded in terms of k, so this is a significant apparent compression of information. Furthermore, the compression works via pure algebra, not taking the combinatorial problem structure into account at all. (We still do not know whether T -Cycle has a proper polynomial kernel, which produces an instance of T -Cycle rather than an annotated matrix as output; but the existence of the compression rules out any attempt at excluding the existence of a polynomial kernel with any of our existing lower-bounds methods.)

But this is an outlier. There are more examples where the algebraic encoding is used to derive purely combinatorial consequences. Perhaps the chief example is the cut-covering set lemma of Kratsch and Wahlström [39]. Given a (possibly directed) graph G and a set X of terminals in G with total capacity k, in randomized polynomial time we can compute a set Z ⊆ V (G) of O(k 3 ) vertices such that for any bipartition X = S ∪ T , Z contains a minimum (S, T )-vertex cut in G. The key algebraic ingredients in this result are twofold. First, the result relies upon the existence of a class of linear matroids known as gammoids, where, informally, combinatorial information about linkages in G is encoded into the linear independence of a collection of k-dimensional linear vectors. Second, given a relevant linear matroid a powerful result from matroid theory, the representative sets (or two families) theorem, allows us to draw important combinatorial consequences for the original graph, such as irrelevant vertex rules identifying vertices in the original graph that can be safely bypassed without affecting any solution. The representative sets theorem is originally due to Lovász [46], with algorithmic improvements by Marx [49] and Fomin et al. [27]. This method gives polynomial kernels for a range of problems, including Odd Cycle Transversal, Almost 2-SAT, and Multiway Cut with s = O(1) terminals, where direct combinatorial attacks appear (so far) completely powerless [39].

Another benefit of the algebraic methods is that instead of merely preserving a "single bit" of information (such as whether an instance has a solu