Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
Checking whether a given graph is an expander is co-NP complete so the problem you seek is also computationally hard. –  Chandra Chekuri Nov 21 '12 at 15:21
    
@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 Nov 22 '12 at 3:51
    
@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 Nov 22 '12 at 4:37
    
@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 Nov 22 '12 at 11:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.