Spotting Trees with Few Leaves
Talkat Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms · on Friday, 2015-11-06·
summary
Claims an algebraic algorithm that generalizes Björklund algebraic method to detect a k-vertex tree with exactly l leaves, running in time that beats the old 2^k bound and matches path algorithms when l is constant, notably 1.66^k for fixed l. Implements a randomized Monte Carlo, polynomial-space routine and uses colorings (classical, fractional, vector) to boost savings; gets a worst-case exponential-time bound of about 3.455^n randomized polynomial-space for the k-internal spanning tree problem.
AI-written summary · about
chapters (17)
- 0:00Start
- 0:37HAMILTONIAN CYCLE in undirected graphs
- 0:53HAMILTONIAN PATH in undirected graphs
- 1:43k-INTERNAL SPANNING TREE (k-IST)
- 3:47FPT and exponential-time algorithms
- 6:29from paths to trees
- 11:02Previous results: restricted graph classes
- 12:50Our results (2): colored graphs
- 14:18Fractional coloring
- 15:06fractionally-colored graphs
- 16:45Our results: updated bounded degree table
- 16:56Vector coloring
- 18:40Relaxation property and computational complexity
- 19:14r-vector-colorable graphs
- 20:37BHKK's k-Path algorithm as black box
- 22:25partitions in colored graphs
- 25:29Further work
related talks
20mA Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems
37m"Algorithms" is Not a Four-Letter Word
27mSuccinct Preferential Attachment Graphs
41mOn counting subgraphs and why counting seeds makes more sense (if one thinks about it clearly)
55mSiegel's Theorem, Edge Coloring, and a Holant Dichotomy
23mWorst-Case to Expander-Case Reductions
21mDocument retrieval in external memory
34mNew Tools for Peak Memory Scheduling