3
$\begingroup$

The only graph problem that I worked with is TSP. It is exponentially hard, but there are tons of heuristics which allows to find near to optimum solution.

So I was wondering, is there any graph problems (or optimization problems which could be mapped onto graph) that are exponentially hard and can not be solved (even approximatly) efficiently for small and mid-sized systems? (let's say 10-20 verticies)

$\endgroup$
  • 1
    $\begingroup$ It's hard to imagine problems of exponential complexity being particularly hard on a 20-vertex graph. Even problems of the form of "There is a set of vertices such that..." can be brute-forced by checking only a million or so sets. $\endgroup$ – David Richerby Jul 13 '17 at 15:46
  • 1
    $\begingroup$ Computing the choosability of a graph (aka list coloring number) might be difficult. $\endgroup$ – Yuval Filmus Jul 13 '17 at 16:02
  • $\begingroup$ @DavidRicherby But problems of the form of "There is an ordering of the vertices such that..." might be harder. What about finding a set of edges (or even worse, arcs)? $\endgroup$ – Pål GD Jul 14 '17 at 18:06
0
$\begingroup$

I recommend you look at a list of NP-complete problems on graphs. For each one, research whether there exists a known approximation algorithm. For some problems we have hardness of approximation results (which say that there is no polynomial-time algorithm that achieves approximation factor $\alpha$, unless $P=NP$). Those are potential candidates that might be of interest. In particular, I'd recommend you study the standard methods for dealing with intractability, then look for a candidate problem where none of those seem to work. You might also look at graph problems that are APX-complete as candidates worthy of further exploration.

For instance, graph coloring might be a possible candidate to look at. I haven't studied that problems so I don't know whether good heuristics exist. I doubt it will be hard on graphs with only 10-20 vertices, but it might be hard with somewhat larger graphs.

$\endgroup$

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.