14
$\begingroup$

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.

Thanks for your time
Best Regards
-Akash

Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – XXYYXX
    Apr 5, 2011 at 18:36
  • $\begingroup$ @XXYYXX this could be an answer. $\endgroup$
    – Suresh Venkat
    Apr 5, 2011 at 21:03
  • $\begingroup$ @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 :( $\endgroup$
    – Shiva Kintali
    Apr 6, 2011 at 0:09
  • $\begingroup$ @Shiva @Akash then the question should reflect that in the title itself. $\endgroup$
    – Suresh Venkat
    Apr 6, 2011 at 2:35
  • $\begingroup$ @suresh, I am sorry the title was not clear enough. I will change it accordingly. $\endgroup$
    – Akash Kumar
    Apr 6, 2011 at 14:40

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.