Source author record

Dhanyamol Antony

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Cutting a tree with Subgraph Complementation is hard, except for some small trees

For a graph property $Π$ , Subgraph Complementation to $Π$ is the problem to find whether there is 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 satisfying the property $Π$ . We prove that the problem of Subgraph Complementation to $T$ -free graphs is NP-Complete, for $T$ being a tree, except for 41 trees of at most 13 vertices (a graph is $T$ -free if it does not contain any induced copies of $T$ ). This result, along with the 4 known polynomial-time solvable cases (when $T$ is a path on at most 4 vertices), leaves behind 37 open cases. Further, we prove that these hard problems do not admit any subexponential-time algorithms, assuming the Exponential Time Hypothesis. As an additional result, we obtain that Subgraph Complementation to paw-free graphs can be solved in polynomial-time.

preprint2021arXiv

On subgraph complementation to H-free graphs

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\geq 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\geq 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\geq 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\geq 8$ , leaving behind four unresolved cases - $C_4, C_5, C_6,$ and $C_7$ . 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. A simple complementation argument implies that results for $\mathcal{G}$ are applicable for $\overline{\mathcal{G}}$ , thereby obtaining similar results for $H$ being the complement of a complete graph, a star, a path, or a cycle. Our results generalize two main results and resolve one open question by Fomin et al. (Algorithmica, 2020).

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.