Algorithms for subgraph complementation to some classes of graphs

• Published in: Information processing letters 2025-02, Vol.188, p.106530, Article 106530
• Main Authors: Antony, Dhanyamol, Pal, Sagartanu, Sandeep, R.B.
• Format: Article
• Language: English
• Subjects: Diamond; Kernelization; Minimum degree; Star graphs; Subgraph complementation
• ISSN: 0020-0190
• DOI: 10.1016/j.ipl.2024.106530

For a class G of graphs, the objective of Subgraph Complementation toG is to find whether there exists a subset S of vertices of the input graph G such that modifying G by complementing the subgraph induced by S results in a graph in G. We obtain a polynomial-time algorithm for the problem when G is the class of graphs with minimum degree at least k, for a constant k, answering an open problem by Fomin et al. (Algorithmica, 2020). When G is the class of graphs without any induced copies of the star graph on t+1 vertices (for any constant t≥3) and diamond, we obtain a polynomial-time algorithm for the problem. This is in contrast with a result by Antony et al. (Algorithmica, 2022) that the problem is NP-complete and cannot be solved in subexponential-time (assuming the Exponential Time Hypothesis) when G is the class of graphs without any induced copies of the star graph on t+1 vertices, for every constant t≥5. •We study a graph modification problem known as subgraph complementation.•We prove that subgraph complementation is polynomial-time solvable if the target graph class is the class of graphs with minimum degree at least k, for any constant k, answering an open problem.•We prove that the problem is polynomial-time solvable if the target graph class is the class of graphs without induced copies of a fixed star graph and a diamond graph.