Skip to main navigation
Skip to Content
Computer Science
University of Toronto
U of T Portal
Student Support
Contact
About
History of U of T Computer Science
Computer Science at U of T Mississauga
Computer Science at U of T Scarborough
Employment Opportunities for Faculty/Lecturers
How to Find Us
Contact
Undergraduate
Prospective Undergraduates
Current Undergraduates
Graduate
Prospective Graduate Students
Current Graduate Students
Research
Research Areas
Partner with us
People
Faculty
Staff
In Memoriam
Alumni and Friends
Honours & Awards
Women in Computer Science
Graduate Student Society
Undergraduate Student Union
Undergraduate Artificial Intelligence Group
Undergraduate Theory Group
News & Events
News
Events
@DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> Theory Seminar - Nov 1
About
Undergraduate
Graduate
Research
People
News & Events
Theory Seminar - Nov 1
Event date: Friday, November 01, 2013, at 11:10 AM
Location: GB248
Speaker: Serge Gaspers, University of New South Wales and NICTA, Sydney, Australia
Title: Backdoors to Satisfaction
Abstract:
A backdoor set is a set of variables of a propositional formula such that fixing the truth values of the variables in the backdoor set moves the formula into some class where the Satisfiability problem is polynomial-time decidable. If we know a small backdoor set we can reduce the question of whether the given formula is satisfiable to the same question for one or several easy formulas that belong to the tractable class under consideration. In this talk I will review parameterized complexity results for problems that arise in the context of backdoor sets, such as the problem of finding a backdoor set of size at most k, parameterized by k. I will also present an outline of a recent FPT-approximation algorithm finding a backdoor to the class of formulas with bounded incidence treewidth.
The talk is based on joint work with Stefan Szeider (Vienna University of Technology), which appeared at ICALP 2012, SAT 2012, FOCS 2013, and a survey in Mike Fellows' Festschrift 2012.