Minimalni rez-cesta

Abstract

This thesis addresses the Min Cut-Path problem: finding a minimal set of edges that simultaneously contains both a u-v cut and a u-v path in a graph. The combination of these two concepts increases the complexity of the problem beyond that of standard algorithms for cuts or paths. We identify and analyze the conditions under which the Min Cut-Path problem allows efficient solutions. For graphs with diam or cut 2, that is, for all x, y with d(x,y) <= 2 or c(x,y) <= 2, we propose a polynomial-time algorithm for the case c(u, v) = 2, based on a decomposition using general square graphs. In Erdős-Rényi random graphs, we present an approximation scheme with an average-case guarantee arbitrarily close to 1. Furthermore, we propose an almost polynomial-time algorithm for sparse instances. Finally, we study the symmetric case c(u,v) = d(u,v) = cp(u,v) and provide polynomial-time algorithms for recognizing this property and finding solutions in nearly 5-regular graphs.

Tato diplomová práce se zabývá problémem minimalni rez-cesta: hledáním minimální množiny hran, která současně obsahuje u-v řez i u-v cestu v grafu. Spojení těchto dvou konceptů zvyšuje složitost problému nad rámec standardních algoritmů pro řez nebo cestu. Identifikujeme a analyzujeme podmínky, za kterých má problém minimalni rez-cesta efektivní řešení. Pro grafy s průměrem nebo řezem nanejvýš dva, tedy když pro všichni x,y d(x,y) <= 2 nebo c(x,y) <= 2, navrhujeme polynomiální algoritmus pro případ c(u,v) = 2, založený na dekompozici pomocí obecných čtvercových grafů. V Erdős-Rényi náhodných grafech prezentujeme aproximační schéma s průměrnou zárukou přesnosti libovolně blízké 1. Dále navrhujeme téměř polynomiální algoritmus pro řídké instance. Nakonec se zabýváme symetrickým případem c(u,v) = d(u,v) = cp(u,v) a poskytujeme polynomiální algoritmy pro rozpoznání této vlastnosti a pro hledání řešení v téměř 5-regulárních grafech.