# Approximation algorithm for Minimum Fill-In and/or minimum elimination ordering (for directed graphs)

Recently while working on a problem, I had to go through some of the literature on nested dissection. I happen to have one (maybe two?) questions related to the same.

First, I will define a few relevant terms. These terms come up when we study the process of Gaussian elimination graph theoretically. Say, we have got a matrix $M$. With this matrix, we associate a directed graph $G_M = (V,E)$ where we have $V = \{v_1, v_2, \ldots, v_n\}$ where $v_i$ corresponds to row i and variable i and $(v_i,v_j) \in E$ iff $M_{ij} \neq 0$ and $i \neq j$.

The elimination process may create some new non-zero elements in locations in $M$ which contained zeroes to begin with; the edges corresponding to these elements are called fill-in. In graph-theoretic terms, removing a vertex $v$ calls for addition of the following set $S_v$ of edges. $S_v = \{(u,w) | (u,v) \in E, (v,w) \in E, (u,w) \not\in E\}$

In order to make the elimination process efficient, we can target minimizing fill-in. By a result of Yannakakis, we know that fill-in minimization is a NP-Complete problem.

It is easy to see that the value of fill-in depends on the ordering of vertices which leads to definition of a related parameter. An elimination ordering is a bijection $\mathbf{\alpha \colon \{1,2,\ldots, n\} \to V}$ and $\mathbf{G_{\alpha} = (V,E, \alpha)}$ is an ordered graph. Basically, this represents the order in which the vertices will be picked for deletion in the corresponding directed graph representation. Corresponding to different orderings, we get different values of fill-ins. The ordering which minimizes the fill-in size is called the minimum elimination ordering. And again we (of course) have that computing the minimum elimination ordering is NP-Complete.

My question

1. What is the best known approximation algorithm for minimizing fill-in?

Also, I would like to know what is the best known "approximation algorithm to minimize elimination ordering". By approximating the minimum elimination ordering, I mean a poly-time algorithm that outputs an elimination ordering which best approximates the minimum fill-in value.