In a graph, the switching operation reverses adjacencies between a subset of vertices and the others. For a hereditary graph class $\mathcal{G}$, we are concerned with the maximum subclass and the minimum superclass of $\mathcal{G}$ that are closed under switching. We characterize the maximum subclass for many important classes $\mathcal{G}$, and prove that it is finite when $\mathcal{G}$ is minor-closed and omits at least one graph. For several graph classes, we develop polynomial-time algorithms to recognize the minimum superclass. We also show that the recognition of the superclass is NP-complete for $H$-free graphs when $H$ is a sufficiently long path or cycle, and it cannot be solved in subexponential time assuming the Exponential Time Hypothesis.

Given a graph G and an integer k, the H-free Edge Editing problem is to find whether there exist at most k pairs of vertices in G such that changing the adjacency of the pairs in G results in a graph without any induced copy of H. Nontrivial polynomial kernels are known to exist for some graphs H with at most 4 vertices, but starting from 5 vertices, polynomial kernels are known only if H is either complete or empty. This suggests the conjecture that there is no other H with at least 5 vertices where H-free Edge Editing admits a polynomial kernel. Towards this goal, we obtain a set H of nine 5-vertex graphs such that if for every H∈H, H-free Edge Editing is incompressible and the complexity assumption NP⊈coNP/poly holds, then H-free Edge Editing is incompressible for every graph H with at least five vertices that is neither complete nor empty. We obtain similar results also for H-free Edge Deletion/Completion.

Given a fixed graph H, the H-free editing problem asks whether we can edit at most k edges to make a graph contain no induced copy of H. We obtain a polynomial kernel for this problem when H is a diamond. The incompressibility dichotomy for H being a 3-connected graph and the classical complexity dichotomy suggest that except for H being a complete/empty graph, H-free editing problems admit polynomial kernels only for a few small graphs H. Therefore, we believe that our result is an essential step toward a complete dichotomy on the compressibility of H-free editing. Additionally, we give a cubic-vertex kernel for the diamond-free edge deletion problem, which is far simpler than the previous kernel of the same size for the problem.

Performing Gaussian elimination to a sparse matrix may turn some zeroes into nonzero values, so called fill-ins, which we want to minimize to keep the matrix sparse. Let n denote the rows of the matrix and k the number of fill-ins. For the minimum fill-in problem, we exclude the existence of polynomial time approximation schemes, assuming P≠NP, and the existence of 2O(n1+ δ) -time approximation schemes for any positive δ, assuming the Exponential Time Hypothesis. Also implied is a 2O(K1\2-δ). nO(1) parameterized lower bound. Behind these results is a new reduction from vertex cover, which might be of its own interest: All previous reductions for similar problems are from some kind of graph layout problems.

For a graph $H$, the $H$-free Edge Deletion problem asks whether there exist at most $k$ edges whose deletion from the input graph $G$ results in a graph without any induced copy of $H$. $H$-free Edge Completion and $H$-free Edge Editing are defined similarly where only completion (addition) of edges are allowed in the former and both completion and deletion are allowed in the latter. We completely settle the classical complexities of these problems by proving that $H$-free Edge Deletion is NP-complete if and only if $H$ is a graph with at least two edges, $H$-free Edge Completion is NP-complete if and only if $H$ is a graph with at least two nonedges, and $H$-free Edge Editing is NP-complete if and only if $H$ is a graph with at least three vertices. Our result on $H$-free Edge Editing resolves a conjecture by Alon and Stav [Theoret. Comput. Sci., 2009, pp. 4920--4927]. Additionally, we prove that these NP-complete problems cannot be solved in parameterized subexponential time, i.e., in time $2^{o(k)}\cdot |G|^{O(1)}$, unless the exponential time hypothesis fails. Furthermore, we obtain implications on the incompressibility and the inapproximability of these problems.

A diamond is a graph obtained by removing an edge from a complete graph on four vertices. A graph is diamond-free if it does not contain an induced diamond. The Diamond-free Edge Deletion problem asks to find whether there exist at most k edges in the input graph whose deletion results in a diamond-free graph. The problem was proved to be NP-complete and a polynomial kernel of O(k^4) vertices was found by Fellows et. al. (Discrete Optimization, 2011). In this paper, we give an improved kernel of O(k^3) vertices for Diamond-free Edge Deletion. We give an alternative proof of the NP-completeness of the problem and observe that it cannot be solved in time 2^{o(k)} * n^{O(1)}, unless the Exponential Time Hypothesis fails.