-
Article
Improved FPT Algorithms for Deletion to Forest-Like Structures
The Feedback Vertex Set problem is undoubtedly one of the most well-studied problems in Parameterized Complexity. In this problem, given an undirected graph G and a non-negative integer k, the objective is to tes...
-
Article
Open AccessDiverse collections in matroids and graphs
We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems. The input to the Weighted Diverse Bases problem consists of a matroid ...
-
Chapter and Conference Paper
On MAX–SAT with Cardinality Constraint
We consider the weighted MAX–SAT problem with an additional constraint that at most k variables can be set to true. We call this problem k –WMAX–SAT. This problem admits a
-
Chapter and Conference Paper
Parameterized Algorithms for Minimum Sum Vertex Cover
Minimum sum vertex cover of an n-vertex graph G is a bijection \(\phi : V(G) \rightarrow [n]\) ...
-
Chapter and Conference Paper
Max-SAT with Cardinality Constraint Parameterized by the Number of Clauses
Max-SAT with cardinality constraint (CC-Max-SAT) is one of the classical NP-complete problems. In this problem, given a CNF-formula $$\varPhi ...
-
Article
On the optimality of pseudo-polynomial algorithms for integer programming
In the classic Integer Programming Feasibility (IPF) problem, the objective is to decide whether, for a given \(m \times n\) ...
-
Chapter and Conference Paper
Socially Fair Matching: Exact and Approximation Algorithms
Matching problems are some of the most well-studied problems in graph theory and combinatorial optimization, with a variety of theoretical as well as practical motivations. However, in many applications of opt...
-
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
Target Set Selection Parameterized by Vertex Cover and More
Diffusion is a natural phenomenon in many real-world networks. Spreading of ideas, rumors in an online social network; propagation of virus, malware in a computer network; spreading of diseases in a human cont...
-
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
Structural Parameterizations with Modulator Oblivion
It is known that problems like Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal are polynomial time solvable in the class of chordal graphs. We consider these problems in a graph that has at most k ver...
-
Article
On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets
In a reconfiguration version of a decision problem \(\mathcal {Q}\) Q the i...
-
Chapter and Conference Paper
Parameterized Complexity of Set-Restricted Disjoint Paths on Chordal Graphs
The Disjoint Paths problem takes as input a graph and pairs of terminals, and asks whether all the terminal pairs can be connected by paths that are vertex disjoint. It is known to be NP-complete even on interval...
-
Chapter and Conference Paper
Parameterized Complexity of List Coloring and Max Coloring
In the List Coloring problem, the input is a graph G and list of colors \(L:V(G)\rightarrow {\mathbb N}\) ...
-
Chapter and Conference Paper
Partial Vertex Cover on Graphs of Bounded Degeneracy
In the Partial Vertex Cover (PVC) problem, we are given an n-vertex graph G and a positive integer k, and the objective is to find a vertex subset S of size k maximizing the number of edges with at least one end-...
-
Chapter and Conference Paper
List Homomorphism: Beyond the Known Boundaries
Given two graphs G and H, and a list \(L(u)\subseteq V(H)\) L ( ...
-
Article
Simultaneous Feedback Edge Set: A Parameterized Perspective
Agrawal et al. (ACM Trans Comput Theory 10(4):18:1–18:25, 2018. https://doi.org/10.1145/3265027) studied a simultaneous variant of the classic Feedback Vertex Set ...
-
Chapter and Conference Paper
Gerrymandering on Graphs: Computational Complexity and Parameterized Algorithms
This paper studies gerrymandering on graphs from a computational viewpoint (introduced by Cohen-Zemach et al. [AAMAS 2018] and continued by Ito et al. [AAMAS 2019]). Our contributions are two-fold: conceptual and...
-
Article
Parameterized low-rank binary matrix approximation
Low-rank binary matrix approximation is a generic problem where one seeks a good approximation of a binary matrix by another binary matrix with some specific properties. A good approximation means that the dif...
-
Article
Parameterized Complexity of Geometric Covering Problems Having Conflicts
The input for the Geometric Coverage problem consists of a pair \(\varSigma =(P,\mathcal {R})\)Σ=(P,R), where P is a set of points in \({\mathbb {R}}^d\)Rd and \(\mathcal {R}\)R is a set of subsets of P defined b...
