-
Chapter and Conference Paper
Parameterized Approximation Algorithms for Weighted Vertex Cover
A vertex cover of a graph is a set of vertices of the graph such that every edge has at least one endpoint in it. In this work, we study Weighted Vertex Cover with solution size as a parameter. Formally, in the ...
-
Article
Open AccessSub-exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number
Fradkin and Seymour (J Comb Theory Ser B 110:19–46, 2015) defined the class of digraphs of bounded independence number as a generalization of the class of tournaments. They argued that the class of digraphs of...
-
Chapter and Conference Paper
An ETH-Tight Algorithm for Bidirected Steiner Connectivity
In the Strongly Connected Steiner Subgraph problem, we are given an n-vertex digraph D, a weight function \(w:A(D)\mapsto {\mathbb {R}}^+\) ...
-
Article
Fast Exact Algorithms for Survivable Network Design with Uniform Requirements
We design exact algorithms for the following two problems in survivable network design: (i) designing a minimum cost network with a desired value of edge connectivity, which is called Minimum Weight ...
-
Article
Open AccessParameterized Complexity of Directed Spanner Problems
We initiate the parameterized complexity study of minimum t-spanner problems on directed graphs. For a positive integer t, a multiplicative t-spanner of a (directed) graph G is a spanning subgraph H such that the...
-
Article
Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized
Let π be a family of graphs. In the classical π-Vertex Deletion problem, given a graph G and a positive integer k, the objective is to check whether there exists a subset S of at most k vertices such that G − S i...
-
Chapter and Conference Paper
An Erdős–Pósa Theorem on Neighborhoods and Domination Number
The neighborhood packing number of a graph is the maximum number of...
-
Chapter and Conference Paper
An FPT Algorithm for Contraction to Cactus
For a collection \(\mathcal {F}\) of graphs, given a graph G and an integer k, the
-
Chapter and Conference Paper
Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized
Let \(\mathrm{\Pi }\) be a family of graphs. In the classical
-
Chapter and Conference Paper
Linear Representation of Transversal Matroids and Gammoids Parameterized by Rank
Given a bipartite graph \(G=(U\uplus V,E)\) , a linear representation of the transversal matroid associated ...
-
Chapter and Conference Paper
Fast Exact Algorithms for Survivable Network Design with Uniform Requirements
We design exact algorithms for the following two problems in survivable network design: (i) designing a minimum cost network with a desired value of edge connectivity, which is called Minimum Weight ...
-
Article
Faster Parameterized Algorithms for Deletion to Split Graphs
An undirected graph is said to be split if its vertex set can be partitioned into two sets such that the subgraph induced on one of them is a complete graph and the subgraph induced on the other is an independent...
-
Chapter and Conference Paper
Reducing Rank of the Adjacency Matrix by Graph Modification
The main topic of this article is to study a class of graph modification problems. A typical graph modification problem takes as input a graph G, a positive integer k and the objective is to add/delete k vertices...
-
Chapter and Conference Paper
Deterministic Truncation of Linear Matroids
Let \(M=(E,\mathcal{I})\) M = ...
-
Chapter and Conference Paper
Parameterized Approximations via d-Skew-Symmetric Multicut
In this paper we design polynomial time approximation algorithms for several parameterized problems such as Odd Cycle Transversal, Almost 2-SAT, Above Guarantee Vertex Cover and Deletion q-Horn Backdoor Set Detec...
-
Chapter and Conference Paper
Parameterized Algorithms to Preserve Connectivity
We study the following family of connectivity problems. For a given λ-edge connected (multi) graph G = (V,E), a set of links L such that G + L = (V, E ∪ L) is (λ + 1)-edge connected, and a positive integer k, the...
-
Article
A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments
In the k-Feedback Arc/Vertex Set problem we are given a directed graph D and a positive integer k and the objective is to check whether it is possible to delete at most k arcs/vertices from D to make it acyclic. ...
-
Chapter and Conference Paper
Faster Exact Algorithms for Some Terminal Set Problems
Many problems on graphs can be expressed in the following language: given a graph G = (V,E) and a terminal set T ⊆ V, find a minimum size set S ⊆ V which intersects all “structures” (such as cycles or paths) pass...
-
Chapter and Conference Paper
Parameterized Algorithms for Even Cycle Transversal
We consider a decision version of the problem of finding the minimum number of vertices whose deletion results in a graph without even cycles. While this problem is a natural analogue of the Odd Cycle Transversal
-
Chapter and Conference Paper
Faster Parameterized Algorithms for Deletion to Split Graphs
An undirected graph is said to be split if its vertex set can be partitioned into two sets such that the subgraph induced on one of them is a complete graph and the subgraph induced on the other is an independent...
