Header menu link for other important links
X

The Parameterized Complexity of Cycle Packing: Indifference is Not an Issue

, Abhishek Sahu, Saket Saurabh, Meirav Zehavi
Published in Springer Nature
2018
Volume: 10807
   
Pages: 712 - 726
Abstract

In the CYCLE PACKING problem, we are given an undirected graph G, a positive integer r, and the task is to check whether there exist r vertex-disjoint cycles. In this paper, we study CYCLE PACKING with respect to a structural parameter, namely, distance to proper interval graphs (indifference graphs). In particular, we show that CYCLE PACKING is fixed-parameter tractable (FPT) when parameterized by t, the size of a proper interval deletion set. For this purpose, we design an algorithm with O(2O(tlogt)nO(1))O(2O(tlogt)nO(1)) running time. Several structural parameterizations for CYCLE PACKING have been studied in the literature and our FPT algorithm fills a gap in the ecology of such parameterizations. We combine color coding, greedy strategy and dynamic programming based on structural properties of proper interval graphs in a non-trivial fashion to obtain the FPT algorithm.

About the journal
JournalData powered by TypesetLatin American Symposium on Theoretical Informatics
PublisherData powered by TypesetSpringer Nature
Open AccessNo