I'm an undergraduate in computer science (hopefully) going on to graduate study next year. Since my program is research-oriented, and also because I can't always take classes in subjects I'm interested in, I spend a lot of free time trying my hand at traditionally 'hard' problems in order to get practice tackling unanswered questions (or at least questions whose answers haven't yet been proven beyond doubt).
I've recently come up with a fast heuristic (I'm calling it so because I don't yet have the grounds to prove or disprove) for a problem considered hard even to approximate in polynomial time (discovering the largest clique in an arbitrary graph).
While on one hand I'm aware that my procedure likely can be shown to be flawed by implementing it by hand and testing it on large graphs, I would prefer to do so first on smaller examples I can investigate manually in order to better understand the shortcomings of my approach, possibly improve it to generate a better heuristic, and more generally gain experience at generating counterexamples by inspection in this domain of problem.
So far, I've been able to verify my approach on small graphs I can come up with by hand, as well as benchmark classes I'm aware of which lend themselves to being drawn at a small scale (I've tried the Keller variant of DIMACS benchmark graphs, but even a 3-Keller graph is somewhat cumbersome to manipulate with pen and paper). My point in making this thread is to ask if any of you are aware of classes of graphs in which it is proven (or at least thought) that finding the largest clique quickly (in polynomial or pseudo-polynomial time) is hard, while also lending themselves to being generated in a small (<= 25?) number nodes.
Thanks for any direction you may be able to offer!
Also, P =? NP general, if that sparks anybody's interest.
To those better versed than I: what is the current state of approximability of graph-related NP-hard problems? I read a paper stating that there's a proven maximum bound on the approximation factor for any maximum clique algorithm of n^(1/3) (unless P = NP), but I'm not sure if there's been any change since that point.
>hard even to approximate in polynomial time
Stop your research immediately before you do something that many more people will regret. The government is not to be trusted in any whit.
Curiosity and hard work can lead to interesting and important results no matter what stage you are at in your academic career. CS, being a relatively young field, still holds many opportunities for discovery for a motivated researcher. Keep up the good work...
... and, yeah, that's probably for the best.
In any case, would you be aware of some instances in which it would be hard to find a clique in a graph? I was thinking of coming up with a scheme whereby I could generate short (a few clauses and a few variables) SAT expressions that have exactly one satisfying assignment and then use the graph as a benchmark.
Not sure off of the top of my head where to point you to find a specific example of this, but I'll guarantee they are out there. It's been a few years since I played with this stuff. I do like your idea of creating your own example, at least to start with. That will be educational in itself.
>would you be aware of some instances in which it would be hard to find a clique in a graph
Obviously a graph with many 'just' sub-optimal cliques would be a pain in the ass to deal with. Generate a maximal clique and then many 'just' smaller clique (max-1, max-2, etc) and glue them randomly together or partially overlap them.
Are you familiar with Hamming graphs? They seem like a principled approach at what you mention, but they too suffer from the issue of not being easily generated in a small number of nodes. https://en.wikipedia.org/wiki/Hamming_graph
Most of my self-generated instances have been surrounding many sub-optimal (and optimal) cliques 'glued' and transposed on top of one another. They have been the more challenging instances; I'll say that.
I'm friends with quite a few people in other STEM disciplines (in fact, we share a lot of classes). I even have pure mathematics friends who share interests with me.
Lucky, my undergraduate institution is more geared towards preparing its students for graduate-level research/coursework; we actually take the same classes as the PhD and Master's students.
This. Even if computer science were utterly useless, it's definitely a field that can produce a living, and there's nothing wrong with somebody having a genuine interest in what he or she studies.
Given how practical and pervasive computer science is now, though, I really don't see a problem with somebody enjoying and pursuing it. The problem given in the OP is a major one in the intersection of computer science and mathematics whose answer relates to one of the biggest mathematical problems we know of. More power to anybody wanting to pursue computer science for genuine reasons, I'd say.