-
Chapter and Conference Paper
Paths to Trees and Cacti
For a family of graphs \(\mathcal F\) , the
-
Chapter and Conference Paper
Hitting and Covering Partially
d-Hitting Set and d-Set Cover are among the classical NP-hard problems. In this paper, we study variants of d-Hitting Set and d-Set Cover, which are called Partial d -Hitting Set (Partial
-
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
On the Complexity of Singly Connected Vertex Deletion
A digraph D is singly connected if for all ordered pairs of vertices \(u,v\in V(D)\) , there is at most one path in D
-
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...
-
Chapter and Conference Paper
Odd Cycle Transversal in Mixed Graphs
An odd cycle transversal (oct, for short) in a graph is a set of vertices whose deletion will leave a graph without any odd cycles. The Odd Cycle Transversal (OCT) problem takes an undirected graph G and a non-ne...
-
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...
-
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
On the Parameterized Complexity of Minus Domination
Dominating Set is a well-studied combinatorial problem. Given a graph \(G=(V,E)\) G ...