Source author record

R. B. Sandeep

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 math.CO

Catalog footprint

Research overview

8works

3topics

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).

preprint2016arXiv

Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds

Given an $n*n$ sparse symmetric matrix with $m$ nonzero entries, performing Gaussian elimination may turn some zeroes into nonzero values. To maintain the matrix sparse, we would like to minimize the number $k$ of these changes, hence called the minimum fill-in problem. Agrawal et al.~[FOCS'90] developed the first approximation algorithm, based on early heuristics by George [SIAM J Numer Anal 10] and by Lipton et al.~[SIAM J Numer Anal 16]. The objective function they used is $m+k$ , the number of nonzero elements after elimination. An approximation algorithm using $k$ as the objective function was presented by Natanzon et al.~[STOC'98]. These two versions are incomparable in terms of approximation. Parameterized algorithms for the problem was first studied by Kaplan et al.~[FOCS'94]. Fomin & Villanger [SODA'12] recently gave an algorithm running in time $2^{O(\sqrt{k} \log k)}+n^{O(1)}$ . Hardness results of this problem are surprisingly scarce, and the few known ones are either weak or have to use nonstandard complexity conjectures. The only inapproximability result by Wu et al.~[IJCAI'15] applies to only the objective function $m+k$ , and is grounded on the Small Set Expansion Conjecture. The only nontrivial parameterized lower bounds, by Bliznets et al.~[SODA'16], include a very weak one based on ETH, and a strong one based on hardness of subexponential-time approximation of the minimum bisection problem on regular graphs. For both versions of the problem, we exclude the existence of PTASs, assuming P $\ne$ NP, and the existence of $2^{O(n^{1-δ})}$ -time approximation schemes for any positive $δ$ , assuming ETH. It also implies a $2^{O(k^{1/2-δ})} n^{O(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.

preprint2015arXiv

A cubic vertex kernel for Diamond-free Edge Deletion and more

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 whether there exist at most $k$ edges in the input graph $G$ whose deletion results in a diamond-free graph. For this problem, 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. Further, we give an $O(k^2)$ vertex kernel for a related problem {Diamond,K_t}-free Edge Deletion, where $t\geq 4$ is any fixed integer. To complement our results, we prove that these problems are NP-complete even for $K_4$ -free graphs and can be solved neither in subexponential time (i.e., $2^{o(|G|)}$ ) nor in parameterized subexponential time (i.e., $2^{o(k)}\cdot |G|^{O(1)}$ ), unless Exponential Time Hypothesis fails. Our reduction implies the hardness and lower bound for a general class of problems, where these problems come as a special case.

preprint2015arXiv

Parameterized lower bound and NP-completeness of some $H$ -free Edge Deletion 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$ . We prove that $H$ -free Edge Deletion is NP-complete if $H$ is a graph with at least two edges and $H$ has a component with maximum number of vertices which is a tree or a regular graph. Furthermore, we obtain that these NP-complete problems cannot be solved in parameterized subexponential time, i.e., in time $2^{o(k)}\cdot |G|^{O(1)}$ , unless Exponential Time Hypothesis fails.

preprint2015arXiv

Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of $H$ -free Edge Modification 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 non-edges and $H$ -free Edge Editing is NP-complete if and only if $H$ is a graph with at least three vertices. 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 Exponential Time Hypothesis fails. Furthermore, we obtain implications on the incompressibility of these problems.

preprint2014arXiv

On Polynomial Kernelization of $\mathcal{H}$ -free Edge Deletion

For a set of graphs $\mathcal{H}$ , the \textsc{ $\mathcal{H}$ -free Edge Deletion} problem asks to find whether there exist at most $k$ edges in the input graph whose deletion results in a graph without any induced copy of $H\in\mathcal{H}$ . In \cite{cai1996fixed}, it is shown that the problem is fixed-parameter tractable if $\mathcal{H}$ is of finite cardinality. However, it is proved in \cite{cai2013incompressibility} that if $\mathcal{H}$ is a singleton set containing $H$ , for a large class of $H$ , there exists no polynomial kernel unless $coNP\subseteq NP/poly$ . In this paper, we present a polynomial kernel for this problem for any fixed finite set $\mathcal{H}$ of connected graphs and when the input graphs are of bounded degree. We note that there are \textsc{ $\mathcal{H}$ -free Edge Deletion} problems which remain NP-complete even for the bounded degree input graphs, for example \textsc{Triangle-free Edge Deletion}\cite{brugmann2009generating} and \textsc{Custer Edge Deletion( $P_3$ -free Edge Deletion)}\cite{komusiewicz2011alternative}. When $\mathcal{H}$ contains $K_{1,s}$ , we obtain a stronger result - a polynomial kernel for $K_t$ -free input graphs (for any fixed $t> 2$ ). We note that for $s>9$ , there is an incompressibility result for \textsc{ $K_{1,s}$ -free Edge Deletion} for general graphs \cite{cai2012polynomial}. Our result provides first polynomial kernels for \textsc{Claw-free Edge Deletion} and \textsc{Line Edge Deletion} for $K_t$ -free input graphs which are NP-complete even for $K_4$ -free graphs\cite{yannakakis1981edge} and were raised as open problems in \cite{cai2013incompressibility,open2013worker}.

preprint2014arXiv

The chromatic discrepancy of graphs

For a proper vertex coloring $c$ of a graph $G$ , let $φ_c(G)$ denote the maximum, over all induced subgraphs $H$ of $G$ , the difference between the chromatic number $χ(H)$ and the number of colors used by $c$ to color $H$ . We define the chromatic discrepancy of a graph $G$ , denoted by $φ(G)$ , to be the minimum $φ_c(G)$ , over all proper colorings $c$ of $G$ . If $H$ is restricted to only connected induced subgraphs, we denote the corresponding parameter by $\hatφ(G)$ . These parameters are aimed at studying graph colorings that use as few colors as possible in a graph and all its induced subgraphs. We study the parameters $φ(G)$ and $\hatφ(G)$ and obtain bounds on them. We obtain general bounds, as well as bounds for certain special classes of graphs including random graphs. We provide structural characterizations of graphs with $φ(G) = 0$ and graphs with $\hatφ(G) = 0$ . We also show that computing these parameters is NP-hard.

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.

R. B. Sandeep

Research overview

Is this your work?

8 publications

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

On subgraph complementation to H-free graphs

Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds

A cubic vertex kernel for Diamond-free Edge Deletion and more

Parameterized lower bound and NP-completeness of some $H$ -free Edge Deletion problems

Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of $H$ -free Edge Modification Problems

On Polynomial Kernelization of $\mathcal{H}$ -free Edge Deletion

The chromatic discrepancy of graphs

See the researcher in context

Building this map preview

R. B. Sandeep

Research overview

Is this your work?

8 publications

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

On subgraph complementation to H-free graphs

Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds

A cubic vertex kernel for Diamond-free Edge Deletion and more

Parameterized lower bound and NP-completeness of some HHH-free Edge Deletion problems

Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of HHH-free Edge Modification Problems

On Polynomial Kernelization of H\mathcal{H}H-free Edge Deletion

The chromatic discrepancy of graphs

See the researcher in context

Building this map preview

Parameterized lower bound and NP-completeness of some $H$ -free Edge Deletion problems

Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of $H$ -free Edge Modification Problems

On Polynomial Kernelization of $\mathcal{H}$ -free Edge Deletion