Local Equivalence Classes of Distance-Hereditary Graphs using Split Decompositions

Titel: Lokale Equivalentieklassen van Afstand-Hereditaire Grafen met behulp van Split-decomposities

Auteurs: Nicholas Connolly, Shin Nishio en Kae Nemoto.

1. Probleemstelling

Het artikel behandelt het probleem van het tellen van de grootte van lokale equivalentieklassen (LC-orbieten) van grafen.

• Lokale Complementatie (LC): Een operatie geïntroduceerd door Bouchet waarbij het subgraaf van de buren van een gekozen vertex wordt vervangen door zijn complement (bestaande randen worden verwijderd, ontbrekende randen worden toegevoegd).
• Equivalentie: Twee grafen zijn lokaal equivalent als de ene via een reeks lokale complementaties in de andere kan worden omgezet.
• Uitdaging: Het bepalen van het aantal unieke grafen in een LC-orbit is een uitdagend wiskundig probleem. In het algemeen is het tellen van de orbitgrootte #P-compleet. Bestaande formules zijn beperkt tot specifieke gevallen (zoals paden en cycli) of vereisen brute-force methoden die alleen werken voor zeer kleine grafen (tot 9 vertices).
• Doel: Het afleiden van expliciete formules voor de grootte van LC-orbieten voor brede families van afstand-hereditaire grafen (distance-hereditary graphs), een klasse van grafen die belangrijk is in de kwantum-informatietheorie (graftoestanden).

2. Methodologie

De auteurs introduceren een nieuwe aanpak gebaseerd op split-decompositie (ontwikkelde door Cunningham) en een nieuw hulpmiddel: de Quotient-Augmented Strong Split Tree (QASST).

• Split-decompositie: Een recursieve methode om een graaf te ontleden in eenvoudigere componenten (quotient-grafen) door het identificeren van "splits" (partities van de vertices waarbij de randen tussen de twee delen een volledige bipartiete graaf vormen).
• QASST: Een boomstructuur waarbij de interne knopen gelabeld zijn met de quotient-grafen (die in het geval van afstand-hereditaire grafen altijd volledige grafen $K_n$ of ster-grafen $S_n$ zijn) en de randen corresponderen met sterke splits.
• Invariantheid: Een cruciale bevinding is dat lokaal equivalente grafen dezelfde sterke splits hebben (dus dezelfde sterke split-boom), hoewel hun quotient-grafen kunnen veranderen.
• Propagatie van LC: De auteurs tonen aan hoe een lokale complementatie op een vertex in de oorspronkelijke graaf zich voortplant door de QASST, wat resulteert in lokale complementaties op de aangesloten quotient-grafen.
• Tellen via Symmetrie: In plaats van elke graaf in de orbit te enumereren, tellen de auteurs de mogelijke combinaties van symmetrie-klassen van de quotient-grafen (compleet, ster-centrum, ster-spaak) binnen de QASST. Ze berekenen een bovengrens (op basis van het product van orbitgroottes van de quotient-grafen) en een ondergrens (door expliciete transformaties te construeren). Voor de onderzochte families blijken deze grenzen samen te vallen.

3. Belangrijkste Bijdragen

1. Formulering van QASST: De definitie en toepassing van de QASST als primair hulpmiddel om de structuur van lokaal equivalente grafen te analyseren.
2. Expliciete Formules: Het afleiden van gesloten formules voor de grootte van LC-orbieten voor drie belangrijke families van afstand-hereditaire grafen:
   • Volledige bipartiete grafen ($K_{n,m}$).
   • Volledige $k$-partiete grafen ($K_{n_1, \dots, n_k}$).
   • Clique-stars en Multi-leaf repeater grafen.
3. Karakterisering van Minimale Representanten: Het identificeren van grafen binnen een orbit die het minimum aantal randen of de minimale maximale vertexgraad hebben, wat relevant is voor optimalisatieproblemen in de fysica.
4. Isomorfisme-analyse: Het onderscheid maken tussen het aantal gelabelde grafen in een orbit en het aantal niet-isomorfe (ongelabelde) grafen.

4. Resultaten

A. Volledige Bipartiete Grafen ($K_{n,m}$)

Voor $n, m \geq 2$ is de grootte van de LC-orbit:
$$|O(K_{n,m})| = nm + n + m + 3$$
De auteurs tonen aan dat deze orbit bestaat uit verschillende symmetrie-klassen van quotient-grafen (combinaties van ster-centrum en ster-spaak). Ze identificeren ook dat de grafen met het minste aantal randen "binary stars" zijn.

B. Volledige $k$-partiete Grafen en Clique-Stars

Voor de familie van volledige $k$-partiete grafen en clique-stars (die QASST-equivalent zijn maar niet noodzakelijk lokaal equivalent) worden de orbitgroottes gescheiden:

• Volledige $k$-partiet ($K_{n_1, \dots, n_k}$): De grootte wordt bepaald door producten met een even aantal termen van $(n_i + 1)$.
• Clique-Star ($CS^r_{n_1, \dots, n_k}$): De grootte wordt bepaald door producten met een oneven aantal termen van $(n_i + 1)$.
  De som van deze twee orbitgroottes is precies gelijk aan de grootte van de QASST-equivalentieklasse, wat aantoont dat deze twee families samen de volledige ruimte van lokaal equivalente grafen voor deze structuur vullen.

C. Multi-leaf Repeater Grafen

De auteurs tonen aan dat multi-leaf repeater grafen ($MR_{n_1, \dots, n_k}$) afhankelijk zijn van de pariteit van $k$:

• Als $k$ even is, is de repeater graaf lokaal equivalent aan een volledige $k$-partiete graaf.
• Als $k$ oneven is, is de repeater graaf lokaal equivalent aan een clique-star.

D. Optimalisatie (Randen en Graad)

Er worden formules afgeleid om de grafen te vinden binnen een orbit die het minste aantal randen hebben (minimale edge representative) of de laagste maximale vertexgraad. Dit is cruciaal voor het minimaliseren van experimentele resources in kwantumcomputing.

5. Betekenis en Toepassing

• Kwantuminformatietheorie: Grafische toestanden (graph states) vormen een centrale resource voor meetingsgebaseerde kwantumcomputing. Single-qubit Clifford-operaties corresponderen met lokale complementaties. Het kunnen tellen van de orbitgrootte en het vinden van optimale representanten (minimale randen/graad) helpt bij het minimaliseren van de resources die nodig zijn om een bepaalde kwantumtoestand te prepareren.
• Netwerkrobustheid: Afstand-hereditaire grafen zijn relevant voor communicatienetwerken omdat ze robuust zijn tegen het verlies van vertices.
• Wiskundige Vooruitgang: Het artikel biedt een systematische methode om een #P-compleet probleem op te lossen voor een grote en belangrijke klasse van grafen, waarbij brute-force methoden worden vervangen door elegante combinatorische tellingen via split-decompositie.

Conclusie:
Dit werk levert een aanzienlijke stap voorwaarts in het begrijpen van lokale equivalentie in grafen. Door de link tussen split-decompositie en lokale complementatie te benutten, kunnen de auteurs exacte formules afleiden voor complexe families van grafen, wat direct toepasbaar is in de optimalisatie van kwantumnetwerken en -algoritmen.