Source author record

Somnath Sikdar

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 Discrete Mathematics Computational Complexity Logic in Computer Science math.CO physics.soc-ph Social and Information Networks

Catalog footprint

Research overview

10works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Fast Biclustering by Dual Parameterization

We study two clustering problems, Starforest Editing, the problem of adding and deleting edges to obtain a disjoint union of stars, and the generalization Bicluster Editing. We show that, in addition to being NP-hard, none of the problems can be solved in subexponential time unless the exponential time hypothesis fails. Misra, Panolan, and Saurabh (MFCS 2013) argue that introducing a bound on the number of connected components in the solution should not make the problem easier: In particular, they argue that the subexponential time algorithm for editing to a fixed number of clusters (p-Cluster Editing) by Fomin et al. (J. Comput. Syst. Sci., 80(7) 2014) is an exception rather than the rule. Here, p is a secondary parameter, bounding the number of components in the solution. However, upon bounding the number of stars or bicliques in the solution, we obtain algorithms which run in time $2^{5 \sqrt{pk}} + O(n+m)$ for p-Starforest Editing and $2^{O(p \sqrt{k} \log(pk))} + O(n+m)$ for p-Bicluster Editing. We obtain a similar result for the more general case of t-Partite p-Cluster Editing. This is subexponential in k for fixed number of clusters, since p is then considered a constant. Our results even out the number of multivariate subexponential time algorithms and give reasons to believe that this area warrants further study.

preprint2015arXiv

Kernelization and Sparseness: the case of Dominating Set

We prove that for every positive integer $r$ and for every graph class $\mathcal G$ of bounded expansion, the $r$ -Dominating Set problem admits a linear kernel on graphs from $\mathcal G$ . Moreover, when $\mathcal G$ is only assumed to be nowhere dense, then we give an almost linear kernel on $\mathcal G$ for the classic Dominating Set problem, i.e., for the case $r=1$ . These results generalize a line of previous research on finding linear kernels for Dominating Set and $r$ -Dominating Set. However, the approach taken in this work, which is based on the theory of sparse graphs, is radically different and conceptually much simpler than the previous approaches. We complement our findings by showing that for the closely related Connected Dominating Set problem, the existence of such kernelization algorithms is unlikely, even though the problem is known to admit a linear kernel on $H$ -topological-minor-free graphs. Also, we prove that for any somewhere dense class $\mathcal G$ , there is some $r$ for which $r$ -Dominating Set is W[ $2$ ]-hard on $\mathcal G$ . Thus, our results fall short of proving a sharp dichotomy for the parameterized complexity of $r$ -Dominating Set on subgraph-monotone graph classes: we conjecture that the border of tractability lies exactly between nowhere dense and somewhere dense graph classes.

preprint2015arXiv

Kernelization Using Structural Parameters on Sparse Graph Classes

Meta-theorems for polynomial (linear) kernels have been the subject of intensive research in parameterized complexity. Heretofore, meta-theorems for linear kernels exist on graphs of bounded genus, $H$ -minor-free graphs, and $H$ -topological-minor-free graphs. To the best of our knowledge, no meta-theorems for polynomial kernels are known for any larger sparse graph classes; e.g., for classes of bounded expansion or for nowhere dense ones. In this paper we prove such meta-theorems for the two latter cases. More specifically, we show that graph problems that have finite integer index (FII) have linear kernels on graphs of bounded expansion when parameterized by the size of a modulator to constant-treedepth graphs. For nowhere dense graph classes, our result yields almost-linear kernels. While our parameter may seem rather strong, we argue that a linear kernelization result on graphs of bounded expansion with a weaker parameter (than treedepth modulator) would fail to include some of the problems covered by our framework. Moreover, we only require the problems to have FII on graphs of constant treedepth. This allows us to prove linear kernels for problems such as Longest Path/Cycle, Exact $s,t$ -Path, Treewidth, and Pathwidth, which do not have FII on general graphs (and the first two not even on bounded treewidth graphs).

preprint2014arXiv

A Faster Parameterized Algorithm for Treedepth

The width measure \emph{treedepth}, also known as vertex ranking, centered coloring and elimination tree height, is a well-established notion which has recently seen a resurgence of interest. We present an algorithm which---given as input an $n$ -vertex graph, a tree decomposition of the graph of width $w$ , and an integer $t$ ---decides Treedepth, i.e. whether the treedepth of the graph is at most $t$ , in time $2^{O(wt)} \cdot n$ . If necessary, a witness structure for the treedepth can be constructed in the same running time. In conjunction with previous results we provide a simple algorithm and a fast algorithm which decide treedepth in time $2^{2^{O(t)}} \cdot n$ and $2^{O(t^2)} \cdot n$ , respectively, which do not require a tree decomposition as part of their input. The former answers an open question posed by Ossona de Mendez and Nesetril as to whether deciding Treedepth admits an algorithm with a linear running time (for every fixed $t$ ) that does not rely on Courcelle's Theorem or other heavy machinery. For chordal graphs we can prove a running time of $2^{O(t \log t)}\cdot n$ for the same algorithm.

preprint2014arXiv

Overlapping Communities in Social Networks

Complex networks can be typically broken down into groups or modules. Discovering this "community structure" is an important step in studying the large-scale structure of networks. Many algorithms have been proposed for community detection and benchmarks have been created to evaluate their performance. Typically algorithms for community detection either partition the graph (non-overlapping communities) or find node covers (overlapping communities). In this paper, we propose a particularly simple semi-supervised learning algorithm for finding out communities. In essence, given the community information of a small number of "seed nodes", the method uses random walks from the seed nodes to uncover the community information of the whole network. The algorithm runs in time $O(k \cdot m \cdot \log n)$ , where $m$ is the number of edges; $n$ the number of links; and $k$ the number of communities in the network. In sparse networks with $m = O(n)$ and a constant number of communities, this running time is almost linear in the size of the network. Another important feature of our algorithm is that it can be used for either non-overlapping or overlapping communities. We test our algorithm using the LFR benchmark created by Lancichinetti, Fortunato, and Radicchi specifically for the purpose of evaluating such algorithms. Our algorithm can compete with the best of algorithms for both non-overlapping and overlapping communities as found in the comprehensive study of Lancichinetti and Fortunato.

preprint2012arXiv

Linear kernels and single-exponential algorithms via protrusion decompositions

A \emph{ $t$ -treewidth-modulator} of a graph $G$ is a set $X \subseteq V(G)$ such that the treewidth of $G-X$ is at most some constant $t-1$ . In this paper, we present a novel algorithm to compute a decomposition scheme for graphs $G$ that come equipped with a $t$ -treewidth-modulator. This decomposition, called a \emph{protrusion decomposition}, is the cornerstone in obtaining the following two main results. We first show that any parameterized graph problem (with parameter $k$ ) that has \emph{finite integer index} and is \emph{treewidth-bounding} admits a linear kernel on $H$ -topological-minor-free graphs, where $H$ is some arbitrary but fixed graph. A parameterized graph problem is called treewidth-bounding if all positive instances have a $t$ -treewidth-modulator of size $O(k)$ , for some constant $t$ . This result partially extends previous meta-theorems on the existence of linear kernels on graphs of bounded genus [Bodlaender et al., FOCS 2009] and $H$ -minor-free graphs [Fomin et al., SODA 2010]. Our second application concerns the Planar- $\mathcal{F}$ -Deletion problem. Let $\mathcal{F}$ be a fixed finite family of graphs containing at least one planar graph. Given an $n$ -vertex graph $G$ and a non-negative integer $k$ , Planar- $\mathcal{F}$ -Deletion asks whether $G$ has a set $X\subseteq V(G)$ such that $|X|\leq k$ and $G-X$ is $H$ -minor-free for every $H\in \mathcal{F}$ . Very recently, an algorithm for Planar- $\mathcal{F}$ -Deletion with running time $2^{O(k)} n \log^2 n$ (such an algorithm is called \emph{single-exponential}) has been presented in [Fomin et al., FOCS 2012] under the condition that every graph in $\mathcal{F}$ is connected. Using our algorithm to construct protrusion decompositions as a building block, we get rid of this connectivity constraint and present an algorithm for the general Planar- $\mathcal{F}$ -Deletion problem running in time $2^{O(k)} n^2$ .

preprint2012arXiv

Linear Kernels on Graphs Excluding Topological Minors

We show that problems which have finite integer index and satisfy a requirement we call treewidth-bounding admit linear kernels on the class of $H$ -topological-minor free graphs, for an arbitrary fixed graph $H$ . This builds on earlier results by Fomin et al.\ on linear kernels for $H$ -minor-free graphs and by Bodlaender et al.\ on graphs of bounded genus. Our framework encompasses several problems, the prominent ones being Chordal Vertex Deletion, Feedback Vertex Set and Edge Dominating Set.

preprint2012arXiv

Lower Bounds on the Complexity of MSO1 Model-Checking

One of the most important algorithmic meta-theorems is a famous result by Courcelle, which states that any graph problem definable in monadic second-order logic with edge-set quantifications (i.e., MSO2 model-checking) is decidable in linear time on any class of graphs of bounded tree-width. Recently, Kreutzer and Tazari proved a corresponding complexity lower-bound - that MSO2 model-checking is not even in XP wrt. the formula size as parameter for graph classes that are subgraph-closed and whose tree-width is poly-logarithmically unbounded. Of course, this is not an unconditional result but holds modulo a certain complexity-theoretic assumption, namely, the Exponential Time Hypothesis (ETH). In this paper we present a closely related result. We show that even MSO1 model-checking with a fixed set of vertex labels, but without edge-set quantifications, is not in XP wrt. the formula size as parameter for graph classes which are subgraph-closed and whose tree-width is poly-logarithmically unbounded unless the non-uniform ETH fails. In comparison to Kreutzer and Tazari; $(1)$ we use a stronger prerequisite, namely non-uniform instead of uniform ETH, to avoid the effectiveness assumption and the construction of certain obstructions used in their proofs; and $(2)$ we assume a different set of problems to be efficiently decidable, namely MSO1-definable properties on vertex labeled graphs instead of MSO2-definable properties on unlabeled graphs. Our result has an interesting consequence in the realm of digraph width measures: Strengthening the recent result, we show that no subdigraph-monotone measure can be "algorithmically useful", unless it is within a poly-logarithmic factor of undirected tree-width.

preprint2011arXiv

Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory

We present an alternative proof of a theorem by Courcelle, Makowski and Rotics which states that problems expressible in MSO are solvable in linear time for graphs of bounded rankwidth. Our proof uses a game-theoretic approach and has the advantage of being self-contained, intuitive, and fairly easy to follow. In particular, our presentation does not assume any background in logic or automata theory. We believe that it is good to have alternative proofs of this important result. Moreover our approach can be generalized to prove other results of a similar flavor, for example, that of Courcelle's Theorem for treewidth.

preprint2010arXiv

Are there any good digraph width measures?

Several different measures for digraph width have appeared in the last few years. However, none of them shares all the "nice" properties of treewidth: First, being \emph{algorithmically useful} i.e. admitting polynomial-time algorithms for all $\MS1$-definable problems on digraphs of bounded width. And, second, having nice \emph{structural properties} i.e. being monotone under taking subdigraphs and some form of arc contractions. As for the former, (undirected) $\MS1$ seems to be the least common denominator of all reasonably expressive logical languages on digraphs that can speak about the edge/arc relation on the vertex set.The latter property is a necessary condition for a width measure to be characterizable by some version of the cops-and-robber game characterizing the ordinary treewidth. Our main result is that \emph{any reasonable} algorithmically useful and structurally nice digraph measure cannot be substantially different from the treewidth of the underlying undirected graph. Moreover, we introduce \emph{directed topological minors} and argue that they are the weakest useful notion of minors for digraphs.

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.

Somnath Sikdar

Research overview

Is this your work?

10 publications

Fast Biclustering by Dual Parameterization

Kernelization and Sparseness: the case of Dominating Set

Kernelization Using Structural Parameters on Sparse Graph Classes

A Faster Parameterized Algorithm for Treedepth

Overlapping Communities in Social Networks

Linear kernels and single-exponential algorithms via protrusion decompositions

Linear Kernels on Graphs Excluding Topological Minors

Lower Bounds on the Complexity of MSO1 Model-Checking

Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory

Are there any good digraph width measures?

See the researcher in context

Building this map preview