Parameterized extension complexity of independent set and related problems

DOI10.1016/j.dam.2017.04.042zbMath1395.05125arXiv1511.08841OpenAlexW2962710723MaRDI QIDQ2413967

Petr Hliněný, Hans Raj Tiwary, Jakub Gajarský

Publication date: 17 September 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

extension complexitybounded expansionindependent set polytopefixed-parameter polynomial extension

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Unnamed Item, Fixed cardinality stable sets, New limits of treewidth-based tractability in optimization

Cites Work

• Unnamed Item
• Fundamentals of parameterized complexity
• Sparsity. Graphs, structures, and algorithms
• On the extension complexity of combinatorial polytopes
• Disjunctive programming: Properties of the convex hull of feasible points
• Extended formulations for vertex cover
• Grad and classes with bounded expansion. I: Decompositions
• A note on the extension complexity of the knapsack polytope
• Exponential Lower Bounds for Polytopes in Combinatorial Optimization
• Linear time low tree-width partitions and algorithmic consequences
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• Approximation Limits of Linear Programs (Beyond Hierarchies)
• Reformulation and Decomposition of Integer Programs
• Deciding First-Order Properties of Nowhere Dense Graphs
• The Matching Polytope has Exponential Extension Complexity
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Extended formulations in combinatorial optimization