Partitioning vertices of graphs into paths of the same length

Discrete Applied Mathematics. 2025. Т. 373. С. 179–195.

Duginov O., Dmitriy Malyshev, Dmitriy Mokeev

Given a graph, the (induced) P_k-partition problem is to decide whether its vertex set can be partitioned into subsets, each of which induces (the k-path) a k-vertex subgraph with a Hamiltonian path. We show that these problems are NP-complete for planar subcubic bipartite (H_1,H_2,...,H_ℓ)-free graphs of girth g, for any k,g≥3,l≥1, where Hi is obtained by joining central vertices in two copies of P_3 with P_{i+1}. We show that the P_k-partition (induced P_k-partition) problem is NP-complete for split graphs and any k≥5, chordal graphs and any k≥4 (any k≥3), line graphs of planar bipartite graphs and any k≥5 (any k≥3). We show that the P_4-partition and, for any k≥5, induced P_k-partition problems, restricted to split graphs, are polynomial. Additionally, we prove NP-completeness for the optimization version of the induced P_4-partition problem and split graphs.

Keywords: path packing, path partition, special graph classes, computational complexity, path packing, path partition, special graph classes, computational complexity