CSP dichotomie platí pro digrafy bez začátků a konců ( pozitivní odpověď na hypotézu Bang-Jensena a Hella)
2009
Abstrakt
Bang-Jensen a Hell vyslovili v roce 1990 hypotézu (užitím jazyka grafových homomorfismů) o dichotomii problému splnitelnosti omezení (CSP) pro digrafy bez zdrojů a stoků. Hypotéza říká, že CSP pro takový digraf je polynomiálně řešitelné, pokud každá komponenta jeho dřeně je cyklus, a je NP-úplné jinak.
V tomto článku tuto hypotézu dokážeme, a jako důsledek získáme důkaz hypotézy Bang-Jensena, Hella a MacGillivraye z roku 1995 klasifikující dědičně těžké digrafy. Dále ukážeme, že CSP dichotomie pro digrafy bez zdrojů a stoků souhlasí s algebraickou dichotomickou hypotézou Bulatova, Jeavonse a Krokhina z roku 2005.