You are not logged in |
Solving problems parameterized by tree-width in single exponential time: a logical approach
- Speaker(s)
- Michał Pilipczuk
- Affiliation
- Uniwersytet Warszawski
- Date
- April 6, 2011, 2:15 p.m.
- Room
- room 5870
- Seminar
- Seminar Automata Theory
We introduce a variant of modal logic on graphs, dubbed EXISTENTIAL COUNTING
MODAL LOGIC (ECML), which captures a vast majority of problems known
to be tractable in single exponential time when parameterized by treewidth. It
appears that all these results can be subsumed by the theorem that model checking
of ECML admits an algorithm with such complexity. We extend ECML by
adding a certain type of connectivity requirements and, basing on the Cut&Count
technique, prove that the problems expressible in the extension are also tractable in single exponential time when parameterized by treewidth; however, using randomization. The need for navigationality of the introduced logic is justified by a negative result that an expository problem involving a non-acyclic condition, C_l-VERTEX DELETION for l>=5, does not admit such a robust algorithm unless Exponential Time Hypothesis fails.
MODAL LOGIC (ECML), which captures a vast majority of problems known
to be tractable in single exponential time when parameterized by treewidth. It
appears that all these results can be subsumed by the theorem that model checking
of ECML admits an algorithm with such complexity. We extend ECML by
adding a certain type of connectivity requirements and, basing on the Cut&Count
technique, prove that the problems expressible in the extension are also tractable in single exponential time when parameterized by treewidth; however, using randomization. The need for navigationality of the introduced logic is justified by a negative result that an expository problem involving a non-acyclic condition, C_l-VERTEX DELETION for l>=5, does not admit such a robust algorithm unless Exponential Time Hypothesis fails.
