Parameterizing path partitions
From MaRDI portal
Abstract: We study the algorithmic complexity of partitioning the vertex set of a given (di)graph into a small number of paths. The Path Partition problem (PP for short) has been studied extensively, as it includes Hamiltonian Path as a special case. However, the natural variants where the paths are required to be either induced, called Induced Path Partition (IPP for short) or shortest, called Shortest Path Partition (SPP for short), have received much less attention. Both problems are known to be NP-complete on undirected graphs; we strengthen this by showing that they remain so even on planar bipartite directed acyclic graphs (DAGs), and that SPP remains NP-hard on undirected bipartite graphs. Furthermore, when parameterized by the natural parameter "number of paths", both problems are shown to be W[1]-hard on DAGs. We also show that SPP is in XP both for DAGs and undirected graphs for the same parameter (while IPP is known to be NP-hard on undirected graphs, even for two paths). On the positive side, we show that for undirected graphs, both problems are in FPT when parameterized by the neighborhood diversity of the input graph. Moreover, when considering the dual parameterization (graph order minus number of paths), all three variants, IPP, SPP and PP, are shown to be in FPT for undirected graphs.
Cites work
- Algorithmic meta-theorems for restrictions of treewidth
- Covering Points of a Digraph with Point-Disjoint Paths and Its Application to Code Optimization
- Finding k Disjoint Paths in a Directed Planar Graph
- Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
- Graph minors. XIII: The disjoint paths problem
- scientific article; zbMATH DE number 3465355 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Introduction to algorithms.
- LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
- Note on Dilworth's Decomposition Theorem for Partially Ordered Sets
- On mapping processes to processors in distributed systems
- On Path Cover Problems in Digraphs and Applications to Program Testing
- On the \(k\)-path partition of graphs.
- On the isometric path partition problem
- Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow
- Parameterized algorithms
- Parameterized Algorithms for Modular-Width
- Parameterized tractability of edge-disjoint paths on directed acyclic graphs
- Planar 3DM is NP-complete
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- Splitting a graph into disjoint induced paths or cycles.
- The directed subgraph homeomorphism problem
- The disjoint paths problem in quadratic time
- The path partition problem and related problems in bipartite graphs
Cited in
(12)- Path partitions and forward-only trellis algorithms
- On graphs coverable by \({k}\) shortest paths
- Backdoor DNFs
- Is this network proper forest-based?
- Path partitions of phylogenetic networks
- Parameterizing path partitions
- Spanning trees minimizing branching costs
- Additive approximation algorithm for geodesic centers in -hyperbolic graphs
- Merging rules for strong structural controllability and minimum input problem in undirected networks
- Polynomial-time algorithms for \textsc{Path Cover} on trees and graphs of bounded treewidth
- Covering and partitioning of split, chain and cographs with isometric paths
- Covering and partitioning of split, chain and cographs with isometric paths
This page was built for publication: Parameterizing path partitions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6057329)
