On space efficiency of algorithms working on structural decompositions of graphs

Speaker(s)

Marcin Wrochna

Affiliation

Uniwersytet Warszawski

Date

Jan. 13, 2016, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

Motivated by failed attempts at making dynamic algorithms on tree-width use less space (without using more time), we look at this from a complexity-theoretic point of view. I will mention relations to Savitch's theorem and then show how the problem of solving, say, 3-Coloring on graphs of treewidth, pathwidth, tree-depth at most s(n) is complete for classes of nondet. poly-time Turing machines with different stack access to ~s(n) memory. This gives a nice hierarchy with some corollaries.

---