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?

  • 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 '12 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 '12 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 '12 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 '12 at 11:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.