Výpočetní složitost zobecněné dominace: Úplná dichotomie pro chordální grafy

Abstrakt

Ukazujeme, že pro chordální grafy platí pro problém rozhodnutí existence tzv. sigma,rho-dominující množinu úplná dichotomie: Tento problém je polynomiálně řešitelný, pokud každý chordální graf obsahuje nejvýše jednu sigma,rho-dominující množinu, jinak je NP-úplný. Pro dané množiny sigma a rho podáváme rekurzivní algoritmus, který určí, která z těchto dvou možností nastává.

Klíčová slova

• Computational
• complexity
• generalized
• domination
• complete
• dichotomy
• chordal
• graphs