On the Parameterized Tractability of Packing Vertex-Disjoint A-Paths with Length Constraints
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911450611580928 |
|---|---|
| author | Bandopadhyay, Susobhan Banik, Aritra Majumdar, Diptapriyo Sahu, Abhishek |
| author_facet | Bandopadhyay, Susobhan Banik, Aritra Majumdar, Diptapriyo Sahu, Abhishek |
| contents | Given an undirected graph G and a set A \subseteq V(G), an A-path is a path in G that starts and ends at two distinct vertices of A with intermediate vertices in V(G) \setminus A. An A-path is called an (A,\ell)-path if the length of the path is exactly \ell. In the {\sc (A, \ell)-Path Packing} problem (ALPP), we seek to determine whether there exist k vertex-disjoint (A, \ell)-paths in G or not. We pursue this problem with respect to structural parameters. We prove that ALPP is W[1]-hard when it is parameterized by the combined parameter distance to path (dtp) and |A|. In addition, we consider the combined parameters distance to cluster (cvd) + |A| and distance to cluster (cvd) + \ell. For both these combined parameters, we provide FPT algorithms. Finally, we consider the vertex cover number (vc) as the parameter and provide a kernel with O(vc^2) vertices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_14768 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the Parameterized Tractability of Packing Vertex-Disjoint A-Paths with Length Constraints Bandopadhyay, Susobhan Banik, Aritra Majumdar, Diptapriyo Sahu, Abhishek Data Structures and Algorithms Discrete Mathematics G.2.2 Given an undirected graph G and a set A \subseteq V(G), an A-path is a path in G that starts and ends at two distinct vertices of A with intermediate vertices in V(G) \setminus A. An A-path is called an (A,\ell)-path if the length of the path is exactly \ell. In the {\sc (A, \ell)-Path Packing} problem (ALPP), we seek to determine whether there exist k vertex-disjoint (A, \ell)-paths in G or not. We pursue this problem with respect to structural parameters. We prove that ALPP is W[1]-hard when it is parameterized by the combined parameter distance to path (dtp) and |A|. In addition, we consider the combined parameters distance to cluster (cvd) + |A| and distance to cluster (cvd) + \ell. For both these combined parameters, we provide FPT algorithms. Finally, we consider the vertex cover number (vc) as the parameter and provide a kernel with O(vc^2) vertices. |
| title | On the Parameterized Tractability of Packing Vertex-Disjoint A-Paths with Length Constraints |
| topic | Data Structures and Algorithms Discrete Mathematics G.2.2 |
| url | https://arxiv.org/abs/2602.14768 |