Description
Absztrakt:
Legyenek k>0 és l egész számok. Egy G=(V,E) gráfot (k,l)-kritikusnak hívunk, ha |E|=k|V|-l, és i(X) \leq k|X|-l teljesül minden olyan X részhalmazára a csúcsoknak, melyre k|X|-l nemnegatív. Azt mondjuk, hogy G (k,l)-merev, ha van feszítő (k,l)-kritikus részgráfja. G (k,l)-redundáns, ha minden e élére G-e (k,l)-merev.
A következő növelési feladatot vizsgáljuk: Adott G (k,l)-merev gráfot tegyünk (k,l)-redundánssá minimális sok él hozzávételével. Ez a probléma a 2-élösszeföggővé növelési, az erősen k-fa-összefüggővé növelési, és a kétdimenziós redundáns merevvé növelési feladatok közös általánosítása. A feladatra polinomiális algoritmust és minimax tételt adunk (k,l)-kritikus bemenet esetén. Általános (k,l)-merev bemenetre megmutatjuk, hogy a feladat NP-nehéz minden olyan (k,l) pár esetén, ahol k < l; míg k \geq l-re polinomidőben megoldható.