In a 2006 presentation titled EXPANDER GRAPHS - ARE THERE ANY MYSTERIES LEFT? , 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?

  • 1
    $\begingroup$ 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? $\endgroup$ Sep 30 '10 at 22:15
  • $\begingroup$ @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$). $\endgroup$ Sep 30 '10 at 22:38
  • 2
    $\begingroup$ @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? $\endgroup$ Sep 30 '10 at 22:43
  • 2
    $\begingroup$ @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. $\endgroup$
    – arnab
    Oct 1 '10 at 0:04
  • 1
    $\begingroup$ @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. $\endgroup$ Oct 1 '10 at 6:52

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.

  • $\begingroup$ In your last line, do you mean that your paper constructs unbalanced expanders, because then you might have an answer to this question: cstheory.stackexchange.com/questions/592/… $\endgroup$ Oct 2 '10 at 18:04
  • $\begingroup$ Suresh: yes, the paper constructs unbalanced expanders/samplers/extractors, but not any better than the known constructions of such. $\endgroup$ Oct 4 '10 at 23:49

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...).


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.