Abstract
In the Determinant Maximization problem, given an n × n positive semidefinite matrix A in ℚ^{n × n} and an integer k, we are required to find a k × k principal submatrix of A having the maximum determinant. This problem is known to be NPhard and further proven to be W[1]hard with respect to k by Koutis (2006); i.e., a f(k)n^𝒪(1)time algorithm is unlikely to exist for any computable function f. However, there is still room to explore its parameterized complexity in the restricted case, in the hope of overcoming the generalcase parameterized intractability. In this study, we rule out the fixedparameter tractability of Determinant Maximization even if an input matrix is extremely sparse or low rank, or an approximate solution is acceptable. We first prove that Determinant Maximization is NPhard and W[1]hard even if an input matrix is an arrowhead matrix; i.e., the underlying graph formed by nonzero entries is a star, implying that the structural sparsity is not helpful. By contrast, we show that Determinant Maximization is solvable in polynomial time on tridiagonal matrices. Thereafter, we demonstrate the W[1]hardness with respect to the rank r of an input matrix. Our result is stronger than Koutis' result in the sense that any k × k principal submatrix is singular whenever k > r. We finally give evidence that it is W[1]hard to approximate Determinant Maximization parameterized by k within a factor of 2^{c√k} for some universal constant c > 0. Our hardness result is conditional on the Parameterized Inapproximability Hypothesis posed by Lokshtanov, Ramanujan, Saurab, and Zehavi (2020), which asserts that a gap version of Binary Constraint Satisfaction Problem is W[1]hard. To complement this result, we develop an εadditive approximation algorithm that runs in ε^{r²}⋅r^𝒪(r³)⋅n^𝒪(1) time for the rank r of an input matrix, provided that the diagonal entries are bounded.
BibTeX  Entry
@InProceedings{ohsaka:LIPIcs.ISAAC.2022.46,
author = {Ohsaka, Naoto},
title = {{On the Parameterized Intractability of Determinant Maximization}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {46:146:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772587},
ISSN = {18688969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17331},
URN = {urn:nbn:de:0030drops173316},
doi = {10.4230/LIPIcs.ISAAC.2022.46},
annote = {Keywords: Determinant maximization, Parameterized complexity, Approximability}
}
Keywords: 

Determinant maximization, Parameterized complexity, Approximability 
Collection: 

33rd International Symposium on Algorithms and Computation (ISAAC 2022) 
Issue Date: 

2022 
Date of publication: 

14.12.2022 