Algorithmic Aspects of Vertex Elimination on Directed Graphs

Source abstract

We consider a graph-theoretic elimination process which models Gaussian elimination on sparse systems of linear equations. We describe this process by constructive theoretical results which lead to efficient algorithms to 1) compute the fill-in produced by any elimination ordering; 2) find a perfect elimination ordering if one exists; and 3) reduce any fill-in to a minimal fill-in. We relate the complexity of these elimination problems to other well-studied problems by showing that tasks 1) and 2) are at least as time-consuming as testing whether a directed graph is transitive, and that the problem of finding a minimum ordering is $NP$-complete.