<p>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. </p>

<p>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 <strong>directed graph</strong> $G_M = (V,E)$ where we have $V = \{v_1, v_2, \ldots, v_n\}$ where $v_i$ corresponds to <em>row i</em> and <em>variable i</em> and $(v_i,v_j) \in E$ <em>iff</em> $M_{ij} \neq 0$ and $i \neq j$.</p>

<p>The elimination process may create some new <em>non-zero elements</em>  in locations in $M$ which contained <em>zeroes</em> to begin with; the edges corresponding to these elements are called <strong>fill-in</strong>. 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\}$</p>

<p>In order to make the elimination process efficient, we can target minimizing fill-in. By a <a href="http://www.math.ucla.edu/~jhellrun/course_files/Winter%202007/Math%20270C%20-%20Computational%20Linear%20Algebra/Computing%20the%20Minimum%20Fill-In%20is%20NP-Complete.pdf">result of Yannakakis</a>, we know that fill-in minimization is a NP-Complete problem.</p>

<p>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 <strong><em>elimination ordering</em></strong> 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 <em>minimum elimination ordering</em>. And again we (of course) have that computing the minimum elimination ordering is NP-Complete.</p>

<p>My question</p>

<blockquote>
  <ol>
  <li>What is the best known approximation algorithm for minimizing fill-in? </li>
  </ol>
</blockquote>

<p>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.</p>

<p>Thanks for your time<br>
Best Regards<br>
-Akash</p>

CC BY-SA 2.5
2011-04-05T18:36:24.760Z
The paper "A Polynomial Approximation Algorithm for the Minimum Fill-In Problem" by  
Natanzon, Assaf and Shamir, Ron and Sharan, Roded
SIAM J. Comput. 2000
Volume 30 Pages 1067--1079
gives algorithm with polylogarithmic approximation ratio. I also think they work with undirected graphs. Not sure if anything beyond that is known.
XXYYXX
CC BY-SA 2.5
2011-04-05T21:03:02.450Z
@XXYYXX this could be an answer.
Suresh Venkat
CC BY-SA 2.5
2011-04-06T00:09:30.687Z
@Suresh, @XXYYXX : Akash and myself are looking for an answer to the above question since it is required for a project we are working on. We are looking for an answer for the general case of directed graphs as highlighted in the question. The paper pointed by @XXYYXX handles only the undirected graphs. Unfortunately undirected graph does not help us :(
Shiva Kintali
CC BY-SA 2.5
2011-04-06T02:35:44.537Z
@Shiva @Akash then the question should reflect that in the title itself.
Suresh Venkat
CC BY-SA 2.5
2011-04-06T14:40:38.923Z
@suresh, I am sorry the title was not clear enough. I will change it accordingly.
Akash Kumar
<ds.algorithms><graph-theory><approximation-algorithms><linear-algebra>
Approximation algorithm for Minimum Fill-In and/or minimum elimination ordering (for directed graphs)
Akash Kumar
# Approximation algorithm for Minimum Fill-In and/or minimum elimination ordering (for directed graphs)

(Asked by: username_0 on 2011-04-05)

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](http://www.math.ucla.edu/~jhellrun/course_files/Winter%202007/Math%20270C%20-%20Computational%20Linear%20Algebra/Computing%20the%20Minimum%20Fill-In%20is%20NP-Complete.pdf), 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.

Thanks for your time  
Best Regards  
-Akash

**Tags:** ds.algorithms, graph-theory, approximation-algorithms, linear-algebra

> **Comments:**
> **username_1**: The paper "A Polynomial Approximation Algorithm for the Minimum Fill-In Problem" by   Natanzon, Assaf and Shamir, Ron and Sharan, Roded SIAM J. Comput. 2000 Volume 30 Pages 1067--1079 gives algorithm with polylogarithmic approximation ratio. I also think they work with undirected graphs. Not sure if anything beyond that is known.  
> **username_2**: @username_1 this could be an answer.  
> **username_3**: @Suresh, @username_1 : Akash and myself are looking for an answer to the above question since it is required for a project we are working on. We are looking for an answer for the general case of directed graphs as highlighted in the question. The paper pointed by @username_1 handles only the undirected graphs. Unfortunately undirected graph does not help us :(  
> **username_2**: @Shiva @Akash then the question should reflect that in the title itself.  
> **username_0**: @suresh, I am sorry the title was not clear enough. I will change it accordingly.  

---

## 0 answers

