2026-08-04T19:11:12Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:20572 2024-08-23T05:50:28Z ddc:004 open_access
Tractability of Packing Vertex-Disjoint A-Paths Under Length Constraints Bandopadhyay, Susobhan Banik, Aritra Majumdar, Diptapriyo Sahu, Abhishek Parameterized complexity (A,𝓁)-Path Packing Kernelization Randomized-Exponential Time Hypothesis Graph Classes Given an undirected graph G and a set A βŠ† 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)⧡A. An A-path is called an (A,𝓁)-path if the length of the path is exactly 𝓁. In the (A, 𝓁)-Path Packing problem (ALPP), we seek to determine whether there exist k vertex-disjoint (A, 𝓁)-paths in G or not. The problem is already known to be fixed-parmeter tractable when parameterized by k+𝓁 via color coding while it remains Para-NP-hard when parameterized by k (Hamiltonian Path) or 𝓁 (P₃-Partition) alone. Therefore, a logical direction to pursue this problem is to examine it in relation to structural parameters. Belmonte et al. initiated a study along these lines and proved that ALPP parameterized by pw+|A| is W[1]-hard where pw is the pathwidth of G. In this paper, we strengthen their result and prove that it is unlikely that ALPP is fixed-parameter tractable even with respect to a bigger parameter (|A|+dtp) where dtp denotes the distance between G and a path graph (distance to path). We use a randomized reduction to achieve the mentioned result. Toward this, we prove a lemma similar to the influential "isolation lemma": Given a set system (X,β„±) if the elements of X are assigned a weight uniformly at random from a set of values fairly large, then each subset in β„± will have a unique weight with high probability. We believe that this result will be useful beyond the scope of this paper. ALPP being hard even for structural parameters like distance to path+|A| rules out the possibility of any FPT algorithms for many well-known other structural parameters, including FVS+|A| and treewidth+|A|. There is a straightforward FPT algorithm for ALPP parameterized by vc, the vertex cover number of the input graph. Following this, we consider the parameters CVD(cluster vertex deletion)+|A| and CVD+|𝓁| and show the problem to be FPT with respect to these parameters. Note that CVD is incomparable to the treewidth of a graph and has been in vogue recently. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Susobhan Bandopadhyay and Aritra Banik and Diptapriyo Majumdar and Abhishek Sahu 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.16 urn:nbn:de:0030-drops-205725 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.16 eng https://creativecommons.org/licenses/by/4.0/legalcode