Paper Info
Title
Lower Bounds on Dynamic Programming for Maximum Weight Independent Set
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^{\Omega(w/d)}$ gates and that if $G$ is planar then any MWIS-circuit of $G$ has $2^{\Omega(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^{\Omega(t/d)}$ gates. It follows that treewidth characterizes optimal MWIS-circuits up to polynomials for all bounded degree graphs and planar graphs, and treedepth characterizes optimal MWIS-formulas up to polynomials for all bounded degree graphs.
Year
DOI
Venue
2021
10.4230/LIPIcs.ICALP.2021.87
ICALP
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
0
1
Name
Order
Citations
PageRank
Tuukka Korhonen103.38