Showing 2022Show all
2 papers · 1 filter
cs.DS2022
A Dynamic MaxSAT-based Approach to Directed Feedback Vertex Sets
Rafael Kiesel, André Schidler
We propose a new approach to the Directed Feedback Vertex Set Problem (DFVSP), where the input is a directed graph and the solution is a minimum set of vertices whose removal makes…
cs.DS2022
Weighted Model Counting with Twin-Width
Robert Ganian, Filip Pokrývka, André Schidler +2
Bonnet et al. (FOCS 2020) introduced the graph invariant twin-width and showed that many NP-hard problems are tractable for graphs of bounded twin-width, generalizing similar resul…