Minimum fill-in: Inapproximability and almost tight lower bounds

Yixin Cao, R. B. Sandeep

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

Abstract

Given an n×n sparse symmetric matrix with m nonzero entries, performing Gaussian elimination may turn some zeroes into nonzero values, so called fill-ins. The minimum fill-in problem asks whether it is possible to perform the elimination with at most k fill-ins. We exclude the existence of polynomial time approximation schemes for this problem, assuming P≠NP, and the existence of 2O(n1−δ)-time approximation schemes for any positive δ, assuming the Exponential Time Hypothesis. We also give a 2O(k1/2−δ)⋅nO(1) parameterized lower bound. All these results come as corollaries of a new reduction from vertex cover to the minimum fill-in problem, which might be of its own interest: All previous reductions for similar problems start from some kind of graph layout problems, and hence have limited use in understanding their fine-grained complexity.

Original languageEnglish
Article number104514
Pages (from-to)1-9
JournalInformation and Computation
Volume271
DOIs
Publication statusPublished - Apr 2020

Keywords

  • Fine-grained complexity
  • Inapproximability
  • Sparse matrix
  • Subexponential-time algorithm

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Cite this