Fixed parameter algorithms for counting and deciding bounded restrictive list H-colorings

Josep Díaz, Maria Serna, Dimitrios M. Thilikos

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

We study the fixed parameter tractability of the parameterized counting and decision version of the restrictive H-coloring problem. These problems are defined by fixing the number of preimages of a subset C of the vertices in H through a partial weight assignment (H,C,K). We consider two families of partial weight assignment the simple and the plain. For simple partial weight assignments we show an FPT algorithm for counting list (H, C, K)-colorings and faster algorithms for its decision version. For the more general class of plain partial weight assignment we give an FPT algorithm for the (H, C, K)-coloring decision problem. We introduce the concept of compactor and an algorithmic technique, compactor enumeration, that allow us to design the FPT algorithms for the counting version (and probably export the technique to other problems).

Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsSusanne Albers, Tomasz Radzik
PublisherSpringer Verlag
Pages275-286
Number of pages12
ISBN (Print)3540230254, 9783540230250
DOIs
StatePublished - 2004

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3221
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Fixed parameter algorithms for counting and deciding bounded restrictive list H-colorings'. Together they form a unique fingerprint.

Cite this