Domináns élkészlet

A gráfelméletben a G  = ( V ,  E ) gráf éldomináns halmaza (vagy éldomináns halmaza ) D  ⊆  E részhalmaza úgy, hogy bármely él, amely nincs D -ben , szomszédos legalább egy D -beli éllel . Az (a)–(d) ábrák példákat mutatnak be domináns élhalmazokra (piros élek).

A legkisebb domináns élhalmaz a legkisebb domináns élhalmaz. Az (a) és (b) ábrák a legkisebb domináns élhalmazokra mutatnak példákat (ellenőrizhető, hogy egy adott gráfban nincs-e két élből álló domináns halmaz).

Tulajdonságok

A G gráf éleinek domináns halmaza az L vonalgráf domináns halmaza ( G ), és fordítva.

Bármilyen maximális egyezés mindig éldomináns halmaz. A (b) és (d) ábra a maximális egyezésekre mutat példákat.

Ezenkívül a legkisebb domináns élhalmaz mérete megegyezik a legkisebb maximális egyezés méretével . A legkisebb maximális illeszkedés a legkisebb domináns élkészlet. A (b) ábra példát mutat a legkisebb maximális egyezésre. A legkisebb domináns élhalmaz nem feltétlenül a legkisebb maximális illeszkedés, amint azt az (a) ábra szemlélteti. A legkisebb domináns D élhalmaz ismeretében azonban könnyű megtalálni a legkisebb maximális egyezést | D | élek (lásd például Michalis Giannakakis és Fanica Gavrila cikkét [1] ).

Algoritmusok és számítási bonyolultság

Annak meghatározása, hogy egy adott gráfhoz van-e adott méretű domináns élhalmaz, NP-teljes (tehát a legkisebb domináns élhalmaz megtalálása NP-nehéz ). Michalis Giannakakis és Fanica Gavril [1] kimutatta, hogy a probléma NP-teljes még egy 3-as maximális csúcsfokozatú bipartit gráfnál is, és egy 3-as maximális csúcsfokozatú síkgráfnál is .

Létezik egy egyszerű polinomiális időközelítő algoritmus 2-es közelítési tényezővel – bármilyen maximális egyezést találunk. A maximális illeszkedés a domináns élkészlet. Sőt, a maximális illeszkedés M kétszer akkora lehet, mint a legkisebb maximális illesztés, és a legkisebb maximális illesztés mérete is megegyezik a legkisebb domináns élhalmaz méretével.

Lehetséges 2-szeres közelítéssel is közelíteni a probléma éllel súlyozott változatát, de az algoritmus sokkal bonyolultabb [2] .

Khlebikov és Hlebikova [3] kimutatta, hogy a legjobb együtthatóval (7/6) végzett keresés NP-nehéz probléma.

Jegyzetek

1. ↑ 1 2 Yanakakis, Gavril, 1980 .
2. ↑ Fujito, Nagamochi, 2002 .
3. ↑ Chlebík, Chlebíková, 2006 .

Irodalom

• Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela, Marco Protasi. Komplexitás és közelítés: Kombinatorikus optimalizálási problémák és közelíthetőségi  tulajdonságaik . — 2. - Berin, Heidelberg, New York: Springer-Verlag, 2003. - ISBN 3-540-65431-3 . .

A legkisebb domináns élkészlet (optimalizálási változat) a GT3 probléma a B függelékben (370. oldal). A legkisebb maximális egyezés (optimalizálási verzió) a GT10 probléma a B függelékben (374. oldal).

• Miroslav Chlebik, Janka Chlebikova. Az éldomináns halmazproblémák közelítő keménysége  //  Journal of Combinatorial Optimization. - 2006. - 20. évf. 11 , iss. 3 . — P. 279–290 . - doi : 10.1007/s10878-006-7908-0 . .
• Michael R. Garey, David S. Johnson. Számítógépek és kezelhetetlenség: Útmutató az NP-  teljesség elméletéhez . - W. H. Freeman, 1979. - ISBN 0-7167-1045-5 . .

Az élek uralkodó halmazát (a megoldható változatban) a domináns halmazprobléma, a GT2 feladat tárgyalja az A1.1. függelékben. A legkisebb maximális egyezés (a megoldhatósági változatban) a GT10 probléma az A1.1. függelékben.

• Mihalis Yannakakis, Fanica Gavril. Éldomináns halmazok gráfokban  //  SIAM Journal on Applied Mathematics. - 1980. - 1. évf. 38 , iss. 3 . — P. 364–372 . - doi : 10.1137/0138030 . — . .
• Toshihiro Fujito, Hiroshi Nagamochi. Egy 2-közelítési algoritmus a minimális súlyú él domináló halmazproblémához  //  Discrete Applied Mathematics. - 2002. - 20. évf. 118 , iss. 3 . — P. 199–207 . - doi : 10.1016/S0166-218X(00)00383-8 .

Linkek

• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger (2000), "Az NP optimalizálási problémák kompendiuma" :

A legkisebb domináns élkészlet , A legkisebb maximális egyezés .