Source author record

Shuvam Kant Tripathi

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 Computational Complexity math.CO

Catalog footprint

Research overview

2works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Maximum Minimal Feedback Vertex Set: A Parameterized Perspective

In this paper we study a maximization version of the classical Feedback Vertex Set (FVS) problem, namely, the Max Min FVS problem, in the realm of parameterized complexity. In this problem, given an undirected graph $G$ , a positive integer $k$ , the question is to check whether $G$ has a minimal feedback vertex set of size at least $k$ . We obtain following results for Max Min FVS. 1) We first design a fixed parameter tractable (FPT) algorithm for Max Min FVS running in time $10^kn^{\mathcal{O}(1)}$ . 2) Next, we consider the problem parameterized by the vertex cover number of the input graph (denoted by $\mathsf{vc}(G)$ ), and design an algorithm with running time $2^{\mathcal{O}(\mathsf{vc}(G)\log \mathsf{vc}(G))}n^{\mathcal{O}(1)}$ . We complement this result by showing that the problem parameterized by $\mathsf{vc}(G)$ does not admit a polynomial compression unless coNP $\subseteq$ NP/poly. 3) Finally, we give an FPT-approximation scheme (fpt-AS) parameterized by $\mathsf{vc}(G)$ . That is, we design an algorithm that for every $ε>0$ , runs in time $2^{\mathcal{O}\left(\frac{\mathsf{vc}(G)}ε\right)} n^{\mathcal{O}(1)}$ and returns a minimal feedback vertex set of size at least $(1-ε){\sf opt}$ .

preprint2020arXiv

The Satisfactory Partition Problem

The Satisfactory Partition problem consists in deciding if the set of vertices of a given undirected graph can be partitioned into two nonempty parts such that each vertex has at least as many neighbours in its part as in the other part. This problem was introduced by Gerber and Kobler [European J. Oper. Res. 125 (2000) 283-291] and further studied by other authors, but its parameterized complexity remains open until now. It is known that the Satisfactory Partition problem, as well as a variant where the parts are required to be of the same cardinality, are NP-complete. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that (1) the problem is FPT when parameterized by the neighbourhood diversity of the input graph, (2) it can be solved in $O(n^{8 {\tt cw}})$ where ${\tt cw}$ is the clique-width,(3) a generalized version of the problem is W[1]-hard when parameterized by the treewidth.

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.