Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds

Yixin Cao, R. B. Sandeep

Given an $n\ast n$ sparse symmetric matrix with $m$ nonzero entries, performing Gaussian elimination may turn some zeroes into nonzero values. To maintain the matrix sparse, we would l…