Maximal kardinalitetsmatchning - Maximum cardinality matching

Maximal kardinalmatchning är ett grundläggande problem i grafteorin . Vi får ett diagram , och målet är att hitta en matchning som innehåller så många kanter som möjligt, det vill säga en maximal kardinalitetsundersättning av kanterna så att varje toppunkt intill högst en kant av delmängden. Eftersom varje kant täcker exakt två hörn motsvarar detta problem uppgiften att hitta en matchning som täcker så många hörn som möjligt. ${\ displaystyle G}$

Ett viktigt speciellt fall av det maximala kardinalitetsmatchningsproblemet är när G är en bipartitgraf , vars hörn V är uppdelade mellan vänster hörn i X och höger hörn i Y , och kanterna i E ansluter alltid en vänster topp till en höger topp. I det här fallet kan problemet effektivt lösas med enklare algoritmer än i allmänhet.

Algoritmer för tvåpartsdiagram

Det enklaste sättet att beräkna en maximal kardinalmatchning är att följa algoritmen Ford – Fulkerson . Denna algoritm löser det mer allmänna problemet med att beräkna det maximala flödet , men kan enkelt anpassas: vi förvandlar helt enkelt grafen till ett flödesnätverk genom att lägga till en källpunkt i grafen med en kant till alla vänstra hörn i X , lägga till en sänkspets ha en kant från alla högra hörn i Y , hålla alla kanter mellan X och Y och ge en kapacitet på 1 till varje kant. Ford-Fulkerson-algoritmen fortsätter sedan genom att upprepade gånger hitta en förstärkningsväg från något x ∈ X till något y ∈ Y och uppdatera matchande M genom att ta den symmetriska skillnaden för den vägen med M (förutsatt att en sådan väg existerar). Som varje väg kan hittas i tid, är den löpande tiden , och den maximala matchningen består av kanterna på E som bär strömma från X till Y . ${\ displaystyle \ O (E)}$${\ displaystyle \ O (VE)}$

En förbättring av denna algoritm ges av den mer detaljerade Hopcroft – Karp-algoritmen , som söker efter flera förstärkningsvägar samtidigt. Denna algoritm körs i tid. ${\ displaystyle O ({\ sqrt {V}} E)}$

Algoritmen för Chandran och Hochbaum för tvåpartsdiagram körs i tid som beror på storleken på den maximala matchningen , som för är . Med hjälp av booleska operationer på ord av storlek förbättras komplexiteten ytterligare till . ${\ displaystyle k}$${\ displaystyle | X | <| Y |}$${\ displaystyle O \ left (\ min \ {| X | k, E \} + {\ sqrt {k}} \ min \ {k ^ {2}, E \} \ right)}$${\ displaystyle \ lambda}$${\ displaystyle O \ left (\ min \ left \ {| X | k, {\ frac {| X || Y |} {\ lambda}}, E \ right \} + k ^ {2} + {\ frac {k ^ {2.5}} {\ lambda}} \ höger)}$

Mer effektiva algoritmer finns för speciella typer av tvåpartsdiagram:

• För glesa tvåpartsdiagram kan det maximala matchningsproblemet lösas med Madrys algoritm baserat på elektriska flöden.${\ displaystyle {\ tilde {O}} (E ^ {10/7})}$
• För plana tvåpartsdiagram kan problemet lösas i tid där n är antalet hörnpunkter genom att minska problemet till maximalt flöde med flera källor och sänkor.${\ displaystyle O (n \ log ^ {3} n)}$

Algoritmer för godtyckliga grafer

Den blomning algoritmen finner en maximal-kardinalitet matchning i allmänhet (inte nödvändigtvis bipartita) grafer. Det går i tid . En bättre prestanda för O ( √ V E ) för allmänna grafer, som matchar prestanda för Hopcroft – Karp-algoritmen på tvåpartsdiagram, kan uppnås med den mycket mer komplicerade algoritmen för Micali och Vazirani. Samma gräns uppnåddes av en algoritm av Blum ( de ) och en algoritm av Gabow och Tarjan . ${\ displaystyle O (| V | ^ {2} \ cdot | E |)}$

Ett alternativt tillvägagångssätt använder randomisering och är baserad på den snabba matrismultiplikation algoritm. Detta ger en randomiserad algoritm för allmänna diagram med komplexitet . Detta är i teorin bättre för tillräckligt täta diagram , men i praktiken är algoritmen långsammare. ${\ displaystyle O (V ^ {2.376})}$

Andra algoritmer för uppgiften granskas av Duan och Pettie (se tabell I). När det gäller approximationsalgoritmer påpekar de också att blomningsalgoritmen och algoritmerna av Micali och Vazirani kan ses som approximationsalgoritmer som körs linjärt för alla fasta felbundna.

Ansökningar och generaliseringar

• Genom att hitta en maximal kardinalitetsmatchning är det möjligt att avgöra om det finns en perfekt matchning .
• Problemet med att hitta en matchning med maximal vikt i ett viktat diagram kallas problemet för maximal viktmatchning , och dess begränsning till tvåpartsdiagram kallas tilldelningsproblemet . Om varje toppunkt kan matchas till flera toppar samtidigt är detta ett generaliserat tilldelningsproblem .
• En prioritetsmatchning är en särskild maximal kardinalitetsmatchning där prioriterade toppar matchas först.
• Problemet med att hitta en maximal kardinalitetsmatchning i en hypergraf är NP-komplett även för 3-enhetliga hyperbilder.

Referenser