Reconfiguration of graphs with connectivity constraints

09/14/2018
by   Nicolas Bousquet, et al.
0

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 CC is nested if for every C,C' ∈CC either C ∩ C' = ∅ 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 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 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 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset