{"id":1192,"date":"2016-12-27T16:09:39","date_gmt":"2016-12-27T15:09:39","guid":{"rendered":"https:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=1192"},"modified":"2016-12-29T14:49:54","modified_gmt":"2016-12-29T13:49:54","slug":"computing-a-tree-decomposition","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20152016-2\/jezyki-automaty-i-obliczenia-2\/monadic-second-order-logic-and-courcelles-theorem\/computing-a-tree-decomposition","title":{"rendered":"Computing a tree decomposition"},"content":{"rendered":"

In this page we prove Theorem 1 below, which says that tree decompositions of slightly suboptimal width can be computed in cubic time. More precisely, we show that for every \"k \in \Nat\" there is a\u00a0cubic time algorithm which inputs a graph and fails or outputs a tree decomposition of width \"<3k\". The algorithm succeeds if the input graph\u00a0has tree width \"< k\". The constants in the cubic time depend exponentially on \"k\". \u00a0The theorem includes a set of distinguished vertices, which are used in its proof, but for external purposes like Courcelle’s Theorem one can assume that the set of distinguished vertices is empty.<\/p>\n

Theorem 1.\u00a0<\/strong>Fix \"k \in \Nat\". There is a cubic time algorithm which does this:<\/em><\/p>\n