Charles Explorer logo
🇬🇧

Some Parameterized Problems Related to Seidel's Switching

Publication at Faculty of Mathematics and Physics |
2008

Abstract

Seidel's switching of vertex set is an operation, which deletes edges leaving this set from the graph and adds those edges between the set and the rest of the graph, that weren't there originally. Other edges remain untouched by this operation.

The usual question in parameterized complexity is whether the exponential part of the algorithms for hard problems can be bounded by some function of only selected parameter, which we assume to be small. We study the complexity of a question, if the given graph can be turned into a graph with some property P using Seidel's switching, from the parameterized view.

We show fixed parameter tractability of switching to a regular graph, to a graph with bounded degree of vertices, or with bounded number of edges, a graph without a forbidden subgraph and a bipartite graph.