Alladi Ramakrishnan Hall

Tractability of Packing Vertex-Disjoint A-Paths under Length Constraints

Abhishek Sahu

NISER

Given an undirected graph G = (V, E) and a set A ⊆ V (G), an A-path is a path in G that starts and ends at two distinct vertices of A. An A-path P of G is called an (A, ℓ)-path if the length of P is exactly ℓ. The (A, ℓ)-Path Packing problem asks if given a graph G = (V, E) and a subset A ⊆ V (G), there are
at least k vertex disjoint (A, ℓ)-paths in G. Similarly, Short (A, ℓ)-Path Packing asks if G has at least k vertex-disjoint A-paths each having length at most ℓ. In this paper, we provide a systematic study of parameterized complexity and kernelization of (A, ℓ)-Path Packing and Short (A, ℓ)-Path Packing with
respect to deletion distance to some natural hereditary graph classes. Let dtp(G), cvd(G), vc(G), nd(G) and
tc(G) be the sizes of a minimum path deletion set, minimum cluster vertex deletion set, minimum vertex cover,
minimum neighborhood diversity, and minimum twin cover respectively. Then, we prove the following results
for (A, ℓ)-Path Packing and Short (A, ℓ)-Path Packing.

(A, ℓ)-Path Packing is W[1]-complete when parameterized by dtp(G) + |A|.

(A, ℓ)-Path Packing is FPT when parameterized by cvd(G) + |A| as well as when parameterized by
cvd(G) + ℓ.

Short (A, ℓ)-Path Packing admits FPT algorithms when parameterized by cvd(G) as well as when
parameterized by nd(G).

From the kernelization perspective, we prove that Short (A, ℓ)-Path Packing and (A, ℓ)-Path Packing
admit a polynomial kernels when parameterized by tc(G) and vc(G), respectively.