On Subgraph Complementation to H-free Graphs
| Autor: | Sagartanu Pal, Jay Garchar, R. B. Sandeep, Dhanyamol Antony, Sagnik Sen, R. Subashini |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Zdroj: | Graph-Theoretic Concepts in Computer Science ISBN: 9783030868376 WG |
| DOI: | 10.1007/978-3-030-86838-3_9 |
| Popis: | For a class \(\mathcal {G}\) of graphs, the problem Subgraph Complement to \(\mathcal {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 \(\mathcal {G}\). We investigate the complexity of the problem when \(\mathcal {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\ge 1\), the problem is solvable in polynomial-time. This applies even when \(\mathcal {G}\) is a subclass of \(K_t\)-free graphs recognizable in polynomial-time, for example, the class of \((t-2)\)-degenerate graphs. 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\ge 5\). This, along with 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\ge 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\ge 8\), leaving behind four unresolved cases - \(C_4, C_5, C_6,\) and \(C_7\). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|