Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Korhonen, Tuukka https://www.dagstuhl.de/lipics License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-141562
URL:

Lower Bounds on Dynamic Programming for Maximum Weight Independent Set

pdf-format:


Abstract

We prove lower bounds on pure dynamic programming algorithms for maximum weight independent set (MWIS). We model such algorithms as tropical circuits, i.e., circuits that compute with max and + operations. For a graph G, an MWIS-circuit of G is a tropical circuit whose inputs correspond to vertices of G and which computes the weight of a maximum weight independent set of G for any assignment of weights to the inputs. We show that if G has treewidth w and maximum degree d, then any MWIS-circuit of G has 2^{Ω(w/d)} gates and that if G is planar, or more generally H-minor-free for any fixed graph H, then any MWIS-circuit of G has 2^{Ω(w)} gates. An MWIS-formula is an MWIS-circuit where each gate has fan-out at most one. We show that if G has treedepth t and maximum degree d, then any MWIS-formula of G has 2^{Ω(t/d)} gates. It follows that treewidth characterizes optimal MWIS-circuits up to polynomials for all bounded degree graphs and H-minor-free graphs, and treedepth characterizes optimal MWIS-formulas up to polynomials for all bounded degree graphs.

BibTeX - Entry

@InProceedings{korhonen:LIPIcs.ICALP.2021.87,
  author =	{Korhonen, Tuukka},
  title =	{{Lower Bounds on Dynamic Programming for Maximum Weight Independent Set}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{87:1--87:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14156},
  URN =		{urn:nbn:de:0030-drops-141562},
  doi =		{10.4230/LIPIcs.ICALP.2021.87},
  annote =	{Keywords: Maximum weight independent set, Treewidth, Tropical circuits, Dynamic programming, Treedepth, Monotone circuit complexity}
}

Keywords: Maximum weight independent set, Treewidth, Tropical circuits, Dynamic programming, Treedepth, Monotone circuit complexity
Seminar: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Issue date: 2021
Date of publication: 02.07.2021


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI