Subexponential time algorithms for finding small tree and path decompositions

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)

Abstract

The Minimum Size Tree Decomposition (MSTD) and Minimum Size Path Decomposition (MSPD) problems ask for a given n-vertex graph G and integer k, what is the minimum number of bags of a tree decomposition (respectively, path decomposition) of width at most k. The problems are known to be NP-complete for each fixed k¿=¿4. In this paper we present algorithms that solve both problems for fixed k in 2^O(n/ logn) time and show that they cannot be solved in 2^o(n / logn) time, assuming the Exponential Time Hypothesis.
Original languageEnglish
Title of host publicationAlgorithms - ESA 2015 (23rd Annual European Symposium, Patras, Greece, September 14-16, 2015)
EditorsN. Bansal, I. Finocchi
Place of PublicationBerlin
PublisherSpringer
Pages179-190
ISBN (Print)978-3-662-48349-7
DOIs
Publication statusPublished - 2015

Publication series

NameLecture Notes in Computer Science
Volume9294
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Subexponential time algorithms for finding small tree and path decompositions'. Together they form a unique fingerprint.

Cite this