
AbstractGiven a graph $$G = (V,E)$$ G = ( V , E ) , $$A \subseteq V$$ A ⊆ V , and integers k and $$\ell $$ ℓ , the $$(A,\ell )$$ ( A , ℓ ) -Path Packing problem asks to find k vertex-disjoint paths of length exactly $$\ell $$ ℓ that have endpoints in A and internal points in $$V{\setminus }A$$ V \ A . We study the parameterized complexity of this problem with parameters |A|, $$\ell $$ ℓ , k, treewidth, pathwidth, and their combinations. We present sharp complexity contrasts with respect to these parameters. Among other results, we show that the problem is polynomial-time solvable when $$\ell \le 3$$ ℓ ≤ 3 , while it is NP-complete for constant $$\ell \ge 4$$ ℓ ≥ 4 . We also show that the problem is W[1]-hard parameterized by pathwidth$${}+|A|$$ + | A | , while it is fixed-parameter tractable parameterized by treewidth$${}+\ell $$ + ℓ . Additionally, we study a variant called Short A-Path Packing that asks to find k vertex-disjoint paths of length at most$$\ell $$ ℓ . We show that all our positive results on the exact-length version can be translated to this version and show the hardness of the cases where |A| or $$\ell $$ ℓ is a constant.
FOS: Computer and information sciences, \(A\)-path packing, 000, Treewidth, 511, Parameterized complexity, tractability and kernelization, A-path packing, 004, Principes généraux des mathématiques, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Fixed-parameter tractability, Graph theory (including graph drawing) in computer science, fixed-parameter tractability, Computer Science - Data Structures and Algorithms, treewidth, Data Structures and Algorithms (cs.DS), Paths and cycles
FOS: Computer and information sciences, \(A\)-path packing, 000, Treewidth, 511, Parameterized complexity, tractability and kernelization, A-path packing, 004, Principes généraux des mathématiques, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Fixed-parameter tractability, Graph theory (including graph drawing) in computer science, fixed-parameter tractability, Computer Science - Data Structures and Algorithms, treewidth, Data Structures and Algorithms (cs.DS), Paths and cycles
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
