Skip to Main content Skip to Navigation

An Unified FPT Algorithm for Width of Partition Functions

Abstract : During the last decades, several polynomial-time algorithms have been designed that decide whether a graph has tree-width (resp., path-width, branch-width, etc.) at most k, where k is a fixed parameter. Amini et al. (Discrete Mathematics'09) use the notions of partitioning-trees and partition functions as a generalized view of classical decompositions of graphs, namely tree decomposition, path decomposition, branch decomposition, etc. In this paper, we propose a set of simple sufficient conditions on a partition function Φ, that ensures the existence of a linear-time explicit algorithm deciding if a set A has Φ-width at most k (k fixed). In particular, the algorithm we propose unifies the existing algorithms for tree-width, path-width, linear-width, branch-width, carving-width and cut-width. It also provides the first Fixed Parameter Tractable linear-time algorithm to decide if the q-branched tree-width, defined by Fomin et al. (Algorithmica'09), of a graph is at most k (k and q are fixed). Moreover, the algorithm is able to decide if the special tree-width, defined by Courcelle (FSTTCS'10), is at most k, in linear-time where k is a Fixed Parameter. Our decision algorithm can be turned into a constructive one by following the ideas of Bodlaender and Kloks (J. of Alg. 1996).
Complete list of metadatas
Contributor : Ronan Pardo Soares <>
Submitted on : Monday, September 30, 2013 - 11:46:57 AM
Last modification on : Monday, October 12, 2020 - 10:30:36 AM
Long-term archiving on: : Friday, April 7, 2017 - 4:22:34 AM


Files produced by the author(s)


  • HAL Id : hal-00865575, version 2


Pascal Berthomé, Tom Bouvier, Frédéric Mazoit, Nicolas Nisse, Ronan Pardo Soares. An Unified FPT Algorithm for Width of Partition Functions. [Research Report] RR-8372, INRIA. 2013. ⟨hal-00865575v2⟩



Record views


Files downloads