Minimum fill-in: Inapproximability and almost tight lower bounds

Yixin Cao, R. B. Sandeep

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

9 Citations (Scopus)


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 P6=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.
Original languageEnglish
Title of host publication28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
PublisherAssociation for Computing Machinery
Number of pages6
ISBN (Electronic)9781611974782
Publication statusPublished - 1 Jan 2017
Event28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 - Hotel Porta Fira, Barcelona, Spain
Duration: 16 Jan 201719 Jan 2017


Conference28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this