Parameterized counting algorithms for general graph covering problems

Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos

Research output: Contribution to journalConference articlepeer-review


We examine the general problem of covering graphs by graphs: given a graph G, a collection P of graphs each on at most p vertices, and an integer r, is there a collection C of subgraphs of G, each belonging to P, such that the removal of the graphs in C from G creates a graph none of whose components have more than r vertices? We can also require that the graphs in C be disjoint (forming a "matching"). This framework generalizes vertex cover, edge dominating set, and minimal maximum matching. In this paper, we examine the parameterized complexity of the counting version of the above general problem. In particular, we show how to count the solutions of size at most k of the covering and matching problems in time O(n·r(pk+r) + 2 f(k,p,r)), where n is the number of vertices in G and f is a simple polynomial. In order to achieve the additive relation between the polynomial and the non-polynomial parts of the time complexity of our algorithms, we use the compactor technique, the counting analogue of kernelization for parameterized decision problems.

Original languageEnglish (US)
Pages (from-to)99-109
Number of pages11
JournalLecture Notes in Computer Science
StatePublished - 2005
Event9th International Workshop on Algorithms and Data Structures, WADS 2005 - Waterloo, Canada
Duration: Aug 15 2005Aug 17 2005

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Parameterized counting algorithms for general graph covering problems'. Together they form a unique fingerprint.

Cite this