4 citations · 13 across the 17 of their papers we have counts for
37 papers
Solving SAT via Treewidth Backdoors in Linear Time: Beyond Sparsity
Jan Dreier, Robert Ganian, Marlene Gründel +2
The Boolean Satisfiability (SAT) problem is a remarkably expressive computational problem, serving both as a cornerstone of complexity theory and as a unifying language for a wide…
Hitting Minors: Stronger Lower Bounds
Jongseo Lee, Roohani Sharma, Sebastian Wiederrecht
For a fixed finite collection of graphs , the -Minor-Free Deletion problem asks, given a graph and an integer , whether there is a set $S\subseteq…
Tractability of Hard Digraph Cut Problems on Eulerian Instances: Treewidth Reduction and Reducing CMSO to Unbreakable Eulerian Instances
Esther Galby, Roohani Sharma, Bart van der Steenhoven
Eulerian digraphs retain the directional structure of general digraphs while exhibiting a symmetry of cuts reminiscent of undirected graphs. We show that this symmetry extends beyo…
Multiway -Cut is fixed-parameter tractable
Tony Huynh, Eun Jung Kim, Sang-il Oum +2
A connectivity function on a finite set is a function that is submodular and symmetric, with . Given a connectivity function via…
Where Treewidth and Pathwidth Diverge: Towards a Uniform Kernel for Pathwidth- Deletion
Ahmed Ghazy, Jakob Greilhuber, Tim A. Hartmann +1
For a constant , Pathwidth- Deletion is the problem of deciding whether, for a given graph and integer , there is a set of size at most su…
Reducing CMSO to Unbreakable Graphs Cannot be Computable
Colin Geniet, Roohani Sharma
Lokshtanov, Ramanujan, Saurabh, and Zehavi [ICALP 2018] proved that for any CMSO formula , testing on arbitrary graphs can be reduced to testing it on -unbreakable gr…