  If a sparse semidefinite program (SDP), specified over $n\times n$ matrices
and subject to $m$ linear constraints, has an aggregate sparsity graph $G$ with
small treewidth, then chordal conversion will sometimes allow an interior-point
method to solve the SDP in just $O(m+n)$ time per-iteration, which is a
significant speedup over the $\Omega(n^{3})$ time per-iteration for a direct
application of the interior-point method. Unfortunately, the speedup is not
guaranteed by an $O(1)$ treewidth in $G$ that is independent of $m$ and $n$, as
a diagonal SDP would have treewidth zero but can still necessitate up to
$\Omega(n^{3})$ time per-iteration. Instead, we construct an extended aggregate
sparsity graph $\bar{G}\supseteq G$ by forcing each constraint matrix $A_{i}$
to be its own clique in $G$. We prove that a small treewidth in $\bar{G}$ does
indeed guarantee that chordal conversion will solve the SDP in $O(m+n)$ time
per-iteration, to $\epsilon$-accuracy in at most
$O(\sqrt{m+n}\log(1/\epsilon))$ iterations. This sufficient condition covers
many successful applications of chordal conversion, including the MAX-$k$-CUT
relaxation, the Lov\'asz theta problem, sensor network localization, polynomial
optimization, and the AC optimal power flow relaxation, thus allowing theory to
match practical experience.
