PaperlayerView exact revision on arXiv

Source-linked AI summary

Narrow sieves for parameterized paths and packings

Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto

arXiv:1007.1161v1cs.DS

TL;DR

The paper targets hard combinatorial problems whose algorithms can depend exponentially on output parameters rather than input size. It uses algebraic and combinatorial sieving to improve parameterized running times, including a k-path bound below base 2, and also gives an edge-coloring algorithm. The k-path approach is not presented as extending to other natural structures, including directed paths.

  • Problem

    Hard problems such as long simple paths and disjoint set packings require inexact or super-polynomial, potentially exponential, time under standard complexity assumptions.

    Source: §1 · p. 1

  • Method

    The algorithms associate multilinear monomials with target structures and sieve unwanted contributions, using determinants for several problems and a combinatorial pairing for k-path.

    Source: §2.1 · p. 7, §2.10 · p. 13

  • Results

    The paper lowers exponent bases below 2 for parameterized problems, including O*(1.66^k) for k-path and O*(1.4933^p) for p-packing of 3-sets.

    Source: §1 · p. 1, §1.1 · p. 2, §1.2 · p. 3

  • Takeaways & Limitations

    The methods also yield a nontrivial upper bound for edge coloring regular graphs, beyond the parameterized problems.

    Source: §1 · p. 1

    The k-path algorithm does not appear to extend to other natural combinatorial structures, including directed paths.

    Source: §1.6 · p. 6

Abstract

from arXiv · show

We present randomized algorithms for some well-studied, hard combinatorial problems: the k-path problem, the p-packing of q-sets problem, and the q-dimensional p-matching problem. Our algorithms solve these problems with high probability in time exponential only in the parameter (k, p, q) and using polynomial space; the constant bases of the exponentials are significantly smaller than in previous works. For example, for the k-path problem the improvement is from 2 to 1.66. We also show how to detect if a d-regular graph admits an edge coloring with $d$ colors in time within a polynomial factor of O(2^{(d-1)n/2}). Our techniques build upon and generalize some recently published ideas by I. Koutis (ICALP 2009), R. Williams (IPL 2009), and A. Bj\"orklund (STACS 2010, FOCS 2010).

1. Introduction

The paper improves parameterized algorithms for hard combinatorial problems by lowering exponential bases below 2, with running time exponential in output parameters rather than input size. It also gives an edge-coloring bound and develops algebraic and combinatorial sieving methods.

1.1. Finding a path.

  • O*(1.66^k) solves undirected k-path with constant one-sided error, breaking the exponent-base-2 barrier.The authors note that exp(o(k)) time would imply exp(o(n)) time for Hamiltonian path, contradicting ETH.Source: §1.1 · p. 2, Previous work · p. 2

1.2. Packing disjoint triples.

  • O*(1.4933^p) solves p-packing of 3-sets with constant one-sided error.The paper also gives an ETH-based lower-bound proposition: vertex-disjoint triangle p-packing has no exp(o(p)) algorithm unless 3-CNF satisfiability has an exp(o(n)) algorithm.Source: §1.2 · p. 3

1.3. Uniform set packing.

  • The general p-packing of q-sets problem has a randomized O*(f(p, q)) algorithm, with bounds that behave well for small q but do not improve O*(2^qp) uniformly.For nonuniform p-packing, the authors consider an O*(f(p)) algorithm unlikely, citing W[1]-hardness of finding an independent set of size p.Source: §1.3 · pp. 4–5

1.4. Multidimensional matching.

  • O*(2^((q−2)p)) solves q-dimensional p-packing with constant one-sided error.The input family is assumed polynomial in the universe size so the suppressed input-reading cost remains polynomial.Source: §1.4 · p. 5

1.5. Edge colouring.

  • O*(2^((d−1)n/2)) time and polynomial space suffice to decide d-edge-colorability of d-regular graphs.The problem is NP-complete for each d ≥ 3, while its exponential-time complexity remains open.Source: §1.5 · p. 6

1.6. Methods.

  • The methods associate multilinear monomials with target structures and sieve unwanted contributions; determinants handle packing, matching, and edge coloring, while k-path uses a combinatorial pairing argument.For k = n, the path method yields an O*(1.66^n) Hamiltonian-path algorithm by a different approach.Source: §1.6 · p. 6

2. A Projection Sieve for k-Paths

Section 2 develops an inclusion–exclusion sieve over multivariate polynomials for the k-path problem. Its overview combines labeled walks, cancellation of unwanted monomials, and polynomial-time evaluation for walks avoiding selected labels.

2.1. Overview.

  • A random partition into V1 and V2 defines bijective labeling by assigning a unique label to each walk occurrence of a vertex in G[V1] and an edge in G[V2].An object may receive multiple labels when it occurs multiple times; labels need not follow visitation order.Source: §2.1 · p. 7
  • Each labeled walk is represented by a monomial containing edge variables and label-indexed variables for V1 vertices and V2 edges.A path can be uniquely recovered from its monomial and source vertex, whereas distinct non-path walks can share a monomial.Source: §2.1 · p. 7
  • For a labeled non-path, the pairing transposes labels at the first closed subwalk’s V1 start or reverses that subwalk and its labels at a V2 start, canceling identical monomials.The figure illustrates the two cases: label transposition leaves the walk unchanged, while reversal changes the subwalk and its labels.Source: §2.1 · p. 8, Figure 1 · p. 8
  • The sieve uses four ingredients: distinct variable supports for labeled paths, characteristic-2 pairing to cancel bijectively labeled non-paths, inclusion–exclusion to remove non-bijective labelings, and polynomial-time evaluation.The inclusion–exclusion sieve requires at most 3k/4 labels with high probability when the walks are chosen carefully.Source: §2.1 · p. 8

2.2. Preliminaries on strings.

  • The string preliminaries treat a walk as a string and define strings, substrings, reversals, concatenation, and strings constrained by position-specific symbol sets.The overview presents the string viewpoint as a convenient way to formulate walks.Source: §2.2 · pp. 8–9

2.3. Walks in graphs.

The section defines graph walks as alternating vertex-edge strings, then represents selected symbols by their positions. It restricts the sieve to admissible walks, a subset chosen to reduce labels.

2.3. Walks in graphs.

  • A k-walk is an alternating string of k vertices and k−1 connecting edges; it is a path when no vertex repeats.A walk that is not a path contains a closed subwalk.Source: §2.3 · p. 9

2.4. Representing strings as sets.

  • For a string, B{·} records each occurrence of a symbol from B together with its position, allowing the string to be recovered when B is the full alphabet.Source: §2.4 · p. 9

2.5. Admissible walks.

  • Admissible walks are a technical subset of k-walks introduced to reduce the number of labels used by the sieve.The definition is parameterized by a fixed start vertex, a partition V = V1 ∪ V2, and counts k, k1, and ℓ2; it also requires V2EV1EV2-palindromelessness, a property that every path satisfies.Source: §2.5 · pp. 9–10
  • Figure 2 illustrates the position projections and admissibility test: W1 is admissible with k = 6, k1 = 3, and ℓ2 = 1, whereas W2 contains the forbidden fGcGf palindrome.Source: Figure 2 · p. 10

2.6. Random projection.

Randomly partitioning the vertices gives a probability that a fixed path is admissible, with positive probability only for specified parameter ranges. The section then assigns labels to admissible walks, including a bijective labeling used in the sieve.

2.6. Random projection.

  • A fixed k-path has positive probability of admissibility exactly when k1 = k and ℓ2 = 0, or k1 < k and k1 + ℓ2 ≤ k−1 ≤ 2k1 + ℓ2.For a uniformly random partition, admissibility is counted by the fraction of binary strings with exactly k1 ones and ℓ2 occurrences of adjacent 2s.Source: §2.6 · p. 10

2.7. Labeled admissible walks.

  • A labeled admissible walk assigns labels from K1 to its V1-position occurrences and from L2 to its E2-edge occurrences; the labeling is bijective when both assignments are bijections.The example distinguishes bijective assignments from ones that omit a label.Source: §2.7 · pp. 11–12

2.8. Fingerprinting and identifiability.

The section represents each labeled admissible walk by a fingerprint monomial in variables for edges, V1 vertex-position labels, and E2 edge-position labels. These fingerprints identify paths, and uniquely identify both the path and its labeling when the labels are bijective.

  • Fingerprints of labeled non-paths are deliberately not unique, enabling their cancellation in the sieve.Source: §2.8 · p. 12
  • The fingerprint uses edge variables xe and label-indexed variables yv,i and ze,i for V1 vertices and E2 edges, respectively.For paths, the x-variables recover the walk from its start vertex, while the y- and z-variables recover its labeling.Source: §2.8 · p. 12
  • A fingerprint monomial uniquely determines the edges and their multiplicities in a labeled admissible walk, and therefore uniquely identifies any path.For a path with bijective κ1 and λ2, the monomial uniquely identifies the labeled walk as well.Source: §2.8 · p. 12

2.9. Sieving for bijective labelings.

The sieve uses inclusion–exclusion to isolate bijectively labeled admissible walks and separates paths from non-paths. In characteristic 2, a fixed-point-free involution pairing non-paths with equal fingerprints makes their total contribution vanish.

2.9. Sieving for bijective labelings.

  • Inclusion–exclusion over forbidden labels isolates the bijectively labeled admissible walks from all labeled admissible walks.The setup defines label-avoiding families L[I1, J2] and the set B of bijectively labeled walks.Source: §2.9 · p. 13

2.10. Bijectively labeled non-path fingerprints cancel.

  • A fixed-point-free involution pairing bijectively labeled non-paths with equal fingerprints makes their sum vanish in characteristic 2.The non-path contribution is separated from the path contribution before constructing the pairing.Source: §2.10 · p. 13
  • The pairing construction uses the first closed subwalk of each non-path as its designated structural feature.Source: §2.10 · p. 13

2.11. The pairing on R1 – label transposition.

The section pairs members of R1 by changing the labeling at the two positions that end C(W). The change preserves the relevant value while producing a distinct partner, so the pairing is a fixed-point-free involution.

2.11. The pairing on R1 – label transposition.

  • For a bijectively labeled (W, κ1, λ2), positions j and ℓ contain c(W), and κ1(c,j) ≠ κ1(c,ℓ); hence κ′1 differs from κ1 and (W, κ′1, λ2) ∈ R1.Source: §2.11 · p. 13
  • Because (W, κ1, λ2) is bijectively labeled, κ1(c, j) ≠ κ1(c, ℓ); consequently, κ′1 ≠ κ1 and (W, κ′1, λ2) ∈ R1.Source: §2.11 · p. 13
  • Applying φ twice returns the original element, and φ never fixes an element of R1.Source: §2.11 · p. 14

2.12. The pairing on R2 – labeled reversal of first closed subwalk.

The section pairs elements of R2 by reversing the first closed subwalk and transferring its labels to corresponding positions. The reversal preserves admissibility and the monomial, while case analysis ensures the paired element is distinct.

2.12. The pairing on R2 – labeled reversal of first closed subwalk.

  • Reversing the first closed subwalk C in W produces another admissible walk W′ and reversing it again recovers W.Source: §2.12 · p. 14
  • The map transfers κ1 and λ2 labels along the position correspondence ρ, preserving the monomial and making the reversal an involution on labeled walks.Source: §2.12 · p. 14
  • The reversal is distinct when C is not a palindrome; for a palindrome, the first closed subwalk has length 5 and corresponding E2 edge occurrences receive different labels.Source: §2.12 · pp. 14–15

2.13. The algorithm.

The randomized algorithm detects a k-path by testing a generating-function evaluation after randomly partitioning the vertices and using dynamic programming. With γ1 = 0.5 and γ2 = 0.207107, it runs in O*(1.6569^k) time.

2.13. The algorithm.

  • The algorithm randomly partitions the vertices, then uses a generating function and the DeMillo–Lipton–Schwartz–Zippel lemma to test for an admissible k-path.Source: §2.13 · p. 15
  • Dynamic programming evaluates the expression for random indeterminate assignments, with the evaluation requiring O(2k1+ℓ2k3n4) arithmetic operations over F2b.Source: §2.13 · pp. 15–16
  • A fixed k-path starting at s is witnessed with probability at least (1 − e^−1)/2 after ⌈1/P(k, k1, ℓ2)⌉ repetitions.The procedure sets b = ⌈log2 6k⌉.Source: §2.13 · p. 16
  • O*(1.6569^k) time is achieved for γ1 = 0.5 and γ2 = 0.207107.The parameters are set as k1 = ⌊γ1k⌋ and ℓ2 = ⌊γ2k⌋.Source: §2.13 · p. 16

3. A Determinant Sieve for q-Dimensional p-Packings

The determinant sieve extends Edmonds’s signed generating function from two dimensions to q-dimensional p-packings by enforcing the first two dimensions with a determinant and sieving over the others. Its randomized algorithm detects a p-packing in O*(2^{p(q−2)}) time for polynomial-size families.

3.1. Prepackings and Edmonds’s symbolic determinant.

  • A j-prepacking consists of j pairwise-disjoint sets when projected to U1 ∪ U2, with each set identifying one element in each of U1 and U2.Source: §3.1 · p. 16
  • Edmonds’s determinant represents a signed generating function over bijections between U1 and U2, and the sieve extends this constraint to q dimensions.This lets the method restrict sieving to the remaining q−2 dimensions.Source: §3.1 · pp. 16–17

3.2. Fingerprinting and identifiability.

  • The fingerprint monomial uniquely determines the prepacking and its compatible bijection; for a p-packing with bijective labels, it also determines the labeling.Source: §3.2 · p. 17

3.3. Sieving for bijective labelings.

  • Inclusion-exclusion over avoided labels isolates bijectively labeled p-prepackings in the determinant expression.Source: §3.3 · p. 17, §3.4 · p. 17

3.4. Fingerprints of bijectively labeled non-p-packings cancel.

  • Non-p-packings cancel in characteristic 2 by swapping the labels on two sets sharing a projected element, yielding a fixed-point-free involution that preserves the monomial.Source: §3.4 · pp. 17–18

3.5. The algorithm.

  • The resulting polynomial is nonzero exactly when F contains a p-packing, so a random assignment can test for one.Source: §3.5 · p. 18
  • O*(2^{p(q−2)}) time suffices to witness a p-packing with probability at least 1/2 for polynomial-size families.The algorithm evaluates the inclusion-exclusion sum over label subsets and extracts the coefficient of w^p.Source: §3.5 · p. 18

4. A Projection–Determinant Sieve for p-Packings of q-Sets

The section develops a randomized projection-and-determinant sieve for detecting p-packings of q-sets. It uses characteristic-2 cancellation and polynomial evaluation to recognize packings and gives parameter-dependent running times for q=3, 4, and 5.

4.1. Tutte’s observation.

  • Tutte’s observation pairs non-involutions by reversing a cycle of length at least three, so their determinant contributions cancel in characteristic 2.Symmetry of the matrix preserves the paired contributions.Source: §4.1 · p. 19

4.2. Admissible packings and prepackings.

  • A prepacking is admissible, has p0, p1, and p2 sets meeting U1 in zero, one, and two points, respectively, and is pairwise disjoint when projected to U1.Compatible involutions fix singleton intersections and transpose two-point intersections.Source: §4.2 · pp. 20–21

4.3. Random projection.

  • A random partition of U gives a fixed packing a probability of appearing as a (p0,p1,p2)-packing, according to the numbers of sets intersecting U1 in zero, one, or two points.The admissibility lemma analyzes this projection probability; the excerpt gives no explicit value for it.Source: §4.3 · p. 21

4.4. Fingerprinting and identifiability.

  • The labeling scheme combines a compatible involution with labels on the domain, and a packing’s monomial uniquely identifies the packing and, for bijective labels, its labeling.Labels are assigned to the U2 elements paired with sets in the packing.Source: §4.4 · pp. 21–22

4.5. Sieving for bijective labelings.

  • Inclusion-exclusion over avoided labels isolates bijectively labeled prepackings for the sieve.The bijectively labeled objects are then separated into packings and non-packings.Source: §4.5 · p. 22, §4.6 · p. 22

4.6. Fingerprints of bijectively labeled non-(p0, p1, p2)-packings cancel.

  • A pairing argument makes the sum of fingerprints for bijectively labeled non-packings vanish in characteristic 2.This cancellation leaves the packing contribution in the sieve.Source: §4.6 · p. 22

4.7. The algorithm.

  • With parameter choices making each fixed packing a valid projected packing with positive probability, the repeated randomized procedure witnesses it with probability at least (1−e^-1)/2.The procedure tests whether a generating polynomial is nonzero; its nonzero status characterizes the existence of the relevant packing.Source: §4.7 · p. 23
  • O*(3.3432^p) for q=3, O*(7.2562^p) for q=4, and O*(15.072^p) for q=5, for polynomial-size families F.The corresponding parameter choices are β1=0.281509, β2=0.679622; β1=0.323262, β2=0.612790; and β1=0.338614, β2=0.582673.Source: §4.7 · p. 24

5. A Determinant Sieve for Edge-Coloring

The section turns edge-coloring of regular graphs into a search for edge-disjoint perfect matchings, using determinant-based generating functions and a labeling sieve. It obtains a polynomial-space randomized algorithm and extends the approach to nonregular graphs.

5.1. Tutte’s observation revisited.

  • A d-regular graph has a d-edge-coloring exactly when it contains d−1 pairwise edge-disjoint perfect matchings.Each color class must be a perfect matching.Source: §5.1 · p. 24

5.2. Fingerprinting and identifiability.

  • The sieve uses a monomial fingerprint that identifies a tuple of perfect matchings and, when the matchings are edge-disjoint and labels bijective, its labeling.Each matching tuple is assigned labels over its edge-index domain.Source: §5.2 · p. 24

5.3. Sieving for bijective labelings.

  • Inclusion-exclusion over labels selects bijectively labeled tuples of perfect matchings for the sieve.The label-avoiding subsets are defined before the inclusion-exclusion step.Source: §5.3 · p. 24

5.4. Fingerprints of bijectively labeled non-disjoint p-tuples cancel.

  • A pairing argument cancels the fingerprints of bijectively labeled tuples that are not edge-disjoint in characteristic 2.The excluded tuples are those with at least one edge occurring in multiple matchings.Source: §5.4 · p. 25

5.5. The algorithm.

  • The determinant sieve evaluates generating functions for perfect matchings and uses the resulting polynomial’s nonzero status to test for a disjoint matching tuple.Tutte’s lemma supplies the determinant computation for each matching; the randomized evaluation has polynomial arithmetic cost per assignment.Source: §5.5 · p. 25
  • O*(2^((d−1)n/2)) time and polynomial space suffice to test whether a d-regular graph has a d-edge-coloring, with success probability Ω(1).The algorithm detects d−1 pairwise edge-disjoint perfect matchings.Source: §5.5 · p. 25

5.6. Graphs that are not regular.

  • For nonregular graphs, the modified algorithm runs in O*(2^m) time and polynomial space, where m=|E|.It uses matchings instead of perfect matchings, sets |L|=m, and takes p=∆.Source: §5.6 · p. 25
Loading 1007.1161v1…