Extension Complexity, MSO Logic, and Treewidth

DOI10.4230/LIPIcs.SWAT.2016.18zbMath1378.68178arXiv1507.04907OpenAlexW2963680946MaRDI QIDQ5369520

Petr Kolman, Martin Koutecký, Hans Raj Tiwary

Publication date: 17 October 2017

Full work available at URL: https://arxiv.org/abs/1507.04907

zbMATH Keywords

MSO logicextension complexityFPTCourcelle's theorem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Logic in computer science (03B70)

Related Items (6)

Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond ⋮ Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity ⋮ Smaller extended formulations for the spanning tree polytope of bounded-genus graphs ⋮ Extended formulations for vertex cover ⋮ Strong reductions for extended formulations ⋮ New limits of treewidth-based tractability in optimization

This page was built for publication: Extension Complexity, MSO Logic, and Treewidth