Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Wednesday, August 05, 2015, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Dominik Scheder (Shanghai Jiaotong University)
Let G=(V,E) be a directed graph (digraph). A decycling set is a set of vertices X such that G-X has no directed cycles. In this talk we consider digraphs in which every vertex has two incoming and two outgoing edges. We call those graphs (2,2)-regular graphs.
It is easy to show that every (2,2)-regular digraph has a decycling set of size at most 2/3 |V|, and this is tight. Things become much more exciting if we consider (2,2)-regular digraphs of *large girth*.
For those one can show that a decycling set of roughly size 0.38 |V| exists. This follows from the analysis of the PPSZ k-SAT algorithm. We improve the bound significantly to (1-ln(2))|V| ~ 0.31 |V|.
The motivation for this work comes from the hope that better upper bounds on decycling sets translate into an improved analysis of the PPSZ k-SAT algorithm, which is currently the fastest algorithm for the important NP-complete problem k-SAT.
Automatic MiSe System Software Version 1.4803M | admin login