Egy G irányított gráf k-változós mûveletei alatt a G^k \rightarrow G gráfhomomorfizmusokat értjük, azaz azokat a leképezéseket, amelyekre ha (g_i,h_i) él G-ben i=1,2,...,k-ra, akkor (f(g_1, ..., g_k), f(h_1,...,h_k)) is él G-ben.
A címben szereplõ többségi mûvelet olyan f: G^k \rightarrow G homomorfizmust takar, amelyre
A többségi mûvelettel rendelkezõ gráfok fontos szerepet játszanak bonyolultságelméleti szempontból. Ismert, hogy a többségi mûvelettel rendelkezõ struktúrákhoz tartozó CSP-probléma például polinomiális idõben eldönthetõ. Azonban nem ismerünk polinom idejû algoritmust annak eldöntésére, hogy tetszõleges relációs struktúra rendelkezik-e többségi mûvelettel. Az elõadásban megadunk egy polinomiális idejû algoritmust, amely a fenti kérdést reflexív gráfok esetén eldönti.
Minden érdeklõdõt szeretettel várunk,
Péter