4 citations · 13 across the 17 of their papers we have counts for
8 papers · 1 filter
Open Problems in (Hyper)Graph Decomposition
Deepak Ajwani, Rob H. Bisseling, Katrin Casel +26
Large networks are useful in a wide range of applications. Sometimes problem instances are composed of billions of entities. Decomposing and analyzing these structures helps us gai…
Approximate Monotone Local Search for Weighted Problems
Baris Can Esmer, Ariel Kulik, Daniel Marx +2
In a recent work, Esmer et al. describe a simple method - Approximate Monotone Local Search - to obtain exponential approximation algorithms from existing parameterized exact algor…
Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
R. Krithika, V. K. Kutty Malu, Roohani Sharma +1
In this work, we initiate the complexity study of Biclique Contraction and Balanced Biclique Contraction. In these problems, given as input a graph G and an integer k, the objectiv…
Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
Florent Foucaud, Esther Galby, Liana Khazaliya +4
Treewidth (tw) is an important parameter that, when bounded, yields tractability for many problems. For example, graph problems expressible in Monadic Second Order (MSO) logic and…
Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations
Barış Can Esmer, Ariel Kulik, Dániel Marx +2
The goal of this paper is to understand how exponential-time approximation algorithms can be obtained from existing polynomial-time approximation algorithms, existing parameterized…
Parameterized Complexity Classification for Interval Constraints
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak +3
Constraint satisfaction problems form a nicely behaved class of problems that lends itself to complexity classification results. From the point of view of parameterized complexity,…