Leírás
Egy konjunktív normálformában (KNF) adott Boole-függvényt Horn függvénynek nevezünk, ha minden klóz pontosan egy pozitív literált tartalmaz. Egy Horn függvénynek több KNF reprezentációja is létezik; célunk egy olyan reprezentáció megkeresése, mely minél kevesebb klózból áll. Ez a probléma a matematika több területén is felmerül, mint például algebra, logika, gépi tanulás, adatbázisok elmélete, vagy éppen algoritmikus kérdések a biológiából. Boros és Gruber megmutatták, hogy már az optimális klózszám polilogaritmikus approximációja is NP-nehéz feladat. Ugyanakkor O(n)-approximáció könnyen adható a feladatra az úgynevezett Guigues-Duquenne bázisok segítségével, ahol n a formulában szereplő változók számát jelöli. Természetes kérdés, hogy a két korlát között hol az igazság, így vizsgálataink arra irányulnak, hogy lehetséges-e O(n^c)-approximáló algoritmust adni a problémára valamely 0<c<1 konstans esetén.
Egy Horn klóz, mely pontosan egy pozitív literált tartalmaz, azonosítható egy irányított hiperéllel, melynek több tőpontja és egyetlen fejpontja van. Ily módon a Horn formulákkal kapcsolatos kérdések az irányított hipergráfok nyelvén is megfogalmazhatóak. Speciálisan a Horn formulák minimális reprezentációjának problémája esetén a következő gráfelméleti kérdést kapjuk. Egy irányított hiperél egy (T,h) pár, ahol T a tőpontok halmaza, míg h a hiperél feje. Azt mondjuk, hogy (T,h) kilép egy X halmazból, ha T részhalmaza X-nek és h nincs benne X-ben. A feladat a következő: adott egy irányított hipergráf, keressünk egy minimális élszámú másik hipergráfot úgy, hogy a két gráfban megegyezik a nulla kifokú halmazok rendszere.
Az előadáson O(log n)-approximációt adunk arra a speciális esetre, amikor a kiindulási hipergráfban bármely hiperél tövéből elérhető minden más pont az úgynevezett forward chaining eljárás segítségével. Az eredmények Boros Endrével, Ondrej Cepekkel, Petr Kucerával és Kazuhisa Makinoval közösek.