ICE-TCS Lectures Series - Eva Jelinkova - Computational complexity of Seidel's switching of graphs
The next ICE- TCS talk for this semester will be delivered on Friday, 9 October, by Eva Jelinkova (Charles University, Czech Republic). The talk, entitled "Computational complexity of Seidel's switching of graphs", will be held in room K5 at Reykjavík University (Kringlan 1) from 14:00 till 15:00.
Further information about forthcoming ICE- TCS events may be found at the ICE-TCS news page
Abstract
Seidel's switch is a graph operation which makes a given vertex adjacent to precisely those vertices to which it was non-adjacent before, while keeping the rest of the graph unchanged. Two graphs are
called switching-equivalent if one can be made isomorphic to the other by a sequence of switches. We study the computational complexity of deciding if a given graph is switching-equivalent to a graph having a certain desired property. There is no obvious relation between this complexity and the complexity of recognizing the property itself.
We present a polynomial-time algorithm for deciding if a graph is switching-equivalent to a claw-free graph. Further, we show that it is NP-complete to decide if a graph is switching-equivalent to a graph containing at most a prescribed number of edges.
This is joint work with Jan Kratochvil (Charles University, Prague).
