Diameter of Minimal Separators in Graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2014

Diameter of Minimal Separators in Graphs

Diamètre des séparateurs minimaux dans les graphes

Résumé

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.
Nous \'etablissons des relations g\'en\'erales entre les propri\'et\'es topologiques des graphes et leurs propri\'et\'es m\'etriques.Dans ce but, nous bornons sup\'erieurement le diam\`etre des \emph{s\'eparateurs minimaux} dans un graphe par une fonction de leur taille.Plus pr\'ecis\'ement, nous prouvons que, dans n'importe quel graphe $G$, le diam\`etre de tout s\'eparateur minimal $S$ dans $G$ est au plus $\lfloor \frac{\ell(G)} {2}\rfloor \cdot (|S|-1)$ avec $\ell(G)$ la plus grande taille d'un cycle isom\'etrique dans $G$.Nous am\'eliorons cette borne dans le cas des graphes pour lesquels il existe un \emph{ordre d'\'elimination isom\'etrique}: nous prouvons que tout s\'eparareur minimal $S$ dans un tel graphe a pour diam\`etre au plus $2 (|S|-1)$. Nos preuves sont principalement bas\'ees sur le fait que les s\'eparateurs minimaux dans un graphe $G$ sont connexes dans l'une de ses puissances.Une cons\'equence facile de nos r\'esultats est que pour tout graphe $G$, la \emph{treelength} $tl(G)$ est au plus $\lfloor \frac{\ell(G)} {2}\rfloor$ fois sa \emph{treewidth} $tw(G)$.En compl\'ement de cette relation, nous prouvons que, pour tout graphe $G$ qui exclut un \emph{apex graph} $H$ comme mineur, $tw(G) \leq c_H \cdot tl(G)$ avec $c_H$ une constante qui ne d\'epend que de $H$.Nous am\'eliorons cette constante dans le cas o\`u $G$ est de genre born\'e.En cons\'equence de quoi, nous obtenons un algorithme tr\`es simple avec facteur d'approximation $O(\ell(G))$ pour calculer la treewidth des graphes qui excluent un apex graph comme mineur en temps $O(n m)$.
Fichier principal
Vignette du fichier
RR-8639_dec2014.pdf (749.18 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01088423 , version 1 (27-11-2014)
hal-01088423 , version 2 (19-12-2014)

Identifiants

  • HAL Id : hal-01088423 , version 2

Citer

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⟩
272 Consultations
582 Téléchargements

Partager

Gmail Facebook X LinkedIn More