<p>Expander constructions given an expander which is a sub-graph of a complete graph. Sometimes we don't want to construct an arbitrary expander, want to find an expander inside another given graph. In a sense this is similar to finding a spanning tree inside a graph. Furthermore we usually don't want just an arbitrary expander, we have some cost function on the edges and we want to minimize the total cost of the edges we select for our expander (similar to minimum wight spanning tree problem). Is there a good algorithm for this purpose? Or is this problem computationally difficult to solve?</p>

<blockquote>
  <p><strong>Minimum Expander Problem</strong>:<br>
  Given a graph $G$ with weights for its edges, and two numbers $d$ and $h$,<br>
  Find a a sub-graph of $G$ which is expander of degree $d$ and expansion $h$ and 
  has the minimum total weight among such sub-graphs.</p>
</blockquote>

<p>We can relax the problem to get an approximation version (e.g. the total weight is at most twice of the optimal weight, and the sub-graph is close to a $d$ and $h$ expander.)</p>

<p>What is known about these problems?</p>

CC BY-SA 3.0
2012-11-21T15:21:57.810Z
Checking whether a given graph is an expander is co-NP complete so the problem you seek is also computationally hard.
Chandra Chekuri
CC BY-SA 3.0
2012-11-22T03:51:57.373Z
@Chandra I'm not able to see the correspondence..How can we check if a given graph is an expander using the above routine?
Jagadish
CC BY-SA 3.0
2012-11-22T04:37:15.377Z
@Jagdish. Suppose you want to check whether a graph $G$ is an expander. Set all edge of $G$ to weight $0$ and make $G$ a complete graph by adding all other edges with weight $1$. Then use an algorithm for your problem as a subroutine.
Chandra Chekuri
CC BY-SA 3.0
2012-11-22T11:07:02.943Z
@Chandra But the routine returns 'Yes' if G has a subgraph which is an expander, while G itself might not be an expander. Maybe I'm missing something?
Jagadish
<ds.algorithms><reference-request><graph-theory><approximation-algorithms><expanders>
Minimum weight expander
Anonymous
# Minimum weight expander

(Asked by: username_0 on 2012-11-20)

Expander constructions given an expander which is a sub-graph of a complete graph. Sometimes we don't want to construct an arbitrary expander, want to find an expander inside another given graph. In a sense this is similar to finding a spanning tree inside a graph. Furthermore we usually don't want just an arbitrary expander, we have some cost function on the edges and we want to minimize the total cost of the edges we select for our expander (similar to minimum wight spanning tree problem). Is there a good algorithm for this purpose? Or is this problem computationally difficult to solve?

> **Minimum Expander Problem**:  
> Given a graph $G$ with weights for its edges, and two numbers $d$ and $h$,  
> Find a a sub-graph of $G$ which is expander of degree $d$ and expansion $h$ and
> has the minimum total weight among such sub-graphs.

We can relax the problem to get an approximation version (e.g. the total weight is at most twice of the optimal weight, and the sub-graph is close to a $d$ and $h$ expander.)

What is known about these problems?

**Tags:** ds.algorithms, reference-request, graph-theory, approximation-algorithms, expanders
> **Comments:**
> **username_1**: Checking whether a given graph is an expander is co-NP complete so the problem you seek is also computationally hard.  
> **username_2**: @Chandra I'm not able to see the correspondence..How can we check if a given graph is an expander using the above routine?  
> **username_1**: @Jagdish. Suppose you want to check whether a graph $G$ is an expander. Set all edge of $G$ to weight $0$ and make $G$ a complete graph by adding all other edges with weight $1$. Then use an algorithm for your problem as a subroutine.  
> **username_2**: @Chandra But the routine returns 'Yes' if G has a subgraph which is an expander, while G itself might not be an expander. Maybe I'm missing something?  

---

## 0 answers

