What is a $k$-path
In an undirected graph $G = (V, E)$, a $k$-path is a sequence of $k + 1$ distinct nodes $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 nodes $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.
Input specification
Each instance consists of a single text file in DIMACS format with different line types. Lines of the form c ... are comments and should be ignored. For undirected graphs, the first non-comment line is of the form p graph #nodes #edges for a graph on #nodes nodes and #edges edges. The following #edges lines are of the form e u v, stating that there is an undirected edge between nodes u and v. One example instance is provided below:
c A graph with 8 vertices and 12 edges
p graph 8 12
e 1 3
e 1 4
e 1 5
e 1 6
e 1 7
e 1 8
e 2 3
e 2 4
e 2 5
e 2 6
e 2 7
e 2 8
For directed weighted graphs, the first non-comment line is p digraph #nodes #arcs k, including the target length k for the path we are looking for. The following #arcs lines describe the arcs in the form a u v w describing an arc from u to v of weight w. The weight of an arc is a positive integer between $1$ and $2^{31}$, inclusive, and the sum of all arc weights is between $1$ and $2^{63}$. An example instance is provided below:
p digraph 6 7 3
a 1 2 2
a 2 3 2
c This comment appears in the middle of the instance description
a 2 5 3
a 3 6 5
a 4 1 6
a 5 4 1
a 5 6 7
Output specification
The verifier will ignore any comment lines of the form c .... The first non-comment line of the output for undirected graphs should contain the length of the path in the number of edges k. The following k+1 non-comment lines contain the nodes of the path in order.
For the weighted track, the only difference is that the first line should be of the form k w, stating that there is a path of length k and maximum weight w. We guarantee that a k-path always exists in our public and private instances, but for completeness, we recommend the solvers to output just 0 0 without any nodes if none exists. The only exception to this guarantee is the weighted tiny test set instance sample-7.gr for demonstrative purposes. The solutions for the above instances could be
c Outputs can also contain comments if you prefer!
4
3
1
4
2
5
and
3 12
1
2
5
6
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.