Abstract

We consider a game on an undirected graph, in which vertices are eliminated. When a vertex is eliminated, the incident edges are removed, but new edges may be added to the graph according to a prescribed rule. The edges that are added will eventually be removed at later stages of the game. The graph will be empty at end of the game. We are interested in the total number of new edges that the game sees throughout the elimination. The order in which the vertices are eliminated will affect the number of new edges added to the graph. Thus, we are interested in finding an elimination order that minimizes a function, which depends on the number of new edges added during the game. In this talk, we will provide an overview of the elimination game. We will also discuss some old and new results on the complexity of the game. This elimination game is relevant to the problem of computing a triangular factorization of a sparse matrix.