Název:
Minimum 0-Extension problém na grafových metrikách
Překlad názvu:
Minimum 0-Extensions of Graph Metrics
Autoři:
Dvořák, Martin ; Bulín, Jakub (vedoucí práce) ; Majerech, Vladan (oponent) Typ dokumentu: Diplomové práce
Rok:
2021
Jazyk:
eng
Abstrakt: [eng][cze] We consider the Minimum 0-Extension Problem for a given fixed undirected graph with positive weights. We study the computational com- plexity of the threshold decision variant with respect to properties of the fixed graph, in particular modularity and orientability, as defined by Karzanov in [Eur. J. Comb., 19/1 (1998)]. We approach the problem from the viewpoint of the Finite-Valued CSP, which allows us to employ the rich theory that was developed to prove the Dichotomy Conjecture. On the negative side, we provide an explicit reduction from the Max-Cut Problem to obtain NP-hardness for non-modular graphs. For non-orientable graphs, we express a cost function that satisfies a certain condition which guarantees the existence of an implicit reduction from the Max-Cut Problem. On the positive side, we construct symmetric fractional polymorphisms in order to show that the so-called Basic LP Relaxation can solve two special cases of weighted modular orientable graphs: paths and rectangles. 1Uvažujeme Minimum 0-Extension problém pro pevně-daný neori- entovaný graf s kladnými vahami hran. Studujeme výpočetní složitost jeho rozhodovací varianty v závislosti na vlastnostech toho pevně-daného grafu, konkrétně s ohledem na to, zda je tento graf modulární a zda je orientovatelný ve smyslu, jak ho definoval Karzanov [Eur. J. Comb., 19/1 (1998)]. Na tento problém se díváme z pohledu Finite-Valued CSP, což nám umožňuje využít bohatství teorie, která byla vyvinuta pro důkaz jejich dichotomie. V rámci spodního odhadu složitosti, nejprve zkonstruujeme explicitní re- dukci z Max-Cut problému, čímž získáme NP-těžkost pro nemodulární grafy. Pro neorientovatelné grafy vyjádříme funkci, která splní určitou podmínku, jež zaručí existenci implicitní redukce z Max-Cut problému. Co se týče pozi- tivních výsledků, pomocí symetrických zlomkových polymorfismů ukážeme, že některé speciální případy pro vážené modulární orientovatelné grafy lze řešit technikou zvanou Basic LP Relaxation, konkrétně Minimum 0-Extension problém pro grafy typu cesta a pro grafy typu obdélník. 1
Klíčová slova:
splňování omezujících podmínek|nemodulární grafy|grafové metriky|výpočetní složitost; constraint satisfaction|non-modular graphs|graph metrics|computational complexity