Reconfiguration of graphs with connectivity constraints

Nicolas Bousquet 1 Arnaud Mary 2, 3
1 G-SCOP_OC - OC
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
Abstract : A graph $G$ realizes the degree sequence $S$ if the degrees of its vertices is $S$. Hakimi gave a necessary and sufficient condition to guarantee that there exists a connected multigraph realizing $S$. Taylor later proved that any connected multigraph can be transformed into any other via a sequence of flips (maintaining connectivity at any step). A flip consists in replacing two edges $ab$ and $cd$ by the diagonals $ac$ and $bd$. In this paper, we study a generalization of this problem. A set of subsets of vertices $\mathcal{CC}$ is \emph{nested} if for every $C,C' \in \mathcal{CC}$ either $C \cap C' = \emptyset$ or one is included in the other. We are interested in multigraphs realizing a degree sequence $S$ and such that all the sets of a nested collection $\mathcal{CC}$ induce connected subgraphs. Such constraints naturally appear in tandem mass spectrometry. We show that it is possible to decide in polynomial if there exists a graph realizing $S$ where all the sets in $\mathcal{CC}$ induce connected subgraphs. Moreover, we prove that all such graphs can be obtained via a sequence of flips such that all the intermediate graphs also realize $S$ and where all the sets of $\mathcal{CC}$ induce connected subgraphs. Our proof is algorithmic and provides a polynomial time approximation algorithm on the shortest sequence of flips between two graphs whose ratio depends on the depth of the nested partition.
Type de document :
Communication dans un congrès
WAOA 2018 - International Workshop on Approximation and Online Algorithms, Aug 2018, Helsinki, Finland. Springer, 11312, pp.295-309, Lecture Notes in Computer Science. 〈10.1007/978-3-030-04693-4_18〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01964723
Contributeur : Marie-France Sagot <>
Soumis le : dimanche 23 décembre 2018 - 13:05:08
Dernière modification le : vendredi 18 janvier 2019 - 15:21:56

Lien texte intégral

Identifiants

Collections

Citation

Nicolas Bousquet, Arnaud Mary. Reconfiguration of graphs with connectivity constraints. WAOA 2018 - International Workshop on Approximation and Online Algorithms, Aug 2018, Helsinki, Finland. Springer, 11312, pp.295-309, Lecture Notes in Computer Science. 〈10.1007/978-3-030-04693-4_18〉. 〈hal-01964723〉

Partager

Métriques

Consultations de la notice

36