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. 1
| Identifer | oai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:438026 |
| Date | January 2021 |
| Creators | Dvořák, Martin |
| Contributors | Bulín, Jakub, Majerech, Vladan |
| Source Sets | Czech ETDs |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/masterThesis |
| Rights | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.0025 seconds