Ha adott egy nxm-es A Boole mátrix, azt mondjuk, hogy a G irányított gráf realizálja A-t, ha G-nek m forrása és n nyelője van, melyek megfelelnek A oszlopainak és sorainak, oly módon, hogy az i. nyelő a j-edik forrásból pontosan akkor elérhető G-ben, ha Aij=1. A célunk az A mátrixot minél kisebb élszámú G gráffal realizálni, ezt a minimális értéket OR(A)-val jelöljük. Természetesen elég körmentes gráfok közt vizsgálódni; ha a realizáló gráfokban az utak hosszára teszünk egy d felső korlátot, az úgy elérhető minimális élszámot OR_d(A)-val jelöljük. Ily módon pl. OR2(A) megfelel a mátrix minél kisebb összköltségű téglalapokkal való fedésének, ahol egy téglalap egy csupa 1-es részmátrixa A-nak, egy axb méretű téglalap költsége pedig a+b. Stasys Jukna és Igor Szergejev 2013-as "Complexity of Linear Boolean Operators" surveyében ezzel kapcsolatban számos nyitott problémát vet fel, ezek közül kettő:
- 7.3. A Dk Kneser-Sierpinski mátrix az a 2kx2k-s mátrix, melynek sorai és oszlopai a k-elemű halmaz részhalmazaival cimkézettek, és AH,K pontosan akkor 1, ha H és K diszjunktak. Kérdés OR2(Dk).
Ismert alsó korlát n^{log5 / 2}, felső n^{1+\sqrt{2}}, itt n=2k. Dimitrij Chistikovval, Jeffrey Shallittel és Anna Lubiwwal megjavítottuk a felső korlátot n9/4-re. Összehasonlításként ezek a kitevők rendre kb. 1.16096, 1.27 és 1.16993. Sejtjük, hogy a valóság a log5 / 2.
- 7.5. Ha a fenti lefedési problémában a mátrixok költségét uniforman 1-re vesszük, az úgy kapott bonyolultsági mértéket jelölje rank(A) . Ismert, hogy ha az A mátrixban nincs (k+1)x(k+1)-es téglalap (A "k+1"-mentes), akkor OR(A) >= ||A||/k2, ahol ||A|| az egyesek száma A-ban, és ha C az A és B mátrixok tenzor szorzata, akkor OR(C) >= rank(A)*||B||/k2, ha B (k+1)-mentes. Ez felveti a kérdést, hogy vajon az erősebb OR(C) = rank(A) * OR(B) állítás igaz lehet-e?
Ezzel kapcsolatosan pedig azt mutattuk meg, hogy OR(C) >= rank(A) * OR(B) / logn, ha A egy nxn-es mátrix. Mindkét esetben egy vonatkozó módosított halmazlefedési feladat LP relaxáltját elemeztük, az első esetben mohó approximációval, a második esetben az erős dualitási tétellel.
Minden érdeklődőt szeretettel várunk,
Péter