Parameterized Complexity of Chordal Conversion for Sparse Semidefinite Programs with Small Treewidth

Abstract

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 frequently allow an interior-point method to solve the SDP in just \(O(m+n)\) time per-iteration. This is a significant reduction over the minimum \(\Omega(n^{3})\) time per-iteration for a direct solution, but a definitive theoretical explanation was previously unknown. Contrary to popular belief, the speedup is not guaranteed by a small treewidth in \(G\), 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 \(\overline{G}\supseteq G\) by forcing each constraint matrix \(A_{i}\) to be its own clique in \(G\). We prove that a small treewidth in \(\overline{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. For classical SDPs like the MAX-\(k\)-CUT relaxation and the Lovasz Theta problem, the two sparsity graphs coincide \(G=\overline{G}\), so our result provide a complete characterization for the complexity of chordal conversion, showing that a small treewidth is both necessary and sufficient for \(O(m+n)\) time per-iteration. Real-world SDPs like the AC optimal power flow relaxation have different graphs \(G\subseteq\overline{G}\) with similar small treewidths; while chordal conversion is already widely used on a heuristic basis, in this paper we provide the first rigorous guarantee that it solves such SDPs in \(O(m+n)\) time per-iteration. [Supporting code at https://github.com/ryz-codes/chordalConv/]