tw)*n time

Abstract: Knowing how small treewidth can be exploited algorithmically in NP-hard problems, we ask about speeding up classical polynomial-time algorithms to (quasi-)linear in the graph size, while keeping the dependency on treewidth polynomial. We provide a fundamental toolbox for this purpose: - an algorithm for computing approximate tree decompositions in O(poly(tw) n log n) time. - an O(tw^3 n) algorithm for basic linear algebra tasks like computing the determinant, rank of an nxn matrix, or solving a system of linear equations. - an O(tw^2 n log n) algorithm for max-vertex-flow and O(tw^4 n log^2 n) randomized algorithm for finding a maximum matching. Joint work with Fedor V. Fomin, Daniel Lokshtanov, Michał Pilipczuk, and Saket Saurabh.