Computing the Minimum Fill-In is NP-Complete

DOI10.1137/0602010zbMath0496.68033OpenAlexW2027566319MaRDI QIDQ3960122

Mihalis Yannakakis

Publication date: 1981

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/8561d23058501c8f2c245bffb3001e488192a7a3

zbMATH Keywords

Gaussian eliminationgraph chordalsparse symmetric positive definite systems of linear equations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items (only showing first 100 items - show all)

Planar Disjoint-Paths Completion ⋮ Seeing Arboretum for the (partial k-) Trees ⋮ Computing Tree Decompositions ⋮ Updating credal networks is approximable in polynomial time ⋮ All roads lead to Rome -- new search methods for the optimal triangulation problem ⋮ Unnamed Item ⋮ Minimal elimination of planar graphs ⋮ Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree ⋮ Decomposition Methods for Sparse Matrix Nearness Problems ⋮ Estimating spatial covariance using penalised likelihood with weightedL₁penalty ⋮ Graphical Models and Message-Passing Algorithms: Some Introductory Lectures ⋮ Exactly Solving Sparse Rational Linear Systems via Roundoff-Error-Free Cholesky Factorizations ⋮ A Polynomial-Time Algorithm for Outerplanar Diameter Improvement ⋮ Pathwidth is NP-Hard for Weighted Trees ⋮ Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone ⋮ A polynomial-time algorithm for outerplanar diameter improvement ⋮ Independent sets in asteroidal triple-free graphs ⋮ Complexity of modification problems for best match graphs ⋮ Complexity of Finding Embeddings in a k-Tree ⋮ Completion to chordal distance-hereditary graphs: a quartic vertex-kernel ⋮ Algebras for Tree Decomposable Graphs ⋮ Linear optimization over homogeneous matrix cones ⋮ Parallelized integrated nested Laplace approximations for fast Bayesian inference ⋮ Wheel-Free Deletion Is W[2-Hard] ⋮ Automating algorithm selection: checking for matrix properties that can simplify computations ⋮ Generating weakly chordal graphs from arbitrary graphs ⋮ Decomposition of arithmetical np-hard problems ⋮ Characterizing and Computing Minimal Cograph Completions ⋮ Unnamed Item ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Transmission operators for the non-overlapping Schwarz method for solving Helmholtz problems in rectangular cavities ⋮ On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints ⋮ Unnamed Item ⋮ On 3-degree 4-chordal graphs ⋮ On computing large temporal (unilateral) connected components ⋮ Algorithms and complexity of sandwich problems in graphs (extended abstract) ⋮ A cubic vertex-kernel for \textsc{Trivially Perfect Editing} ⋮ Unnamed Item ⋮ A cubic-vertex kernel for flip consensus tree ⋮ Digraphs of bounded elimination width ⋮ The General Minimum Fill-In Problem ⋮ Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs ⋮ Searching for better fill-in ⋮ Recognizing Sparse Perfect Elimination Bipartite Graphs ⋮ NP-hard graph problems and boundary classes of graphs ⋮ How to use the minimal separators of a graph for its chordal triangulation ⋮ Minimal comparability completions of arbitrary graphs ⋮ Unnamed Item ⋮ Tree decomposition and discrete optimization problems: a survey ⋮ Fast Hierarchical Solvers For Sparse Matrices Using Extended Sparsification and Low-Rank Approximation ⋮ A survey of direct methods for sparse linear systems ⋮ On the ordering of sparse linear systems ⋮ On the interval completion of chordal graphs ⋮ A Separator Theorem for Chordal Graphs ⋮ Complexity classification of some edge modification problems ⋮ NP-completeness results for edge modification problems ⋮ Minimal elimination ordering for graphs of bounded degree ⋮ An improved derandomized approximation algorithm for the max-controlled set problem ⋮ Robustness to Dependency in Portfolio Optimization Using Overlapping Marginals ⋮ Parameterized Enumeration for Modification Problems ⋮ Graph classes and the switch Markov chain for matchings ⋮ Computational aspects of DNA mixture analysis ⋮ Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem ⋮ Unnamed Item ⋮ Approximation Algorithms for Minimum Chain Vertex Deletion ⋮ Vertex deletion on split graphs: beyond 4-hitting set ⋮ Chordal decomposition in operator-splitting methods for sparse semidefinite programs ⋮ Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results ⋮ A Subexponential Parameterized Algorithm for Proper Interval Completion ⋮ Minimum fill-in: inapproximability and almost tight lower bounds ⋮ Polynomial Kernels for Proper Interval Completion and Related Problems ⋮ A note on fast approximate minimum degree orderings for symmetric matrices with some dense rows ⋮ Efficient Adaptive MCMC Through Precision Estimation ⋮ Triangulation Heuristics for BN2O Networks ⋮ Solving quadratically constrained convex optimization problems with an interior-point method ⋮ Unnamed Item ⋮ An $$\mathcal {O}(n^2)$$ Time Algorithm for the Minimal Permutation Completion Problem ⋮ Exploring the Subexponential Complexity of Completion Problems ⋮ Approximation algorithms in combinatorial scientific computing ⋮ Exact Solution of Sparse Linear Systems via Left-Looking Roundoff-Error-Free LU Factorization in Time Proportional to Arithmetic Work ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Decision Diagram Decomposition for Quadratically Constrained Binary Optimization ⋮ Decomposable Probabilistic Influence Diagrams ⋮ The Complexity of the Partial Order Dimension Problem ⋮ Bayesian networks: the minimal triangulations of a graph ⋮ Unnamed Item ⋮ Vertex Deletion Problems on Chordal Graphs ⋮ Customizable Contraction Hierarchies ⋮ PMORSy: parallel sparse matrix ordering software for fill-in minimization ⋮ Minimal triangulations of graphs: a survey ⋮ A vertex incremental approach for maintaining chordality ⋮ A linear time algorithm to list the minimal separators of chordal graphs ⋮ Lex M versus MCS-M ⋮ The homogeneous set sandwich problem ⋮ Efficient solutions of hierarchical systems of linear equations ⋮ An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph ⋮ Chordal editing is fixed-parameter tractable ⋮ Bipartite permutation graphs ⋮ On Dasgupta's hierarchical clustering objective and its relation to other graph parameters

Cites Work

• Unnamed Item
• Unnamed Item
• Some simplified NP-complete graph problems
• Node-Deletion Problems on Bipartite Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithmic Aspects of Vertex Elimination on Directed Graphs

This page was built for publication: Computing the Minimum Fill-In is NP-Complete