7
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ Checking whether a given graph is an expander is co-NP complete so the problem you seek is also computationally hard. $\endgroup$
    – Chandra Chekuri
    Nov 21, 2012 at 15:21
  • $\begingroup$ @Chandra I'm not able to see the correspondence..How can we check if a given graph is an expander using the above routine? $\endgroup$
    – Jagadish
    Nov 22, 2012 at 3:51
  • $\begingroup$ @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. $\endgroup$
    – Chandra Chekuri
    Nov 22, 2012 at 4:37
  • $\begingroup$ @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? $\endgroup$
    – Jagadish
    Nov 22, 2012 at 11:07

0

Reset to default

Your Answer

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