Mikołaj Bojańczyk ; Michał Pilipczuk - Optimizing tree decompositions in MSO

lmcs:6993 - Logical Methods in Computer Science, February 3, 2022, Volume 18, Issue 1 - https://doi.org/10.46298/lmcs-18(1:26)2022
Optimizing tree decompositions in MSO

Authors: Mikołaj Bojańczyk ; Michał Pilipczuk

    The classic algorithm of Bodlaender and Kloks [J. Algorithms, 1996] solves the following problem in linear fixed-parameter time: given a tree decomposition of a graph of (possibly suboptimal) width k, compute an optimum-width tree decomposition of the graph. In this work, we prove that this problem can also be solved in mso in the following sense: for every positive integer k, there is an mso transduction from tree decompositions of width k to tree decompositions of optimum width. Together with our recent results [LICS 2016], this implies that for every k there exists an mso transduction which inputs a graph of treewidth k, and nondeterministically outputs its tree decomposition of optimum width. We also show that mso transductions can be implemented in linear fixed-parameter time, which enables us to derive the algorithmic result of Bodlaender and Kloks as a corollary of our main result.

    Volume: Volume 18, Issue 1
    Published on: February 3, 2022
    Accepted on: August 9, 2021
    Submitted on: December 20, 2020
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Discrete Mathematics,Computer Science - Data Structures and Algorithms
    Fundings :
      Source : OpenAIRE Graph
    • A unified theory of finite-state recognisability; Funder: European Commission; Code: 683080


    Consultation statistics

    This page has been seen 571 times.
    This article's PDF has been downloaded 500 times.