Accéder directement au contenu Accéder directement à la navigation
Rapport

Treelength of Series-parallel graphs

Abstract : The length of a tree-decomposition of a graph is the maximum distance between two vertices of a same bag of the decomposition. The treelength of a graph is the minimum length among its tree-decomposition. Treelength of graphs has been studied for its algorithmic applications in classical metric problems such as Traveling Salesman Problem or metric dimension of graphs and also, in compact routing in the context of distributed computing. Deciding whether the treelength of a general graph is at most 2 is NP-complete (graphs of treelength one are precisely the chordal graphs), and it is known that the treelength of a graph cannot be approximated up to a factor less than 3/2 (the best known approximation algorithm for treelength has an approximation ratio of 3). However, nothing is known on the computational complexity of treelength in planar graphs, except that the treelength of any outerplanar graph is equal to the third of the maximum size of its isometric cycles. This work initiates the study of treelength in planar graphs by considering its next natural subclass, namely the one of series-parallel graphs. We first fully describe the treelength of melon graphs (set of pairwise internally disjoint paths linking two vertices), showing that, even in such a restricted graph class, the expression of the treelength is not trivial. Then, we show that treelength can be approximated up to a factor 3/2 in series-parallel graphs. Our main result is a polynomial-time algorithm for deciding whether a series-parallel graph has treelength at most 2. Our latter result relies on a characterization of series-parallel graphs with treelength 2 in terms of an infinite family of forbidden isometric subgraphs.
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.archives-ouvertes.fr/hal-03010346
Contributeur : Thomas Dissaux <>
Soumis le : mardi 17 novembre 2020 - 16:34:21
Dernière modification le : lundi 14 décembre 2020 - 18:08:16

Fichier

Lagos_2021.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-03010346, version 1

Citation

Thomas Dissaux, Guillaume Ducoffe, Nicolas Nisse, Simon Nivelle. Treelength of Series-parallel graphs. [Research Report] Inria & Université Cote d'Azur, CNRS, I3S, Sophia Antipolis, France. 2020. ⟨hal-03010346⟩

Partager

Métriques

Consultations de la notice

10

Téléchargements de fichiers

33