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

https://hal.inria.fr/hal-00865575
Contributor : Ronan Pardo Soares <>
Submitted on : Monday, September 30, 2013 - 11:46:57 AM
Last modification on : Thursday, February 7, 2019 - 2:24:36 PM
Long-term archiving on : Friday, April 7, 2017 - 4:22:34 AM

File

RR-8372.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00865575, version 2

Citation

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⟩

Share

Metrics

Record views

664

Files downloads

326