Source author record

Naveen Sivadasan

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 math.CO Discrete Mathematics Computation and Language Digital Libraries Information Retrieval Machine Learning physics.soc-ph Social and Information Networks

Catalog footprint

Research overview

11works

9topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Multi-label classification for biomedical literature: an overview of the BioCreative VII LitCovid Track for COVID-19 literature topic annotations

The COVID-19 pandemic has been severely impacting global society since December 2019. Massive research has been undertaken to understand the characteristics of the virus and design vaccines and drugs. The related findings have been reported in biomedical literature at a rate of about 10,000 articles on COVID-19 per month. Such rapid growth significantly challenges manual curation and interpretation. For instance, LitCovid is a literature database of COVID-19-related articles in PubMed, which has accumulated more than 200,000 articles with millions of accesses each month by users worldwide. One primary curation task is to assign up to eight topics (e.g., Diagnosis and Treatment) to the articles in LitCovid. Despite the continuing advances in biomedical text mining methods, few have been dedicated to topic annotations in COVID-19 literature. To close the gap, we organized the BioCreative LitCovid track to call for a community effort to tackle automated topic annotation for COVID-19 literature. The BioCreative LitCovid dataset, consisting of over 30,000 articles with manually reviewed topics, was created for training and testing. It is one of the largest multilabel classification datasets in biomedical scientific literature. 19 teams worldwide participated and made 80 submissions in total. Most teams used hybrid systems based on transformers. The highest performing submissions achieved 0.8875, 0.9181, and 0.9394 for macro F1-score, micro F1-score, and instance-based F1-score, respectively. The level of participation and results demonstrate a successful track and help close the gap between dataset curation and method development. The dataset is publicly available via https://ftp.ncbi.nlm.nih.gov/pub/lu/LitCovid/biocreative/ for benchmarking and further development.

preprint2016arXiv

Kmerlight: fast and accurate k-mer abundance estimation

k-mers (nucleotide strings of length k) form the basis of several algorithms in computational genomics. In particular, k-mer abundance information in sequence data is useful in read error correction, parameter estimation for genome assembly, digital normalization etc. We give a streaming algorithm Kmerlight for computing the k-mer abundance histogram from sequence data. Our algorithm is fast and uses very small memory footprint. We provide analytical bounds on the error guarantees of our algorithm. Kmerlight can efficiently process genome scale and metagenome scale data using standard desktop machines. Few applications of abundance histograms computed by Kmerlight are also shown. We use abundance histogram for de novo estimation of repetitiveness in the genome based on a simple probabilistic model that we propose. We also show estimation of k-mer error rate in the sampling using abundance histogram. Our algorithm can also be used for abundance estimation in a general streaming setting. The Kmerlight tool is written in C++ and is available for download and use from https://github.com/nsivad/kmerlight.

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.

preprint2015arXiv

Subgraph Similarity Search in Large Graphs

One of the major challenges in applications related to social networks, computational biology, collaboration networks etc., is to efficiently search for similar patterns in their underlying graphs. These graphs are typically noisy and contain thousands of vertices and millions of edges. In many cases, the graphs are unlabeled and the notion of similarity is also not well defined. We study the problem of searching an induced subgraph in a large target graph that is most similar to the given query graph. We assume that the query graph and target graph are undirected and unlabeled. We use graphlet kernels \cite{shervashidze2009efficient} to define graph similarity. Graphlet kernels are known to perform better than other kernels in different applications. Our algorithm maps topological neighborhood information of vertices in the query and target graphs to vectors. These local topological informations are then combined to find a target subgraph having highly similar global topology with the given query graph. We tested our algorithm on several real world networks such as facebook network, google plus network, youtube network, amazon network etc. Most of them contain thousands of vertices and million edges. Our algorithm is able to detect highly similar matches when queried in these networks. Our multi-threaded implementation takes about one second to find the match on a 32 core machine, excluding the time for one time preprocessing. Computationally expensive parts of our algorithm can be further scaled to standard parallel and distributed frameworks like map-reduce.

preprint2014arXiv

Approximating the Cubicity of Trees

Cubicity of a graph $G$ is the smallest dimension $d$ , for which $G$ is a unit disc graph in ${\mathbb{R}}^d$ , under the $l^\infty$ metric, i.e. $G$ can be represented as an intersection graph of $d$ -dimensional (axis-parallel) unit hypercubes. We call such an intersection representation a $d$ -dimensional cube representation of $G$ . Computing cubicity is known to be inapproximable in polynomial time, within an $O(n^{1-ε})$ factor for any $ε>0$ , unless NP=ZPP. In this paper, we present a randomized algorithm that runs in polynomial time and computes cube representations of trees, of dimension within a constant factor of the optimum. It is also shown that the cubicity of trees can be approximated within a constant factor in deterministic polynomial time, if the cube representation is not required to be computed. As far as we know, this is the first constant factor approximation algorithm for computing the cubicity of trees. It is not yet clear whether computing the cubicity of trees is NP-hard or not.

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.

preprint2012arXiv

Lower Bounds for Boxicity

An axis-parallel $b$ -dimensional box is a Cartesian product $R_1\times R_2\times...\times R_b$ where $R_i$ is a closed interval of the form $[a_i,b_i]$ on the real line. For a graph $G$ , its \emph{boxicity} box(G) is the minimum dimension $b$ , such that $G$ is representable as the intersection graph of boxes in $b$ -dimensional space. Although boxicity was introduced in 1969 and studied extensively, there are no significant results on lower bounds for boxicity. In this paper, we develop two general methods for deriving lower bounds. Applying these methods we give several results, some of which are listed below: (1) The boxicity of a graph on $n$ vertices with no universal vertices and minimum degree $δ$ is at least $n/2(n-δ-1)$ . (2) Consider the $\mathcal{G}(n,p)$ model of random graphs. Let $p \le 1- \frac{40 \log n}{n^2}$ . Then, for $G \in \mathcal{G}(n,p)$ , almost surely $box(G)=Ω(np(1-p))$ . On setting $p=1/2$ we immediately infer that almost all graphs have boxicity $Ω(n)$ . (3) Spectral lower bounds for the boxicity of $k$ -regular graphs. (4) The boxicity of random $k$ -regular graphs on $n$ vertices (where $k$ is fixed) is $Ω(k/\log k)$ . (5) There exists a positive constant $c$ such that almost all balanced bipartite graphs on $2n$ vertices with exactly $m$ edges have boxicity at least $c m/n$ , for $m\le c' n^2/3$ for any positive constant $c' < 1$ .

preprint2010arXiv

Boxicity of Line Graphs

Boxicity of a graph H, denoted by box(H), is the minimum integer k such that H is an intersection graph of axis-parallel k-dimensional boxes in R^k. In this paper, we show that for a line graph G of a multigraph, box(G) <= 2Δ(\lceil log_2(log_2(Δ)) \rceil + 3) + 1, where Δdenotes the maximum degree of G. Since Δ<= 2(χ- 1), for any line graph G with chromatic number χ, box(G) = O(χlog_2(log_2(χ))). For the d-dimensional hypercube H_d, we prove that box(H_d) >= (\lceil log_2(log_2(d)) \rceil + 1)/2. The question of finding a non-trivial lower bound for box(H_d) was left open by Chandran and Sivadasan in [L. Sunil Chandran and Naveen Sivadasan. The cubicity of Hypercube Graphs. Discrete Mathematics, 308(23):5795-5800, 2008]. The above results are consequences of bounds that we obtain for the boxicity of fully subdivided graphs (a graph which can be obtained by subdividing every edge of a graph exactly once).

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.

Naveen Sivadasan

Research overview

Is this your work?

11 publications

Multi-label classification for biomedical literature: an overview of the BioCreative VII LitCovid Track for COVID-19 literature topic annotations

Kmerlight: fast and accurate k-mer abundance estimation

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

Subgraph Similarity Search in Large Graphs

Approximating the Cubicity of Trees

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

The chromatic discrepancy of graphs

Lower Bounds for Boxicity

Boxicity of Line Graphs

See the researcher in context

Building this map preview

Naveen Sivadasan

Research overview

Is this your work?

11 publications

Multi-label classification for biomedical literature: an overview of the BioCreative VII LitCovid Track for COVID-19 literature topic annotations

Kmerlight: fast and accurate k-mer abundance estimation

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

Subgraph Similarity Search in Large Graphs

Approximating the Cubicity of Trees

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

The chromatic discrepancy of graphs

Lower Bounds for Boxicity

Boxicity of Line 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