Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds
Yixin Cao, R. B. Sandeep · 2017
Performing Gaussian elimination to a sparse matrix may turn some zeroes into nonzero values, so called fill-ins, which we want to minimize to keep the matrix sparse. Let n denote the rows of the matrix and k the number of fill-ins. For the minimum fill-in problem, we exclude the existence of polynomial time approximation schemes, assuming P≠NP, and the existence of 2O(n1+ δ) -time approximation schemes for any positive δ, assuming the Exponential Time Hypothesis. Also implied is a 2O(K1\2-δ). nO(1) parameterized lower bound. Behind these results is a new reduction from vertex cover, which might be of its own interest: All previous reductions for similar problems are from some kind of graph layout problems.