Source-linked AI summary
Finding paths of length k in O*(2^k) time
Ryan Williams
TL;DR
The paper addresses the parameterized k-path problem of finding a simple path of length at least k in a graph. It develops a randomized algebraic method that detects multilinear terms in a polynomial representation, yielding an O*(2^k) algorithm. The algorithm has one-sided correctness and succeeds with probability at least 1/5 before amplification, while related extensions and derandomization remain limited.
Problem
The k-path problem asks whether a graph contains a simple path of length at least k, a problem that is NP-complete when k is part of the input.
Method
The algorithm substitutes random group-algebra elements into the k-walk polynomial so non-multilinear terms vanish while some multilinear terms survive.
Results
O*(2^k) time is achieved, with output yes with probability at least 1/5 when a multilinear term exists and always no otherwise.
Takeaways & Limitations
The result matches the known O*(2^n) runtime for Hamilton path across all parameter values k.
Takeaways & Limitations
The approach does not appear to extend to weighted graphs, and its derandomization appears difficult.
Abstract
from arXiv · showhide
We give a randomized algorithm that determines if a given graph has a simple path of length at least k in O(2^k poly(n,k)) time.
1 Introduction
The k-path problem asks whether a graph contains a simple path of length at least k, a problem that is NP-complete when k is part of the input. The paper gives a randomized O*(2^k) algorithm, matching the known runtime for Hamilton paths across all k.
- The k-path problem asks whether a graph contains a simple path of length at least k and, if so, produces such a path.
- When k is part of the input, the k-path problem is NP-complete.
- The paper extends Koutis’s approach to obtain an O*(2^k) randomized algorithm for finding a k-path.
- A substantial improvement in the runtime dependence on k would imply a faster Hamilton path algorithm, an open problem for over forty years.
2 Preliminaries
The paper introduces group algebras as algebraic structures combining a field and a multiplicative group. Their elements are formal sums over group elements, with pointwise addition and convolution-like multiplication.
- A group algebra F[G] combines properties of a field F and a multiplicative group G.Its elements have coefficients from F and are indexed by elements of G.
- Elements of F[G] are formal sums over group elements with coefficients from the field.
- Addition in F[G] is defined pointwise.
- Multiplication in F[G] has the form of a convolution.
- The operations define a ring with zero and multiplicative identity inherited from the field and group.
- Z^k_2 is the group of binary k-vectors under componentwise addition modulo 2, with the all-zeros vector as identity.Every vector is its own inverse.
3 Algorithm for the k-Path Problem
The algorithm detects k-paths by representing graph walks as a polynomial and randomly evaluating it so non-multilinear terms vanish while multilinear terms survive with constant probability. It runs in O*(2^k) time and can be extended to construct a path.
- Polynomial representation: A k-path exists exactly when the k-walk polynomial P_k contains a multilinear term.The polynomial is evaluated through an arithmetic circuit derived from the graph.
- Correctness: If P_k has a multilinear term, the randomized algorithm outputs yes with probability at least 1/5, while it always outputs no when none exists.The success bound follows from the probability of obtaining independent vectors and a nonzero random scalar evaluation.
- Running time: The algorithm runs in O*(2^k s(n)) time for a circuit of size s(n), yielding O*(2^k) time for k-path detection.Group-algebra elements use 2^k-vector representations, and multiplication is implemented with a Walsh-Hadamard transform.
- Polynomial representation: The polynomial framework assumes multilinear terms have degree at least k, which can be enforced by trying all j from 1 to k and adding variables.The transformation targets the case where at least one multilinear term has degree exactly k.
- Randomized evaluation: Random vectors over Z_2^k and characteristic-two arithmetic cancel terms with repeated variables, so non-multilinear terms evaluate to zero.When the associated vectors are linearly dependent, the corresponding product vanishes; independent vectors generate surviving span terms.
4 Conclusion
The conclusion identifies Short Cheap Tour as fixed-parameter tractable but leaves open whether it can reach O*(2^k) time. It also highlights unresolved derandomization and the limitation that the paper’s algorithm does not extend to weighted graphs.
- The authors ask whether Short Cheap Tour can be solved in O*(2^k) time.
- Short Cheap Tour can be solved in O*(4^k) time by a randomized algorithm that succeeds with high probability.
- The paper’s algorithm does not appear to extend to weighted graphs.
- A deterministic k-path algorithm with the same runtime remains an open question.The authors note that their algorithm appears more difficult to derandomize, and that derandomizing polynomial identity testing in polynomial time would imply strong circuit lower bounds.