NDMI037 Geometrické reprezentace grafů I - LS 2016

Čtvrtek 14:00 - S6

Přednášíme společně s prof. Kratochvílem.

25. 2.
Chordální grafy
Definice chordálních grafů jako grafů bez indukovaných kružnic délky delší než 3.
Definice simpliciálního vrcholu. Lemma, že v chordálním grafu každý minimální vrcholový řez indukuje kliku. Věta, že každý chordální graf obsahuje alespoň jeden simpliciální vrchol.
Definice PES (perfect elimination scheme), důsledek, že chordální grafy jsou perfektní a největší klika i optimální obarvení lze najít z PES v polynomiálním čase metodou barvení First Fit.
Následující jsou ekvivalentní (1) G je chordální (2) G má PES (3) G má klikově stromový rozklad (4) G je průnikový graf podstromů ve stromech.
M. C. Golumbic: Algorithmic Graph Theory and Perfect Graphs, Elsevier, 2004

3. 3.
Intervalové, permutační a srovnatelné grafy
Intervalové grafy, srovnatelné grafy (grafy porovnatelnosti v částečných uspořádáních), permutační grafy, funkční grafy (průnikové grafy grafů spojitých funkcí na uzavřeném intervalu): definice.
Charakterizační věty:

M. C. Golumbic: Algorithmic Graph Theory and Perfect Graphs, Elsevier, 2004

10. 3.
Algoritmus pro rozpoznávání chordálních grafů
Prohledávání grafů LexBFS, konstrukce PES v lineárním čase, ověření PES v lineárním čase.
M. C. Golumbic: Algorithmic Graph Theory and Perfect Graphs, Elsevier, 2004

17. 3. Rozpoznávání srovnatelných a intervalových grafů
Polynomiální algoritmus pro generování tranzitivních orientací a testování, zda daný graf je srovnatelný. Důsledek: testování, zda daný graf je intervalový v polynomiálním čase.
M. C. Golumbic: Algorithmic Graph Theory and Perfect Graphs, Elsevier, 2004

24. 3.
χ-omezenost PC grafů
Definice χ-omezených tříd grafů.
Definice CA ("circular-arc") grafů, a důkaz, že jsou χ-omezené.
Definice PC ("polygon-circle") grafů jako průnikových grafů mnohoúhelníků v kružnici. Důkaz, že PC grafy jsou χ-omezené.
A. V. Kostochka, J. Kratochvíl: Covering and coloring polygon-circle graphs. Discrete Mathematics 163(1-3): 299-305 (1997).

31. 3.
Další výsledky o χ-omezenosti
Průnikové grafy křivek bez násobných průsečíku a s obvodem aspoň 5 mají omezenou barevnost. Průnikové grafy úseček s obvodem 4 mají neomezenou barevnost.
A. V. Kostochka, J. Nešetřil: Coloring Relatives of Intervals on the Plane, I: Chromatic Number Versus Girth. Europ. J. Combinatorics (1998) 19, 103–110.
A. Pawlik et al.: Triangle-free intersection graphs of line segments with large chromatic number. Journal of Combinatorial Theory, Series B 105, 6-10. (arXiv)

7. 4.
PQ-stromy a rozpoznávání intervalových grafů v lineárním čase
Hledání permutací, v níž zadané množiny prvků tvoří intervaly (cyklická a lineární verze). Převedení lineární verze na cyklickou. Definice (nezakořeněných) PQ-stromů, použití PQ-stromů na řešení cyklické verze úlohy. Graf je intervalový právě když jeho maximální kliky lze uspořádat tak, že kliky obsahující daný vrchol tvoří interval. Rozpoznávání intervalových grafů pomocí PQ-stromů v lineárním čase. (Podrobnější zápis z této přednášky)
M. C. Golumbic: Algorithmic Graph Theory and Perfect Graphs, Elsevier, 2004.
W.-L. Hsu: PC-trees and circular ones arrangements. Theoretical Computer Science 296(1), 99–116.

14. 4. Přednáška odpadla

21. 4.
Klikovost, nezávislost a barevnost ve speciálních třídách grafů
Jak najít optimální obarvení, největší kliku, nezávislou množinu (a nejtěžší váženou kliku a nezávislou množinu pro grafy, jejichž vrcholy mají předepsané nezáporné váhy)? Vyřešeno v polynomiálním čase pro INT a CHOR, v nevážené verzi i pro CO (poslední část doděláme příště).

28. 4.
Ještě ke klikovosti a nezávislosti
Algoritmus pro nalezení největší nezávislé množiny ve srovnatelném grafu (dokončení z minula). IFA grafy, jejich vztah ke STRING, PC a CO-CO. Důkaz, že každý chordální graf je PC-graf, a tedy i IFA-graf. Algoritmy pro nalezení největší kliky a největší nezávislé množiny v IFA grafu s danou IFA reprezentací.
5. 5.
NP-těžkost
Důkaz, že rozpoznávání STRING je NP-těžké. Důkaz, že barevnost CA-grafů je NP-těžká.
J. Kratochvíl: String graphs. II. recognizing string graphs is NP-hard. Journal of Combinatorial Theory, Series B 52(1), 67-78, 1991.
D. Marx: A short proof of the NP-completeness of circular arc coloring, 2003.

12. 5.
STRING je v NEXP
Souvislost mezi rozpoznáváním STRING a testováním slabé a silné realizovatelnosti. Věta Schaefera a Štefankoviče o tom, že každý realizovatelný AT-graf má slabou realizaci s nejvýše exponenciálně mnoha průsečíky.
M. Schaefer, D. Štefankovič: Decidability of string graphs. Journal of Computer and System Sciences 68, 319–334, 2004.

19. 5.
STRING je v NP
Algoritmus pro testování slabé AT-realizovatelnosti (a tím i rozpoznávání STRING-grafů) v NP. Základní schéma algoritmu.
M. Schaefer, E. Sedgwick, D. Štefankovič: Recognizing string graphs in NP. Journal of Computer and System Sciences 67, 365-380, 2003.

26. 5.
STRING je v NP
Dokončení NP-algoritmu pro testování slabé AT-realizovatelnosti (a tím i rozpoznávání STRING-grafů) v NP. Užití výsledků o existenci LZ-komprimovaných řešení rovnic nad slovy (samotné výsledky o rovnicích nad slovy a o LZ-kódování byly předvedeny bez důkazu).
M. Schaefer, E. Sedgwick, D. Štefankovič: Recognizing string graphs in NP. Journal of Computer and System Sciences 67, 365-380, 2003.
L. Gasieniec, M. Karpinski, W. Plandowski, W. Rytter: Efficient algorithms for Lempel-Ziv encoding. Proceedings of SWAT’96, Lecture Notes in Computer Science 1097, 392-403, 1996.
W. Plandowski, W. Rytter: Application of Lempel-Ziv Encodings to the Solution of Word Equations. Proceedings of ICALP'98, Lecture Notes in Computer Science 1443, 731-742, 1998.