Minimum Conflict Free Colouring Parameterized by Treewidth
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Springer Link
Abstract
Conflict free q-Colouring of a graph G refers to the colouring of a subset of vertices of G using q colours such that every vertex has a neighbour of unique colour. In this paper, we study the Minimum Conflict free q-Colouring problem. Given a graph G and a fixed constant q, Minimum Conflict free q-Colouring is to find a Conflict free q-Colouring of G that minimises the number of coloured vertices. We study the Minimum Conflict free q-Colouring problem parameterized by the treewidth of G. We give an FPT algorithm for this problem and also prove running time lower bounds under Exponential Time Hypothesis (ETH) and Strong Exponential Time Hypothesis (SETH).
Description
Only IISERM authors are available in the record.
Citation
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 12016 LNCS, pp. 439-450