On Subgraph Complementation to H-free Graphs

• Published in: Algorithmica 2022-10, Vol.84 (10), p.2842-2870
• Main Authors: Antony, Dhanyamol, Garchar, Jay, Pal, Sagartanu, Sandeep, R. B., Sen, Sagnik, Subashini, R.
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Algorithms; Apexes; Complement; Complexity; Computer Science; Computer Systems Organization and Communication Networks; Data Structures and Information Theory; Graph theory; Graphs; Mathematics of Computing; Polynomials; Theory of Computation
• ISSN: 0178-4617; 1432-0541
• DOI: 10.1007/s00453-022-00991-3

For a class G of graphs, the problem Subgraph Complement to G asks whether one can find a subset S of vertices of the input graph G such that complementing the subgraph induced by S in G results in a graph in G . We investigate the complexity of the problem when G is H -free for H being a complete graph, a star, a path, or a cycle. We obtain the following results: When H is a K t (a complete graph on t vertices) for any fixed t ≥ 1 , the problem is solvable in polynomial-time. This applies even when G is a subclass of K t -free graphs recognizable in polynomial-time, for example, the class of d -degenerate graphs, where d = t - 2 for t > 2 . When H is a K 1 , t (a star graph on t + 1 vertices), we obtain that the problem is NP-complete for every t ≥ 5 . This, along with the known results, leaves only two unresolved cases— K 1 , 3 and K 1 , 4 . When H is a P t (a path on t vertices), we obtain that the problem is NP-complete for every t ≥ 7 , leaving behind only two unresolved cases— P 5 and P 6 . When H is a C t (a cycle on t vertices), we obtain that the problem is NP-complete for every t ≥ 7 , leaving behind only three unresolved cases— C 4 , C 5 , and C 6 . Further, we prove that these hard problems do not admit subexponential-time algorithms (algorithms running in time 2 o ( ∣ V ( G ) ∣ ) ), assuming the Exponential Time Hypothesis. We show that the complexity results on a graph class G is also true for the class G ¯ of the complement graphs of G . Therefore, each of the above results mentioned for the H -free class of graphs is also valid for the H ¯ -free class of graphs. It is noteworthy that our results generalize two main results, namely, Subgraph Complement to triangle-free graphs and Subgraph Complement to d -degenerate graphs, and resolves one open question due to Fomin et al. (Algorithmica, 2020).