A unified FPT Algorithm for Width of Partition Functions
- Creators
- Berthomé, Pascal
- Nisse, Nicolas
- Others:
- Laboratoire d'Informatique Fondamentale d'Orléans (LIFO) ; Université d'Orléans (UO)-Ecole Nationale Supérieure d'Ingénieurs de Bourges
- Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE) ; Inria Sophia Antipolis - Méditerranée (CRISAM) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED) ; Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
- INRIA
Citation
Description
During the last decades, several polynomial-time algorithms have been designed that decide if a graph has treewidth (resp., pathwidth, branchwidth, etc.) at most $k$, where $k$ is a fixed parameter. Amini {\it et al.} (to appear in SIAM J. Discrete Maths.) 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 $\Phi$, that ensures the existence of a linear-time explicit algorithm deciding if a set $A$ has $\Phi$-width at most $k$ ($k$ fixed). In particular, the algorithm we propose unifies the existing algorithms for treewidth, pathwidth, linearwidth, branchwidth, carvingwidth and cutwidth. It also provides the first Fixed Parameter Tractable linear-time algorithm deciding if the $q$-branched treewidth, defined by Fomin {\it et al.} (Algorithmica 2007), of a graph is at most $k$ ($k$ and $q$ are fixed). Our decision algorithm can be turned into a constructive one by following the ideas of Bodlaender and Kloks (J. of Alg. 1996).
Additional details
- URL
- https://hal.inria.fr/inria-00321766
- URN
- urn:oai:HAL:inria-00321766v1
- Origin repository
- UNICA