BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

R. B. Sandeep

R. B. Sandeep appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsComputational Complexitymath.CO

Catalog footprint

What is connected

8works
3topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

8 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
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).

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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}.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access