## 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 2^{O(n1−δ)}-time approximation schemes for any positive δ, assuming the Exponential Time Hypothesis. We also give a 2^{O(k1/2−δ)}⋅n^{O(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 language | English |
---|---|

Article number | 104514 |

Pages (from-to) | 1-9 |

Journal | Information and Computation |

Volume | 271 |

DOIs | |

Publication status | Published - 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