zbMATH — the first resource for mathematics

Minimum fill-in: inapproximability and almost tight lower bounds. (English) Zbl 1435.68111
Summary: Given an \(n \times 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 \(\mathrm{P} \neq \mathrm{NP}\), and the existence of \(2^{O(n^{1 - \delta})}\)-time approximation schemes for any positive \(\delta\), assuming the Exponential Time Hypothesis. We also give a \(2^{O(k^{1/2 - \delta})} \cdot 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.
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
65F50 Computational methods for sparse matrices
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] Agrawal, Ajit, Network Design and Network Cut Dualities: Approximation Algorithms and Applications (1992), Brown University: Brown University Providence, Rhode Island, PhD thesis, Technical Report CS-91-60
[2] Agrawal, Ajit; Klein, Philip N.; Ravi, Ramamurthy, Cutting down on fill using nested dissection: provably good elimination orderings, (Graph Theory and Sparse Matrix Computation. Graph Theory and Sparse Matrix Computation, The IMA Volumes in Mathematics and Its Applications, vol. 56 (1993), Springer-Verlag: Springer-Verlag Heidelberg), 31-55, a preliminary version appeared in FOCS 1990
[3] Alimonti, Paola; Kann, Viggo, Some APX-completeness results for cubic graphs, Theor. Comput. Sci., 237, 1-2, 123-134 (2000)
[4] Ambühl, Christoph; Mastrolilli, Monaldo; Svensson, Ola, Inapproximability results for maximum edge biclique, minimum linear arrangement, and sparsest cut, SIAM J. Comput., 40, 2, 567-596 (2011), a preliminary version appeared in FOCS 2007
[5] Arnborg, Stefan; Corneil, Derek G.; Proskurowski, Andrzej, Complexity of finding embeddings in a k-tree, SIAM J. Algebraic Discrete Methods, 8, 2, 277-284 (1987)
[6] Bliznets, Ivan; Cygan, Marek; Komosa, Paweł; Mach, Łukáš; Pilipczuk, Michał, Lower bounds for the parameterized complexity of minimum fill-in and other completion problems, (Krautamer, Robert, Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2016), SIAM), 1132-1151
[7] Bonnet, Edouard; Escoffier, Bruno; Kim, Eun Jung; Paschos, Vangelis Th., On subexponential and FPT-time inapproximability, Algorithmica, 71, 3, 541-565 (2015)
[8] Brooks, Rowland Leonard, On colouring the nodes of a network, Math. Proc. Camb. Philos. Soc., 37, 4, 194-197 (1941)
[9] Chung, Fan R. K.; Mumford, David, Chordal completions of planar graphs, J. Comb. Theory, Ser. B, 62, 1, 96-106 (1994)
[10] Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket, Parameterized Algorithms (2015), Springer
[11] Dinur, Irit, The PCP theorem by gap amplification, J. ACM, 54, 3, 12 (2007), a preliminary version appeared in STOC 2006
[12] Fomin, Fedor V.; Villanger, Yngve, Subexponential parameterized algorithm for minimum fill-in, SIAM J. Comput., 42, 6, 2197-2216 (2013), a preliminary version appeared in SODA 2012
[13] Garey, Michael R.; Johnson, David S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco
[14] Garey, Michael R.; Johnson, David S.; Stockmeyer, Larry J., Some simplified NP-complete graph problems, Theor. Comput. Sci., 1, 3, 237-267 (1976), a preliminary version appeared in STOC 1974
[15] George, Alan, Nested dissection of a regular finite element mesh, SIAM J. Numer. Anal., 10, 2, 345-363 (1973)
[16] George, Alan; Liu, Joseph W. H., Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall Series in Computational Mathematics (1981), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[17] Gilbert, John R.; Tarjan, Robert Endre, The analysis of a nested dissection algorithm, Numer. Math., 50, 4, 377-404 (1987)
[18] Impagliazzo, Russell; Paturi, Ramamohan, On the complexity of k-SAT, J. Comput. Syst. Sci., 62, 2, 367-375 (2001), a preliminary version appeared in CCC 1999
[19] Impagliazzo, Russell; Paturi, Ramamohan; Zane, Francis, Which problems have strongly exponential complexity?, J. Comput. Syst. Sci., 63, 4, 512-530 (2001), a preliminary version appeared in FOCS 1998
[20] Kaplan, Haim; Shamir, Ron; Tarjan, Robert Endre, Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs, SIAM J. Comput., 28, 5, 1906-1922 (1999), a preliminary version appeared in FOCS 1994
[21] Kashiwabara, Toshinobu; Fujisawa, Toshio, An NP-complete problem on interval graphs, (Proceedings of the 1979 International Symposium on Circuits and Systems (1979)), 82-83
[22] Kashiwabara, Toshinobu; Fujisawa, Toshio, NP-completeness of the problem of finding a minimum-clique-number interval graph containing a given graph as a subgraph, (Proceedings of the 1979 International Symposium on Circuits and Systems (1979)), 657-660
[23] Leighton, Frank Thomson; Rao, Satish, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, J. ACM, 46, 6, 787-832 (1999), a preliminary version appeared in FOCS 1988
[24] Lipton, Richard J.; Rose, Donald J.; Tarjan, Robert Endre, Generalized nested dissection, SIAM J. Numer. Anal., 16, 2, 346-358 (1979)
[25] Lipton, Richard J.; Tarjan, Robert Endre, A separator theorem for planar graphs, SIAM J. Appl. Math., 36, 177-189 (1979)
[26] Lokshtanov, Daniel; Marx, Dániel; Saurabh, Saket, Lower bounds based on the exponential time hypothesis, Bull. Eur. Assoc. Theor. Comput. Sci., 105, 41-72 (2011)
[27] Marx, Dániel, On the optimality of planar and geometric approximation schemes, (Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (2007), IEEE Computer Society), 338-348
[28] Natanzon, Assaf; Shamir, Ron; Sharan, Roded, A polynomial approximation algorithm for the minimum fill-in problem, SIAM J. Comput., 30, 4, 1067-1079 (2000), a preliminary version appeared in STOC 1998
[29] Papadimitriou, Christos H.; Yannakakis, Mihalis, Optimization, approximation, and complexity classes, J. Comput. Syst. Sci., 43, 3, 425-440 (1991), a preliminary version appeared in STOC 1988
[30] Prasad, Raghavendra; Steurer, David, Graph expansion and the unique games conjecture, (Schulman, Leonard J., Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC) (2010), ACM), 755-764
[31] Ravi, Ramamurthy; Agrawal, Ajit; Klein, Philip N., Ordering problems approximated: single-processor scheduling and interval graph completion, (Albert, Javier Leach; Monien, Burkhard; Rodríguez-Artalejo, Mario, Automata, Languages and Programming (ICALP). Automata, Languages and Programming (ICALP), LNCS, vol. 510 (1991), Springer), 751-762
[32] Rose, Donald J., A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations, (Reed, Ronald C., Graph Theory and Computing (1973), Academic Press: Academic Press New York), 183-217
[33] Tarjan, Robert Endre, Graph theory and Gaussian elimination, (Bunch, James R.; Rose, Donald J., Sparse Matrix Computations (1976), Academic Press: Academic Press New York), 3-22, also available as Technical Report CS-TR-75-526, Computer Science Department, Stanford University
[34] Villanger, Yngve; Heggernes, Pinar; Paul, Christophe; Telle, Jan Arne, Interval completion is fixed parameter tractable, SIAM J. Comput., 38, 5, 2007-2020 (2009), a preliminary version appeared in STOC 2007
[35] Wu, Yu; Austrin, Per; Pitassi, Toniann; Liu, David, Inapproximability of treewidth, one-shot pebbling, and related layout problems, J. Artif. Intell. Res., 49, 569-600 (2014), a preliminary version appeared in IJCAI 2015
[36] Yannakakis, Mihalis, Computing the minimum fill-in is NP-complete, SIAM J. Algebraic Discrete Methods, 2, 1, 77-79 (1981)
[37] Yannakakis, Mihalis, Node-deletion problems on bipartite graphs, SIAM J. Comput., 10, 2, 310-327 (1981)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.