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:
- Následující jsou ekvivalentní: (1) G je intervalový (2) G je
chordální a doplněk G je srovnatelný (3) G má klikově-cestovou
reprezentaci.
- G je permutační, právě když G i doplněk G jsou srovnatelné.
- G je funkční právě když doplněk G je srovnatelný.
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.