Problem
This year features the $k$-Path problem of finding a path of length $k$ in a graph. See also the IPEC’26 Announcement Slides.
What is a $k$-path
In an undirected graph $G = (V, E)$, a $k$-path is a sequence of $k + 1$ distinct vertices $v_1, v_2, \dots, v_{k+1}$ such that $\lbrace v_i, v_{i+1} \rbrace \in E$ for all $i \in \lbrace 1, 2, \dots, k \rbrace$.
In a weighted directed graph $G = (V, A, w)$ with a weight function $w$ mapping directed edges into positive real numbers, a $k$-path is a sequence of $k + 1$ distinct vertices $v_1, v_2, \dots, v_{k+1}$ such that $(v_i, v_{i+1}) \in A$ for all $i \in \lbrace 1, 2, \dots, k \rbrace$, and its weight is $\sum_{i=1}^{k} w(v_i, v_{i+1})$.
For example, the above figure contains an undirected $4$-path on the left and a directed $3$-path of weight $12$ on the right.
Complexity
Finding the longest path is NP-hard due to the NP-completeness of the Hamiltonian Path problem. It is, however, fixed-parameter tractable in the length of the path. Numerous FPT-time approaches have been designed for the problem such as color coding and algebraic algorithms. The $k$-Path problem is also FPT with respect to many other parameters such as treedepth. On the negative results, $k$-Path does not admit a polynomial kernel unless $\text{NP} \subseteq \text{coNP} / \text{poly}$.
Literature
- Alon, N., Yuster, R., and Zwick, U. (1995). Color-coding.
- Björklund, A., Husfeldt, T., Kaski, P., and Koivisto, M. (2017). Narrow sieves for parameterized paths and packings.
- Björklund, A., Kaski, P., and Kowalik, Ł. (2014). Fast witness extraction using a decision oracle.
- Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Hermelin, D. (2009). On problems without polynomial kernels.
- Monien, B. (1985). How to find long paths efficiently.
- Nederlof, J. (2025). Weighted $k$-Path and Other Problems in Almost $O^*(2^k)$ Deterministic Time via Dynamic Representative Sets.
- Nederlof, J., Pilipczuk, M., Swennenhuis, C. M., and Węgrzycki, K. (2023). Hamiltonian cycle parameterized by treedepth in single exponential time and polynomial space.
- Tsur, D. (2019). Faster deterministic parameterized algorithm for $k$-path.
- Williams, R. (2009). Finding paths of length $k$ in $O^*(2^k)$ time.
We also wish to acknowledge the past ICGCA contests on counting paths as potentially relevant sources for ideas and literature.
Timeline
- September 2026: Announcement of the challenge and tracks ✅
- October 2026: Definition of input and output formats, tiny test set, and verifier
- January 2027: Release of public instances and details about the benchmark
- April 2027: Submission via optil.io opens
- Early July 2027: Final submission deadline
- Mid-July 2027: Solver review phase
- End of July 2027: Announcement of results
Tracks
The challenge features three distinct tracks:
- an “exact unweighted” track – output the largest integer $k$ in an undirected unweighted graph $G$ such that $G$ contains a $k$-path together with the path as a witness.
- an “exact weighted” track – output a $k$-path of maximum weight for a given $k$ in a weighted directed graph.
- a “heuristic” track – output a valid lower bound for the maximum path length in an undirected unweighted graph, computed within a reasonable time limit, and a path witnessing the lower bound.
Zulip
Join us on Zulip for discussions and updates.
Program Committee
- Juha Harviainen (University of Helsinki, Finland)
- André Schidler (University of Freiburg, Germany)
- Frank Sommer (University of Jena, Germany)