Source author record

Rian Neogi

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

ResearcherUnclaimed source record

Catalog footprint

What is connected

2works
2topics
4close collaborators

Actions

Connect this record

Log in to claim

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

2 published item(s)

preprint2020arXiv

On the Parameterized Complexity of Deletion to $\mathcal{H}$-free Strong Components

{\sc Directed Feedback Vertex Set (DFVS)} is a fundamental computational problem that has received extensive attention in parameterized complexity. In this paper, we initiate the study of a wide generalization, the {\sc ${\cal H}$-free SCC Deletion} problem. Here, one is given a digraph $D$, an integer $k$ and the objective is to decide whether there is a vertex set of size at most $k$ whose deletion leaves a digraph where every strong component excludes graphs in the fixed finite family ${\cal H}$ as (not necessarily induced) subgraphs. When ${\cal H}$ comprises only the digraph with a single arc, then this problem is precisely DFVS. Our main result is a proof that this problem is fixed-parameter tractable parameterized by the size of the deletion set if ${\cal H}$ only contains rooted graphs or if ${\cal H}$ contains at least one directed path. Along with generalizing the fixed-parameter tractability result for DFVS, our result also generalizes the recent results of Göke et al. [CIAC 2019] for the {\sc 1-Out-Regular Vertex Deletion} and {\sc Bounded Size Strong Component Vertex Deletion} problems. Moreover, we design algorithms for the two above mentioned problems, whose running times are better and match with the best bounds for {\sc DFVS}, without using the heavy machinery of shadow removal as is done by Göke et al. [CIAC 2019].

preprint2020arXiv

Recognizing $k$-Clique Extendible Orderings

A graph is $k$-clique-extendible if there is an ordering of the vertices such that whenever two $k$-sized overlapping cliques $A$ and $B$ have $k-1$ common vertices, and these common vertices appear between the two vertices $a,b\in (A\setminus B)\cup (B\setminus A)$ in the ordering, there is an edge between $a$ and $b$, implying that $A\cup B$ is a $(k+1)$-sized clique. Such an ordering is said to be a $k$-C-E ordering. These graphs arise in applications related to modelling preference relations. Recently, it has been shown that a maximum sized clique in such a graph can be found in $n^{O(k)}$ time when the ordering is given. When $k$ is $2$, such graphs are precisely the well-known class of comparability graphs and when $k$ is $3$ they are called triangle-extendible graphs. It has been shown that triangle-extendible graphs appear as induced subgraphs of visibility graphs of simple polygons, and the complexity of recognizing them has been mentioned as an open problem in the literature. While comparability graphs (i.e. $2$-C-E graphs) can be recognized in polynomial time, we show that recognizing $k$-C-E graphs is NP-hard for any fixed $k \geq 3$ and co-NP-hard when $k$ is part of the input. While our NP-hardness reduction for $k \geq 4$ is from the betweenness problem, for $k=3$, our reduction is an intricate one from the $3$-colouring problem. We also show that the problems of determining whether a given ordering of the vertices of a graph is a $k$-C-E ordering, and that of finding an $\ell$-sized (or maximum sized) clique in a $k$-C-E graph, given a $k$-C-E ordering, are complete for the parameterized complexity classes co-W[1] and W[1] respectively, when parameterized by $k$. However we show that the former is fixed-parameter tractable when parameterized by the treewidth of the graph.