Diameter of Minimal Separators in Graphs

David Coudert 1 Guillaume Ducoffe 1 Nicolas Nisse 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : We establish general relationships between the topological properties of graphs and their metric properties. For this purpose, we upper-bound the diameter of the {\it minimal separators} in any graph by a function of their sizes. More precisely, we prove that, in any graph $G$, the diameter of any minimal separator $S$ in $G$ is at most $\lfloor\frac{\ell(G)} {2}\rfloor \cdot (|S|-1)$ where $\ell(G)$ is the maximum length of an isometric cycle in $G$. We refine this bound in the case of graphs admitting a {\it distance preserving ordering} for which we prove that any minimal separator $S$ has diameter at most $2 (|S|-1)$. Our proofs are mainly based on the property that the minimal separators in a graph $G$ are connected in some power of $G$.Our result easily implies that the {\it treelength} $tl(G)$ of any graph $G$ is at most $\lfloor \frac{\ell(G)} {2}\rfloor$ times its {\it treewidth} $tw(G)$. In addition, we prove that, for any graph $G$ that excludes an {\it apex graph} $H$ as a minor, $tw(G) \leq c_H \cdot tl(G)$ for some constant $c_H$ only depending on $H$. We refine this constant when $G$ has bounded genus. As a consequence, we obtain a very simple $O(\ell(G))$-approximation algorithm for computing the treewidth of $n$-node $m$-edge graphs that exclude an apex graph as a minor in $O(n m)$-time.
Complete list of metadatas

Cited literature [33 references]  Display  Hide  Download

https://hal.inria.fr/hal-01088423
Contributor : Nicolas Nisse <>
Submitted on : Friday, December 19, 2014 - 1:36:16 PM
Last modification on : Thursday, February 7, 2019 - 3:25:56 PM
Long-term archiving on : Saturday, April 15, 2017 - 8:38:23 AM

File

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

Identifiers

  • HAL Id : hal-01088423, version 2

Collections

Citation

David Coudert, Guillaume Ducoffe, Nicolas Nisse. Diameter of Minimal Separators in Graphs. [Research Report] RR-8639, Inria Sophia Antipolis; I3S; INRIA. 2014, pp.16. ⟨hal-01088423v2⟩

Share

Metrics

Record views

408

Files downloads

341