<p>Am guessing it may be easy to show that many exact problems (and perhaps strong approximation problems as well) are NP-hard on expanders.  The idea is that if you take an arbitrary constant degree graph $G$ on $n$ vertices, and add another expander $H$ on $n$ disjoint vertices, and put a matching between $G$ and $H$, then you get an expander.  The reason being that any set of less than half the vertices, will have either a constant fraction of the matching edges outside it, or its intersection with $H$ will have at most say $0.51$ fraction of $H$'s vertices.</p>

<p>Since you can choose $H$ arbitrarily (say take a random graph) you can know the optimal solution for your NP problem in $H$, and hence there may be hope (depending on the problem), that given a solution for the combined graph you can get at least an approximate solution for $G$. But I didn't verify this for any concrete problem.</p>

<p>Of course, as mentioned above, there are natural problems (most notably unique games) where one cannot do such tricks and in particular algorithms are known for expanders and not known in the general case. One should also be able to come up with some contrived example of a problem that's NP hard in general but easy on expanders (e.g., take some arbitrary NP hard problem on graphs, and modify it so that all instances with spectral gap more than $1/\log n$ are YES...). </p>

CC BY-SA 2.5
2010-11-22T22:47:48.180Z
2010-11-22T22:47:48.180Z
Boaz Barak
<p>If "unbalanced expanders" count as expanders for the purpose of this question (an unbalanced expander: a bipartite graph $G=(A,B,E)$, such that for every subsets $A'\subseteq A$, $B'\subseteq B$, the fraction of edges between $A'$ and $B'$ is about ${|A'||B'|}/{|A||B|}$), then yes, many problems on expanders (e.g., constraint satisfaction problems) are NP-hard to approximate.</p>

<p>In particular, the proof of the two-query, low error, PCP Theorem [with Ran Raz in 2008] constructs expander graphs.    </p>

CC BY-SA 2.5
2010-10-02T18:04:28.607Z
In your last line, do you mean that your paper constructs unbalanced expanders, because then you might have an answer to this question: http://cstheory.stackexchange.com/questions/592/space-efficient-industrial-unbalanced-expanders
Suresh Venkat
CC BY-SA 2.5
2010-10-04T23:49:18.097Z
Suresh: yes, the paper constructs unbalanced expanders/samplers/extractors, but not any better than the known constructions of such.
Dana Moshkovitz
CC BY-SA 2.5
2010-10-02T15:14:41.043Z
2010-10-02T15:14:41.043Z
Dana Moshkovitz
<p>In a 2006 presentation titled <a href="http://www.cs.huji.ac.il/~nati/PAPERS/diskrete_mathematik_06.pdf">EXPANDER GRAPHS - ARE THERE ANY MYSTERIES LEFT?  </a>
<a href="http://www.cs.huji.ac.il/~nati/PAPERS/diskrete_mathematik_06.pdf"></a>, Nati Linial posed the following open problem:</p>

<blockquote>
  <p>Which $NP$-hard computational problem on graph remain hard when restricted to expander graphs?</p>
</blockquote>

<p><strong>Since then, Has any progress been made to prove such result for an $NP$-hard problem?</strong></p>

CC BY-SA 2.5
2010-09-30T22:15:10.603Z
Could someone perhaps elaborate why this question is interesting? Do we have any examples of NP-hard problems becoming *easy* when restricted to expander graphs?
Jukka Suomela
CC BY-SA 2.5
2010-09-30T22:38:58.650Z
@Jukka: Expanders can be $d$-regular for small $d$ (e.g. $d=3$), yet some NP-hard problems are easy on the class of max-degree $d$ graphs for small $d$ (e.g. GRAPH COLOURING for $d<4$).
András Salamon
CC BY-SA 2.5
2010-09-30T22:43:40.977Z
@András: Sure, but that's not really related to the expansion properties. Let me rephrase: do we have examples of problems that are hard on $d$-regular graphs but easy on $d$-regular expander graphs?
Jukka Suomela
CC BY-SA 2.5
2010-09-30T23:20:05.103Z
@Jukka: if an algorithm decides an NP-hard problem for the class C of instances in polynomial time, then it will also decide every instance in a subclass of C.  I think the point is that to avoid such counterexamples, one needs a class of expanders that has a non-obvious construction.
András Salamon
CC BY-SA 2.5
2010-10-01T00:04:09.647Z
@Jukka: Unique games was shown to have polynomial time approximation algorithms when the constraint graph is an expander [Arora-Khot-Kolla-Steurer-Tulsiani-Vishnoi STOC '08].  This is not known to be the case for general graphs, and if the UGC were true, there are in fact no polynomial time algorithms.  I took this to be the motivation for turkistany's question.
arnab
CC BY-SA 2.5
2010-10-01T01:45:31.520Z
What about problems like independent set? Does independent set become easy on expanders?
Robin Kothari
CC BY-SA 2.5
2010-10-01T06:34:26.650Z
@arnab: Ok, so the question is really about *approximability*, not exact solutions. That makes much more sense, thanks. It might be good to rephrase the questions to emphasise this aspect, if this is indeed the case. (An, in general, I'd prefer to see the motivation stated explicitly.)
Jukka Suomela
CC BY-SA 2.5
2010-10-01T06:52:53.550Z
@Jukka, my motivation is to understand the relation between random properties of expanders and computational hardness of problems. For instance, I don't expect independent set to be easy on expanders.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-10-01T12:40:31.110Z
@turkistany: yes, that's also a good point.
arnab
<cc.complexity-theory><np-hardness><expanders>
NP-hard problems on expander graphs?
Mohammad Al-Turkistany
# NP-hard problems on expander graphs?

(Asked by: username_0 on 2010-09-22)

In a 2006 presentation titled [EXPANDER GRAPHS - ARE THERE ANY MYSTERIES LEFT?](http://www.cs.huji.ac.il/~nati/PAPERS/diskrete_mathematik_06.pdf) 
, Nati Linial posed the following open problem:

> Which $NP$-hard computational problem on graph remain hard when restricted to expander graphs?

**Since then, Has any progress been made to prove such result for an $NP$-hard problem?**

**Tags:** cc.complexity-theory, np-hardness, expanders
> **Comments:**
> **username_1**: Could someone perhaps elaborate why this question is interesting? Do we have any examples of NP-hard problems becoming *easy* when restricted to expander graphs?  
> **username_2**: @Jukka: Expanders can be $d$-regular for small $d$ (e.g. $d=3$), yet some NP-hard problems are easy on the class of max-degree $d$ graphs for small $d$ (e.g. GRAPH COLOURING for $d<4$).  
> **username_1**: @András: Sure, but that's not really related to the expansion properties. Let me rephrase: do we have examples of problems that are hard on $d$-regular graphs but easy on $d$-regular expander graphs?  
> **username_2**: @Jukka: if an algorithm decides an NP-hard problem for the class C of instances in polynomial time, then it will also decide every instance in a subclass of C.  I think the point is that to avoid such counterexamples, one needs a class of expanders that has a non-obvious construction.  
> **username_3**: @Jukka: Unique games was shown to have polynomial time approximation algorithms when the constraint graph is an expander [Arora-Khot-Kolla-Steurer-Tulsiani-Vishnoi STOC '08].  This is not known to be the case for general graphs, and if the UGC were true, there are in fact no polynomial time algorithms.  I took this to be the motivation for turkistany's question.  
> **username_4**: What about problems like independent set? Does independent set become easy on expanders?  
> **username_1**: @arnab: Ok, so the question is really about *approximability*, not exact solutions. That makes much more sense, thanks. It might be good to rephrase the questions to emphasise this aspect, if this is indeed the case. (An, in general, I'd prefer to see the motivation stated explicitly.)  
> **username_0**: @Jukka, my motivation is to understand the relation between random properties of expanders and computational hardness of problems. For instance, I don't expect independent set to be easy on expanders.  
> **username_3**: @turkistany: yes, that's also a good point.  

---

## 2 answers

### Answer by username_6 on 2010-10-02. Score: 13 | Accepted answer

If "unbalanced expanders" count as expanders for the purpose of this question (an unbalanced expander: a bipartite graph $G=(A,B,E)$, such that for every subsets $A'\subseteq A$, $B'\subseteq B$, the fraction of edges between $A'$ and $B'$ is about ${|A'||B'|}/{|A||B|}$), then yes, many problems on expanders (e.g., constraint satisfaction problems) are NP-hard to approximate.

In particular, the proof of the two-query, low error, PCP Theorem [with Ran Raz in 2008] constructs expander graphs.

> **Comments:**
> **username_7**: In your last line, do you mean that your paper constructs unbalanced expanders, because then you might have an answer to this question: http://cstheory.stackexchange.com/questions/592/space-efficient-industrial-unbalanced-expanders  
> **username_6**: Suresh: yes, the paper constructs unbalanced expanders/samplers/extractors, but not any better than the known constructions of such.  

---

### Answer by username_5 on 2010-11-22. Score: 12

Am guessing it may be easy to show that many exact problems (and perhaps strong approximation problems as well) are NP-hard on expanders. The idea is that if you take an arbitrary constant degree graph $G$ on $n$ vertices, and add another expander $H$ on $n$ disjoint vertices, and put a matching between $G$ and $H$, then you get an expander. The reason being that any set of less than half the vertices, will have either a constant fraction of the matching edges outside it, or its intersection with $H$ will have at most say $0.51$ fraction of $H$'s vertices.

Since you can choose $H$ arbitrarily (say take a random graph) you can know the optimal solution for your NP problem in $H$, and hence there may be hope (depending on the problem), that given a solution for the combined graph you can get at least an approximate solution for $G$. But I didn't verify this for any concrete problem.

Of course, as mentioned above, there are natural problems (most notably unique games) where one cannot do such tricks and in particular algorithms are known for expanders and not known in the general case. One should also be able to come up with some contrived example of a problem that's NP hard in general but easy on expanders (e.g., take some arbitrary NP hard problem on graphs, and modify it so that all instances with spectral gap more than $1/\log n$ are YES...).


---

