Directed Path Partition Problem on Directed Acyclic Graphs

We study the problem of partitioning the vertex set of a given directed graph G = (V, E) into a small number of vertex-disjoint directed paths each of order at most a prescribed k, called the DIRECTED k-PATH PARTITION problem (k-PP, for short). The k-PP problem with k = vertical bar V vertical bar is equivalent to the DIRECTED PATH PARTITION problem (PP), where the goal of PP is to find a minimum collection of vertex-disjoint directed paths of any order to cover all the vertices of V. The decision version of k-PP includes the DIRECTED HAMILTONIAN PATH problem as a special case. Therefore, when k is part of the input, the k-PP is APX-hard, and it is not approximable within two unless P = NP. Although k-PP on general graphs are intractable, several tractable cases are known. The k-PP problem with k = 2 (i.e., 2-PP) is essentially equivalent to the MAXIMUM MATCHING problem on directed graphs, which is solvable in polynomial time. Also, it is claimed that if the input is restricted to directed acyclic graphs (DAGs), then PP can be solved in polynomial time. This implies that if the input graph is a DAG of height at most k, then k-PP can be solved in polynomial time since the order of every path in the directed path partition is at most k. In this paper, we prove that k-PP is NP-hard even if the input graph is restricted to planar, bipartite DAGs of height k + 1 and degree at most three. Also, we present the 1.0075-inapproximability of k-PP for any fixed k >= 3. In contrast, we show that k-PP on directed graphs of degree at most two can be solved in polynomial time.