Source author record

N. Sadagopan

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO Data Structures and Algorithms Distributed, Parallel, and Cluster Computing Information Theory math.IT

Catalog footprint

Research overview

17works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

On the Complexity of Connected $(s,t)$ -Vertex Separator

We show that minimum connected $(s,t)$ -vertex separator ( $(s,t)$ -CVS) is $Ω(log^{2-ε}n)$ -hard for any $ε>0$ unless NP has quasi-polynomial Las-Vegas algorithms. i.e., for any $ε>0$ and for some $δ>0$ , $(s,t)$ -CVS is unlikely to have $δ.log^{2-ε}n$ -approximation algorithm. We show that $(s,t)$ -CVS is NP-complete on graphs with chordality at least 5 and present a polynomial-time algorithm for $(s,t)$ -CVS on bipartite chordality 4 graphs. We also present a $\lceil\frac{c}{2}\rceil$ -approximation algorithm for $(s,t)$ -CVS on graphs with chordality $c$ . Finally, from the parameterized setting, we show that $(s,t)$ -CVS parameterized above the $(s,t)$ -vertex connectivity is $W[2]$ -hard.

preprint2020arXiv

The Hamiltonian Cycle in $K_{1,r}$ -free Split Graphs -- A Dichotomy

In this paper, we investigate the well-studied Hamiltonian cycle problem (HCYCLE), and present an interesting dichotomy result on split graphs. T. Akiyama et al. (1980) have shown that HCYCLE is NP-complete in planar bipartite graphs with maximum degree $3$ . Using this reduction, we show that HCYCLE is NP-complete in split graphs. In particular, we show that the problem is NP-complete in $K_{1,5}$ -free split graphs. Further, we present polynomial-time algorithms for Hamiltonian cycle in $K_{1,3}$ -free and $K_{1,4}$ -free split graphs. We believe that the structural results presented in this paper can be used to show similar dichotomy result for Hamiltonian path problem (HPATH) and other variants of HCYCLE.

preprint2016arXiv

2-Trees: Structural Insights and the study of Hamiltonian Paths

For a connected graph, a path containing all vertices is known as \emph{Hamiltonian path}. For general graphs, there is no known necessary and sufficient condition for the existence of Hamiltonian paths and the complexity of finding a Hamiltonian path in general graphs is NP-Complete. We present a necessary and sufficient condition for the existence of Hamiltonian paths in 2-trees. Using our characterization, we also present a linear-time algorithm for the existence of Hamiltonian paths in 2-trees. Our characterization is based on a deep understanding of the structure of 2-trees and the combinatorics presented here may be used in other combinatorial problems restricted to 2-trees.

preprint2016arXiv

Complexity of Steiner Tree in Split Graphs - Dichotomy Results

Given a connected graph $G$ and a terminal set $R \subseteq V(G)$ , {\em Steiner tree} asks for a tree that includes all of $R$ with at most $r$ edges for some integer $r \geq 0$ . It is known from [ND12,Garey et. al \cite{steinernpc}] that Steiner tree is NP-complete in general graphs. {\em Split graph} is a graph which can be partitioned into a clique and an independent set. K. White et. al \cite{white} has established that Steiner tree in split graphs is NP-complete. In this paper, we present an interesting dichotomy: we show that Steiner tree on $K_{1,4}$ -free split graphs is polynomial-time solvable, whereas, Steiner tree on $K_{1,5}$ -free split graphs is NP-complete. We investigate $K_{1,4}$ -free and $K_{1,3}$ -free (also known as claw-free) split graphs from a structural perspective. Further, using our structural study, we present polynomial-time algorithms for Steiner tree in $K_{1,4}$ -free and $K_{1,3}$ -free split graphs. Although, polynomial-time solvability of $K_{1,3}$ -free split graphs is implied from $K_{1,4}$ -free split graphs, we wish to highlight our structural observations on $K_{1,3}$ -free split graphs which may be used in other combinatorial problems.

preprint2016arXiv

Listing All Spanning Trees in Halin Graphs - Sequential and Parallel view

For a connected labelled graph $G$ , a {\em spanning tree} $T$ is a connected and an acyclic subgraph that spans all vertices of $G$ . In this paper, we consider a classical combinatorial problem which is to list all spanning trees of $G$ . A Halin graph is a graph obtained from a tree with no degree two vertices and by joining all leaves with a cycle. We present a sequential and parallel algorithm to enumerate all spanning trees in Halin graphs. Our approach enumerates without repetitions and we make use of $O((2pd)^{p})$ processors for parallel algorithmics, where $d$ and $p$ are the depth, the number of leaves, respectively, of the Halin graph. We also prove that the number of spanning trees in Halin graphs is $O((2pd)^{p})$ .

preprint2016arXiv

On 2K2-free graphs - Structural and Combinatorial View

A connected graph is 2K2-free if it does not contain a pair of independent edges as an induced subgraph. In this paper, we present the structural characterization of minimal vertex separator and show that there are polynomial number of minimal vertex separators in 2K2-free graphs. Further, using the enumeration we show that finding minimum connected vertex separator in 2K2-free graphs is polynomial time solvable. We highlight that finding minimum connected vertex separator is NP-complete in Chordality 5 graphs, which is a super graph class of 2K2-free graphs. Other study includes, enumeration of all distinct maximal independent sets and testing 2K2-free graphs. Also, we present an polynomial time algorithm for feedback vertex set problem in the subclass of 2K2-free graphs.

preprint2016arXiv

R-connectivity Augmentation in Trees

A \emph{vertex separator} of a connected graph $G$ is a set of vertices removing which will result in two or more connected components and a \emph{minimum vertex separator} is a set which contains the minimum number of such vertices, i.e., the cardinality of this set is least among all possible vertex separator sets. The cardinality of the minimum vertex separator refers to the connectivity of the graph G. A connected graph is said to be $k-connected$ if removing exactly $k$ vertices, $k\geq 1$ , from the graph, will result in two or more connected components and on removing any $(k-1)$ vertices, the graph is still connected. A \emph{connectivity augmentation} set is a set of edges which when augmented to a $k$ -connected graph $G$ will increase the connectivity of $G$ by $r$ , $r \geq 1$ , making the graph $(k+r)$ - $connected$ and a \emph{minimum connectivity augmentation} set is such a set which contains a minimum number of edges required to increase the connectivity by $r$ . In this paper, we shall investigate a $r$ - $connectivity$ augmentation in trees, $r \geq 2$ . As part of lower bound study, we show that any minimum $r$ -connectivity augmentation set in trees requires at least $\lceil\frac{1}{2} \sum\limits_{i=1}^{r-1} (r-i) \times l_{i} \rceil$ edges, where $l_i$ is the number of vertices with degree $i$ . Further, we shall present an algorithm that will augment a minimum number of edges to make a tree $(k+r)$ -connected.

preprint2016arXiv

Spanning Trees in 2-trees

A spanning tree of a graph $G$ is a connected acyclic spanning subgraph of $G$ . We consider enumeration of spanning trees when $G$ is a $2$ -tree, meaning that $G$ is obtained from one edge by iteratively adding a vertex whose neighborhood consists of two adjacent vertices. We use this construction order both to inductively list the spanning trees without repetition and to give bounds on the number of them. We determine the $n$ -vertex $2$ -trees having the most and the fewest spanning trees. The $2$ -tree with the fewest is unique; it has $n-2$ vertices of degree $2$ and has $n2^{n-3}$ spanning trees. Those with the most are all those having exactly two vertices of degree $2$ , and their number of spanning trees is the Fibonacci number $F_{2n-2}$ .

preprint2016arXiv

Tri-connectivity Augmentation in Trees

For a connected graph, a {\em minimum vertex separator} is a minimum set of vertices whose removal creates at least two connected components. The vertex connectivity of the graph refers to the size of the minimum vertex separator and a graph is $k$ -vertex connected if its vertex connectivity is $k$ , $k\geq 1$ . Given a $k$ -vertex connected graph $G$ , the combinatorial problem {\em vertex connectivity augmentation} asks for a minimum number of edges whose augmentation to $G$ makes the resulting graph $(k+1)$ -vertex connected. In this paper, we initiate the study of $r$ -vertex connectivity augmentation whose objective is to find a $(k+r)$ -vertex connected graph by augmenting a minimum number of edges to a $k$ -vertex connected graph, $r \geq 1$ . We shall investigate this question for the special case when $G$ is a tree and $r=2$ . In particular, we present a polynomial-time algorithm to find a minimum set of edges whose augmentation to a tree makes it 3-vertex connected. Using lower bound arguments, we show that any tri-vertex connectivity augmentation of trees requires at least $\lceil \frac {2l_1+l_2}{2} \rceil$ edges, where $l_1$ and $l_2$ denote the number of degree one vertices and degree two vertices, respectively. Further, we establish that our algorithm indeed augments this number, thus yielding an optimum algorithm.

preprint2014arXiv

On Uni Chord Free Graphs

A graph is unichord free if it does not contain a cycle with exactly one chord as its subgraph. In [3], it is shown that a graph is unichord free if and only if every minimal vertex separator is a stable set. In this paper, we first show that such a graph can be recognized in polynomial time. Further, we show that the chromatic number of unichord free graphs is one of (2,3, ω(G)). We also present a polynomial-time algorithm to produce a coloring with ω(G) colors.

preprint2014arXiv

Some Combinatorial Problems on Halin Graphs

Let $T$ be a tree with no degree 2 vertices and $L(T)=\{l_1,\ldots,l_r\}, r \geq 2$ denote the set of leaves in $T$ . An Halin graph $G$ is a graph obtained from $T$ such that $V(G)=V(T)$ and $E(G)=E(T) \cup \{\{l_i,l_{i+1}\} ~|~ 1 \leq i \leq r-1\} \cup \{l_1,l_r\}$ . In this paper, we investigate combinatorial problems such as, testing whether a given graph is Halin or not, chromatic bounds, an algorithm to color Halin graphs with the minimum number of colors. Further, we present polynomial-time algorithms for testing and coloring problems.

preprint2014arXiv

Spanning Tree Enumeration in 2-trees: Sequential and Parallel Perspective

For a connected graph, a vertex separator is a set of vertices whose removal creates at least two components. A vertex separator $S$ is minimal if it contains no other separator as a strict subset and a minimum vertex separator is a minimal vertex separator of least cardinality. A {\em clique} is a set of mutually adjacent vertices. A 2-tree is a connected graph in which every maximal clique is of size three and every minimal vertex separator is of size two. A spanning tree of a graph $G$ is a connected and an acyclic subgraph of $G$ . In this paper, we focus our attention on two enumeration problems, both from sequential and parallel perspective. In particular, we consider listing all possible spanning trees of a 2-tree and listing all perfect elimination orderings of a chordal graph. As far as enumeration of spanning trees is concerned, our approach is incremental in nature and towards this end, we work with the construction order of the 2-tree, i.e. enumeration of $n$ -vertex trees are from $n-1$ vertex trees, $n \geq 4$ . Further, we also present a parallel algorithm for spanning tree enumeration using $O(2^n)$ processors. To our knowledge, this paper makes the first attempt in designing a parallel algorithm for this problem. We conclude this paper by presenting a sequential and parallel algorithm for enumerating all Perfect Elimination Orderings of a chordal graph.

preprint2013arXiv

Domain Specific Hierarchical Huffman Encoding

In this paper, we revisit the classical data compression problem for domain specific texts. It is well-known that classical Huffman algorithm is optimal with respect to prefix encoding and the compression is done at character level. Since many data transfer are domain specific, for example, downloading of lecture notes, web-blogs, etc., it is natural to think of data compression in larger dimensions (i.e. word level rather than character level). Our framework employs a two-level compression scheme in which the first level identifies frequent patterns in the text using classical frequent pattern algorithms. The identified patterns are replaced with special strings and to acheive a better compression ratio the length of a special string is ensured to be shorter than the length of the corresponding pattern. After this transformation, on the resultant text, we employ classical Huffman data compression algorithm. In short, in the first level compression is done at word level and in the second level it is at character level. Interestingly, this two level compression technique for domain specific text outperforms classical Huffman technique. To support our claim, we have presented both theoretical and simulation results for domain specific texts.

preprint2013arXiv

Parallel Search with Extended Fibonacci Primitive

Search pattern experienced by the processor to search an element in secondary storage devices follows a random sequence. Formally, it is a random walk and its modeling is crucial in studying performance metrics like memory access time. In this paper, we first model the random walk using extended Fibonacci series. Our simulation is done on a parallel computing model (PRAM) with EREW strategy. Three search primitives are proposed under parallel computing model and each primitive is thoroughly tested on an array of size $10^7$ with the size of random walk being $10^4$ . Our findings reveal that search primitive with pointer jumping is better than the other two primitives. Our key contribution lies in modeling random walk as an extended Fibonacci series generator and simulating the same with various search primitives.

preprint2013arXiv

Simpler Sequential and Parallel Biconnectivity Augmentation

For a connected graph, a vertex separator is a set of vertices whose removal creates at least two components and a minimum vertex separator is a vertex separator of least cardinality. The vertex connectivity refers to the size of a minimum vertex separator. For a connected graph $G$ with vertex connectivity $k (k \geq 1)$ , the connectivity augmentation refers to a set $S$ of edges whose augmentation to $G$ increases its vertex connectivity by one. A minimum connectivity augmentation of $G$ is the one in which $S$ is minimum. In this paper, we focus our attention on connectivity augmentation of trees. Towards this end, we present a new sequential algorithm for biconnectivity augmentation in trees by simplifying the algorithm reported in \cite{nsn}. The simplicity is achieved with the help of edge contraction tool. This tool helps us in getting a recursive subproblem preserving all connectivity information. Subsequently, we present a parallel algorithm to obtain a minimum connectivity augmentation set in trees. Our parallel algorithm essentially follows the overall structure of sequential algorithm. Our implementation is based on CREW PRAM model with $O(Δ)$ processors, where $Δ$ refers to the maximum degree of a tree. We also show that our parallel algorithm is optimal whose processor-time product is O(n) where $n$ is the number of vertices of a tree, which is an improvement over the parallel algorithm reported in \cite{hsu}.

preprint2012arXiv

A Dirac-type Characterization of k-chordal Graphs

Characterization of k-chordal graphs based on the existence of a "simplicial path" was shown in [Chv{á}tal et al. Note: Dirac-type characterizations of graphs without long chordless cycles. Discrete Mathematics, 256, 445-448, 2002]. We give a characterization of k-chordal graphs which is a generalization of the known characterization of chordal graphs due to [G. A. Dirac. On rigid circuit graphs. Abh. Math. Sem. Univ. Hamburg, 25, 71-76, 1961] that use notions of a "simplicial vertex" and a "simplicial ordering".

preprint2011arXiv

A Characterization of all Stable Minimal Separator Graphs

In this paper, our goal is to characterize two graph classes based on the properties of minimal vertex (edge) separators. We first present a structural characterization of graphs in which every minimal vertex separator is a stable set. We show that such graphs are precisely those in which the induced subgraph, namely, a cycle with exactly one chord is forbidden. We also show that deciding maximum such forbidden subgraph is NP-complete by establishing a polynomial time reduction from maximum induced cycle problem [1]. This result is of independent interest and can be used in other combinatorial problems. Secondly, we prove that a graph has the following property: every minimal edge separator induces a matching (that is no two edges share a vertex in common) if and only if it is a tree.

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.

N. Sadagopan

Research overview

Is this your work?

17 publications

On the Complexity of Connected $(s,t)$ -Vertex Separator

The Hamiltonian Cycle in $K_{1,r}$ -free Split Graphs -- A Dichotomy

2-Trees: Structural Insights and the study of Hamiltonian Paths

Complexity of Steiner Tree in Split Graphs - Dichotomy Results

Listing All Spanning Trees in Halin Graphs - Sequential and Parallel view

On 2K2-free graphs - Structural and Combinatorial View

R-connectivity Augmentation in Trees

Spanning Trees in 2-trees

Tri-connectivity Augmentation in Trees

On Uni Chord Free Graphs

Some Combinatorial Problems on Halin Graphs

Spanning Tree Enumeration in 2-trees: Sequential and Parallel Perspective

Domain Specific Hierarchical Huffman Encoding

Parallel Search with Extended Fibonacci Primitive

Simpler Sequential and Parallel Biconnectivity Augmentation

A Dirac-type Characterization of k-chordal Graphs

A Characterization of all Stable Minimal Separator Graphs

See the researcher in context

Building this map preview

N. Sadagopan

Research overview

Is this your work?

17 publications

On the Complexity of Connected (s,t)(s,t)(s,t)-Vertex Separator

The Hamiltonian Cycle in K1,rK_{1,r}K1,r​-free Split Graphs -- A Dichotomy

2-Trees: Structural Insights and the study of Hamiltonian Paths

Complexity of Steiner Tree in Split Graphs - Dichotomy Results

Listing All Spanning Trees in Halin Graphs - Sequential and Parallel view

On 2K2-free graphs - Structural and Combinatorial View

R-connectivity Augmentation in Trees

Spanning Trees in 2-trees

Tri-connectivity Augmentation in Trees

On Uni Chord Free Graphs

Some Combinatorial Problems on Halin Graphs

Spanning Tree Enumeration in 2-trees: Sequential and Parallel Perspective

Domain Specific Hierarchical Huffman Encoding

Parallel Search with Extended Fibonacci Primitive

Simpler Sequential and Parallel Biconnectivity Augmentation

A Dirac-type Characterization of k-chordal Graphs

A Characterization of all Stable Minimal Separator Graphs

See the researcher in context

Building this map preview

On the Complexity of Connected $(s,t)$ -Vertex Separator

The Hamiltonian Cycle in $K_{1,r}$ -free Split Graphs -- A Dichotomy