Táblázatok adatvédelme és gráf optimalizáció

Absztrakt

Ebben a cikkben az adatvédelem egy régi problémáját helyezzük új megvilágításba. Két dimenziós táblázatok publikálásakor az adatszolgáltató bizonyos érzékeny cellákat "letakar", azonban e cellák némelyikének tartalma a közölt többi cellaértékből és a sor- és oszlopösszesenekből esetenként kiszámítható. Cellahelyek egy halmazát védettnek nevezzük, ha azt letakarva egyik cella értéke sem számítható ki egyértelműen. A cellahelyeket rácspontokként kezelve először elemi eszközökkel karakterizáljuk a védett halmazokat, mint ortogonális sokszögek csúcshalmazainak unióit. A védettségre több szükséges és elégséges feltételt is adunk, feltárjuk a védett halmazok hierarchiáját és érdekes tulajdonságaikat. Ha egy halmaz nem védett, akkor ki kell egészíteni újabb, minimális számú, másodlagosan letakart elemmel. Az irodalomban ezt "secondary suppression"-nak nevezik. Gusfield (1988) és mások megoldották az optimalizációs problémát úgy, hogy a táblázat cellahely halmazait bijektíve megfeleltették páros gráfoknak és az így előállt feladatra - bővítsünk egy páros gráfot minimális számú él hozzáadásával hídélmentes páros gráffá - lineáris idejű algoritmust adtak. Mi egy új, egyszerű, lineáris idejű algoritmust adunk erre a gráf bővítési feladatra.