Толық подграфтарды есептеу мәселесі

Кіріспе

Толық субграфтарды есептеу міндеті

Компьютерлік ғылымда клика мәселесі – графтардағы кликаларды (бір-біріне тікелей қосылған төбелердің жиынтығы, сондай-ақ толық субграфтар деп аталады) табудың есептеу мәселесі. Оның әртүрлі тұжырымдамалары бар, олар қандай кликаларды және кликалар туралы қандай ақпаратты табу керекке байланысты. Клика мәселесінің кең таралған тұжырымдамаларына ең үлкен кликаны табу (мүмкін болатын ең көп төбесі бар клика), салмақты графтарда ең үлкен салмақты кликаны табу, барлық максималды кликаларды тізімдеу (көбейтілмейтін кликалар) және граф берілген өлшемнен үлкен кликаны қамтитынын анықтау шешімін табу кіреді. Клика мәселесі нақты әлемде келесідей туындайды. Әлеуметтік желіні қарастырайық, онда графтың төбелері адамдарды, ал қабырғалары өзара таныстықты көрсетеді. Онда клика – бір-бірін танитын адамдардың тобын білдіреді, ал кликаларды табу алгоритмдері осы ортақ достардың топтарын анықтау үшін қолданылуы мүмкін. Әлеуметтік желілердегі қолданысқа қоса, клика мәселесі биоинформатика және есептеу химиясында да көптеген қолданыстарға ие. Клика мәселесінің көптеген нұсқалары қиын. Кликаны анықтау мәселесі NP-толық (Карптың 21 NP-толық мәселесінің бірі). Ең үлкен кликаны табу мәселесі бірқатар параметрлер бойынша шешілмейді және жуықтау қиын. Барлық максималды кликаларды тізімдеуге экспоненциалды уақыт қажет болуы мүмкін, себебі экспоненциалды түрде көптеген максималды кликалары бар графтар бар. Сондықтан, клика мәселесі туралы теорияның көп бөлігі тиімді алгоритмдерге ие болатын графтардың ерекше түрлерін анықтауға немесе есептеудің әртүрлі модельдеріндегі жалпы мәселенің есептеу қиындығын анықтауға арналған. Ең үлкен кликаны табу үшін барлық ішкі жиынтықтарды жүйелі түрде тексеруге болады, бірақ мұндай түйінсіз іздеу ондағаннан астам төбелері бар желілер үшін тиімді емес. Бұл мәселе үшін полиномиалдық уақыт алгоритмі белгілі болмаса да, түйінсіз іздеуге қарағанда тиімді алгоритмдер бар. Мысалы, Брон-Кербош алгоритмі нашар жағдайда оңтайлы уақытта барлық максималды кликаларды тізімдеу үшін қолданылуы мүмкін, сонымен қатар оларды клика үшін полиномиалдық уақытта тізімдеуге болады.

In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph. It has several different formulations depending on which cliques, and what information about the cliques, should be found. Common formulations of the clique problem include finding a maximum clique (a clique with the largest possible number of vertices), finding a maximum weight clique in a weighted graph, listing all maximal cliques (cliques that cannot be enlarged), and solving the decision problem of testing whether a graph contains a clique larger than a given size. The clique problem arises in the following real world setting. Consider a social network, where the graph's vertices represent people, and the graph's edges represent mutual acquaintance. Then a clique represents a subset of people who all know each other, and algorithms for finding cliques can be used to discover these groups of mutual friends. Along with its applications in social networks, the clique problem also has many applications in bioinformatics, and computational chemistry. Most versions of the clique problem are hard. The clique decision problem is NP complete (one of Karp's 21 NP complete problems). The problem of finding the maximum clique is both fixed parameter intractable and hard to approximate. And, listing all maximal cliques may require exponential time as there exist graphs with exponentially many maximal cliques. Therefore, much of the theory about the clique problem is devoted to identifying special types of graph that admit more efficient algorithms, or to establishing the computational difficulty of the general problem in various models of computation. To find a maximum clique, one can systematically inspect all subsets, but this sort of brute force search is too time consuming to be practical for networks comprising more than a few dozen vertices. Although no polynomial time algorithm is known for this problem, more efficient algorithms than the brute force search are known. For instance, the Bron–Kerbosch algorithm can be used to list all maximal cliques in worst case optimal time, and it is also possible to list them in polynomial time per clique.

Тарих және қолдану

Математикада толық субграфтарды зерттеу "клика" терминологиясынан бұрын басталған. Мысалы, толық субграфтар Рэмси теориясын график теориясымен қайта формулирлеуде математикалық әдебиетте ерте пайда болады. Бірақ "клика" термині және кликаларды алгоритмдік түрде тізімдеу мәселесі әлеуметтік ғылымдардан келген, онда толық субграфтар әлеуметтік кликаларды – бір-бірін танитын адамдар тобын модельдеу үшін қолданылады. Олар әлеуметтік желілерді модельдеу үшін графиктерді пайдаланды және әлеуметтік ғылым терминологиясын график теориясына бейімдеді. Толық субграфтарды "кликалар" деп атаған алғашқылар олар болды. Клика мәселесін шешуге арналған алғашқы алгоритмді социологиялық қолданысқа байланысты жасаған. Әлеуметтік ғылым зерттеушілері әлеуметтік желідегі әртүрлі кликалар мен максималды кликаларды, желідегі адамдардың немесе актерлердің "бірлескен кіші топтарын" анықтады, олардың барлығы бірнеше түрлі байланыс қатынастарын бөліседі. Кликаның осы жалпыланған түсініктерінің көпшілігі, әлеуметтік желідегі байланысты актерлер жұптарын көрсететін қабырғалары бар бағытталмаған графикті құрастыру және содан кейін осы графикке клика мәселесін шешуге арналған алгоритмді қолдану арқылы да кездеседі. Харари мен Росс жұмысынан кейін көптеген ғалымдар клика мәселесінің әртүрлі нұсқалары үшін алгоритмдер ойлап тапты. Бұл қолданыстарда әрбір төбе екі молекуладан алынған, бір-біріне сәйкес келетін атомдар жұбын көрсетеді. Егер олар көрсететін сәйкестіктер бір-бірімен үйлесімді болса, екі төбе жиекпен байланысады. Үйлесімділік, мысалы, екі молекуладағы атомдар арасындағы қашықтықтар белгілі бір шешімге дейін шамамен тең болуын білдіруі мүмкін. Осы графиктегі клика – барлық сәйкестіктер бір-бірімен үйлесімді болатын сәйкес атомдар жұбының жиынтығын көрсетеді. Бұл әдістің ерекше жағдайы – екі графиктің ең үлкен ортақ индукцияланған субграфин табу мәселесін олардың көбейтіндісіндегі ең үлкен кликаны табу мәселесіне келтіру үшін графиктердің модулдік көбейтіндісін пайдалану. Автоматты тесттік үлгілерді жасауда кликаларды табу тесттік жиынтықтың мөлшерін шектеуге көмектеседі. Биоинформатикада эволюциялық ағаштарды анықтау, ақуыз құрылымдарын болжау және тығыз өзара әрекеттесетін ақуыз кластерлерін табу үшін кликаларды табу алгоритмдері қолданылған. Тәуелділік графигіндегі кликаларды тізімдеу белгілі бір кездейсоқ процестерді талдаудағы маңызды қадам болып табылады. Математикада Келлер гиперкубтарды бетпе-бет қаптау туралы болжамын , байланысты графқа клика табу алгоритмін қолданып, қарсы мысал тапқан арқылы жоққа шығарды.

The study of complete subgraphs in mathematics predates the "clique" terminology. For instance, complete subgraphs make an early appearance in the mathematical literature in the graph theoretic reformulation of Ramsey theory by But the term "clique" and the problem of algorithmically listing cliques both come from the social sciences, where complete subgraphs are used to model social cliques, groups of people who all know each other. used graphs to model social networks, and adapted the social science terminology to graph theory. They were the first to call complete subgraphs "cliques". The first algorithm for solving the clique problem is that of , who were motivated by the sociological application. Social science researchers have also defined various other types of cliques and maximal cliques in social network, "cohesive subgroups" of people or actors in the network all of whom share one of several different kinds of connectivity relation. Many of these generalized notions of cliques can also be found by constructing an undirected graph whose edges represent related pairs of actors from the social network, and then applying an algorithm for the clique problem to this graph. Since the work of Harary and Ross, many others have devised algorithms for various versions of the clique problem. In these applications, one forms a graph in which each vertex represents a matched pair of atoms, one from each of two molecules. Two vertices are connected by an edge if the matches that they represent are compatible with each other. Being compatible may mean, for instance, that the distances between the atoms within the two molecules are approximately equal, to within some given tolerance. A clique in this graph represents a set of matched pairs of atoms in which all the matches are compatible with each other. A special case of this method is the use of the modular product of graphs to reduce the problem of finding the maximum common induced subgraph of two graphs to the problem of finding a maximum clique in their product. In automatic test pattern generation, finding cliques can help to bound the size of a test set. In bioinformatics, clique finding algorithms have been used to infer evolutionary trees, predict protein structures, and find closely interacting clusters of proteins. Listing the cliques in a dependency graph is an important step in the analysis of certain random processes. In mathematics, Keller's conjecture on face to face tiling of hypercubes was disproved by , who used a clique finding algorithm on an associated graph to find a counterexample.

Анықтамалар

Бағытталмаған график – шекті жиынтығы бар төбелер мен төбелердің ретсіз жұптарынан тұратын жиынтық, олар жиектер деп аталады. Алгоритмдік талдауда графиктердегі төбелер саны n, ал жиектер саны m деп белгіленеді. График G-дегі клика – G-нің толық кіші графигі. Яғни, бұл K-дегі кез келген екі төбе G-дегі жиектің екі ұшын құрайтын K төбелерінің жиынтығы. Максималды клика – оған қосымша төбелерді қосу мүмкін емес клика. Максималды кликаның құрамына кірмейтін әрбір v төбесі үшін, v төбесін кликаға қосылуына кедерес келтіретін, кликадағы және v төбесіне іргелес емес w төбесі болуы керек. Максималды клика – ең көп төбелерді қамтитын клика. Клик саны ω(G) – G графигіндегі максималды кликадағы төбелер саны. Максималды клика мәселесінде кіріс – бағытталмаған график, ал шығыс – графиктегі максималды клика. Егер бірнеше максималды кликалар болса, олардың кез келген біреуін таңдауға болады. Сондықтан көптеген есептеу нәтижелерін екі мәселеге де қолдануға болады, ал кейбір ғылыми еңбектер екі мәселенің арасын нақты ажыратпайды. Дегенмен, екі мәселенің шектеулі графиктер отбасыларына қолданғанда әртүрлі қасиеттері бар. Мысалы, клика мәселесі жазық графиктерде полиномдық уақытта шешілуі мүмкін, ал жазық графиктерде тәуелсіз жиын мәселесі NP-қиын болып қалады.

Бір максималды топты табу

Максималды клика, кейде инклюзиялық максимал деп аталады, үлкен кликаға кірмейтін клика. Сондықтан, кез келген клика максималды кликаға кіреді. Максималды кликалар өте кішкентай болуы мүмкін. График көптеген төбелері бар максималды емес кликаны және максималды болып табылатын 2-өлшемді жеке кликаны қамтуы мүмкін. Ең үлкен (яғни, ең ірі) клика міндетті түрде максималды болса, керісінше дұрыс емес. Әрбір максималды клика максималды болатын графиктердің кейбір түрлері бар; бұл жақсы жабылған графиктердің толықтырулары, онда әрбір максималды тәуелсіз жиын максималды болады. Дегенмен, басқа графиктерде максималды емес максималды кликалар бар. Бір максималды кликаны қарапайым ашкөз алгоритм арқылы табуға болады. Кез келген кликадан бастап (мысалы, кез келген бір төбе немесе тіпті бос жиын), ағымдағы кликаны график қалған төбелері арқылы жүріп, бір төбеден өсіріңіз. Бұл цикл қарастыратын әрбір v төбесі үшін, егер ол кликадағы әрбір төбемен жақын болса, v-ді кликаға қосыңыз, әйтпесе v-ді жойыңыз. Бұл алгоритм сызықтық уақытта жұмыс істейді. Максималды кликаны табудың оңайлығы және олардың ықтимал кішкентай мөлшері ең үлкен немесе басқаша ірі кликаны табудың әлдеқайда қиын алгоритмдік мәселесіне көбірек назар аударуға себеп болды. Дегенмен, кейбір параллель алгоритмдердегі зерттеулер максималды кликаны табу мәселесін қарастырды. Атап айтқанда, лексикографиялық бірінші максималды кликаны табу мәселесі (жоғарыда көрсетілген алгоритммен табылған) полиномиалдық уақыт функциялары класы үшін толық екені көрсетілді. Бұл нәтиже мәселенің NC параллель күрделілік класы шеңберінде шешілмейтінін білдіреді.

Белгіленген өлшемді топтар

Граф G-де k төбесі бар клика бар-жоқ екенін тексеруге және мұндай клика бар болса, оны табуға болады. Бұл алгоритм k төбесі бар әрбір субграфты қарастырады және оның клика құрайтынын тексереді. Бұл алгоритмнің уақыты үлкен O белгісімен көрсетілгендей, шамамен соған тең. Себебі, тексеруге болатын субграфтар саны бар, және әрқайсысының G-де болуын тексеру қажет жиектері бар. Осылайша, k тұрақты мән болғанда, мәселені полиномиалдық уақытта шешуге болады. Бірақ, k тұрақты емес, керісінше, мәселенің кіріс бөлігі ретінде өзгере алатын болса, уақыт экспоненциалды болады. Клика табу мәселесінің ең қарапайым, тривиалды жағдайы – графтың ішінде үшбұрышты табу немесе граф үшбұрышсыз екенін анықтау. G графында m жиегі болса, онда ең көп дегенде Θ(m^(3/2)) үшбұрыш болуы мүмкін (бұл шектеудің тығыз екенін көрсету үшін үлкен тета белгісі қолданылады). Бұл формуланың ең нашар жағдайы G өзі клика болғанда туындайды. Сондықтан, барлық үшбұрыштардың тізімін жасау алгоритмі ең нашар жағдайда кем дегенде Ω(m^(3/2)) уақыт алады (үлкен омега белгісі қолданылады), және осы уақыт шегіне сәйкес келетін алгоритмдер белгілі. Мысалы, төбелерді ең жоғары дәрежеден ең төменгі дәрежеге дейін реттеп, содан кейін реттелген тізімдегі әрбір v төбесі үшін, v төбесін қамтитын және тізімдегі бұрынғы төбелерді қамтамайтын үшбұрыштарды іздеуге болатын алгоритмді қарастырайық. Ол үшін алгоритм v төбесінің барлық көршілерін белгілейді, v төбесінің көршісіне түсетін барлық жиектерді іздеп, екі белгіленген нүктесі бар әрбір жиек үшін үшбұрышты шығарады, содан кейін белгілерді алып тастайды және v төбесін графтан жояды. Авторлар көрсеткендей, бұл алгоритмнің уақыты графтың ағашқа ұқсастығына (a(G) белгіленген) жиектер санымен көбейтілгенге пропорционалды, ал ағашқа ұқсастығы ең көп болғандықтан, бұл алгоритм уақытында жұмыс істейді. Жалпы алғанда, барлық k төбесі бар кликаларды іздеу үшін ұқсас алгоритмді қолдануға болады, ол жиектер санына графтың ағашқа ұқсастығының (k-2) дәрежесіне көбейтілген уақыт алады. Ағашқа ұқсастығы тұрақты графтар үшін, мысалы, жазық графтар (немесе жалпы алғанда, кез келген тривиалды емес минор жабық граф отбасынан алынған графтар) үшін бұл алгоритм уақыт алады, бұл кіріс мөлшеріне пропорционалды болғандықтан оңтайлы. Егер тек бір үшбұрышты табу немесе граф үшбұрышсыз екеніне кепілдік алу қажет болса, жылдам алгоритмдерді қолдануға болады. Байқағанымыздай, граф үшбұрышқа ие болса және тек қана оның іргелес матрицасы мен іргелес матрицаның квадратында бір ұяшықта нөлден өзге жазбалар болса ғана. Сондықтан, үшбұрыштарды табу үшін жылдам матрица көбейту әдістерін қолдануға болады. Бұл алгоритмдер k-ның үлкен мәндері үшін k-кликаларды табу мәселелеріне де қолданылды.

One can test whether a graph G contains a k vertex clique, and find any such clique that it contains, using a brute force algorithm. This algorithm examines each subgraph with k vertices and checks to see whether it forms a clique. It takes time , as expressed using big O notation. This is because there are subgraphs to check, each of which has edges whose presence in G needs to be checked. Thus, the problem may be solved in polynomial time whenever k is a fixed constant. However, when k does not have a fixed value, but instead may vary as part of the input to the problem, the time is exponential. The simplest nontrivial case of the clique finding problem is finding a triangle in a graph, or equivalently determining whether the graph is triangle free. In a graph G with m edges, there may be at most Θ(m^(3/2)) triangles (using big theta notation to indicate that this bound is tight). The worst case for this formula occurs when G is itself a clique. Therefore, algorithms for listing all triangles must take at least Ω(m^(3/2)) time in the worst case (using big omega notation), and algorithms are known that match this time bound. For instance, describe an algorithm that sorts the vertices in order from highest degree to lowest and then iterates through each vertex v in the sorted list, looking for triangles that include v and do not include any previous vertex in the list. To do so the algorithm marks all neighbors of v, searches through all edges incident to a neighbor of v outputting a triangle for every edge that has two marked endpoints, and then removes the marks and deletes v from the graph. As the authors show, the time for this algorithm is proportional to the arboricity of the graph (denoted a(G)) multiplied by the number of edges, which is Since the arboricity is at most , this algorithm runs in time More generally, all k vertex cliques can be listed by a similar algorithm that takes time proportional to the number of edges multiplied by the arboricity to the power (k − 2). For graphs of constant arboricity, such as planar graphs (or in general graphs from any non trivial minor closed graph family), this algorithm takes time, which is optimal since it is linear in the size of the input. If one desires only a single triangle, or an assurance that the graph is triangle free, faster algorithms are possible. As observe, the graph contains a triangle if and only if its adjacency matrix and the square of the adjacency matrix contain nonzero entries in the same cell. Therefore, fast matrix multiplication techniques can be applied to find triangles in time used fast matrix multiplication to improve the algorithm for finding triangles to These algorithms based on fast matrix multiplication have also been extended to problems of finding k cliques for larger values of k.

Барлық ең үлкен топтарды тізімдеу

Нәтижесінде, кез келген n төбелі графтың ең көп дегенде 3^(n/3) максималды кликасы болады. Оларды Bron–Kerbosch алгоритмімен тізімдеуге болады, ол рекурсивті кері іздеу процедурасы. Бұл процедураның негізгі рекурсивті қосалқы бағдарламасы үш аргументке ие: жартылай құрылған (максималды емес) клика, кликаға қосылуы мүмкін үміткер төбелердің жиыны және қосылмауы керек төбелердің басқа жиыны (өйткені бұл бұрыннан табылған кликаға әкеледі). Алгоритм үміткер төбелерді бірінен соң бірі жартылай кликаға қосуға тырысады, әрқайсысы үшін рекурсивті шақыру жасайды. Осы төбелердің әрқайсысын сынап көргеннен кейін, оны қайтадан қосуға болмайтын төбелер жиынына көшіреді. Бұл алгоритмнің нұсқалары тізімделуі қажет кликалар санына сәйкес келетін ең нашар жағдайда жұмыс істеу уақытына ие болуы мүмкін. Сондықтан бұл барлық максималды кликаларды тізімдеу мәселесіне ең нашар жағдайда оңтайлы шешім береді. Сонымен қатар, Bron–Kerbosch алгоритмі тәжірибеде оның баламаларына қарағанда жылдам екендігі туралы кеңінен хабарланды. Алайда, кликалар саны ең нашар жағдайдан айтарлықтай аз болған кезде, басқа алгоритмдер артық болуы мүмкін. Көрсетілгендей, графиктегі барлық максималды кликаны пайда болған кликаға полиномиялық уақыт көлемінде тізімдеуге де болады. Олардың алгоритміне ұқсас, оның орындалу уақыты шығыс көлеміне байланысты, ол шығысқа сезімтал алгоритм деп аталады. Олардың алгоритмі келесі екі байқауға негізделген, берілген G графигінің максималды кликаларын G \ v графигінің максималды кликаларына байланыстырады, ол G-ден кездейсоқ v төбесін алып тастау арқылы алынған: G \ v-дің әрбір максималды кликасы K үшін, K G-де максималды кликаны жалғастырады немесе K ∪ {v} G-де максималды кликаны құрайды. Сондықтан G-де G \ v-ге тең немесе одан көп максималды кликалар бар. G \ v құрамында v жоқ әрбір максималды клика G \ v-дегі максималды клика болып табылады, ал v құрамында G-дегі әрбір максималды клика G \ v-дегі максималды клика K-дан v-ді қосу және v-нің көрші емес элементтерін K-дан алып тастау арқылы құрылуы мүмкін. Осы байқауларды қолдану арқылы олар G-дегі барлық максималды кликаларды рекурсивті алгоритммен v төбесін кездейсоқ таңдап, содан кейін G \ v-дегі әрбір максималды клика K үшін K-ны және v-нің көрші емес элементтерін қосу арқылы құрылған кликаны шығарады. Алайда, G \ v-дің бірнеше аталық кликасынан осылайша G-дегі кейбір кликалар пайда болуы мүмкін, сондықтан олар G \ v-дегі аталық кликалардың ішінде тек қана лексикографиялық жағынан максималды болған кезде G-дегі кликаны шығару арқылы қайталануларды жояды. Бұл принциптің негізінде олар G-дегі барлық максималды кликаларды m – G-дегі жиектер саны, n – төбелер саны болып табылатын клика бойынша уақытта құруға болатынын көрсетеді. Мұны O(ma) кликаға дейін жақсартуға болады, мұнда a – берілген графиктің ағашқа ұқсастығы. Жылдам матрицалық көбейту негізінде шығысқа сезімтал алгоритмнің баламасын ұсынуға болады. Бұл тіпті барлық максималды кликаларды лексикографиялық тәртіппен клика бойынша полиномиялық кідіріспен тізімдеуге болатындығын көрсетеді. Алайда, рет таңдау осы алгоритмнің тиімділігі үшін маңызды: осы реттіліктің керісі үшін, егер P = NP болмаса, полиномиялық кідіру алгоритмі жоқ. Бұл нәтиже негізінде, полиномиялық уақыт бойынша барлық максималды кликаларды тізімдеуге болады, онда кликалар саны полиномиялық шектелген графтар отбасылары үшін. Бұл отбасыларға хордалық графтар, толық графтар, үшбұрышты еркін графтар, интервалдық графтар, шектелген боксикалық графтар және жазықтық графтар кіреді. Атап айтқанда, жазықтық графтарда ең көп дегенде тұрақты өлшемі бар, сызықтық уақытта тізімделуі мүмкін. Бұл графтар отбасының әрқайсысы үшін де солай, олар бір уақытта аз (көп дегенде константалық саны бар) және субграфтарды алу операциясы бойынша жабық. Жергілікті іздеу, ашкөз алгоритмдер және шектеулер бағдарламалау. Кликтерді табу үшін ұсынылған стандартты емес есептеу әдістемелеріне ДНК есептеу және адиабатикалық кванттық есептеу жатады. Максималды клика мәселесі 1992–1993 жылдары DIMACS демеушілігімен жүзеге асырылған және жалпыға қолжетімді графиктер жинағы осы сынақтың эталондық көрсеткіштері ретінде пайдаланылған.

By a result of , every n vertex graph has at most 3^(n/3) maximal cliques. They can be listed by the Bron–Kerbosch algorithm, a recursive backtracking procedure of The main recursive subroutine of this procedure has three arguments: a partially constructed (non maximal) clique, a set of candidate vertices that could be added to the clique, and another set of vertices that should not be added (because doing so would lead to a clique that has already been found). The algorithm tries adding the candidate vertices one by one to the partial clique, making a recursive call for each one. After trying each of these vertices, it moves it to the set of vertices that should not be added again. Variants of this algorithm can be shown to have worst case running time , matching the number of cliques that might need to be listed. Therefore, this provides a worst case optimal solution to the problem of listing all maximal cliques. Further, the Bron–Kerbosch algorithm has been widely reported as being faster in practice than its alternatives. However, when the number of cliques is significantly smaller than its worst case, other algorithms might be preferable. As showed, it is also possible to list all maximal cliques in a graph in an amount of time that is polynomial per generated clique. An algorithm such as theirs in which the running time depends on the output size is known as an output sensitive algorithm. Their algorithm is based on the following two observations, relating the maximal cliques of the given graph G to the maximal cliques of a graph G \ v formed by removing an arbitrary vertex v from G:
For every maximal clique K of G \ v, either K continues to form a maximal clique in G, or K ⋃ {v} forms a maximal clique in G. Therefore, G has at least as many maximal cliques as G \ v does. Each maximal clique in G that does not contain v is a maximal clique in G \ v, and each maximal clique in G that does contain v can be formed from a maximal clique K in G \ v by adding v and removing the non neighbors of v from K.
Using these observations they can generate all maximal cliques in G by a recursive algorithm that chooses a vertex v arbitrarily and then, for each maximal clique K in G \ v, outputs both K and the clique formed by adding v to K and removing the non neighbors of v. However, some cliques of G may be generated in this way from more than one parent clique of G \ v, so they eliminate duplicates by outputting a clique in G only when its parent in G \ v is lexicographically maximum among all possible parent cliques. On the basis of this principle, they show that all maximal cliques in G may be generated in time per clique, where m is the number of edges in G and n is the number of vertices. improve this to O(ma) per clique, where a is the arboricity of the given graph. provide an alternative output sensitive algorithm based on fast matrix multiplication. show that it is even possible to list all maximal cliques in lexicographic order with polynomial delay per clique. However, the choice of ordering is important for the efficiency of this algorithm: for the reverse of this order,
there is no polynomial delay algorithm unless P = NP. On the basis of this result, it is possible to list all maximal cliques in polynomial time, for families of graphs in which the number of cliques is polynomially bounded. These families include chordal graphs, complete graphs, triangle free graphs, interval graphs, graphs of bounded boxicity, and planar graphs. In particular, the planar graphs have cliques, of at most constant size, that can be listed in linear time. The same is true for any family of graphs that is both sparse (having a number of edges at most a constant times the number of vertices) and closed under the operation of taking subgraphs. local search, greedy algorithms, and constraint programming. Non standard computing methodologies that have been suggested for finding cliques include DNA computing and adiabatic quantum computation. The maximum clique problem was the subject of an implementation challenge sponsored by DIMACS in 1992–1993, and a collection of graphs used as benchmarks for the challenge, which is publicly available.

Графиктердің арнайы кластары

Жазық графиктер және басқа да сирек графиктер отбасылары жоғарыда талқыланды: олардың шектелген мөлшерде максималды кликалары бар, оларды сызықтық уақытта тізімдеуге болады. Салыстырылатын графиктердегі максималды кликалар үшін баламалы квадрат уақыт алгоритмін ұсынамыз, бұл пермутациялық графиктерді арнайы жағдай ретінде қамтитын, кеңейтілген толық графиктер класы. Хордалық графиктерде максималды кликаларды жою ретімен төбелерді тізімдеу арқылы және осы ретте әр төбе үшін кликалық көршіліктерді тексеру арқылы табуға болады. Кейбір жағдайларда, бұл алгоритмдер басқа, толық емес, графиктер кластарына да қолданылуы мүмкін. Мысалы, шеңберлік графикте әр төбедің көршілігі пермутациялық график болып табылады, сондықтан шеңберлік графиктегі максималды кликаны әрбір көршілікке пермутациялық график алгоритмін қолдану арқылы табуға болады. Сол сияқты, бірлік дискілік графикте (белгілі геометриялық өрнегімен) екібөлікті графиктердің толықтығына арналған алгоритмді төбелер жұбының ортақ көршіліктеріне қолдану арқылы максималды кликалар үшін полиномиалдық уақыт алгоритмі бар. Эрдос-Рени модельінде салынған кездейсоқ графикте максималды кликаны табудың алгоритмдік мәселесі (әр қабырға 1/2 ықтималдығымен пайда болады, басқа қабырғалардан тәуелсіз) ұсынылды. Кездейсоқ графиктегі максималды кликаның мөлшері жоғары ықтималдықпен логарифмдік болғандықтан, оны күтілетін уақытта қарапайым іздеу арқылы табуға болады. Бұл квазиполиномиалдық уақыт шегі. Мұндай графиктердің клика саны әдетте 2 log2n-ге өте жақын болса да, қарапайым ашкөз алгоритмдер және күрделі кездейсоқ жуықтау әдістері тек log2n мөлшерінде кликаларды табады, бұл жартылай кішкентай. Мұндай графиктердегі максималды кликалар саны жоғары ықтималдықпен log^(2)n экспоненциалды, бұл барлық максималды кликаларды тізімдейтін әдістердің полиномиалдық уақытта жұмыс істеуіне кедергі келтіреді. Бұл мәселенің қиындығына байланысты, бірнеше авторлар ірі кликаларды қосу арқылы кеңейтілген кездейсоқ графиктердегі отырғызылған клика мәселесін зерттеді. Спектрлік әдістер және жартылай анықталған бағдарламалау жасырын өлшемді кликаларды анықтауға мүмкіндік берсе, қазірдің күніне (кіші o белгісімен көрсетілген) өлшемді кликаларды анықтауға арналған полиномиалдық уақыт алгоритмі жоқ.

Planar graphs, and other families of sparse graphs, have been discussed above: they have linearly many maximal cliques, of bounded size, that can be listed in linear time. provide an alternative quadratic time algorithm for maximum cliques in comparability graphs, a broader class of perfect graphs that includes the permutation graphs as a special case. In chordal graphs, the maximal cliques can be found by listing the vertices in an elimination ordering, and checking the clique neighborhoods of each vertex in this ordering. In some cases, these algorithms can be extended to other, non perfect, classes of graphs as well. For instance, in a circle graph, the neighborhood of each vertex is a permutation graph, so a maximum clique in a circle graph can be found by applying the permutation graph algorithm to each neighborhood. Similarly, in a unit disk graph (with a known geometric representation), there is a polynomial time algorithm for maximum cliques based on applying the algorithm for complements of bipartite graphs to shared neighborhoods of pairs of vertices. The algorithmic problem of finding a maximum clique in a random graph drawn from the Erdős–Rényi model (in which each edge appears with probability 1/2, independently from the other edges) was suggested by Because the maximum clique in a random graph has logarithmic size with high probability, it
can be found by a brute force search in expected time This is a quasi polynomial time bound. Although the clique number of such graphs is usually very close to 2 log2n, simple greedy algorithms as well as more sophisticated randomized approximation techniques only find cliques with size log2n, half as big. The number of maximal cliques in such graphs is with high probability exponential in log^(2)n, which prevents methods that list all maximal cliques from running in polynomial time. Because of the difficulty of this problem, several authors have investigated the planted clique problem, the clique problem on random graphs that have been augmented by adding large cliques. While spectral methods and semidefinite programming can detect hidden cliques of size , no polynomial time algorithms are currently known to detect those of size (expressed using little o notation).

Тарату алгоритмдері

Бірнеше авторлар полиномиалдық уақыт ішінде ең үлкенге жақын мөлшерде клика немесе тәуелсіз жиынтықты табуға тырысатын жуықтама алгоритмдерін қарастырды. Бұл жұмыстың көп бөлігі сирек графиктердегі тәуелсіз жиынтықтарға, бірақ бұл қосымша клика мәселесі үшін мағынасы жоқ, сондай-ақ мұндай сиректілік туралы болжамдарға сүйенбейтін жуықтама алгоритмдеріне қатысты болды. Ол, кез келген тұрақты k үшін клика саны Ω(n/log^(k)n) болатын кез келген графтан Ω((log n/log log n)^(2)) өлшемді кликаны табатын полиномиалдық уақыт алгоритмін сипаттайды. Егер берілген кіріс графигінің клика саны n/log n және n/log^(3)n аралығында болса, бұл алгоритмді қолданып, жоғары клика саны бар графтар үшін басқа алгоритмға ауысып, егер екі алгоритм де ештеңе таба алмаса, екі төбелі кликаны таңдау арқылы Фейге ең үлкенінен O(n(log log n)^(2)/log^(3)n) факторға дейін төбелері бар кликаны табатын жуықтама алгоритмін ұсынады. Бұл алгоритмнің жуықтама коэффициенті нашар болғанымен, қазіргі таңдағы ең жақсысы болып табылады. Төменде сипатталған жуықтаманың қиындығына қатысты нәтижелер, сызықтықтан айтарлықтай төмен жуықтама коэффициенті бар жуықтама алгоритмінің болуы мүмкін емес екенін көрсетеді.

NP-толықтығы

Клика шешімі проблемасы NP-толық. Бұл Ричард Карптың 1972 жылғы «Комбинаторлық проблемалар арасындағы келуге келтіру» атты мақаласында NP-толықтығын көрсеткен 21 проблеманың бірі болды. Бұл мәселе Стивен Куктың NP-толық проблемалар теориясын енгізген мақаласында да айтылған. Шешім проблемасының қиындығына байланысты, максималды кликаны табу проблемасы да NP-қиын. Егер оны шеше алсаңыз, шешім беру мәселесін де шеше аласыз, яғни максималды кликаның мөлшерін шешім беру мәселесінде кіріс ретінде берілген мөлшерлік параметрмен салыстыру арқылы. Карптың NP-толықтығын дәлелдеуі – Бульдік қанағаттандыру проблемасынан бірге келуге келтіру. Ол Бульдік формулаларды конъюнктивті қалыпты формада (CNF) максималды клика проблемасының эквивалентті мысалдарына қалай аударуға болатынын сипаттайды. Қанағаттандыру, өз кезегінде, Кук-Левин теоремасында NP-толық екені дәлелденді. Берілген CNF формуласынан Карп әрбір жұп (v, c) үшін төбесі бар граф құрайды, мұнда v – айнымалы немесе оның жоқтығы, ал c – v кіретін формуланың шарттары. Егер олар әртүрлі шарттар үшін үйлесімді айнымалы мәндерін білдірсе, осы екі төбе жиекпен байланыстырылады. Яғни, (v, c) төбесінен (u, d) төбесіне жиек бар, егер c ≠ d және u мен v бір-бірінің жоқтығы болмаса. Егер k CNF формуласындағы шарттардың санын білдірсе, онда k төбелі кликалар осы графқа сәйкес келетін кейбір айнымалыларға шындық мәндерін берудің дұрыс жолдарын білдіреді, формулаға қанағаттандыру үшін. Сондықтан формула тек қана k төбелі клика болған жағдайда ғана қанағаттандырылады. Кейбір NP-толық проблемалар (мысалы, жазық графтардағы саяхатшы сатушысы проблемасы) кіріс мөлшерлік параметрінің сызықтық функциясында экспоненциалды уақытта шешілуі мүмкін, бұл күшпен іздеуден әлдеқайда жылдам. Алайда, кездейсоқ графтардағы клика проблемасы үшін мұндай субекспоненциалды уақыт шегі болуы екіталай, өйткені бұл көптеген басқа стандартты NP-толық проблемалар үшін ұқсас субекспоненциалды шектеулерді білдіретін болар еді.

Сұлбаның күрделілігі

Кликаның есептеу қиындығы оны схеманың күрделілігінің төменгі шектерін дәлелдеу үшін қолдануға алып келді. Белгілі бір мөлшердегі кликаның болуы – монотонды граф қасиеті, яғни егер клика берілген графтың ішінде болса, ол кез келген үстел графтың ішінде де болады. Бұл қасиет монотонды болғандықтан, белгілі бір тұрақты клика мөлшері үшін кликаны табу мәселесін шешу үшін тек "және" және "немесе" қақпаларын қолданатын монотонды схема болуы керек. Дегенмен, мұндай схемалардың мөлшері төбелер санының және клика мөлшерінің суперполиномдық функциясы болып келеді, төбелер санының куб түбіріне қатысты экспоненциалдық өсімді көрсетеді. Тіпті аз ғана "жоқ" қақпаларына рұқсат берілсе де, күрделілік суперполиномдық болып қалады. Сонымен қатар, шектеулі таралуы бар қақпаларды қолданатын клика мәселесі үшін монотонды схеманың тереңдігі клика мөлшеріне қатысты кемінде полиномдық болуы керек.

Шешім ағашының күрделілігі

Графтың қасиетін анықтаудың (детерминистік) шешім ағашының күрделілігі – бұл ең нашар жағдайда графтың белгілі бір қасиетке ие екенін анықтау үшін «u және v төбелері арасында қабырға бар ма?» түріндегі қанша сұраққа жауап беру қажеттігі. Яғни, бұл мәселе үшін Бульдік шешім ағашының ең төменгі биіктігі. Сұрауға болатын n(n-1)/2 мүмкін сұрақ бар. Сондықтан, кез келген граф қасиетін ең көп дегенде n(n-1)/2 сұрақ арқылы анықтауға болады. Сонымен қатар, кездейсоқ және кванттық шешім ағашының күрделілігін анықтауға болады, ол – ең нашар жағдайдың кірісі үшін, берілген графтың қасиетке ие екенін дұрыс анықтау үшін кездейсоқ немесе кванттық алгоритмге жауап беру қажетті сұрақтардың күтілетін саны. Кликтің болу қасиеті монотонды болғандықтан, ол Андреаа-Карп-Розенберг болжамымен қамтылады, онда кез келген тривиальды емес монотонды граф қасиетін анықтаудың детерминистік шешім ағашының күрделілігі дәл n(n-1)/2 тең. Кездейсоқ монотонды граф қасиеттері үшін бұл болжам әлі де дәлелденбеген. Алайда, детерминистік шешім ағаштары үшін және 2 ≤ k ≤ n диапазонындағы кез келген k үшін, k кликтің болу қасиетінің шешім ағашының күрделілігі дәл n(n-1)/2 екені көрсетілген. Детерминистік шешім ағаштары кликті анықтау үшін экспоненциалды көлемді немесе шектелген өлшемдегі кликті анықтау үшін үлкен полиномиалдық көлемді қажет етеді. Андреаа-Карп-Розенберг болжамы сондай-ақ тривиальды емес монотонды функциялардың кездейсоқ шешім ағашының күрделілігі Θ(n²) тең дейді. Бұл болжам да әлі де дәлелденбеген, бірақ k кликтің болу қасиеті үшін 2 ≤ k ≤ n диапазонында шешілді. Бұл қасиеттің кездейсоқ шешім ағашының күрделілігі Θ(n²) екені белгілі. Кванттық шешім ағаштары үшін ең танымал төменгі шек Ω(n), бірақ k ≥ 3 жағдайы үшін сәйкес алгоритм белгісіз.

Белгілі бір параметрмен жұмыс істеу қабілеті

Параметрленген күрделілік – табиғи түрде кіші бүтін параметр k-мен жабдықталған және k өскен сайын проблема қиындап бара жатқан проблемалардың күрделілік теориясын зерттеу, мысалы, графтарда k кликаларды табу. Егер n өлшемді кіріс үшін мәселені шешетін алгоритм және f функциясы болса, онда проблема тұрақты параметрмен шешілетін болады. Яғни, егер k-ның кез келген тұрақты мәні үшін ол полиномиалдық уақытта шешілсе, және полиномиалдың дәрежесі k-ға тәуелді болмаса, онда ол тұрақты параметрмен шешілетін болады. k төбелік кликаларды табу үшін, толық іздеу алгоритмінің жұмыс уақыты O(n^k * k^2) құрайды. n-нің дәрежесі k-ға тәуелді болғандықтан, бұл алгоритм тұрақты параметрмен шешілмейді. Жылдам матрицалық көбейту арқылы жақсартылса да, жұмыс уақыты k-ға сызықтық дәрежеге ие болады. Осылайша, клика мәселесі үшін белгілі алгоритмдердің жұмыс уақыты кез келген k үшін полиномиалды болғанымен, бұл алгоритмдер тұрақты параметрлік шешімге жеткіліксіз. Олар параметрленген проблемалардың иерархиясын, W иерархиясын анықтады және олардың тұрақты параметрлік алгоритмдері жоқ деп болжады. Олар тәуелсіз жиынның (немесе, эквивалентті түрде, кликаның) осы иерархияның бірінші деңгейі W[1] үшін қиын екенін дәлелдеді. Осылайша, олардың болжамына сәйкес, кликаның тұрақты параметрлік алгоритмі жоқ. Бұдан әрі, бұл нәтиже көптеген басқа проблемалардың W[1] қиындығын дәлелдеуге негіз болады және параметрленген күрделілік үшін Кук-Левин теоремасының аналогы ретінде қызмет етеді. k төбелік кликаны табу n^(o(k)) уақытында орындалмайтынын көрсетті, егер экспоненциалдық уақыт гипотезасы сәтсіз болса. Бұл да тұрақты параметрлік алгоритмнің болу мүмкін еместігіне дәлел. Максималды кликаларды тізімдеу немесе максималды кликаны табу проблемалары k параметрімен тұрақты параметрлік шешімге ие болмаса да, олар инстанция күрделілігінің басқа параметрлері үшін тұрақты параметрлік шешімге ие болуы мүмкін. Мысалы, екі проблема да кіріс графының дегенерациясы бойынша параметрленгенде тұрақты параметрлік шешімге ие екені белгілі.

Parameterized complexity is the complexity theoretic study of problems that are naturally equipped with a small integer parameter k and for which the problem becomes more difficult as k increases, such as finding k cliques in graphs. A problem is said to be fixed parameter tractable if there is an algorithm for solving it on inputs of size n, and a function f, such that the algorithm runs in time That is, it is fixed parameter tractable if it can be solved in polynomial time for any fixed value of k and moreover if the exponent of the polynomial does not depend on k.

For finding k vertex cliques, the brute force search algorithm has running time O(n^(k)k^(2)). Because the exponent of n depends on k, this algorithm is not fixed parameter tractable. Although it can be improved by fast matrix multiplication, the running time still has an exponent that is linear in k. Thus, although the running time of known algorithms for the clique problem is polynomial for any fixed k, these algorithms do not suffice for fixed parameter tractability. defined a hierarchy of parametrized problems, the W hierarchy, that they conjectured did not have fixed parameter tractable algorithms. They proved that independent set (or, equivalently, clique) is hard for the first level of this hierarchy, W[1]. Thus, according to their conjecture, clique has no fixed parameter tractable algorithm. Moreover, this result provides the basis for proofs of W[1] hardness of many other problems, and thus serves as an analogue of the Cook–Levin theorem for parameterized complexity. showed that finding k vertex cliques cannot be done in time n^(o(k)) unless the exponential time hypothesis fails. Again, this provides evidence that no fixed parameter tractable algorithm is possible. Although the problems of listing maximal cliques or finding maximum cliques are unlikely to be fixed parameter tractable with the parameter k, they may be fixed parameter tractable for other parameters of instance complexity. For instance, both problems are known to be fixed parameter tractable when parametrized by the degeneracy of the input graph.

Қаттылығы шамамен

Клика проблемасын шамамен шешу қиын болуы мүмкін деген әлсіз нәтижелер ұзақ уақыттан бері белгілі. Клика саны кішкентай бүтін сандық мәндерді қабылдайды және оны есептеу NP-қиын болғандықтан, P = NP болмаса, оның толық полиномиалдық уақытқа жуықтау схемасы болуы мүмкін емес. Егер шамамен дәл жуықтау болса, оның мәнін бүтін санға дөңгелектеу дәл клика санын береді. Алайда, 1990 жылдардың басына дейін, бірнеше авторлар максималды кликаларды шамамен анықтау және ықтималдықпен тексерілетін дәлелдер арасындағы байланысты жасай бастағанға дейін, аз ғана мәлімет белгілі болды. Олар осы байланыстарды максималды клика мәселесі үшін шамалаудың қиындығын дәлелдеу үшін пайдаланды. Бұл нәтижелерді көптеген жақсартулардан кейін, қазір белгілі болғандай, кез келген нақты сан ε > 0 үшін, егер P = NP болмаса, ең үлкен кликаны артық фактормен шамалайтын полиномиалдық уақыт алгоритмі болуы мүмкін емес. Бұл жуықтамау нәтижелерінің негізгі идеясы – Бульдік қанағаттандыру мәселесі сияқты NP-толық мәселе үшін ықтималдықпен тексерілетін дәлелдеу жүйесін көрсететін граф құру. Ықтималдықпен тексерілетін дәлелдеу жүйесінде дәлелдеме биттер тізбегі ретінде ұсынылады. Қанағаттандыру мәселесінің бір мысалы, егер және тек қана қанағаттандырылатын болса, ғана жарамды дәлелдемеге ие болуы керек. Дәлелдемені алгоритммен тексеру, қанағаттандыру мәселесінің кірісінде полиномиалдық уақыт есептеуден кейін, дәлелдеме тізбегінің кездейсоқ таңдалған позицияларының шағын санын тексеруді таңдайды. Биттер үлгісінде қандай мәндер табылғанына байланысты, тексеруші қалған биттерді қарамай, дәлелдемені қабылдайды немесе қабылдамайды. Жалған теріс нәтижелерге жол берілмейді: жарамды дәлелдеме әрқашан қабылдалуы тиіс. Алайда, жарамсыз дәлелдеме кейде қателікпен қабылдануы мүмкін. Кез келген жарамсыз дәлелдеме үшін, тексерушінің оны қабылдауының ықтималдығы төмен болуы керек.

Сауалнамалар мен оқулықтар

Since no English text was provided, and the reference translation is empty, I cannot provide a translation. Please provide the English text you want translated.

Зерттеу мақалалары

. . . Алғаш рет 1992 жылғы Компьютер ғылымының негіздері жөніндегі симпозиумда ұсынылған, . Алғаш рет 1992 жылғы Компьютер ғылымының негіздері жөніндегі симпозиумда ұсынылған, . . . . . . . . . . . . . . . . . . . . . Бастапқы код . . . . . . . . . . . . . . . . . .