3-dimensjonal matching

I matematikk , spesielt i grafteori , er en matchende tredimensjonal (på engelsk: 3-dimensjonal matching ) en generalisering av kobling (også kalt sammenkobling i 2D ) til en ternær situasjon som teknisk sett er den for hypergrafier kalt 3-uniformer . Å finne en tredimensjonal kamp med maksimal størrelse er et kjent NP-hardt problem i beregningskompleksitetsteori .

Definisjon

La og vær tre usammenhengende endelige sett, og la være en delmengde av . Så, er sammensatt av trillinger , med og . En del er en tredimensjonal sammenkobling hvis følgende egenskap holder: for et par tripler og forskjellig fra , har vi , og . Med andre ord, hvis to tredeler er forskjellige på en komponent, må de være forskjellige på alle komponentene. $X, Y$ $Z$ $T$ ${\ displaystyle X \ times Y \ times Z}$ $T$ $(X Y Z)$ ${\ displaystyle x \ i X, y \ i Y}$ $z \ i Z$ ${\ displaystyle M \ subseteq T}$ ${\ displaystyle (x_ {1}, y_ {1}, z_ {1})}$ ${\ displaystyle (x_ {2}, y_ {2}, z_ {2})}$ $M$ ${\ displaystyle x_ {1} \ neq x_ {2}}$ ${\ displaystyle y_ {1} \ neq y_ {2}}$ ${\ displaystyle z_ {1} \ neq z_ {2}}$

Eksempel

Figuren til høyre illustrerer en tredimensjonal sammenkobling. Helheten er representert av røde prikker, blå prikker og grønne prikker. Figur (a) viser det gitte settet ; hver triplett er tegnet i et grått område. Figur (b) viser en tredimensjonal sammenkobling bestående av to elementer, og figur (c) viser en sammenkobling bestående av tre elementer. $X$ $Y$ $Z$ $T$

Sammenkoblingen av figur (c) har maksimal størrelse : det er ingen større størrelse, mens sammenkoblingen av figur (b), selv om den ikke er av maksimal størrelse, er maksimum : den kan ikke forstørres til en større sammenkobling.

Sammenligning med kobling

En kobling , eller to-dimensjonal sammenkobling , kan defineres på en helt analog måte: la og to usammenhengende endelige sett, og enten en del av . En del er en kobling hvis, for et par forskjellige par og av , vi har og . $X$ $Y$ $T$ $X \ ganger Y$ ${\ displaystyle M \ subseteq T}$ $(x_ {1}, y_ {1})$ $(x_ {2}, y_ {2})$ $M$ ${\ displaystyle x_ {1} \ neq x_ {2}}$ ${\ displaystyle y_ {1} \ neq y_ {2}}$

I tilfelle to-dimensjonal matching, kan settet tolkes som settet med kanter av en tosidig graf , hver kant av å koble et toppunkt til et toppunkt på . En todimensjonal sammenkobling er da en sammenkobling i grafen , det vil si et sett med to og to ikke tilstøtende kanter. $T$ ${\ displaystyle G = (X \ cup Y, T)}$ $T$ $X$ $Y$ $G$

På samme måte kan en tredimensjonal sammenkobling tolkes som en generalisering av koblinger til hypergrafer : settene og inneholder toppunktene, hver trippel av er en hyperkant, og settet er dannet av to til to hyper-kanter. usammenhengende, det vil si uten et felles toppunkt. $X, Y$ $Z$ $T$ $M$

Sammenligning med settpakning

En tredimensjonal sammenkobling er et spesielt tilfelle av settpakking : vi kan tolke hver triplett av som en delmengde av ; en tredimensjonal sammenkobling består deretter av to-to-to usammenhengende undergrupper. $(X Y Z)$ $T$ ${\ displaystyle \ {x, y, z \}}$ ${\ displaystyle X \ cup Y \ cup Z}$ $M$

Beslutningsproblem

I beregningskompleksitetsteorien er det tredimensjonale matchingsproblemet navnet på følgende beslutningsproblem : gitt et sett og et helt tall k ; bestemme om det er en tredimensjonal sammenkobling med minst k- elementer. $T$ ${\ displaystyle M \ subseteq T}$

Dette beslutningsproblemet er kjent for å være NP-komplett : det er et av Karps berømte 21 NP-komplette problemer . Imidlertid er det polynomalgoritmer for dette problemet i spesielle tilfeller, for eksempel for "tette" hypergrafier.

Problemet er NP-komplett selv i spesielle tilfeller . I dette tilfellet er en tredimensjonal sammenkobling ikke bare en settpakning, men også et problem med nøyaktig dekning : settet dekker hvert element fra og en gang nøyaktig. ${\ displaystyle k = | X | = | Y | = | Z |}$ $M$ $X, Y$ $Z$

Optimaliseringsproblem

Et maksimalt tredimensjonalt treff er et tredimensjonalt maksimalt match. I kompleksitetsteori er det også navnet på følgende kombinatoriske optimaliseringsproblem : gitt , finn en tredimensjonal matching av maksimal størrelse. $T$ $M$

Ettersom beslutningsproblemet er NP-komplett , er optimaliseringsproblemet NP-vanskelig , og det er derfor sannsynligvis ingen polynomalgoritme for å finne en kamp med 3 maksimale dimensjoner, mens det er effektive algoritmer i polynomtid for dimensjon 2, som Hopcroft og Karp algoritme .

Tilnærmelsesalgoritmer

Problemet er APX-komplett ; med andre ord er det vanskelig å tilnærme det med en konstant faktor. På den annen side eksisterer det en faktorpolynom-tids-tilnærmelsesalgoritme for enhver konstant . $\ varepsilon> 0$ ${\ displaystyle 3/2 + \ varepsilon}$

Det er en veldig enkel polynomalgoritme for å beregne en tredimensjonal match med en tilnærmelsesfaktor 3: det er tilstrekkelig å finne en hvilken som helst tredimensjonal match som ikke kan økes (en maksimal match). Det er ikke nødvendigvis maksimum, men akkurat som en maksimal kobling er en maksimal kobling opp til en faktor på 1/2, er en maksimal tredimensjonal matching maksimum til en faktor på 1/3.

Merknader og referanser

Karp 1972 .
Karpinski, Rucinski og Szymanska 2009
Keevash, Knox og Mycroft 2013
Garey og Johnson 1979 , avsnitt 3.1 og problem SP1 i vedlegg A.3.1.
Korte og Vygen 2006 , avsnitt 15.5.
Papadimitriou og Steiglitz 1998 , avsnitt 15.7.
Crescenzi et al. 2000 .
Ausiello et al. 2003 , SP1 Problem av Vedlegg B .
Kann 1991 .

(fr) Denne artikkelen er delvis eller helt hentet fra den engelske Wikipedia- artikkelen med tittelen " 3-dimensional matching " ( se listen over forfattere ) .

Se også

Relaterte artikler

Bibliografi

Giorgio Ausiello , Pierluigi Crescenzi , Giorgio Gambosi , Viggo Kann , Alberto Marchetti-Spaccamela og Marco Protasi , kompleksitet og tilnærming: kombinatoriske optimaliseringsproblemer og deres tilnærmelsesegenskaper , Springer ,2003.
Pierluigi Crescenzi , Viggo Kann , Magnús Halldórsson , Marek Karpinski og Gerhard Woeginger , “Maximum 3-dimensional matching” , in A Compendium of NP Optimization Problems ,2000( les online ).
(en) Michael Garey og David S. Johnson , Computers and Intractability: A Guide to theory of NP-Completeness , WH Freeman,1979( ISBN 0-7167-1045-5 ).
Viggo Kann , " Maksimal avgrenset tredimensjonal matching er MAX SNP-komplett ", Information Processing Letters , vol. 37, n o 1,1991, s. 27–35 ( DOI 10.1016 / 0020-0190 (91) 90246-E ).
(en) Richard M. Karp , "Reducibility Among Combinatorial Problems" , i Raymond E. Miller og James W. Thatcher, Complexity of Computer Computations , Plenum,1972( ISBN 978-1-4684-2003-6 , DOI 10.1007 / 978-1-4684-2001-2_9 , les online ) , s. 85-103
Marek Karpinski , Andrzej Rucinski og Edyta Szymanska , “ Kompleksiteten av perfekte matchende problemer med tette hypergrafier ”, ISAAC '09 Forhandlinger fra det 20. internasjonale symposiet om algoritmer ,2009, s. 626-636 ( DOI 10.1007 / 978-3-642-10631-6_64 ).
Peter Keevash , Fiachra Knox og Richard Mycroft , “ Polynomial-Time perfect matches in tense hypergraphs ”, STOC '13 Proceedings of the forty-five annual ACM symposium ,2013, s. 311-320 ( DOI 10.1145 / 2488608.2488647 ).
Bernhard Korte og Jens Vygen , kombinatorisk optimalisering: teori og algoritmer , Springer ,2006, 3 e ed..
Christos H. Papadimitriou og Kenneth Steiglitz , Combinatorial Optimization: Algorithms and Complexity , Dover Publications ,1998.