1901:? I think separating out algorithms from hardness makes sense as a way of organizing the material (more sense than splitting cliques from independent sets) but that split could be into separate articles rather than as now separate sections of the same article, and the article we have now is already large and unwieldy. As for calling it "hardness" rather than "lower bounds", I have no objection to that. I do think the hardness bounds are important, though (at least the inapproximability and FPT ones) and wouldn't want to see them tacked on as a disconnected appendix to an article that's mostly about algorithms. As for GA: I think we have enough material here, written at a high enough level of quality, that we should seriously consider this, but a GA review is mostly going to cover low-level issues of grammar and wording; we need to find the best organization for the material ourselves first. —
2014:(not very interesting on a sequential computer but has been studied in parallel algorithms), (4) list all maximal cliques, (5) find a maximum clique, (6) find a minimum-sized maximal clique (more often studied in the complementary form of finding a minimum independent dominating set), (7) count the cliques of a given size (e.g. my WADS'09 paper with Spiro on counting triangles), (8) list all maximal cliques (or maximal independent sets) whose size is smaller than some bound (e.g. my older paper "Small maximal independent sets and faster exact graph coloring"). In addition I could imagine that there might be algorithms for counting maximal cliques or maximum cliques more quickly than listing them all — listing and counting are in general two different things — but I don't know of any published research on that variant. —
1995:
problem. Each seems to have its own set of algorithms, and hardness results. In that order, the hardness results would be NP-completeness, inapproximability results, and #P-completeness. We do have a lot more to say about the decision problem, since it is well-studied, and is well-studied in several restricted settings: fixed parameter tractability, special graph classes, etc. So I would propose a structure which first deals with the decision problem, including all algorithms for fixed size, max clique, special graph classes, FPTs, etc. and includes all relevant hardness results about the decision problem. This section might be the largest of all. Then a section on the approximation problem, then a section on the counting problem, and then other models.
953:). There are many seminal positive and negative results, and numerous reductions to and from maximal (or near-maximum) independent sets. To someone studying distributed computing, independent set problems are as central as, say, SAT and linear programming together to someone studying polynomial-time computation. On the other hand, I can't say much about clique-finding algorithms from the perspective of distributed computing – it isn't even obvious how one should formulate a "clique problem" so that it'd be interesting and relevant from the perspective of distributed computing. Hence if we try to cover
256:
246:
228:
195:
1122:
1074:"Parameterized complexity is the complexity-theoretic study of problems such as finding k-cliques in graphs that are naturally equipped with a small integer parameter k, and for which the problem becomes more difficult as k increases": I guess this should be parsed "... study of problems ... that are naturally equipped with ...", but it's easy to read it "... in graphs that are naturally equipped with ..." Is it just me or should we rephrase this somehow?
3319:"Karp's NP-completeness proof is a many-one reduction from the Boolean satisfiability problem for formulas in conjunctive normal form, which was proved NP-complete in the Cook–Levin theorem." Ugh! Too much jargon in one sentence. Although the sentence is understandable after following all the links, it is very difficult for a general reader. This might be another case where the same material would be ok if split into more than one sentence.
1752:
424:
34:
186:
347:
930:. One issue is whether we should choose a name such as the one we have now that refers only to cliques, or whether the name should also include independent sets (in which case, there's more material that needs to be added to the article, as the clique and independent set problems are quite different in most graph families and I omitted anything that was only about independent sets in my rewrite). —
326:
2570:
1490:
algorithm", it just says "running time". There are algorithms with better worst case running times known (though still with an exponent that's linear in k). And for some algorithms, what we list as the running time isn't necessarily the actual running time of the algorithm even when considered on worst case inputs: it's the best upper bound that we know how to prove, a quite different thing. —
3442:
3406:
3371:
3340:
3316:
3285:
3251:
3170:
3138:
3113:
3032:
3000:
2969:
2938:
2778:
2770:
2738:
2710:
120:
1837:(though not necessarily under that title) and 2. I’d like the structure to abandon the current Algorithm—Lower bounds dichotomy (reasons include (a) the lower bounds are mostly hardness results, not lower bounds, (b) some of the issues don’t really benefit from splitting along this fault line, such as circuit complexity, decision trees, the yet-to-be-written section on counting, etc.).
1213:
1516:
it is and, if necessary, a general template explanation or a simple foonote could be given. I see more issues with packing in too much information (e.g. parametrization) or vagueness (e.g. deterministic versus expected or heuristic running time). An example of these issues: . Although I find an arbitrary policy for these problems sufficient for making infoboxes an asset.
1999:
for maximum clique is like O(1.2^n), we give the NP-completeness proof, which explains why the best known algorithm is exponential time. The other sections are fine. But if this proposal will make one section very large compared to the others, or if this view of combining hardness+algorithms isn't shared by others, I'm fine with Thore's proposal above. --
829:
vertices u in A and v in B such that u is adjacent to every vertex in B and v is adjacent to every vertex in A. Then A is contained in A union v and B is contained in B union u, so neither are maximal, but no further merging can be done. Merging in some intelligent order may work, but the algorithm as stated does not necessarily find any maximal cliques.
3445:"However, an invalid proof may sometimes mistakenly be accepted, as long as the probability that a checker makes a mistake of this type is low." The logic of that statement escapes me. If the probability is high then an invalid proof may still be accepted. So surely this just says an invalid proof may sometimes be accepted without qualification?
2599:
902:, and that’s something we clearly need to rectify. One solution is to let the current algorithm (under the current headline) describe both interpretations, but I can’t see how that would work. An easy alternative is to just fix the redirect. That being said, I am mildly in favour to a more descriptive, and exclusive, article title.
2542:
interpreting it. So the lexicographic ordering not only prevents duplicates from appearing, as it states in the next paragraph, but also prevents non-maximal cliques from appearing, since lexicographic maximum implies maximal. I'll try to rephrase this section when a get a firmer grasp on how the algorithm actually works. --
2503:
2525:
The article says that, given the maximal cliques in G\v, the maximal cliques in G are these plus those sets formed from them by adding v and removing nodes not connected to v. Let G={12,13,23,24,34,35,45}. Then the maximal cliques in G\{5} are {123} and {234}. If I add 5 to {123} and remove the nodes
2142:
Please, what does "m" now stand for exactly in this context? The number of edges of vertices? It is crucial to make this clear, as in a later paragraph it says "...to find triangles in time O(n2.376), which may be faster than O(m3/2) for sufficiently dense graphs.". It makes quite a difference if one
2115:
Results that only work for ind. set., like ind. set. on planar graphs, or the distributed computing version should be elsewhere. As for structure, I would suggest a problem-oriented structure, where we list a problem, like "list all maximal cliques" and then present algorithms and hardness results. --
2054:
Together with the centralised algorithms and hardness results when we discuss the relevant problems. (I think the most relevant problems are "find a maximal independent set" and "find a large independent set", both in general graphs and in special graph classes. I'm worried that covering distributed
1699:
Perhaps there should be more explanation on why the algorithim for finding a single maximum clique runs in linear time? I cannot immediately see why. Whether you store a graph as an adjacency matrix or an adjacency list the cost of constructing the sub-graph on K vertices is O(K^2) so one cannot just
1169:
What I aim to convey is what the problem is about, what it models, how an algorithm could look, and what kind of phenomenon the theory tries to address. I think the brute-force illustration is pretty informative; it should be clear both what we’re looking for, what the algorithm is doing, and that it
925:
I'm not opposed to changing the name. The imperfection in those titles, to me, is that they omit the complexity theoretic side of research on the clique problem, since that's less about finding a clique and more about not finding a clique. One possibility, though it doesn't excite me very much, would
3489:
occur when there is a low probability that a checker makes such a mistake. Clearly that interpretation is illogical and not correct, but it hides the correct meaning. This leads me on to the meaning of the following sentence: "An instance of the satisfiability problem should have a valid proof if
3173:
The mention of adiabatic quantum computing concerns me on two counts. Firstly, as far as I am aware, this is still largely speculative, but you wouldn't know that from what is written (or by following the wikilink for that matter). Secondly the ref is a preprint; has this actually been published?
2013:
Re "I think there are 3 different clique problems": There are many more than three algorithmic versions of the problem about which one can find published papers: (1) yes/no, is there a clique of a given size, (2) list all cliques of a given (typically constant) size, (3) find a single maximal clique
1489:
I'm not a huge fan of infoboxes, because it is difficult to convey any nuance in them. For instance, under "decision problem" "running time", you have O(n^k k^2), the running time of the most naive brute force algorithm for the problem. But it doesn't say "running time for the most naive brute force
1469:
once, and maybe we want one here as well. In truth, I still don’t know if this kind of thing is a good idea. It’s certainly a quick way to get some information about the problem (for example, I’ve always found the compendia like Garey–Johnsson or
Crescenzi et al. actually useful), but there are lots
3205:
Ok on the source then, but it still remains the case that this is a speculative proposal, no? Nobody has actually found cliques using quantum computers have they? Does a quantum computer capable of doing it actually exist? That's what troubles me about it; it just appears in a list of methods as
2114:
My viewpoint, in short, is the following: This article should only contain results related to cliques -- maximal cliques, counting cliques, listing cliques, decision trees, monotone circuit complexity of max clique, etc. Results that work for clique and ind. set. should be present in this article.
2085:
Since I supported the proposal to have only clique-related problems in this article, I would choose option 3. There is a lot of literature on maximal independent sets (and its connection with vertex coloring), which would make a fine addition to an independent set article. Adding it here would make
2028:
Fair enough, we can have more sections for the problems. I guess my main point is that for a given problem, I would prefer an organization where the best algorithm and hardness result are stated together, rather than in different parts of the article. Organizing results by the problem solved, i.e.
1998:
In short, all I'm saying is that
Algorithms + Special graph classes + Hardness, in the suggestion above should be merged into one section with the theme of "decision problem" and hardness results should be presented along with the best algorithms. For instance, after stating that the best algorithm
1842:
These proposals are connected—for example, I’d want a section each on Clique algorithms for special graph classes and
Independent set algorithms for special graph classes, rather than the current awkward things like “finding cliques in the complement of bipartite graphs”—but need somewhat more time
1736:
I played around with drawing a decision tree, mainly because I think it’s a very accessible model of computation and makes a pretty picture. (Possibly too large.) Something is messed up in the SVG rendering (the file look alright when I let Safari’s SVG engine render it.) Any pointers to what I can
1515:
What David
Eppstein explained is precisely how I would interpret the "running time" field -- the best known (proven) upper bound on running time that someone has taken the time to add to Knowledge, with an somewhat arbitrarily chosen level of detail (e.g. big-oh). I see no problem with the field as
828:
This section seems to state that arbitrarily merging cliques will always find a maximal (as opposed to maximum) clique. This is not true. Consider 2 disjoint cliques A and B produced by merging. Assume that there is some edge missing between A and B so that they cannot be merged, but that there are
3178:
Huh? The adiabatic reference, by Childs Farhi
Goldstone and Gutmann, is a journal paper, and always has been listed as such. It had a link to the preprint version for convenience since most readers aren't going to be able to access the official journal version very easily. But I added the link for
2744:
This is a summarized version of the sourced claim in the first paragraph of subsection "Listing all maximal cliques" that "this provides a worst-case-optimal solution to the problem of listing all maximal cliques". Just before that claim, I added a new clarification "matching the number of cliques
1994:
a separate section is a nice idea. That makes it clear that the rest of the article is about algorithms on real computers (or Turing machines). As far as the other secions go, I think there are 3 different clique problems, the decision problem, the optimization problem and the enumeration/counting
1861:
I agree about the lower bound vs algorithms dichotomy. I don't like this split either. For example, instead of splitting the best algorithm and best bounds known for the decision problem, I would prefer a section on the decision problem which gives the best algorithms and gives the NP-completeness
1511:
page that would be vague for someone who just wants the constant). Whoever wants to know more can read the full wikipedia article, go for the technical paper abstracts, or the papers themselves; whichever level of detail they wish to work on. I personally find the highly-condensed resources that
3640:
Feige et al. is part of the same line of research, roughly a year after the earlier results reported in the New York Times article. It is the first to apply that line of research to the clique problem. Probably the "reported in the NYT" claim should be removed, because it is not about clique.
3484:
My problem is that I don't think the sentence is quite saying that semantically. If I have understood your reply correctly, the meaning is supposed to be that it can be acceptable for the algorithm to return some false positives provided the probability of doing so is low. What the sentence
3461:
I don't understand your confusion here, to be honest. What part of the fact that the checker behaves randomly, that it is required that this random behavior should cause it to have low probability of making certain kinds of mistakes, and that other kinds of mistakes are strictly forbidden, is
2047:
Where would we cover the distributed computing aspects: distributed algorithms for finding independent sets, lower bound results for these problems, the connection to distributed graph colouring, other applications of distributed independent set algorithms, etc.? Some possibilities might be:
1807:
Since this article is in pretty good shape right now, has pictures, very detailed references, and at least a few editors actively editing it in the last few days, is anyone up for improving this article further and nominating it for GA-class? (Maybe it is more useful to bring 2 articles up to
1564:
I think the infobox can be put in, it does present a lot of useful info in short. I like infoboxes that present the hardness of approximation result along with the best known approximation algorithm so one can compare them. W-completeness might be more detail than needed in an infobox though.
3042:
It was not part of the input in the immediately preceding sentence, which says "whenever k is a fixed constant". Fixed constant means that it is hardcoded into the algorithm rather than being part of the input. I'm at a bit of a loss on how this could be phrased any more clearly; do you have
2541:
I think I've figured this out. The words "a maximal clique C" in "... each maximal clique in G that does contain v can be formed from a maximal clique C in G \ v by adding v and removing the non-neighbors of v from C," should read "some maximal clique C", not "any maximal clique C" as I was
2526:
not connected to 5 then I get {35}, but this is not maximal in G since it's contained in {345}. I'm guessing that what the article should say is that the cliques of G are the cliques of G\v plus sets formed by adding v to the cliques of G(v), where G(v) is the set of nodes connected to v. --
1666:. Since I put quite an effort into understanding the tiny details of the algorithm, I'd add it to references so others don't have to. Can some one please advise me if that would be appropriate? (I'm not a regular Knowledge contributor, so I'm not sure about the rules yet.) Here is the link:
1160:
represent mutual acquaintance. To find a largest subset of individuals, all of which know each other, one can systematically inspect all subsets, a process that is too time-consuming to be practical for instances with more than a few dozen individuals. Despite many attempts to find better
720:
I removed the proof that maximum clique is NP-complete and replaced it by an appeal to the NP-completeness of independent set. It was a good proof, but I think it's easier to go through independent set, because there's a lot less edges to talk about filling in. Admittedly the proof on
1044:. The Independent set articles can link to this article for common algorithms. That way we can still call this article "clique problem", and let it be a comprehensive article which has everything there is to know about cliques (from an algorithms and complexity point of view). --
445:
1703:
Can someone explain more details of this algorithim and hy its running time is O(n) for non-sparse graphs? (I can see why it is O(n) for sparse graphs). Alternsatively maybe the author means linear in the size of the graph (so vertices ^ 2) in which case I can see the result.
2277:
Hi. Whatever the worst case exactly is, "n choose k" is equal to n!/(k!*(n-k)!) and hence much worse than O(n) even if k=1. Even worse than O(n^k), which is mentioned in the article, so I don't see why it says that there. Can someone explain that or change the paragraph?
1700:
look at sub-graphs. The obvious implementation of the algorithim requires finding the interesection of two sets of integers. If the sets are stored as lists this is O(n+k) and even if they are stored as hash tables its O(min(n,k)) where n,k are the sizes of the sets.
3542:
The external links tool is showing a number of deadlinks (three 404 errors page not found, one server not found, and one 301 error redirecting problem.) While deadlinks are not a cause to fail a GA, that's quite a lot and you might want to do something about them.
2941:"...reported at the time in major newspapers" is cited to the NYT, but that paper does not say it was reported in other papers. We need either a source saying it directly, cites to several different papers carrying the story, or just say it was reported in NYT.
1506:
I think the infobox serves to present the abstracted common properties of problems (like approximability) in a structured way. The most important information here can be fairly condense ("approximation factor: 2" versus several sections of text on the
3462:
unclear? Why should the fact that a mistake can sometimes happen allow use to forget about the probability of it happening and just say that mistakes can happen without qualification? What needs to be changed here to make this less confusing? —
1519:
Some fields that I am uncertain about are "Input&output" (could be lengthy and perhaps better given in text), "W-complete" in "Complexity" seems like too much detail (we could add a lot more), and "Garey-Johnsson" - is this really useful?
2110:
Since this discussion stopped (more than a month ago) before reaching a conclusion that we all agree with, I thought I should start the discussion again. So the question is, what is the scope of this article, and how should we structure it?
1170:
would take a long time. An attractive alternative would be instead to illustrate the behaviour of a poly-time algorithm on a restricted graph class; the message here would then have to be that in general, we can’t get this approach to work.
1116:
The topic of this article lives on the borderline of what might want to be accessed by a general audience, so I suggest we at least try to give a non-technical introduction in the article head. Here’s just an idea, to get the ball rolling.
1077:"due to the fact that the clique number takes on integer values and is NP-hard to compute, it cannot have a fully polynomial-time approximation scheme": Strictly speaking, shouldn't it be "small integer values" instead of "integer values"?
2302:
1070:
Figure caption: "Adapted from Sipser." It'd be nice to have a proper citation; we don't have Sipser in the list of references. I guess it refers to the textbook "Introduction to the Theory of
Computation", but I don't have it here
768:, your algorithm runs in O(n^3) - either you deserve $ 1million prize or the algorithm is wrong. You might try on one of the larger examples given in the link at the bottom of the article and see whether you find the known answer.
1862:
proof. Similarly, a section on the approximation problem, which states the best factor achievable and the best hardness result. Some topics are already covered like this, like decision tree complexity and circuit complexity.
1823:
I’d be eager to hear David’s opinion on this, he’s got a few GAs under his belt. But in principle I think the article deserves a much higher rating and in many respects proudly stands as an example of what this medium can
1618:
Since there is so much information about listing all maximal cliques, the article should say somewhere that finding a single maximal clique is really easy (linear time). I don't know where to put this information though.
3119:
Because it means that the ordering makes a big difference in whether it's possible to list the cliques efficiently. Edited to clarify what NP-hard means in this case (no polynomial-delay algorithm exists unless P = NP).
944:
Indeed, approximation algorithms in bounded-degree graphs are a fairly natural example... And let's not forget other models of computation. From the perspective of distributed computing, independent sets and cliques are
3141:
The sentence beginning "In particular, the planar graphs, and more generally..." is very hard to parse. I had to read it several times before understanding. Can the statements be broken into separate sentences?
2717:. I know that only goes to the glossary, but that could be a good thing for a reader unfamiliar with the subject. It points them early on to a central place where they can get a quick def of unfamiliar terms.
978:
I think expanding the scope of the article is probably not what we need to do right now. Also, based on the large recent expansion, it looks like we're set to get a link to this article from the front page via
3006:
It was referring to "the algorithm described above" (in the same paragraph), and describing it as a greedy algorithm. But I moved the greedy link earlier in the paragraph in hope of making this clearer.
3675:
1512:
Thore listed to be useful and I lament that
Knowledge does not serve that purpose, especially since the general repositories that exist are rarely, if ever, updated and should exist in wiki format.
2086:
this article too long. Also, the distributed algorithms are really specific to finding an independent set (and not clique), so I think it's fair to put all those results in a different article. --
1782:
If you look closely, I think the arrows don't look right. But when I render it in
Firefox, it looks great. I think this is what Thore Husfeldt is referring to. See this blown up png for instance:
1036:
I think the last suggestion is reasonable. Let this article be only about cliques (and things that are common to clique and independent set). Things that only apply to independent sets, can go in
2138:"In a graph with m vertices..." and in the same paragraph "...the time for this algorithm is proportional to the arboricity of the graph (a(G)) times the number of edges, which is O(m a(G))".
469:
1165:
for this problem, no significantly better approach is known, and much of the theory about the clique problem is devoted to establish its computational hardness in many models of computation.
308:
3346:
Done. My usual tendency is just to spell them all out instead of using abbreviations, but I felt that three repetitions of this long phrase in a single paragraph would have been too much. —
3700:
609:
3174:
I'm not saying don't use preprints as refs, but making solid claims about speculative subjects on the basis of them is a bit iffy. Maybe it could be reworded with "<author: -->
2263:
You are right, my assumption was wrong: k=1 is definitely not the worst case (that's around k = n/2). I guess, I should remove this paragraph. Thanks for pointing this out... --
2228:
526:
464:
3077:
is not a constant..." would have made it clear to me on first reading. I'm not sure how important it is to say "part of the input", but both could be said if necessary "when
3527:
Thanks for the thorough listing of issues! I plan to work on these over the next week or so, responding to them individually; I'll ping you again when I think I've done. —
45:
1833:
is an issue for GA-ing, and I would like to propose at least two larger changes to this article. So ’d like to wait. To tip my hand: 1. I’d like this article to be about
3725:
3670:
397:
387:
1893:
So in this proposed revision, would you have a separate article for hardness results? Or would you include all the current material as well as the algorithmic parts of
891:. Both terminologies can be found in the literature, but the algorithmic interpretation of course wins a google fight, though Mathworld uses the Ramsey interpretation.
3690:
2902:
2029:
listing max cliques or decision version of max ind. set on planar graphs, (rather than the nature of the result — algorithmic or hardness) seems more natural to me. --
2868:
1972:(never mind the ordering and the titles) So basically it’s about moving some of the current subsections out of the current two-section Upper/Lower bound structure.
3705:
2637:
2498:{\displaystyle {\binom {n}{k}}={\frac {1}{k!}}n\cdot (n-1)\cdot (n-2)\dots (n-k+1)\leq {\frac {1}{k!}}n\cdot n\cdot n\cdot n\dots n={\frac {n^{k}}{k!}}\leq n^{k}.}
3730:
3715:
2972:"The clique decision problem is not of practical importance; it is formulated in this way in order to ..." Is this just a reformulation of the k-clique problem?
2604:
302:
3291:
Feige wouldn't really be a good source for this sort of evaluation of his own work. But I found and added a recent (2015) publication that says the same thing. —
2975:
The problems are different because they have different outputs (a clique vs a boolean). The sentence above the bullets does say that they are closely related. —
1755:
A decision tree of depth 6 for detecting a 3-clique in a 4-vertex graph. No better constructions are possible, in the sense that it matches the lower bound of
1534:
I agree on the Garey–Johnsson. It’s there because the original motivation to cook up an infobox in the first place is that I’d like
Knowledge’s entries to be
3622:
I followed The NY Times reference in the article and I don’t think it refers to the Feige et. al. article. The NYT refers to a series of papers listed here
2627:
199:
3720:
363:
571:
949:
different things. On the one hand, finding a maximal independent set is a truly central and classical problem in the field (and also closely related to
3685:
3003:"the one found by the greedy algorithm described above". This is the first mention of greedy algorithm, so it is unclear what this is referring to.
3695:
697:, which is a commonly used name that is more accurate and specific. I put a redirect in the way, but I'll take care of the move if there's consent.
141:
1720:
1783:
545:
957:
computational aspects of cliques and independent sets in one article, at least from this perspective it'd be strange if the article was called "
3710:
1096:
I handled your second and third points. I'll let Thore address the first since he drew the figure and knows better than I where it came from. —
410:
354:
331:
278:
1601:
1542:, so I started from that framework, minus the comments. I admit that the Garey–Johnsson number is the clearest example of my chemistry envy.
634:
3626:
1453:
2609:
2676:
2285:
2154:
1685:
983:
some time in the next week or so, so if we do make a decision on a better name we should probably hold off on changing it until later. —
672:
I thought a clique was a fully connected sub-graph? The way it is described here makes me think a clique is two adjacent vertices... --
517:
63:
3288:"Although the approximation ratio of this algorithm is weak, it is the best known to date" Is this sourced to Feige? If not, where?
498:
269:
233:
3680:
3665:
2741:"worst-case optimal time" (or even "optimal time") is not a phrase found in the article body, nor is it explained or wikilinked.
2632:
590:
51:
1924:(exact algorithms for fixed size and maximum cliques) these are agnostic about whether we look for cliques or independent sets
3378:
2059:
1894:
1037:
1007:
1003:
2583:
Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.
3613:
Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.
2051:
A subsection on distributed algorithms in the "Other models of computation" section. (Might be a fairly long subsection.)
555:
436:
208:
3343:"CNF" If the article is to use abbreviations, it should give them in brackets after the first use of the term in full.
2505:
It's a crude estimate but it's always valid and when k is a constant then it's within a constant factor of the truth. —
2792:
565:
479:
600:
362:
related articles on
Knowledge. If you would like to participate, please visit the project page, where you can join
2788:
I added explanations for the first use of each notation. It turns out that   is far too wide but that
1716:
627:
3646:
3571:
3532:
3511:
3467:
3429:
3386:
3351:
3327:
3296:
3265:
3227:
3188:
3150:
3125:
3089:
3048:
3012:
2980:
2949:
2918:
2750:
2725:
2510:
2253:
2019:
1977:
1906:
1848:
1773:
1742:
1643:
1638:
could form a section, consisting of the (easy) algorithm for finding one, and the listing/enumeration results.
1547:
1495:
1479:
1189:
1175:
1101:
988:
935:
927:
915:
680:
Pairwise adjacent means every pair of vertices in the set are adjacent. This is equivalent to your definition.
3630:
1872:
About the other sections you want to add, that's great. I'm in no hurry at all, and of course we don't have a
2158:
1681:
3594:
3549:
3496:
3451:
3212:
3116:"...although the reverse of this order is NP-hard to generate". Interesting, but why is that relevant here?
2714:
2692:
2670:
2655:
2289:
2063:
1898:
1712:
1041:
1011:
999:
734:
722:
103:
808:
I'm going to go ahead and remove it for now. If anyone wants to restore it, please note the reference. --
2651:
694:
1152:, i.e., a set of elements that are pairwise connected. An example is a social network, where the graph’s
1916:
I would have hoped to have had more time for a more though-out proposal, but the sections I envision are
1677:
1470:
of problems about what information should go into such a box in the first place. Maybe its just spam or
1153:
536:
214:
134:
33:
834:
813:
798:
255:
2773:
There needs to be a link to big-O notation on first use. Likewise big-theta, big-omega, little-o etc.
3179:
those who can. (Also, with a notable co-author, it might well pass the "recognized expert" clause of
2281:
2268:
2264:
2237:
2233:
2150:
1708:
1673:
2194:
755:
3642:
3567:
3528:
3507:
3463:
3425:
3382:
3347:
3323:
3292:
3261:
3223:
3184:
3146:
3121:
3085:
3044:
3035:"When k is part of the input to the problem, however, the time is exponential." In what sense was
3008:
2976:
2945:
2914:
2746:
2721:
2506:
2249:
2015:
1973:
1902:
1844:
1769:
1738:
1639:
1543:
1525:
1491:
1475:
1185:
1171:
1157:
1097:
984:
931:
911:
119:
1865:
I also agree about what the article should be about, but the article title should probably not be
1663:
1125:
The brute force algorithm finds a 4-clique in this 7-vertex graph (the complement of the 7-vertex
830:
277:
on Knowledge. If you would like to participate, please visit the project page, where you can join
3589:
3561:
3544:
3491:
3446:
3207:
2687:
2666:
1873:
261:
245:
227:
3490:
and only if it is satisfiable." How does that square with the possibility of false positives?
1121:
673:
455:
55:
3255:
2547:
2531:
2174:
2120:
2091:
2034:
2004:
1881:
1813:
1790:
1751:
1624:
1570:
1431:
1049:
849:
507:
359:
164:
2876:
1932:
algorithms for cliques, algorithms for indpendent sets. This could also be a subsection of
2781:
The brackets following the big-O etc butts right up. They need a space, or a thin space (
1184:
Your proposed new lede looks good to me. I agree that the existing one is too technical. —
707:
2844:
1539:
1959:(listing maximal cliques, #cliques is #P-complete, but FPRASable for some special cases)
2076:
1768:
What's different between what it looks like here and what it's supposed to look like? —
1521:
1466:
1142:
1086:
1023:
1015:
966:
958:
950:
899:
581:
423:
168:
157:
152:
3623:
446:
Requested articles/Applied arts and sciences/Computer science, computing, and Internet
3659:
3506:
Ah, I see. I hadn't noticed that ambiguity. Reworded, splitting into two sentences. —
3180:
895:
738:
726:
698:
681:
2055:
computing aspects in different places might make the text more difficult to follow.)
2569:
1508:
809:
794:
1667:
1659:
3414:
2543:
2527:
2170:
2116:
2087:
2030:
2000:
1877:
1809:
1786:
1620:
1566:
1289:
1130:
1045:
845:
765:
274:
3441:
3405:
3370:
3339:
3315:
3284:
3250:
3169:
3137:
3112:
3031:
2999:
2968:
2937:
2777:
2769:
2737:
2709:
167:
was first studied as a way to find groups of people who all know each other in
1808:
B-class, than one up to GA-class, so perhaps that isn't such a great idea.) --
1126:
251:
1006:, explain the computational aspects that are specific to independent sets in
864:
Maybe this is a good time to think about what this article should be called?
751:
2072:
1212:
1162:
1082:
1019:
962:
488:
128:
2658:. The edit link for this section can be used to add comments to the review.
346:
325:
1876:. I just mentioned this GA-class idea to get everyone's opinions on it. --
881:
Algorithmic aspects of finding a large complete subgraph or its complement
1145:
160:
3650:
3634:
3599:
3588:
Yes, that's done, promoting to GA. A pleasure doing business with you.
3575:
3554:
3536:
3515:
3501:
3471:
3456:
3433:
3390:
3355:
3331:
3300:
3269:
3231:
3217:
3192:
3154:
3129:
3093:
3052:
3016:
2984:
2953:
2922:
2754:
2729:
2697:
2680:
2551:
2535:
2514:
2293:
2272:
2257:
2241:
2178:
2162:
2124:
2095:
2080:
2038:
2023:
2008:
1981:
1910:
1885:
1852:
1843:
than I can devote to them in the next few days, so we’ll have to wait.
1817:
1794:
1777:
1746:
1724:
1689:
1647:
1628:
1574:
1551:
1529:
1499:
1483:
1457:
1381:
1347:
1193:
1179:
1105:
1090:
1053:
1027:
992:
970:
939:
919:
853:
838:
817:
802:
781:? Some special cases may be solved in less than exponential time. For
758:
710:
701:
3206:
if it is a real thing. I think some kind of caveat would be in order.
3183:, but as a journal paper I don't think we need to worry about that.) —
1471:
2247:
Why should you assume k = 1?? It's certainly not O(n) when k : -->
2130:
What does "m" stand for exactly here? number of edges or vertices?
1441:
1149:
980:
867:
Currently, there are at least two problems I know that qualify as
2143:
assumes the number of edges to be m or to be n in this scenario.
778:
2191:
I think it's a combination (select k vertices from n), that's:
725:
isn't all that nice, and any improvement to it would be great.
564:
Find pictures for the biographies of computer scientists (see
179:
15:
1018:
for everything else. That way no changes are needed here. —
2745:
that might need to be listed" for why this is optimal. —
96:
3676:
Knowledge Did you know articles that are good articles
1869:. I can't think of a good name off the top of my head.
1202:
2879:
2847:
2305:
2197:
1600:
harvtxt error: no target: CITEREFNesetrilPoljak1985 (
754:
I can't be sure it's correct, I need some comment. --
777:
Can anyone find a source for the 3-clique algorithm
358:, a collaborative effort to improve the coverage of
273:, a collaborative effort to improve the coverage of
3624:
https://tc.computer.org/tcmf/test-time-1990-awards/
3485:actually says (apparently) is that false positives
844:
It seems wrong indeed. I've removed the passage. --
2896:
2862:
2497:
2222:
951:Graph coloring#Parallel and distributed algorithms
470:Computer science articles needing expert attention
307:This article has not yet received a rating on the
2322:
2309:
2214:
2201:
2169:It's the number of edges. I've fixed that now. --
127:A fact from this article appeared on Knowledge's
2230:, that means O(n) (the worst case if k = 1 is n)
998:I think a reasonable approach would be to merge
3701:Knowledge level-5 vital articles in Mathematics
2134:In the section "Cliques of fixed size" it says:
1662:of the Tsukiyama et al. algorithm along with a
2826:— {{math|{{italics correction|''O''}}(''n'')}}
1668:http://c0de-x.com/how-to-find-maximal-cliques/
1596:
610:WikiProject Computer science/Unreferenced BLPs
61:If it no longer meets these criteria, you can
3081:is not fixed and forms part of the input..."
1133:(7,4)=35 4-vertex subgraphs for completeness.
8:
3163:Finding maximum cliques in arbitrary graphs
1412:The number of inclusion-maximal cliques in
527:Computer science articles without infoboxes
465:Computer science articles needing attention
3039:not part of the input in the prior cases?
2587:
910:sound good (but not quite perfect) to me.
752:http://insaint03.cafe24.com/clique-en.html
431:Here are some tasks awaiting attention:
405:
320:
222:
75:
28:
2878:
2846:
2486:
2463:
2457:
2412:
2331:
2321:
2308:
2306:
2304:
2213:
2200:
2198:
2196:
1867:Algorithms for clique and independent set
1835:Algorithms for clique and independent set
3726:Mid-importance Computer science articles
3671:Engineering and technology good articles
1750:
1540:Maximum Clique entry in the Viggopendium
1120:
46:Engineering and technology good articles
3691:Knowledge vital articles in Mathematics
2883:
2618:
2590:
1589:
1538:as useful and informative as, say, the
1156:represent individuals, and the graph’s
322:
224:
3706:GA-Class vital articles in Mathematics
3084:Ok, copyedited per your suggestions. —
2906:(the LaTeX equivalent of  )
2521:Tsukiyama algorithm stated incorrectly
2189:It says, "there are O(n) subgraphs..."
372:Knowledge:WikiProject Computer science
3731:WikiProject Computer science articles
3716:Unknown-priority mathematics articles
3410:0" I'm not seeing a definition of ε.
3374:"Supergraph" needs a link or a gloss
3175:has suggested that..." or some such.
824:Problem with maximal clique heuristic
375:Template:WikiProject Computer science
7:
2798:does the job. Here is a comparison:
2579:The following discussion is closed.
352:This article is within the scope of
267:This article is within the scope of
185:
183:
3222:Added "that have been suggested". —
2839:— {{math|''O'' (''n'')}}
213:It is of interest to the following
3721:GA-Class Computer science articles
2313:
2205:
546:Timeline of computing 2020–present
156:of programming a computer to find
14:
1265:contain a complete subgraph with
572:Computing articles needing images
287:Knowledge:WikiProject Mathematics
54:. If you can improve it further,
3686:Knowledge level-5 vital articles
3609:The discussion above is closed.
3440:
3404:
3369:
3338:
3314:
3283:
3249:
3168:
3136:
3111:
3030:
2998:
2967:
2936:
2776:
2768:
2736:
2708:
2568:
1211:
1129:) by systematically checking all
737:now. Should be somewhat better.
422:
345:
324:
290:Template:WikiProject Mathematics
254:
244:
226:
193:
184:
118:
32:
3696:GA-Class level-5 vital articles
2993:Finding a single maximal clique
2713:You might consider wikilinking
2223:{\displaystyle {\binom {n}{k}}}
2185:Cliques of fixed size algorithm
873:Algorithms for finding a clique
392:This article has been rated as
2944:Changed to just say the NYT. —
2891:
2885:
2857:
2851:
2536:17:24, 19 September 2013 (UTC)
2406:
2388:
2382:
2370:
2364:
2352:
2060:Independent set (graph theory)
1895:Independent set (graph theory)
1038:Independent set (graph theory)
1008:Independent set (graph theory)
1004:Independent set (graph theory)
779:mentioned in version 111018197
706:Seems like a reasonable idea.
42:has been listed as one of the
1:
3711:GA-Class mathematics articles
3537:20:04, 29 December 2016 (UTC)
3457:16:23, 29 December 2016 (UTC)
3322:Split into three sentences. —
2698:21:38, 26 December 2016 (UTC)
2681:21:38, 26 December 2016 (UTC)
2552:21:17, 25 November 2013 (UTC)
2273:14:42, 28 November 2010 (UTC)
2258:23:37, 21 November 2010 (UTC)
2242:23:16, 21 November 2010 (UTC)
2125:20:57, 15 February 2010 (UTC)
2081:19:39, 30 December 2009 (UTC)
2039:02:28, 28 December 2009 (UTC)
2024:01:27, 28 December 2009 (UTC)
2009:21:52, 27 December 2009 (UTC)
1982:21:28, 27 December 2009 (UTC)
1911:20:51, 27 December 2009 (UTC)
1886:20:40, 27 December 2009 (UTC)
1853:20:19, 27 December 2009 (UTC)
1818:19:59, 27 December 2009 (UTC)
1795:17:41, 23 December 2009 (UTC)
1778:17:37, 23 December 2009 (UTC)
1747:14:03, 23 December 2009 (UTC)
1648:13:54, 23 December 2009 (UTC)
1629:14:47, 21 December 2009 (UTC)
1575:05:23, 26 December 2009 (UTC)
1552:16:29, 21 December 2009 (UTC)
1530:16:15, 21 December 2009 (UTC)
1500:19:30, 20 December 2009 (UTC)
1484:19:22, 20 December 2009 (UTC)
1313:Clique number, Maximum Clique
1194:17:49, 20 December 2009 (UTC)
1180:17:45, 20 December 2009 (UTC)
1106:20:32, 19 December 2009 (UTC)
1091:19:24, 19 December 2009 (UTC)
1054:21:08, 30 December 2009 (UTC)
1028:11:30, 19 December 2009 (UTC)
993:08:15, 19 December 2009 (UTC)
971:19:41, 18 December 2009 (UTC)
940:17:15, 18 December 2009 (UTC)
920:13:27, 18 December 2009 (UTC)
818:15:00, 19 February 2008 (UTC)
803:15:27, 16 February 2008 (UTC)
626:Tag all relevant articles in
366:and see a list of open tasks.
281:and see a list of open tasks.
3600:14:04, 13 January 2017 (UTC)
3576:04:18, 13 January 2017 (UTC)
3555:15:12, 12 January 2017 (UTC)
3516:04:18, 13 January 2017 (UTC)
3502:14:58, 12 January 2017 (UTC)
3472:08:06, 12 January 2017 (UTC)
3434:08:01, 10 January 2017 (UTC)
3391:07:59, 10 January 2017 (UTC)
3356:07:57, 10 January 2017 (UTC)
3332:06:17, 12 January 2017 (UTC)
3301:06:10, 12 January 2017 (UTC)
3232:07:55, 10 January 2017 (UTC)
3218:00:28, 10 January 2017 (UTC)
1732:Decision tree, help with SVG
1725:03:50, 26 October 2014 (UTC)
1597:Nesetril & Poljak (1985)
750:I suggest a algorithm here.
635:WikiProject Computer science
411:WikiProject Computer science
355:WikiProject Computer science
3566:Done. Is that everything? —
3270:23:50, 9 January 2017 (UTC)
3193:23:49, 9 January 2017 (UTC)
3155:01:21, 8 January 2017 (UTC)
3130:01:21, 8 January 2017 (UTC)
3106:Listing all maximal cliques
3094:23:49, 9 January 2017 (UTC)
3053:01:21, 8 January 2017 (UTC)
3017:01:21, 8 January 2017 (UTC)
2985:07:59, 3 January 2017 (UTC)
2954:07:59, 3 January 2017 (UTC)
2923:04:38, 2 January 2017 (UTC)
2755:02:52, 2 January 2017 (UTC)
2730:02:52, 2 January 2017 (UTC)
2096:02:07, 1 January 2010 (UTC)
1992:Other models of computation
1965:Other models of computation
793:is the number of edges. --
566:List of computer scientists
148:The text of the entry was:
3747:
3065:Understood. Any of "when
2515:01:13, 10 March 2011 (UTC)
2294:00:41, 10 March 2011 (UTC)
1967:(decision trees, circuits)
839:16:07, 17 April 2008 (UTC)
693:I propose we move this to
398:project's importance scale
150:Did you know ... that the
3399:Hardness of approximation
3244:Special classes of graphs
1387:
1304:
1220:
1210:
1205:
1137:In computer science, the
928:Clique (computer science)
676:19:21, May 7, 2004 (UTC)
628:Category:Computer science
404:
391:
378:Computer science articles
340:
306:
239:
221:
78:
74:
22:Skip to table of contents
3651:16:33, 7 July 2023 (UTC)
3635:15:58, 7 July 2023 (UTC)
3611:Please do not modify it.
3278:Approximation algorithms
3069:is not fixed...", "when
2931:History and applications
2581:Please do not modify it.
2179:14:02, 17 May 2010 (UTC)
2163:13:15, 17 May 2010 (UTC)
1690:08:34, 1 June 2013 (UTC)
854:12:11, 12 May 2008 (UTC)
759:18:36, 26 May 2007 (UTC)
729:01:49, 8 Jun 2005 (UTC)
711:09:05, 28 May 2005 (UTC)
702:23:58, 27 May 2005 (UTC)
684:19:38, 26 Mar 2005 (UTC)
630:and sub-categories with
309:project's priority scale
21:
3681:GA-Class vital articles
3666:Knowledge good articles
3073:is variable...", "when
2811:— {{math|''O''(''n'')}}
2715:adjacent (graph theory)
2656:Talk:Clique problem/GA1
2064:Maximal independent set
1899:maximal independent set
1042:Maximal independent set
1012:Maximal independent set
1000:Independent set problem
785:= 3, there exists an O(
741:04:47, 8 Jun 2005 (UTC)
735:independent set problem
723:independent set problem
270:WikiProject Mathematics
3413:Changed to "for every
2898:
2897:{\displaystyle O\,(n)}
2864:
2499:
2224:
1764:
1654:Example implementation
1465:I made an infobox for
1167:
1134:
764:The problem is proven
695:maximum clique problem
591:Computer science stubs
3025:Cliques of fixed size
2899:
2865:
2500:
2225:
2058:Somewhere else, e.g.
1951:(current 3.3 and 3.6)
1930:Special graph classes
1754:
1124:
1119:
904:Algorithms for clique
889:Ramsey number problem
200:level-5 vital article
52:good article criteria
2905:O\,(n)</math: -->
2877:
2863:{\displaystyle O(n)}
2845:
2303:
2195:
1444:for restricted cases
1066:Some minor details:
409:Things you can help
293:mathematics articles
104:Good article nominee
2106:Structure and scope
1281:)
883:. The other is the
3618:NY Times reference
3409:"for every ε : -->
3364:Circuit complexity
2894:
2884:
2871:O(n)</math: -->
2860:
2793:italics correction
2582:
2495:
2220:
1765:
1664:C++ implementation
1249:vertices. Integer
1135:
877:Computing a clique
789:) algorithm where
746:Algorithm feedback
262:Mathematics portal
209:content assessment
79:Article milestones
2646:
2645:
2580:
2477:
2425:
2344:
2320:
2284:comment added by
2212:
2153:comment added by
1728:
1713:Princess stargirl
1711:comment added by
1693:
1676:comment added by
1660:depth description
1658:I have a more in
1634:I agree. I guess
1463:
1462:
1449:Inapproximability
1374:Inapproximability
665:
664:
661:
660:
657:
656:
653:
652:
649:
648:
319:
318:
315:
314:
178:
177:
142:December 21, 2009
113:
112:
70:
27:
26:
3738:
3565:
3444:
3423:
3408:
3373:
3342:
3318:
3287:
3256:chromatic number
3253:
3172:
3140:
3115:
3034:
3002:
2971:
2940:
2903:
2901:
2900:
2895:
2869:
2867:
2866:
2861:
2838:
2825:
2819:
2810:
2797:
2791:
2784:
2780:
2772:
2740:
2712:
2600:Copyvio detector
2588:
2572:
2504:
2502:
2501:
2496:
2491:
2490:
2478:
2476:
2468:
2467:
2458:
2426:
2424:
2413:
2345:
2343:
2332:
2327:
2326:
2325:
2312:
2296:
2229:
2227:
2226:
2221:
2219:
2218:
2217:
2204:
2165:
1727:
1705:
1692:
1670:
1606:
1605:
1594:
1388:Counting problem
1215:
1203:
1014:), and refer to
908:Finding a clique
639:
633:
508:Computer science
437:Article requests
426:
419:
418:
406:
380:
379:
376:
373:
370:
369:Computer science
360:Computer science
349:
342:
341:
336:
332:Computer science
328:
321:
295:
294:
291:
288:
285:
264:
259:
258:
248:
241:
240:
230:
223:
206:
197:
196:
189:
188:
187:
180:
165:undirected graph
122:
99:
97:January 13, 2017
76:
59:
36:
29:
16:
3746:
3745:
3741:
3740:
3739:
3737:
3736:
3735:
3656:
3655:
3620:
3615:
3614:
3559:
3417:
3309:NP-completeness
2904:— <math: -->
2875:
2874:
2870:— <math: -->
2843:
2842:
2829:
2815:
2814:
2801:
2795:
2789:
2782:
2650:This review is
2642:
2614:
2585:
2576:
2575:
2574:
2565:
2560:
2523:
2482:
2469:
2459:
2417:
2336:
2307:
2301:
2300:
2279:
2199:
2193:
2192:
2187:
2148:
2132:
2108:
1805:
1734:
1706:
1671:
1656:
1636:Maximal cliques
1616:
1614:Maximal cliques
1611:
1610:
1609:
1599:
1595:
1591:
1438:Approximability
1354:Approximability
1201:
1114:
1112:Accessible head
1064:
981:"Did you know?"
862:
826:
775:
748:
718:
691:
670:
645:
642:
637:
631:
619:Project-related
614:
595:
576:
550:
531:
512:
493:
474:
450:
377:
374:
371:
368:
367:
334:
292:
289:
286:
283:
282:
260:
253:
207:on Knowledge's
204:
194:
174:
173:
169:social networks
146:
95:
12:
11:
5:
3744:
3742:
3734:
3733:
3728:
3723:
3718:
3713:
3708:
3703:
3698:
3693:
3688:
3683:
3678:
3673:
3668:
3658:
3657:
3654:
3653:
3643:David Eppstein
3627:72.219.138.131
3619:
3616:
3608:
3607:
3606:
3605:
3604:
3603:
3602:
3581:
3580:
3579:
3578:
3568:David Eppstein
3529:David Eppstein
3525:
3524:
3523:
3522:
3521:
3520:
3519:
3518:
3508:David Eppstein
3477:
3476:
3475:
3474:
3464:David Eppstein
3438:
3437:
3436:
3426:David Eppstein
3401:
3400:
3396:
3395:
3394:
3393:
3383:David Eppstein
3366:
3365:
3361:
3360:
3359:
3358:
3348:David Eppstein
3336:
3335:
3334:
3324:David Eppstein
3311:
3310:
3306:
3305:
3304:
3303:
3293:David Eppstein
3280:
3279:
3275:
3274:
3273:
3272:
3262:David Eppstein
3246:
3245:
3241:
3240:
3239:
3238:
3237:
3236:
3235:
3234:
3224:David Eppstein
3198:
3197:
3196:
3195:
3185:David Eppstein
3165:
3164:
3160:
3159:
3158:
3157:
3147:David Eppstein
3134:
3133:
3132:
3122:David Eppstein
3108:
3107:
3103:
3102:
3101:
3100:
3099:
3098:
3097:
3096:
3086:David Eppstein
3058:
3057:
3056:
3055:
3045:David Eppstein
3043:suggestions? —
3027:
3026:
3022:
3021:
3020:
3019:
3009:David Eppstein
2995:
2994:
2990:
2989:
2988:
2987:
2977:David Eppstein
2964:
2963:
2959:
2958:
2957:
2956:
2946:David Eppstein
2933:
2932:
2928:
2927:
2926:
2925:
2915:David Eppstein
2910:
2909:
2908:
2907:
2893:
2890:
2887:
2882:
2872:
2859:
2856:
2853:
2850:
2840:
2827:
2812:
2774:
2765:
2764:
2760:
2759:
2758:
2757:
2747:David Eppstein
2734:
2733:
2732:
2722:David Eppstein
2705:
2704:
2685:
2661:
2660:
2644:
2643:
2641:
2640:
2635:
2630:
2624:
2621:
2620:
2616:
2615:
2613:
2612:
2610:External links
2607:
2602:
2596:
2593:
2592:
2586:
2577:
2573:Promoted to GA
2567:
2566:
2563:
2562:
2561:
2559:
2556:
2555:
2554:
2522:
2519:
2518:
2517:
2507:David Eppstein
2494:
2489:
2485:
2481:
2475:
2472:
2466:
2462:
2456:
2453:
2450:
2447:
2444:
2441:
2438:
2435:
2432:
2429:
2423:
2420:
2416:
2411:
2408:
2405:
2402:
2399:
2396:
2393:
2390:
2387:
2384:
2381:
2378:
2375:
2372:
2369:
2366:
2363:
2360:
2357:
2354:
2351:
2348:
2342:
2339:
2335:
2330:
2324:
2319:
2316:
2311:
2261:
2260:
2250:David Eppstein
2231:
2216:
2211:
2208:
2203:
2190:
2186:
2183:
2182:
2181:
2144:
2139:
2135:
2131:
2128:
2107:
2104:
2103:
2102:
2101:
2100:
2099:
2098:
2069:
2068:
2067:
2056:
2052:
2045:
2044:
2043:
2042:
2041:
2016:David Eppstein
1996:
1990:First, making
1985:
1984:
1974:Thore Husfeldt
1969:
1968:
1961:
1960:
1953:
1952:
1945:
1944:
1937:
1936:
1926:
1925:
1918:
1917:
1903:David Eppstein
1891:
1890:
1889:
1888:
1870:
1863:
1856:
1855:
1845:Thore Husfeldt
1839:
1838:
1826:
1825:
1804:
1801:
1800:
1799:
1798:
1797:
1770:David Eppstein
1739:Thore Husfeldt
1733:
1730:
1655:
1652:
1651:
1650:
1640:Thore Husfeldt
1615:
1612:
1608:
1607:
1588:
1587:
1583:
1582:
1581:
1580:
1579:
1578:
1577:
1557:
1556:
1555:
1554:
1544:Thore Husfeldt
1517:
1513:
1503:
1502:
1492:David Eppstein
1476:Thore Husfeldt
1472:chemistry envy
1467:Graph coloring
1461:
1460:
1450:
1446:
1445:
1439:
1435:
1434:
1429:
1425:
1424:
1421:
1417:
1416:
1410:
1406:
1405:
1394:
1390:
1389:
1385:
1384:
1375:
1371:
1370:
1355:
1351:
1350:
1345:
1341:
1340:
1335:
1331:
1330:
1319:
1315:
1314:
1311:
1307:
1306:
1302:
1301:
1298:
1294:
1293:
1287:
1283:
1282:
1275:
1271:
1270:
1259:
1255:
1254:
1239:
1235:
1234:
1227:
1223:
1222:
1218:
1217:
1216:
1208:
1207:
1206:Graph coloring
1200:
1197:
1186:David Eppstein
1172:Thore Husfeldt
1139:clique problem
1113:
1110:
1109:
1108:
1098:David Eppstein
1079:
1078:
1075:
1072:
1063:
1060:
1059:
1058:
1057:
1056:
1031:
1030:
1016:Clique problem
985:David Eppstein
976:
975:
974:
973:
959:Clique problem
932:David Eppstein
912:Thore Husfeldt
900:Clique problem
869:Clique problem
861:
858:
857:
856:
825:
822:
821:
820:
774:
771:
770:
769:
747:
744:
743:
742:
717:
714:
690:
687:
686:
685:
669:
666:
663:
662:
659:
658:
655:
654:
651:
650:
647:
646:
644:
643:
641:
640:
623:
615:
613:
612:
606:
596:
594:
593:
587:
577:
575:
574:
569:
561:
551:
549:
548:
542:
532:
530:
529:
523:
513:
511:
510:
504:
494:
492:
491:
485:
475:
473:
472:
467:
461:
451:
449:
448:
442:
430:
428:
427:
415:
414:
402:
401:
394:Mid-importance
390:
384:
383:
381:
364:the discussion
350:
338:
337:
335:Mid‑importance
329:
317:
316:
313:
312:
305:
299:
298:
296:
279:the discussion
266:
265:
249:
237:
236:
231:
219:
218:
212:
190:
176:
175:
153:clique problem
147:
126:
125:
123:
115:
114:
111:
110:
107:
100:
92:
91:
88:
85:
81:
80:
72:
71:
40:Clique problem
37:
25:
24:
19:
13:
10:
9:
6:
4:
3:
2:
3743:
3732:
3729:
3727:
3724:
3722:
3719:
3717:
3714:
3712:
3709:
3707:
3704:
3702:
3699:
3697:
3694:
3692:
3689:
3687:
3684:
3682:
3679:
3677:
3674:
3672:
3669:
3667:
3664:
3663:
3661:
3652:
3648:
3644:
3639:
3638:
3637:
3636:
3632:
3628:
3625:
3617:
3612:
3601:
3598:
3597:
3593:
3592:
3587:
3586:
3585:
3584:
3583:
3582:
3577:
3573:
3569:
3563:
3562:Spinningspark
3558:
3557:
3556:
3553:
3552:
3548:
3547:
3541:
3540:
3539:
3538:
3534:
3530:
3517:
3513:
3509:
3505:
3504:
3503:
3500:
3499:
3495:
3494:
3488:
3483:
3482:
3481:
3480:
3479:
3478:
3473:
3469:
3465:
3460:
3459:
3458:
3455:
3454:
3450:
3449:
3443:
3439:
3435:
3431:
3427:
3420:
3416:
3412:
3411:
3407:
3403:
3402:
3398:
3397:
3392:
3388:
3384:
3380:
3376:
3375:
3372:
3368:
3367:
3363:
3362:
3357:
3353:
3349:
3345:
3344:
3341:
3337:
3333:
3329:
3325:
3321:
3320:
3317:
3313:
3312:
3308:
3307:
3302:
3298:
3294:
3290:
3289:
3286:
3282:
3281:
3277:
3276:
3271:
3267:
3263:
3259:
3258:
3257:
3252:
3248:
3247:
3243:
3242:
3233:
3229:
3225:
3221:
3220:
3219:
3216:
3215:
3211:
3210:
3204:
3203:
3202:
3201:
3200:
3199:
3194:
3190:
3186:
3182:
3177:
3176:
3171:
3167:
3166:
3162:
3161:
3156:
3152:
3148:
3144:
3143:
3139:
3135:
3131:
3127:
3123:
3118:
3117:
3114:
3110:
3109:
3105:
3104:
3095:
3091:
3087:
3083:
3082:
3080:
3076:
3072:
3068:
3064:
3063:
3062:
3061:
3060:
3059:
3054:
3050:
3046:
3041:
3040:
3038:
3033:
3029:
3028:
3024:
3023:
3018:
3014:
3010:
3005:
3004:
3001:
2997:
2996:
2992:
2991:
2986:
2982:
2978:
2974:
2973:
2970:
2966:
2965:
2961:
2960:
2955:
2951:
2947:
2943:
2942:
2939:
2935:
2934:
2930:
2929:
2924:
2920:
2916:
2912:
2911:
2888:
2880:
2873:
2854:
2848:
2841:
2836:
2832:
2828:
2823:
2818:
2813:
2808:
2804:
2800:
2799:
2794:
2787:
2786:
2779:
2775:
2771:
2767:
2766:
2762:
2761:
2756:
2752:
2748:
2743:
2742:
2739:
2735:
2731:
2727:
2723:
2719:
2718:
2716:
2711:
2707:
2706:
2702:
2701:
2700:
2699:
2696:
2695:
2691:
2690:
2683:
2682:
2678:
2675:
2672:
2668:
2667:Spinningspark
2665:
2659:
2657:
2653:
2648:
2647:
2639:
2636:
2634:
2631:
2629:
2626:
2625:
2623:
2622:
2617:
2611:
2608:
2606:
2603:
2601:
2598:
2597:
2595:
2594:
2589:
2584:
2571:
2557:
2553:
2549:
2545:
2540:
2539:
2538:
2537:
2533:
2529:
2520:
2516:
2512:
2508:
2492:
2487:
2483:
2479:
2473:
2470:
2464:
2460:
2454:
2451:
2448:
2445:
2442:
2439:
2436:
2433:
2430:
2427:
2421:
2418:
2414:
2409:
2403:
2400:
2397:
2394:
2391:
2385:
2379:
2376:
2373:
2367:
2361:
2358:
2355:
2349:
2346:
2340:
2337:
2333:
2328:
2317:
2314:
2299:
2298:
2297:
2295:
2291:
2287:
2286:129.215.5.255
2283:
2275:
2274:
2270:
2266:
2259:
2255:
2251:
2246:
2245:
2244:
2243:
2239:
2235:
2209:
2206:
2184:
2180:
2176:
2172:
2168:
2167:
2166:
2164:
2160:
2156:
2155:93.211.185.46
2152:
2145:
2140:
2136:
2129:
2127:
2126:
2122:
2118:
2112:
2105:
2097:
2093:
2089:
2084:
2083:
2082:
2078:
2074:
2070:
2065:
2061:
2057:
2053:
2050:
2049:
2046:
2040:
2036:
2032:
2027:
2026:
2025:
2021:
2017:
2012:
2011:
2010:
2006:
2002:
1997:
1993:
1989:
1988:
1987:
1986:
1983:
1979:
1975:
1971:
1970:
1966:
1963:
1962:
1958:
1955:
1954:
1950:
1949:Approximation
1947:
1946:
1942:
1939:
1938:
1935:
1931:
1928:
1927:
1923:
1920:
1919:
1915:
1914:
1913:
1912:
1908:
1904:
1900:
1896:
1887:
1883:
1879:
1875:
1871:
1868:
1864:
1860:
1859:
1858:
1857:
1854:
1850:
1846:
1841:
1840:
1836:
1832:
1828:
1827:
1822:
1821:
1820:
1819:
1815:
1811:
1802:
1796:
1792:
1788:
1784:
1781:
1780:
1779:
1775:
1771:
1767:
1766:
1762:
1758:
1753:
1749:
1748:
1744:
1740:
1731:
1729:
1726:
1722:
1718:
1714:
1710:
1701:
1698:
1694:
1691:
1687:
1683:
1679:
1678:Devillmeister
1675:
1669:
1665:
1661:
1653:
1649:
1645:
1641:
1637:
1633:
1632:
1631:
1630:
1626:
1622:
1613:
1603:
1598:
1593:
1590:
1586:
1576:
1572:
1568:
1563:
1562:
1561:
1560:
1559:
1558:
1553:
1549:
1545:
1541:
1537:
1533:
1532:
1531:
1527:
1523:
1518:
1514:
1510:
1505:
1504:
1501:
1497:
1493:
1488:
1487:
1486:
1485:
1481:
1477:
1473:
1468:
1459:
1455:
1451:
1448:
1447:
1443:
1440:
1437:
1436:
1433:
1430:
1427:
1426:
1422:
1419:
1418:
1415:
1411:
1408:
1407:
1403:
1399:
1395:
1392:
1391:
1386:
1383:
1379:
1376:
1373:
1372:
1368:
1364:
1360:
1356:
1353:
1352:
1349:
1346:
1343:
1342:
1339:
1336:
1333:
1332:
1328:
1324:
1320:
1317:
1316:
1312:
1309:
1308:
1303:
1299:
1297:Garey–Johnson
1296:
1295:
1291:
1288:
1285:
1284:
1280:
1276:
1273:
1272:
1268:
1264:
1260:
1257:
1256:
1252:
1248:
1244:
1240:
1237:
1236:
1232:
1228:
1225:
1224:
1219:
1214:
1209:
1204:
1198:
1196:
1195:
1191:
1187:
1182:
1181:
1177:
1173:
1166:
1164:
1159:
1155:
1151:
1147:
1144:
1141:is to find a
1140:
1132:
1128:
1123:
1118:
1111:
1107:
1103:
1099:
1095:
1094:
1093:
1092:
1088:
1084:
1076:
1073:
1069:
1068:
1067:
1061:
1055:
1051:
1047:
1043:
1039:
1035:
1034:
1033:
1032:
1029:
1025:
1021:
1017:
1013:
1009:
1005:
1001:
997:
996:
995:
994:
990:
986:
982:
972:
968:
964:
960:
956:
952:
948:
943:
942:
941:
937:
933:
929:
924:
923:
922:
921:
917:
913:
909:
905:
901:
898:redirects to
897:
896:Party problem
892:
890:
886:
885:Party problem
882:
878:
874:
870:
865:
860:Article title
859:
855:
851:
847:
843:
842:
841:
840:
836:
832:
823:
819:
815:
811:
807:
806:
805:
804:
800:
796:
792:
788:
784:
780:
772:
767:
763:
762:
761:
760:
757:
753:
745:
740:
736:
732:
731:
730:
728:
724:
716:Removed proof
715:
713:
712:
709:
704:
703:
700:
696:
689:Proposed move
688:
683:
679:
678:
677:
675:
667:
636:
629:
625:
624:
622:
620:
616:
611:
608:
607:
605:
603:
602:
597:
592:
589:
588:
586:
584:
583:
578:
573:
570:
567:
563:
562:
560:
558:
557:
552:
547:
544:
543:
541:
539:
538:
533:
528:
525:
524:
522:
520:
519:
514:
509:
506:
505:
503:
501:
500:
495:
490:
487:
486:
484:
482:
481:
476:
471:
468:
466:
463:
462:
460:
458:
457:
452:
447:
444:
443:
441:
439:
438:
433:
432:
429:
425:
421:
420:
417:
416:
412:
408:
407:
403:
399:
395:
389:
386:
385:
382:
365:
361:
357:
356:
351:
348:
344:
343:
339:
333:
330:
327:
323:
310:
304:
301:
300:
297:
280:
276:
272:
271:
263:
257:
252:
250:
247:
243:
242:
238:
235:
232:
229:
225:
220:
216:
210:
202:
201:
191:
182:
181:
172:
170:
166:
162:
159:
155:
154:
144:
143:
138:
136:
135:Did you know?
130:
124:
121:
117:
116:
108:
106:
105:
101:
98:
94:
93:
89:
86:
83:
82:
77:
73:
68:
66:
65:
57:
53:
49:
48:
47:
41:
38:
35:
31:
30:
23:
20:
18:
17:
3621:
3610:
3595:
3590:
3550:
3545:
3526:
3497:
3492:
3486:
3452:
3447:
3418:
3213:
3208:
3078:
3074:
3070:
3066:
3036:
2834:
2830:
2821:
2816:
2806:
2802:
2783: 
2693:
2688:
2684:
2673:
2663:
2662:
2649:
2638:Instructions
2578:
2524:
2276:
2262:
2188:
2147:Thank you.
2146:
2141:
2137:
2133:
2113:
2109:
1991:
1964:
1956:
1948:
1940:
1933:
1929:
1921:
1892:
1866:
1834:
1830:
1806:
1760:
1756:
1735:
1707:— Preceding
1702:
1696:
1695:
1672:— Preceding
1657:
1635:
1617:
1592:
1584:
1535:
1509:Vertex Cover
1464:
1420:Running time
1413:
1401:
1397:
1377:
1366:
1362:
1358:
1337:
1326:
1322:
1305:Optimisation
1292:, W-complete
1278:
1274:Running time
1266:
1262:
1250:
1246:
1242:
1230:
1183:
1168:
1138:
1136:
1115:
1080:
1065:
1062:Some details
977:
954:
946:
907:
903:
893:
888:
884:
880:
876:
872:
868:
866:
863:
827:
790:
786:
782:
776:
749:
719:
705:
692:
674:Bryanlharris
671:
618:
617:
601:Unreferenced
599:
598:
580:
579:
554:
553:
535:
534:
516:
515:
497:
496:
478:
477:
454:
453:
435:
434:
393:
353:
268:
215:WikiProjects
198:
151:
149:
140:
132:
102:
62:
60:
56:please do so
44:
43:
39:
3415:real number
2962:Definitions
2686:Looking...
2652:transcluded
2280:—Preceding
2149:—Preceding
1957:Enumeration
1874:WP:DEADLINE
1824:accomplish.
1432:#P-complete
1290:NP-complete
894:Currently,
766:NP-complete
284:Mathematics
275:mathematics
234:Mathematics
3660:Categories
3379:supergraph
2605:Authorship
2591:GA toolbox
2265:Vojta.jina
2234:Vojta.jina
1934:Algorithms
1922:Algorithms
1585:References
1428:Complexity
1344:Complexity
1286:Complexity
1163:algorithms
1127:Path graph
708:MathMartin
139:column on
50:under the
3254:Wikilink
2664:Reviewer:
2628:Templates
2619:Reviewing
2558:GA Review
1831:stability
1829:However,
1697:Question:
1522:C. lorenz
1338:\alpha(G)
1329:vertices.
1269:vertices?
871:. One is
773:Reference
489:Computing
203:is rated
161:subgraphs
129:Main Page
3591:Spinning
3546:Spinning
3493:Spinning
3448:Spinning
3260:Done. —
3209:Spinning
2720:Added. —
2689:Spinning
2677:contribs
2633:Criteria
2282:unsigned
2151:unsigned
1943:(NPC, W)
1941:Hardness
1803:GA-class
1721:contribs
1709:unsigned
1686:contribs
1674:unsigned
1536:at least
1404:vertices
1229:Clique,
1221:Decision
1199:Infobox?
1154:vertices
1146:subgraph
1143:complete
733:Rewrote
668:Untitled
537:Maintain
480:Copyedit
205:GA-class
158:complete
64:reassess
3145:Done. —
2763:General
1456:unless
1380:unless
1365:log log
1348:NP-hard
1233:-Clique
887:or the
831:Bjoeris
810:Rampion
795:Rampion
756:insaint
518:Infobox
456:Cleanup
396:on the
131:in the
87:Process
3377:Done:
3181:WP:SPS
2564:RESULT
2544:RDBury
2528:RDBury
1763:-1)/2.
1458:P = NP
1409:Output
1396:Graph
1382:P = NP
1334:Output
1321:Graph
1258:Output
1241:Graph
846:Mellum
499:Expand
211:scale.
163:in an
109:Listed
90:Result
3596:Spark
3551:Spark
3498:Spark
3453:Spark
3421:: -->
3214:Spark
2694:Spark
2654:from
2171:Robin
2117:Robin
2088:Robin
2031:Robin
2001:Robin
1878:Robin
1810:Robin
1787:Robin
1621:Robin
1567:Robin
1442:FPRAS
1400:with
1393:Input
1325:with
1318:Input
1261:Does
1245:with
1238:Input
1158:edges
1150:graph
1148:in a
1046:Robin
1002:into
961:". —
582:Stubs
556:Photo
413:with:
192:This
3647:talk
3631:talk
3572:talk
3533:talk
3512:talk
3487:only
3468:talk
3430:talk
3424:". —
3387:talk
3352:talk
3328:talk
3297:talk
3266:talk
3228:talk
3189:talk
3151:talk
3126:talk
3090:talk
3049:talk
3013:talk
2981:talk
2950:talk
2919:talk
2751:talk
2726:talk
2703:Lead
2671:talk
2548:talk
2532:talk
2511:talk
2290:talk
2269:talk
2254:talk
2248:1. —
2238:talk
2175:talk
2159:talk
2121:talk
2092:talk
2077:talk
2073:Miym
2035:talk
2020:talk
2005:talk
1978:talk
1907:talk
1897:and
1882:talk
1849:talk
1814:talk
1791:talk
1774:talk
1743:talk
1737:do?
1717:talk
1682:talk
1644:talk
1625:talk
1602:help
1571:talk
1548:talk
1526:talk
1496:talk
1480:talk
1454:PTAS
1423:O(3)
1361:log
1310:Name
1300:GT19
1226:Name
1190:talk
1176:talk
1102:talk
1087:talk
1083:Miym
1071:now.
1050:talk
1024:talk
1020:Miym
1010:(or
989:talk
967:talk
963:Miym
947:very
936:talk
916:talk
850:talk
835:talk
814:talk
799:talk
739:Deco
727:Deco
699:Deco
682:Deco
84:Date
3381:. —
1452:No
1040:or
955:all
926:be
906:or
879:or
875:or
388:Mid
303:???
3662::
3649:)
3633:)
3574:)
3535:)
3514:)
3470:)
3432:)
3389:)
3354:)
3330:)
3299:)
3268:)
3230:)
3191:)
3153:)
3128:)
3092:)
3051:)
3015:)
2983:)
2952:)
2921:)
2796:}}
2790:{{
2785:)
2753:)
2728:)
2679:)
2550:)
2534:)
2513:)
2480:≤
2449:…
2443:⋅
2437:⋅
2431:⋅
2410:≤
2395:−
2386:…
2377:−
2368:⋅
2359:−
2350:⋅
2292:)
2271:)
2256:)
2240:)
2232:--
2177:)
2161:)
2123:)
2094:)
2079:)
2071:—
2062:+
2037:)
2022:)
2007:)
1980:)
1909:)
1884:)
1851:)
1816:)
1793:)
1785:--
1776:)
1745:)
1723:)
1719:•
1688:)
1684:•
1646:)
1627:)
1619:--
1573:)
1565:--
1550:)
1528:)
1498:)
1482:)
1474:.
1357:O(
1277:O(
1192:)
1178:)
1104:)
1089:)
1081:—
1052:)
1026:)
991:)
969:)
938:)
918:)
852:)
837:)
816:)
801:)
638:}}
632:{{
67:it
58:.
3645:(
3641:—
3629:(
3570:(
3564::
3560:@
3531:(
3510:(
3466:(
3428:(
3422:0
3419:ε
3385:(
3350:(
3326:(
3295:(
3264:(
3226:(
3187:(
3149:(
3124:(
3120:—
3088:(
3079:k
3075:k
3071:k
3067:k
3047:(
3037:k
3011:(
3007:—
2979:(
2948:(
2917:(
2913:—
2892:)
2889:n
2886:(
2881:O
2858:)
2855:n
2852:(
2849:O
2837:)
2835:n
2833:(
2831:O
2824:)
2822:n
2820:(
2817:O
2809:)
2807:n
2805:(
2803:O
2749:(
2724:(
2674:·
2669:(
2546:(
2530:(
2509:(
2493:.
2488:k
2484:n
2474:!
2471:k
2465:k
2461:n
2455:=
2452:n
2446:n
2440:n
2434:n
2428:n
2422:!
2419:k
2415:1
2407:)
2404:1
2401:+
2398:k
2392:n
2389:(
2383:)
2380:2
2374:n
2371:(
2365:)
2362:1
2356:n
2353:(
2347:n
2341:!
2338:k
2334:1
2329:=
2323:)
2318:k
2315:n
2310:(
2288:(
2267:(
2252:(
2236:(
2215:)
2210:k
2207:n
2202:(
2173:(
2157:(
2119:(
2090:(
2075:(
2066:?
2033:(
2018:(
2003:(
1976:(
1905:(
1880:(
1847:(
1812:(
1789:(
1772:(
1761:n
1759:(
1757:n
1741:(
1715:(
1680:(
1642:(
1623:(
1604:)
1569:(
1546:(
1524:(
1520:—
1494:(
1478:(
1414:G
1402:n
1398:G
1378:n
1369:)
1367:n
1363:n
1359:n
1327:n
1323:G
1279:n
1267:k
1263:G
1253:.
1251:k
1247:n
1243:G
1231:k
1188:(
1174:(
1131:C
1100:(
1085:(
1048:(
1022:(
987:(
965:(
934:(
914:(
848:(
833:(
812:(
797:(
791:n
787:n
783:k
621::
604::
585::
568:)
559::
540::
521::
502::
483::
459::
440::
400:.
311:.
217::
171:?
145:.
137:"
133:"
69:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
