19 citations · 35 across the 7 of their papers we have counts for
3 papers · 1 filter
Backdoors to Tractable Valued CSP
Robert Ganian, M. S. Ramanujan, Stefan Szeider
We extend the notion of a strong backdoor from the CSP setting to the Valued CSP setting (VCSP, for short). This provides a means for augmenting a class of tractable VCSP instances…
Combining Treewidth and Backdoors for CSP
Robert Ganian, M. S. Ramanujan, Stefan Szeider
We show that CSP is fixed-parameter tractable when parameterized by the treewidth of a backdoor into any tractable CSP problem over a finite constraint language. This result combin…
A Linear Time Parameterized Algorithm for Directed Feedback Vertex Set
Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh
In the Directed Feedback Vertex Set (DFVS) problem, the input is a directed graph on vertices and edges, and an integer . The objective is to determine whether there…