Author name cluster

Ankit Abhinav

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

2 author rows

TCS Journal 2025 Journal Article

Towards transitive-free digraphs

Ankit Abhinav
Satyabrata Jana
Abhishek Sahu

In a digraph D, an arc e = ( x, y ) in D is considered transitive if there is a path from x to y in D − e. A digraph is transitive-free if it does not contain any transitive arc. In the Transitive-free Vertex Deletion (TVD) problem, the goal is to find at most k vertices S such that D − S has no transitive arcs. In our work, we study a more general version of the TVD problem, denoted by ℓ -Relaxed Transitive-free Vertex Deletion (ℓ -RTVD), where we look for at most k vertices S such that D − S has no more than ℓ transitive arcs. We explore ℓ -RTVD on various well-known graph classes of digraphs such as directed acyclic graphs (DAGs), planar DAGs, α-bounded digraphs, tournaments, and their multiple generalizations such as in-tournaments, out-tournaments, local tournaments, acyclic local tournaments, and obtain the following results. Although the problem admits polynomial-time algorithms in tournaments, α-bounded digraphs, and acyclic local tournaments for fixed values of ℓ, it remains NP -Hard even in planar DAGs with maximum degree 6. In the parameterized realm, for ℓ -RTVD on in-tournaments and out-tournaments, we obtain polynomial kernels parameterized by k + ℓ for bounded independence number. But the problem remains fixed-parameter intractable on DAGs when parameterized by k.

Details DOI

TCS Journal 2023 Journal Article

Parameterized algorithms for finding highly connected solution

Ankit Abhinav
Susobhan Bandopadhyay
Aritra Banik
Saket Saurabh

To introduce our question and the parameterization, consider the classical Vertex Cover problem. In this problem, the input is a graph G on n vertices and a positive integer ℓ, and the goal is to find a vertex subset S of size at most ℓ such that G − S is an independent set. Further, we want that G [ S ] is highly connected. That is, G [ S ] should be n − k edge-connected. Clearly, the problem is NP-complete, as substituting k = n − 1, we obtain the Connected Vertex Cover problem. A simple observation also shows that the problem admits an algorithm with running time n O ( k ). Since the problem is polynomial-time solvable for every fixed integer k, a natural parameter is the integer k. In all the problems we consider, the parameter is k, and the goal is to find a solution S of size at most ℓ, such that G [ S ] is n − k edge-connected and G − S satisfies a property. We show that this version of well-known problems such as Vertex Cover, Feedback Vertex Set, Odd Cycle Transversal and Multiway Cut admit an algorithm with running time f ( k ) ⋅ n O ( 1 ), that is, they are FPT with the parameter k. One of our main subroutines to obtain these algorithms is an FPT algorithm for n − k edge connected Steiner Subgraph, which could be of an independent interest. Finally, we also show that such an algorithm is not possible for Multicut.

Details DOI

MFCS Conference 2022 Conference Paper

Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets

Ankit Abhinav
Susobhan Bandopadhyay
Aritra Banik
Yasuaki Kobayashi
Shunsuke Nagano
Yota Otachi
Saket Saurabh 0001

For a connected graph G = (V, E) and s, t ∈ V, a non-separating s-t path is a path P between s and t such that the set of vertices of P does not separate G, that is, G - V(P) is connected. An s-t path P is non-disconnecting if G - E(P) is connected. The problems of finding shortest non-separating and non-disconnecting paths are both known to be NP-hard. In this paper, we consider the problems from the viewpoint of parameterized complexity. We show that the problem of finding a non-separating s-t path of length at most k is W[1]-hard parameterized by k, while the non-disconnecting counterpart is fixed-parameter tractable (FPT) parameterized by k. We also consider the shortest non-separating path problem on several classes of graphs and show that this problem is NP-hard even on bipartite graphs, split graphs, and planar graphs. As for positive results, the shortest non-separating path problem is FPT parameterized by k on planar graphs and on unit disk graphs (where no s, t is given). Further, we give a polynomial-time algorithm on chordal graphs if k is the distance of the shortest path between s and t.

Details