Perfekt beställningsdiagram - Perfectly orderable graph

I grafteorin är en perfekt beställbar graf en graf vars hörn kan ordnas på ett sådant sätt att en girig färgningsalgoritm med den ordningen optimalt färgar varje inducerad subgraf i den givna grafen. Perfekt beställbara grafer bildar ett speciellt fall av de perfekta graferna , och de inkluderar ackorddiagram , jämförbarhetsdiagram och avstånds-ärftliga grafer . Att testa om ett diagram är perfekt beställbart är dock NP-komplett .

Definition

Den giriga färgningsalgoritmen, när den tillämpas på en given ordning av topparna i ett diagram G , betraktar kurvorna i diagrammet i sekvens och tilldelar varje toppunkt sin första tillgängliga färg, det minsta uteslutna värdet för den uppsättning färger som används av sina grannar. Olika toppunktbeställningar kan leda till att denna algoritm använder olika antal färger. Det finns alltid en ordning som leder till en optimal färgning - detta gäller till exempel den ordning som bestäms av en optimal färgning genom att sortera topparna efter deras färg - men det kan vara svårt att hitta. De perfekt ordningsbara graferna definieras som de grafer för vilka det finns en ordning som är optimal för den giriga algoritmen, inte bara för själva grafen utan för alla dess inducerade underbilder .

Mer formellt sägs en graf G vara perfekt ordningsbar om det finns en ordning π för G- hörn , så att varje inducerad subgraf av G är optimalt färgad av den giriga algoritmen med användning av följden av π inducerad av undergraferna. . En ordning π har den här egenskapen exakt när det inte finns fyra hörn a , b , c och d för vilka abcd är en inducerad bana, a visas före b i ordningen och c visas efter d i ordningen.

Beräkningskomplexitet

Perfekt beställbara diagram är NP-kompletta att känna igen. Det är dock lätt att testa om en viss beställning är en perfekt beställning av ett diagram. Följaktligen är det också NP-svårt att hitta en perfekt ordning av en graf, även om grafen redan är känd för att vara perfekt beställbar.

Relaterade diagramklasser

Varje perfekt beställbar graf är en perfekt graf .

Akkorddiagram är perfekt beställbara; en perfekt ordning av ett ackorddiagram kan hittas genom att vända en perfekt eliminationsordning för diagrammet. Således ger applicering av girig färgning till en perfekt beställning en effektiv algoritm för optimal färgning av ackorddiagram. Jämförbarhetsdiagram är också perfekt beställbara, med en perfekt ordning som ges genom en topologisk ordning av en transitiv orientering av diagrammet. De komplementgraf av tolerans grafer är helt beställningsbar.

En annan klass av perfekt beställningsbar grafer ges av kurvorna G så att, i varje undergrupp av fem hörn från G , åtminstone en av de fem har en sluten område som är en delmängd av (eller lika med) den slutna området av en annan av de fem hörnpunkterna. På motsvarande sätt är dessa diagram där den delade ordningen på stängda kvarter, ordnad efter uppsättning inkludering, har högst fyra bredd . Den 5-vertex cyklisk graf har en stadsdel partiell ordning bredd fem, så fyra är den maximala bredden som säkerställer perfekt orderability. Som med ackorddiagrammen (och till skillnad från de perfekt beställbara graferna mer generellt) är kurvorna med bredd fyra igenkännliga på polynomtid.

Ett begrepp som är mellanliggande mellan den perfekta elimineringsordningen för ett ackorddiagram och en perfekt ordning är en semiperfekt eliminationsordning : i en eliminationsordning finns det ingen tre-vertex- inducerad väg där mittpunkten är den första av de tre som elimineras, och i en eliminationsordning för semiperfekt finns det ingen fyrkantsinducerad bana där en av de två mittpunkterna är den första som elimineras. Det motsatta av denna beställning uppfyller därför kraven för en perfekt beställning, så diagram med eliminationsbeställningar för semiperfekter är perfekt beställbara. I synnerhet kan samma lexikografiska bredd-första sökalgoritm som används för att hitta perfekta eliminationsordningar för ackorddiagram användas för att hitta semiperfekt eliminationsorder för avstånds-ärftliga grafer , som därför också är perfekt beställbara.

Diagrammen för vilka varje vertexordning är en perfekt ordning är graferna . Eftersom grafer är graferna utan fyra-vertex-inducerad väg, kan de inte bryta mot banbeställningskravet på en perfekt ordning.

Flera ytterligare klasser av perfekt beställbara diagram är kända.

Anteckningar

Referenser

  • Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999), Grafklasser: A Survey , SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X
  • Christen, Claude A .; Selkow, Stanley M. (1979), "Några perfekta färgningsegenskaper för grafer", Journal of Combinatorial Theory , serie B, 27 (1): 49–59, doi : 10.1016 / 0095-8956 (79) 90067-4 , MR  0539075
  • Chvátal, Václav (1984), "Perfekt beställbara grafer", i Berge, Claude ; Chvátal, Václav (red.), Ämnen i perfekta grafer , Annaler för diskret matematik, 21 , Amsterdam: Nordholland, s. 63–68. Som citerad av Maffray (2003) .
  • Chvátal, Václav ; Hoàng, Chính T .; Mahadev, NVR; De Werra, D. (1987), "Fyra klasser av perfekt beställbara grafer", Journal of Graph Theory , 11 (4): 481–495, doi : 10.1002 / jgt.3190110405.
  • Dragan, FF; Nicolai, F. (1995), LexBFS-beställningar av avstånds-ärftliga grafer , Schriftenreihe des Fachbereichs Mathematik der Univ. Duisburg SM-DU-303. Som nämnts av Brandstädt, Le & Spinrad (1999) .
  • Felsner, Stefan; Raghavan, Vijay; Spinrad, Jeremy (2003), "Erkänningsalgoritmer för beställningar av liten bredd och diagram med litet Dilworth-nummer" , Order , 20 (4): 351–364 (2004), doi : 10.1023 / B: ORDE.0000034609.99940.fb , MR  2079151 , S2CID  1363140.
  • Golumbic, Martin Charles ; Monma, Clyde L .; Trotter, William T. Jr. (1984), "Toleransdiagram", Diskret tillämpad matematik , 9 (2): 157–170, doi : 10.1016 / 0166-218X (84) 90016-7 , MR  0761599
  • Hoàng, Chính T .; Maffray, Frédéric; Olariu, Stephan; Preissmann, Myriam (1992), "En charmig klass av perfekt beställbara grafer" , Diskret matematik , 102 (1): 67–74, doi : 10.1016 / 0012-365X (92) 90348-J.
  • Hoàng, Chính T .; Reed, Bruce A. (1989), "Några klasser av perfekt beställbara grafer", Journal of Graph Theory , 13 (4): 445–463, doi : 10.1002 / jgt.3190130407.
  • Maffray, Frédéric (2003), "On the coloration of perfect charts", i Reed, Bruce A .; Försäljning, Cláudia L. (red.), Senaste framstegen inom algoritmer och kombinatorik , CMS-böcker i matematik, 11 , Springer-Verlag, s. 65–84, doi : 10.1007 / 0-387-22444-0_3 , ISBN 0-387-95434-1.
  • Middendorf, Matthias; Pfeiffer, Frank (1990), "Om komplexiteten att känna igen perfekt beställbara grafer", Diskret matematik , 80 (3): 327–333, doi : 10.1016 / 0012-365X (90) 90251-C.
  • Payan, Charles (1983), "Perfectness and Dilworth number", Discrete Mathematics , 44 (2): 229-230, doi : 10.1016 / 0012-365X (83) 90064-X , MR  0689816.