Showing 2017Show all
3 papers · 1 filter
cs.DS2017
On the Parameterized Complexity of Contraction to Generalization of Trees
Akanksha Agrawal, Saket Saurabh, Prafullkumar Tale
For a family of graphs , the -Contraction problem takes as an input a graph and an integer , and the goal is to decide if there exists $S \subseteq E(G)…
cs.DS2017
Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra +2
Given a graph and a parameter , the Chordal Vertex Deletion (CVD) problem asks whether there exists a subset of size at most that hits all induced cycl…
cs.DS2017
Polylogarithmic Approximation Algorithms for Weighted--Deletion Problems
Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra +2
For a family of graphs , the canonical Weighted Vertex Deletion problem is defined as follows: given an -vertex undirected graph and a weight function $w: V…