Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems

Given a graph G we provide dynamic programming algorithms for many locally checkable vertex subset and vertex partitioning problems. Their runtime is polynomial in the number of equivalence classes of problem-specific equivalence relations on subsets of vertices, defined on a given decomposition tre...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2013-11, Vol.511, p.66-76
Main Authors: Bui-Xuan, Binh-Minh, Telle, Jan Arne, Vatshelle, Martin
Format: Article
Language:English
Subjects:
Computer Science
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a graph G we provide dynamic programming algorithms for many locally checkable vertex subset and vertex partitioning problems. Their runtime is polynomial in the number of equivalence classes of problem-specific equivalence relations on subsets of vertices, defined on a given decomposition tree of G. Using these algorithms all these problems become solvable in polynomial time for many well-known graph classes like interval graphs and permutation graphs (Belmonte and Vatshelle (2013)  [1]). Given a decomposition of boolean-width k we show that the algorithms will have runtime O(n42O(k2)), providing the first large class of problems solvable in fixed-parameter single-exponential time in boolean-width.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2013.01.009