Solving problems parameterized by tree-width in single exponential time: a logical approach

Prelegent(ci)

Michał Pilipczuk

Afiliacja

Uniwersytet Warszawski

Termin

6 kwietnia 2011 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

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.

---