WAOA 2018 Paper Abstract

TITLE: Reconfiguration of graphs with connectivity constraints
AUTHORS: Arnaud Mary and Nicolas Bousquet

Abstract:
A graph $G$ realizes the degree sequence $S$ if the degrees of its vertices in the non increasing order is $S$. 
Hakimi~\cite{HakiI} gave a necessary and sufficient condition to guarantee that there exists a connected multigraph realizing $S$. Taylor~\cite{taylor81} later proved that all the connected multigraphs can be obtained from any of them via a sequence of flips. A flip consists in replacing two edges $ab,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 nested if for every $C,C' \in \mathcal{CC}$ either $C \cap C' = \emptyset$ or the 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 provides an approximation algorithm on the shortest transformation whose ratio depends on the depth of the nested partition.