Lower bounds on dynamic programming for maximum weight independent set

DOI10.4230/LIPICS.ICALP.2021.87MaRDI QIDQ7241186zbMATH OpenFDO

Authors Tuukka Korhonen

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2021.87

zbMATH Keywords

dynamic programmingmaximum weight independent setmonotone circuit complexitytreedepthtreewidthtropical circuits

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A Dichotomy Theorem for Polynomial Evaluation
• A fast algorithm for the maximum clique problem
• Boolean-width of graphs
• Connecting knowledge compilation classes and width parameters
• Determining the Stability Number of a Graph
• Explicit constructions of linear-sized superconcentrators
• Exponential Time Complexity of Weighted Counting of Independent Sets
• Graph minors. II. Algorithmic aspects of tree-width
• scientific article; zbMATH DE number 7204408 (Why is no real title available?)
• scientific article; zbMATH DE number 7651188 (Why is no real title available?)
• Improved bounds for the excluded-minor approximation of treedepth
• Independent set in P₅-free graphs in polynomial time
• Independent set on P_k-free graphs in quasi-polynomial time
• Large Induced Subgraphs via Triangulations and CMSO
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Linearity of grid minors in treewidth with applications through bidimensionality
• Lopsided Lovász Local lemma and Latin transversals
• Lower bounds for tropical circuits and dynamic programs
• Negation can be exponentially powerful
• On cliques in graphs
• On Interpolation and Automatization for Frege Systems
• On nowhere dense graphs
• On space efficiency of algorithms working on structural decompositions of graphs
• On the \(\mathrm{AC}^0\) complexity of subgraph isomorphism
• On the Complexity of the Interlace Polynomial
• On the maximum weight independent set problem in graphs without induced cycles of length at least five
• On the Parallel Evaluation of Multivariate Polynomials
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• Sur le problème des courbes gauches en topologie.
• Tensor network complexity of multilinear maps
• The Bidimensional Theory of Bounded-Genus Graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Tropical complexity, Sidon sets, and dynamic programming
• Width, depth, and space: tradeoffs between branching and dynamic programming

Cited in

(1)

• Courcelle's theorem for Lipschitz continuity

This page was built for publication: Lower bounds on dynamic programming for maximum weight independent set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7241186)