Cograph

Turán-grafen T ( 13,4), ett exempel på en kograf

I grafteorin är en kograf , eller komplement-reducerbar graf , eller P ₄ -fri graf , en graf som kan genereras från singelvertexgrafen K ₁ genom komplementering och disjunkt förening . Det vill säga, familjen av kografer är den minsta klassen av grafer som inkluderar K ₁ och är stängd under komplement och osammanhängande förening.

Cographs har upptäckts oberoende av flera författare sedan 1970-talet; tidiga referenser inkluderar Jung (1978) , Lerchs (1971) , Seinsche (1974) och Sumner (1974) . De har också kallats D*-grafer , ärftliga Dacey-grafer (efter det relaterade arbetet av James C. Dacey Jr. om ortomodulära gitter ) och 2-paritetsgrafer . De har en enkel strukturell sönderdelning som involverar disjunkta unions- och komplementgrafoperationer som kan representeras kortfattat av ett märkt träd, och används algoritmiskt för att effektivt lösa många problem som att hitta den maximala klicken som är svåra för mer allmänna grafklasser.

Särskilda fall av kograferna inkluderar de fullständiga graferna , fullständiga tvådelade grafer , klustergrafer och tröskeldiagram . Kograferna är i sin tur specialfall av ärftliga avståndsgrafer , permutationsgrafer , jämförbarhetsgrafer och perfekta grafer .

Definition

Rekursiv konstruktion

Alla kografer kan konstrueras enligt följande regler:

1. varje enskild vertexgraf är en kograf;
2. om $G$ är en kograf, så är dess komplementgraf ${\overline {G}}$ ;
3. om $G$ och $H$ är kografer, så är deras disjunkta förening $G\cup H$ .

Kograferna kan definieras som de grafer som kan konstrueras med hjälp av dessa operationer, utgående från graferna med en vertex. Alternativt, istället för att använda komplementoperationen, kan man använda joinoperationen, som består av att bilda den disjunkta föreningen $G\cup H$ och sedan lägga till en kant mellan varje par av ett vertex från $G$ och en vertex från $H$ .

Andra karaktäriseringar

Flera alternativa karakteriseringar av kografer kan ges. Bland dem:

• En kograf är en graf som inte innehåller vägen P ₄ på 4 hörn (och därmed av längd 3) som en inducerad subgraf . Det vill säga, en graf är en kograf om och endast om för fyra hörn $v_{1},v_{2},v_{3},v_{4}$ , om $\{v_{1},v_{2}\},\{v_{2},v_{3}\}$ och $\{v_{3},v_{4}\}$ är kanter på grafen då minst en av ${\ displaystyle \{v_{1},v_{3}\},\{v_{1},v_{4}\}}$ eller $\{v_{2},v_{4 }\}$ är också en kant.
• En kograf är en graf vars alla inducerade subgrafer har egenskapen att varje maximal klick skär varje maximal oberoende uppsättning i en enda vertex.
• En kograf är en graf där varje icke-trivial inducerad subgraf har minst två hörn med samma grannskap.
• En kograf är en graf där varje ansluten inducerad subgraf har ett frånkopplat komplement.
• En kograf är en graf vars alla anslutna inducerade subgrafer har en diameter på högst 2.
• En kograf är en graf där varje ansluten komponent är en avståndsärftlig graf med en diameter på högst 2.
• En kograf är en graf med högst 2 klickbredd .
• En kograf är en jämförbarhetsgraf av en serieparallell partiell ordning .
• En kograf är en permutationsgraf av en separerbar permutation .
• En kograf är en graf vars minimala ackordkompletteringar är trivialt perfekta grafer .
• En kograf är en ärftligt välfärgad graf , en graf så att varje girig färgning av varje inducerad subgraf använder ett optimalt antal färger.
• En graf är en kograf om och endast om varje vertexordning i grafen är en perfekt ordning , eftersom att ha inget P ₄ betyder att inget hinder för en perfekt ordning kommer att existera i någon vertexordning.

Cotrees

Ett cotree och motsvarande kograf. Varje kant ( u , v ) i kografen har en färg som matchar den minst gemensamma förfadern till u och v i koträdet.

Ett cotree är ett träd där de interna noderna är märkta med siffrorna 0 och 1. Varje cotree T definierar en kograf G med bladen på T som hörn, och i vilket subträdet som är rotat vid varje nod av T motsvarar den inducerade subgrafen i G definierat av uppsättningen löv som faller från den noden:

• Ett underträd som består av en enda lövnod motsvarar en inducerad subgraf med en enda vertex.
• Ett underträd med rötter i en nod märkt 0 motsvarar föreningen av subgraferna som definieras av den nodens barn.
• Ett underträd som är rotat vid en nod märkt 1 motsvarar sammanfogningen av subgraferna definierade av den nodens barn; det vill säga vi bildar föreningen och lägger till en kant mellan varannan hörn som motsvarar löv i olika underträd. Alternativt kan sammanfogningen av en uppsättning grafer ses som bildad genom att komplettera varje graf, bilda föreningen av komplementen och sedan komplettera den resulterande föreningen.

Ett ekvivalent sätt att beskriva kografen som bildas av ett cotree är att två hörn är sammankopplade med en kant om och endast om den lägsta gemensamma förfadern av motsvarande blad är märkt med 1. Omvänt kan varje kograf representeras på detta sätt av ett cotree . Om vi ​​kräver att etiketterna på någon rot-bladsbana i detta träd ska växla mellan 0 och 1, är denna representation unik.

Beräkningsegenskaper

Cographs kan kännas igen i linjär tid, och en cotree-representation konstrueras, med hjälp av modulär nedbrytning , partitionsförfining , LexBFS eller delad uppdelning . När en samträdsrepresentation väl har konstruerats kan många välbekanta grafproblem lösas via enkla bottom-up-beräkningar på cotrees.

Till exempel, för att hitta den maximala klicken i en kograf, beräkna i ordning nerifrån och upp den maximala klicken i varje subgraf som representeras av ett underträd till koträdet. För en nod märkt 0 är den maximala klicken den maximala bland klicken som beräknas för den nodens barn. För en nod märkt 1 är den maximala klicken föreningen av klicken som beräknas för den nodens barn och har en storlek lika med summan av barnklickstorlekarna. Genom att växelvis maximera och summera värden lagrade vid varje nod i cotree kan vi alltså beräkna den maximala klickstorleken, och genom att växelvis maximera och ta fackföreningar kan vi konstruera själva den maximala klicken. Liknande bottom-up-trädberäkningar gör att den maximala oberoende uppsättningen , vertexfärgningsnumret , maximala klicktäckningen och Hamiltoniciteten (det vill säga förekomsten av en Hamilton-cykel ) kan beräknas i linjär tid från en cotree-representation av en kograf. Eftersom kografer har begränsat klickbredden, Courcelles sats användas för att testa vilken egenskap som helst i den monadiska andra ordningens logik för grafer (MSO ₁ ) på kografer i linjär tid.

Problemet med att testa om en given graf är k hörn borta och/eller t kanter bort från en kograf är löserbart med fasta parametrar . Att bestämma om en graf kan k -kant-deletas till en kograf kan lösas i O ^* (2,415 ^k ) tid, och k -kant-redigeras till en kograf i O ^* (4,612 ^k ). Om den största inducerade kografsubgrafen i en graf kan hittas genom att ta bort k hörn från grafen, kan den hittas i O ^* (3,30 ^k ) tid.

Två kografer är isomorfa om och endast om deras samträd (i den kanoniska formen utan två angränsande hörn med samma etikett) är isomorfa. På grund av denna ekvivalens kan man i linjär tid bestämma om två kografer är isomorfa, genom att konstruera deras samträd och tillämpa ett linjärt tidsisomorfismtest för märkta träd.

Om H är en inducerad subgraf av en kograf G , så är H själv en kograf; cotree för H kan bildas genom att ta bort några av bladen från cotree för G och sedan undertrycka noder som bara har ett barn. Det följer av Kruskals trädsats att förhållandet att vara en inducerad subgraf är en väl kvasi-ordning på kograferna. Således, om en underfamilj av kograferna (såsom de plana kograferna) stängs under inducerade subgrafoperationer, har den ett ändligt antal förbjudna inducerade subgrafer . Beräkningsmässigt betyder detta att testning av medlemskap i en sådan underfamilj kan utföras i linjär tid, genom att använda en nedifrån-och-upp-beräkning på samträdet till en given graf för att testa om den innehåller någon av dessa förbjudna subgrafer. Men när storlekarna på två kografer båda är variabla, är testet om en av dem är en inducerad subgraf till den andra NP-komplett .

Kografer spelar en nyckelroll i algoritmer för att känna igen läs-en gång funktioner .

Uppräkning

Antalet sammankopplade kografer med n hörn, för n = 1, 2, 3, ..., är:

1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, 7068, 21965, 68954, ... (sekvens A000669 i OEIS )

För n > 1 finns det samma antal frånkopplade kografer, eftersom för varje kograf är exakt en av den eller dess komplementgraf kopplad.

Relaterade graffamiljer

Underklasser

Varje komplett graf K _n är en kograf, med ett cotree som består av en enda 1-nod och n blad. På liknande sätt är varje komplett tvådelad graf _{Ka, en kograf} b . Dess samträd är rotat i en 1-nod som har två 0-nodsbarn, ett med ett lövbarn och ett med b lövbarn. En Turán-graf kan bildas genom sammanfogningen av en familj av lika stora oberoende uppsättningar; sålunda är det också en kograf, med ett cotree rotat på en 1-nod som har en underordnad 0-nod för varje oberoende uppsättning.

Varje tröskeldiagram är också en kograf. En tröskelgraf kan bildas genom att upprepade gånger lägga till en vertex, antingen kopplad till alla tidigare hörn eller till ingen av dem; varje sådan operation är en av de osammanfogade fackliga eller sammanfogade operationerna genom vilka ett cotree kan bildas.

Superklasser

Karakteriseringen av kografer genom egenskapen att varje klick och maximal oberoende uppsättning har en icke-tom skärningspunkt är en starkare version av den definierande egenskapen för starkt perfekta grafer , där varje inducerad subgraf innehåller en oberoende uppsättning som skär alla maximala klick. I en kograf skär varje maximal oberoende uppsättning alla maximala klicker. Således är varje kograf starkt perfekt.

Det faktum att kografer är P4 _- fria innebär att de är perfekt beställningsbara . Faktum är att varje vertexordning för en kograf är en perfekt ordning, vilket ytterligare antyder att max klickfynd och min färgning kan hittas i linjär tid med vilken girig färg som helst och utan behov av en cotree-nedbrytning.

Varje kograf är en avståndsärftlig graf , vilket betyder att varje inducerad väg i en kograf är den kortaste vägen . Kograferna kan karakteriseras bland de ärftliga avståndsgraferna som att de har diameter två i varje ansluten komponent. Varje kograf är också en jämförbarhetsgraf av en serieparallell partiell ordning , erhållen genom att ersätta den osammanfogade unions- och sammanfogningsoperationerna genom vilka kografen konstruerades av osammanhängande unions- och ordinalsummaoperationer på partiella beställningar. Eftersom starkt perfekta grafer, perfekt beställningsbara grafer, ärftliga avståndsgrafer och jämförbarhetsgrafer alla är perfekta grafer , är kografer också perfekta.

Anteckningar

•   Berge, C .; Duchet, P. (1984), "Strongly perfect graphs", Topics on Perfect Graphs , North-Holland Mathematics Studies, vol. 88, Amsterdam: North-Holland, s. 57–61, doi : 10.1016/S0304-0208(08)72922-0 , MR 0778749 .
•   Bose, Prosenjit ; Buss, Jonathan; Lubiw, Anna (1998), "Pattern matching for permutations", Information Processing Letters , 65 (5): 277–283, doi : 10.1016/S0020-0190(97)00209-3 , MR 1620935 .
•   Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy P. (1999), Graph Classes: A Survey , SIAM Monographs on Discrete Mathematics and Applications, ISBN 978-0-89871-432-6 .
• Burlet, M.; Uhry, JP (1984), "Parity Graphs", Topics on Perfect Graphs , Annals of Discrete Mathematics, vol. 21, s. 253–277 .
•   Bretscher, A.; Corneil, DG ; Habib, M.; Paul, C. (2008), "A simple Linear Time LexBFS Cograph Recognition Algorithm", SIAM Journal on Discrete Mathematics , 22 (4): 1277–1296, CiteSeerX 10.1.1.188.5016 , doi : 10.60667/9.60667 .
• Cai, L. (1996), "Fixed-parameter tractability of graph modification problems for hereditary properties", Information Processing Letters , 58 (4): 171–176, doi : 10.1016/0020-0190(96)00050-6 .
•   Christen, Claude A.; Selkow, Stanley M. (1979), "Some perfect coloring properties of graphs", Journal of Combinatorial Theory , Series B, 27 (1): 49–59, doi : 10.1016/0095-8956(79)90067-4 , MR 0539075 .
•   Corneil, DG ; Lerchs, H.; Stewart Burlingham, L. (1981), "Complement reducible graphs", Discrete Applied Mathematics , 3 (3): 163–174, doi : 10.1016/0166-218X(81)90013-5 , MR 0619603 .
•   Corneil, DG ; Perl, Y.; Stewart, LK (1985), "A linear recognition algorithm for cographs", SIAM Journal on Computing , 14 (4): 926–934, doi : 10.1137/0214065 , MR 0807891 .
•     Courcelle, B.; Makowsky, JA; Rotics, U. (2000), "Linear time solvable optimization problems on graphs of bounded clique-width", Theory of Computing Systems , 33 (2): 125–150, doi : 10.1007/s002249910009 , 6 MR 413,0009 , MR 413 , 0bl , MR 413 , 0bl 1009.68102 .
• Courcelle, B. ; Olariu, S. (2000), " Upper bounds to the clique width of graphs" , Discrete Applied Mathematics , 101 (1–3): 77–144, doi : 10.1016/S0166-218X(99) 00184-14 ,   .
•   Damaschke, Peter (1990), "Induced subgraphs and well-quasi-ording", Journal of Graph Theory , 14 (4): 427–435, doi : 10.1002/jgt.3190140406 , MR 1067237 .
• Damaschke, Peter (1991), "Induced subraph isomorphism for cographs is NP-complete", i Möhring, Rolf H. (red.), Graph- Theoretic Concepts in Computer Science: 16th International Workshop WG '90 Berlin, Tyskland, 20 juni –22, 1990, Proceedings , Lecture Notes in Computer Science, vol. 484, Springer-Verlag, s. 72–78, doi : 10.1007/3-540-53832-1_32 .
•    Gioan, Emeric; Paul, Christophe (2012), "Split decomposition and graph-labeld trees: characterizations and fullt dynamiska algoritmer för totalt nedbrytbara grafer", Discrete Applied Mathematics , 160 (6): 708–733, arXiv : 0810.1823 , doi .01 . dam.2011.05.007 , MR 2901084 , S2CID 6528410 .
•    Golumbic, Martin C .; Gurvich, Vladimir (2011), "Read-once functions" (PDF) , i Crama, Yves; Hammer, Peter L. (red.), Boolean functions , Encyclopedia of Mathematics and its Applications, vol. 142, Cambridge University Press, Cambridge, s. 519–560, doi : 10.1017/CBO9780511852008 , ISBN 978-0-521-84751-3 , MR 2742439 .

•   Habib, Michel; Paul, Christophe (2005), "A simple linear time algorithm for cograph recognition" (PDF) , Discrete Applied Mathematics , 145 (2): 183–197, doi : 10.1016/j.dam.2004.01.011 , MR 201 .
• Jung, HA (1978), "On a class of posets and the corresponding comparability graphs", Journal of Combinatorial Theory , Series B, 24 (2): 125–133, doi : 10.1016/0095-8956(78)90013-8 MR 0491356 .   _
• Lerchs, H. (1971), On cliques and kernels , Tech. Rapport, Inst. för komp. Sci., Univ. av Toronto .
• Liu, Yunlong Liu; Wang, Jianxin; Guo, Jiong; Chen, Jianer (2012), "Complexity and parameterized algorithms for Cograph Editing", Theoretical Computer Science , 461 : 45–54, doi : 10.1016/j.tcs.2011.11.040 .
• Nastos, James; Gao, Yong (2010), "A novel branching strategy for parameterized graph modification problems", i Wu, Weili; Daescu, Ovidiu (red.), Combinatorial Optimization and Applications – 4th International Conference, COCOA 2010, Kailua-Kona, HI, USA, 18–20 december 2010, Proceedings, Part II , Lecture Notes in Computer Science, vol. 6509, Springer, s. 332–346, arXiv : 1006.3020 , doi : 10.1007/978-3-642-17461-2_27
•   Parra, Andreas; Scheffler, Petra (1997), "Characterizations and algorithmic applications of chordal graph embeddings", 4th Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1995), Discrete Applied Mathematics , 79 (1–3): 171–188, 171–188, do . /S0166-218X(97)00041-3 , MR 1478250 .
•   Seinsche, D. (1974), "On a property of the class of n -colorable graphs", Journal of Combinatorial Theory , Series B, 16 (2): 191–193, doi : 10.1016/0095-8956(74)90063 -X , MR 0337679 .
•   Sumner, DP (1974), "Dacey graphs", Journal of the Australian Mathematical Society , 18 (4): 492–502, doi : 10.1017/S1446788700029232 , MR 0382082 .

externa länkar

• "Cograph graphs" , informationssystem om grafklassinneslutningar
• Weisstein, Eric W. , "Cograph" , MathWorld