-
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 ...
-
Chapter and Conference Paper
Parameterized Algorithms for Eccentricity Shortest Path Problem
Given an undirected graph \( G=(V,E) \) G = (
-
Chapter and Conference Paper
Burn and Win
Given a graph G and an integer k, the Graph Burning problem asks whether the graph G can be burned in at most k rounds. Graph burning is a model for information spreading in a network, where we study how fast the...
-
Article
A Polynomial Kernel for Bipartite Permutation Vertex Deletion
In a permutation graph, vertices represent the elements of a permutation, and edges represent pairs of elements that are reversed by the permutation. In the Permutation Vertex Deletion problem, given an undirecte...
-
Article
Parameterized Complexity of Conflict-Free Matchings and Paths
An input to a conflict-free variant of a classical problem \(\Gamma \)Γ, called Conflict-Free\(\Gamma \)Γ, consists of an instance I of \(\Gamma \)Γ coupled with a graph H, called the conflict graph. A solution t...
-
Chapter and Conference Paper
Parameterized Complexity of Fair Feedback Vertex Set Problem
Given a graph \(G=(V,E)\), a subset \(S\subseteq V(G)\) is said to be a feedback vertex set of G if \(G-S\) is a forest. In the Feedback Vertex Set (FVS) problem, we are given an undirected graph G, and a positiv...