Structural and algorithmic studies on some graph modifications based on complementation

Abstract

Complementation is a very fundamental graph operation. The atomic operation in complemen- tation is to flip the adjacency between a pair of vertices, i.e., to add an edge between them if it does not exist, and to delete the edge if it exists. We conduct structural and algorithmic study of three kinds of graph complementations, namely, subgraph complementation, switching, and local complementation. Each of these complementations is specified by a pair (G, S), where G is a graph and S is a subset of its vertices. In subgraph complementation, the subgraph induced by S is complemented. In switching, the adjacencies of pairs u, v of vertices are flipped, where u is from S and v is from V (G) \ S. Local complementation is a special type of subgraph complementation in which S is the set of neighbors of a vertex in G. newlineLet G be a graph class. Subgraph complementation to G is the problem defined as follows: for a given graph G, does there exist a subset S of vertices of G such that complementing the graph induced by S in G results in a graph in G? A comprehensive study of this problem was initiated by Fomin et al. (Algorithmica, 2020). We study the complexity of the problem when G is one of the following graph classes: Kt-free , paw-free, graphs with minimum degree at least r (a constant), {star, diamond}-free. We obtain polynomial-time algorithm in each case. Moreover, we show that Subgraph complementation to G is polynomially equivalent to Subgraph complementation to G, where G is the set of complements of graphs in G. Our results resolve two open problems, and subsume two main results by Fomin et al. (Algorithmica, 2020). newlineSwitching was introduced by van Lint and Seidel in 1966. Various aspects of switching have been studied for the last six decades. For a hereditary graph class G, there is a unique maximal subclass of G closed under switching, and a unique minimal superclass of G closed under switching. We refer to them as the maximum subclass of G closed under switching and the minimum superclass of G closed under s