4 papers · 1 filter
Beyond Max-Cut: λ-Extendible Properties Parameterized Above the Poljak-Turzík Bound
Matthias Mnich, Geevarghese Philip, Saket Saurabh +1
Poljak and Turzík (Discrete Math. 1986) introduced the notion of λ-extendible properties of graphs as a generalization of the property of being bipartite. They showed that for any…
Hitting forbidden minors: Approximation and Kernelization
Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra +2
We study a general class of problems called F-deletion problems. In an F-deletion problem, we are asked whether a subset of at most vertices can be deleted from a graph suc…
FPT Algorithms for Connected Feedback Vertex Set
Neeldhara Misra, Geevarghese Philip, Venkatesh Raman +2
We study the recently introduced Connected Feedback Vertex Set (CFVS) problem from the view-point of parameterized algorithms. CFVS is the connected variant of the classical Feedba…
Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
Geevarghese Philip, Venkatesh Raman, Somnath Sikdar
We show that the k-Dominating Set problem is fixed parameter tractable (FPT) and has a polynomial kernel for any class of graphs that exclude K_{i,j} as a subgraph, for any fixed i…