PaperlayerView exact revision on arXiv

Source-linked AI summary

A Deterministic Polynomial Kernel for Odd Cycle Transversal

Tomohiro Koana, Soh Kumabe

arXiv:2609.29141v1cs.DS

TL;DR

Odd Cycle Transversal had a randomized polynomial kernel, and whether general graphs admit a deterministic polynomial kernel remained open. The paper derandomizes cut covering through deterministic almost multilinear representations of gammoids and computes representative families from them. It obtains a deterministic polynomial-time kernel with O(k^12) vertices and edges.

  • Problem

    Whether Odd Cycle Transversal on general graphs admits a deterministic polynomial kernel remained open despite a randomized polynomial kernel.

    Source: §1 · p. 2

  • Method

    The paper constructs almost multilinear gammoid representations deterministically and computes the representative families needed to derandomize cut covering.

    Source: §1 · p. 3

  • Results

    O(k^12) vertices and edges suffice for a deterministic polynomial-time Odd Cycle Transversal kernelization.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The same algorithm also yields deterministic polynomial kernels for Almost 2-SAT, fixed-finite-group Group Feedback Vertex Set, and Vertex Multiway Cut with a fixed number of undeletable terminals.

    Source: §1 · p. 2

Abstract

from arXiv · show

We give a deterministic polynomial kernel for Odd Cycle Transversal, derandomizing the randomized kernel of Kratsch and Wahlstr\"om (TALG 2014). Our algorithm uses a deterministic polynomial-time construction of almost multilinear representations of gammoids. Such a representation assigns a block of columns to each element so that, for every subset of elements, the normalized matrix rank approximates its matroid rank to within a prescribed additive error $\delta$. The construction builds on recent breakthroughs in NC algorithms for matching. Our kernelization algorithm then computes the required representative families from these representations.

1 Introduction

Odd Cycle Transversal had a randomized polynomial kernel, while a deterministic polynomial kernel for general graphs remained open. This paper derandomizes cut covering using almost multilinear gammoid representations and obtains a deterministic kernel with O(k^12) vertices and edges.

1 Introduction

  • O(k^12) vertices and edges suffice for a deterministic polynomial-time kernelization of Odd Cycle Transversal parameterized by the number k of deleted vertices.This resolves the open question for general graphs.Source: §1 · p. 2
  • The same algorithm applied to Kratsch and Wahlström’s reductions yields deterministic polynomial kernels for Almost 2-SAT, fixed-finite-group Group Feedback Vertex Set, and Vertex Multiway Cut with a fixed number of undeletable terminals.Source: §1 · p. 2
  • O((|S| + |T|)^3)-size cut-covering sets can be computed in deterministic polynomial time for disjoint terminal sets S and T.The set contains S ∪ T and a minimum (A, B)-cut for every A ⊆ S and B ⊆ T.Source: §1 · p. 2
  • The cut-covering framework encodes vertices as triples in one uniform matroid and two gammoids, using representative families to identify vertices that can be bypassed safely.Repeating this process yields a cut-covering set.Source: §1 · pp. 2–3
  • Almost multilinear gammoid representations let the authors compute the exact representative families needed for cut covering in deterministic polynomial time.Deterministic polynomial-time linear representations of gammoids are not known; the randomized construction is where randomization enters the prior cut-covering algorithm.Source: §1 · p. 3
  • For every rational δ > 0, transversal matroids and gammoids admit deterministic δ-almost multilinear representations over a prime field with polynomially bounded prime and running time.The bounds are polynomial in the input size and 1/δ.Source: §1 · pp. 3–4
  • The representation construction adapts a simplified polynomial-multiplicity rank-computation approach developed after deterministic NC algorithms for bipartite matching.Kopparty and Saraf simplified the matching approach with a criterion based on polynomial multiplicities; the paper adapts that construction.Source: §1 · p. 3
  • With sufficiently accurate almost multilinear representations, representative families for tuples from d matroids can be computed deterministically with size at most 2rd.The algorithm retains a candidate when its tensor subspace increases span dimension by at least td/2; in the cut-covering construction, d = 3 and r = max{|S|, |T|}, giving O((|S| + |T|)^3) candidates independently of representation scale.Source: §1 · p. 4

2 Preliminaries

The preliminaries establish graph, cut, and matroid conventions, then define the transversal matroids, gammoids, representations, and representative families used in the paper.

2 Preliminaries

  • A directed (A, B)-cut meets every directed path from A to B, and its minimum size equals the maximum number of pairwise vertex-disjoint A-to-B paths.The graph conventions also define paths as having no repeated vertices and vertex-disjoint paths as sharing no vertices, including endpoints.Source: §2 · p. 4
  • A matroid is a finite ground set with independent sets closed under subsets and satisfying exchange; its rank is the size of a largest independent subset.The preliminaries also give dual rank and direct-sum definitions, and identify uniform matroids as those whose independent sets have size at most the rank.Source: §2 · pp. 4–5

Transversal matroids

  • A transversal matroid on a bipartite graph has one side as its ground set, and a set is independent exactly when a matching covers it.The graph and its bipartition are part of algorithmic inputs.Source: Transversal matroids · p. 5

Gammoids

  • A strict gammoid’s independent sets are vertex sets reachable from its sources by vertex-disjoint directed paths; a gammoid is a restriction of a strict gammoid.Paths may have length zero, and a restriction retains the same path condition in the original graph.Source: Gammoids · p. 5
  • A linear representation encodes matroid independence as linear independence of matrix columns, while a representative family preserves every independent extension possible from the original family.For tuples from matroids on a common ground set, representativeness is interpreted in their direct sum on disjoint copies.Source: Gammoids · p. 5
  • The preliminaries define tensor subspaces as spans of tensors formed from vectors in the component subspaces, with dimension equal to the product of their dimensions.For a quotient map, the dimension of the image of a subspace is given by the dimension of its sum with the quotient subspace minus that subspace’s dimension.Source: Gammoids · p. 5

3 Prior methods for randomized cut covering

Prior cut covering uses randomized matroid representations and deterministic representative-family computation to identify vertices that can be bypassed. This framework reduces cut covering to preserving essential vertices across terminal choices.

3.1 Randomized linear representations of transversal matroids and gammoids

  • Random substitutions in the Edmonds matrix represent transversal matroids with success probability at least 1−ε; duality then yields representations of gammoids.The construction chooses a prime p so that 2n2^n/ε < p < 4n2^n/ε.Source: §3.1 · p. 6

3.2 Representative families in direct sums

  • Tensor algebra computes representative families for tuples in direct sums, retaining all independent extensions with at most r^d tuples.The tuple vectors lie in a tensor space of dimension r^d, where Gaussian elimination selects a basis.Source: §3.2 · p. 7

3.3 From representative families to cut covering

  • Each nonterminal vertex becomes a triple in three rank-at-most-r matroids; a representative family of at most r^3 triples retains essential vertices.Essentiality is tested through closest minimum cuts on the original and reversed graphs.Source: §3.3 · p. 8
  • A vertex omitted from the representative family can be bypassed while preserving every minimum cut value; repetition leaves at most r^3 + |S| + |T| vertices.Bypassing adds arcs for two-arc paths through the vertex before deleting it.Source: §3.3 · p. 8

4 Almost multilinear representations

The paper replaces randomized gammoid representations with deterministic almost multilinear ones, whose normalized block-matrix ranks approximate matroid ranks. Polynomial independence bounds support the transversal construction, which extends to gammoids by dualizing and restricting.

4 Almost multilinear representations

  • A δ-almost multilinear representation assigns each element a block of t columns whose normalized matrix ranks approximate matroid ranks within additive error δ.The constructions run in time polynomial in the input size and 1/δ.Source: §4 · pp. 8–9

4.1 Polynomial independence and multiplicity bounds

  • When polynomial degrees are below p, the Wronskian criterion tests linear independence, and multiplicity bounds yield independence for polynomials with prescribed zeros.The latter condition requires K > n(t + n − 1) and K + t − 1 < p.Source: §4.1 · p. 9

4.2 Transversal matroids

  • For transversal matroids, the deterministic construction gives a δ-almost multilinear representation over a prime field, with prime and runtime polynomial in input size and 1/δ.Its rank bounds t r_T(F) ≤ ρ_T(F) ≤ (t + 2n)r_T(F) yield normalized additive error at most δ.Source: §4.2 · pp. 10–11

4.3 Gammoids

  • Dualizing and restricting almost multilinear representations yields deterministic polynomial-time gammoid representations over a prime field, with prime and runtime polynomial in input size and 1/δ.Dualization changes the error bound from δ to 2δ while preserving the scale; restriction preserves the scale and error bound.Source: §4.3 · pp. 11–12

5 Computing representative families

The section gives a deterministic algorithm for computing small representative families from almost multilinear representations. It bounds the family size and running time, and proves that the retained tuples preserve representation.

5 Computing representative families

  • Given the stated rank and error bounds, a representative family of size at most 2r^d is computable deterministically in time N^{O(d)}.Here N is the total bit length of the representations.Source: §5 · p. 12
  • Each tuple contributes a subspace formed from the column spaces for its coordinates, and the algorithm accumulates the subspaces of retained tuples.The matrix for each tuple is built from the corresponding block-column spaces.Source: §5 · p. 12
  • The algorithm retains a tuple only when adding its subspace increases the accumulated dimension by at least td/2.Since the accumulated dimension is at most td(r+δ)^d, the output has size at most 2r^d.Source: §5 · p. 12
  • The retained tuples form a representative family because any good tuple is retained unless an earlier good tuple was already retained.The proof bounds the projected dimension of subspaces generated by bad tuples to show that processing a good tuple must increase dimension enough for retention.Source: §5 · pp. 12–13
  • Gaussian elimination computes each dimension gain and updates a basis for the accumulated space, yielding total running time N^{O(d)}.The analysis uses at most N^{O(d)} field operations, each taking (log p)^{O(1)} bit operations.Source: §5 · p. 13

6 The Odd Cycle Transversal kernel

The paper obtains a deterministic polynomial-time Odd Cycle Transversal kernel with O(k^12) vertices and edges. It combines a cut-covering construction with representative families and parity-based reductions.

6 The Odd Cycle Transversal kernel

  • The cut-covering construction yields a set of size O((|S|+|T|)^3) containing S∪T and a minimum (A,B)-cut for every A⊆S and B⊆T.It uses one uniform matroid and two gammoids, each of rank at most max{|S|,|T|}, with representative families computed using Theorem 1.5.Source: §6 · p. 14
  • Odd Cycle Transversal parameterized by k admits a deterministic polynomial-time kernelization with O(k^12) vertices and edges.The output parameter is at most k.Source: §6 · p. 14
  • The reduction starts with an O(k^2)-size odd cycle transversal, then uses cut correspondence to obtain a set Z of size O(k^6) containing a minimum one.The initial transversal is produced by [KMRS20]; the reductions use and.Source: §6 · p. 14
  • After forced-vertex reductions, parity constraints become edges or length-two paths, producing an equivalent ordinary instance with O(k^12) vertices and edges.A deleted subdivision vertex can be replaced by an endpoint without increasing solution size; all steps are deterministic polynomial time.Source: §6 · p. 14

Declaration of generative AI use

The authors report that ChatGPT 6 Astra generated the proof of Theorem 1.1 and helped draft the manuscript; they verified and revised both and take full responsibility.

Declaration of generative AI use

Loading 2609.29141v1…