Problém parity matroidů - Matroid parity problem - Wikipedia

Příklad problému parity matroidu na a grafický matroid: daný graf s barevnými hranami, který má přesně dva okraje na barvu, najděte co největší les, který má opět přesně dva okraje na barvu.

v kombinatorická optimalizace, problém parity matroidu je problém najít největší nezávislou sadu spárovaných prvků v a matroid.^[1] Problém formuloval Lawler (1976) jako společné zobecnění shoda grafu a průnik matroidů.^[1][2] Je také známý jako polymatroid odpovídající, nebo matchoid problém.^[3]

Paritu matroidů lze vyřešit v polynomiální čas pro lineární matroidy. Ale je NP-tvrdé pro některé kompaktně zastoupené matroidy a vyžaduje více než polynomický počet kroků v matroid věštec Modelka.^[1][4]

Aplikace paritních algoritmů matroidů zahrnují hledání velké planární podgrafy^[5] a hledání vkládání grafů z maximální rod.^[6] Tyto algoritmy lze také použít k vyhledání spojené dominující sady a sady vrcholů zpětné vazby v grafech maximálního stupně tři.^[7]

Formulace

A matroid lze definovat z a konečná množina prvků a z pojmu, co to znamená, aby byly podmnožiny prvků nezávislé, s výhradou následujících omezení:

• Každá podmnožina nezávislé množiny by měla být nezávislá.
• Li ${ displaystyle S}$ a ${ displaystyle T}$ jsou nezávislé množiny, s ${ displaystyle | T |> | S |}$, pak existuje prvek ${ displaystyle t v T}$ takhle ${ displaystyle S cup {t }}$ je nezávislý.^[1]

Příklady matroidů zahrnují lineární matroidy (ve kterém jsou prvky vektory v a vektorový prostor, s lineární nezávislost ), grafické matroidy (ve kterém jsou prvky hranami v neorientovaný graf, nezávislé, pokud obsahují č cyklus ) a rozdělit matroidy (ve kterém prvky patří do rodiny disjunktní sady, a jsou nezávislé, pokud obsahují nejvýše jeden prvek v každé sadě). Grafické matroidy a dělící matroidy jsou speciální případy lineárních matroidů.^[1]

V problému parity matroidu se vstup skládá z matroidu spolu s párováním jeho prvků, takže každý prvek patří jednomu páru. Cílem je najít podmnožinu párů, pokud možno co největší, aby spojení párů ve zvolené podmnožině bylo nezávislé.^[1][2] Další zdánlivě obecnější variace, ve které přípustné páry tvoří graf, spíše než mít pouze jeden pár na prvek, je ekvivalentní: prvek, který se objevuje ve více než jednom páru, lze nahradit několika kopiemi prvku, jednou na pár.^[8]

Algoritmy

Problém parity matroidů pro lineární matroidy lze vyřešit pomocí a randomizovaný algoritmus včas ${ displaystyle O (nr ^ { omega -1})}$, kde ${ displaystyle n}$ je počet prvků matroidu, ${ displaystyle r}$ je jeho hodnost (velikost největší nezávislé sady) a ${ displaystyle omega}$ je exponent v časových mezích pro rychlé násobení matic.^[1]Zejména pomocí maticového algoritmu násobení Le Gall,^[9] lze to vyřešit včas ${ displaystyle O (nr ^ {1.3729})}$Bez použití rychlého násobení matic lze problém s paritou lineárního matroidu vyřešit včas ${ displaystyle O (nr ^ {2})}$.^[1]

Tyto algoritmy jsou založeny na a lineární algebra formulace problému pomocí Geelen & Iwata (2005). Předpokládejme, že vstup do problému sestává z ${ displaystyle m}$ páry ${ displaystyle r}$-dimenzionální vektory (uspořádané jako vektory sloupců v matice ${ displaystyle M}$ velikosti ${ displaystyle r krát 2 m}$). Pak je počet párů v optimálním řešení

${ displaystyle { frac {1} {2}} operatorname {rank} { begin {pmatrix} 0 & M M ^ {T} & T end {pmatrix}} - m,}$

kde ${ displaystyle T}$ je bloková diagonální matice jejichž bloky jsou ${ displaystyle 2 krát 2}$ dílčí matice formuláře

${ displaystyle { begin {pmatrix} 0 & t_ {i} - t_ {i} & 0 end {pmatrix}}}$

pro sled proměnných ${ displaystyle t_ {1}, tečky t_ {m}}$.^[10] The Schwartz – Zippelovo lemma lze použít k testování, zda má tato matice úplnou hodnost nebo ne (tj. zda má řešení velikost.) ${ displaystyle r / 2}$ nebo ne) přiřazením náhodných hodnot proměnným ${ displaystyle t_ {i}}$ a testování, zda výsledná matice má určující nula. Použitím a chamtivý algoritmus který odstraňuje páry jeden po druhém nastavením jejich neurčitostí na nulu, dokud matice zůstane v plné hodnosti (zachování inverzní matice pomocí Sherman – Morrisonův vzorec zkontrolovat pořadí po každém odstranění), lze najít řešení, kdykoli tento test ukáže, že existuje. Další metody rozšiřují tento algoritmus v případě, že optimální řešení problému parity matroidu má méně než ${ displaystyle r / 2}$ páry.^[1]

U grafických matroidů jsou známy efektivnější algoritmy s dobou chodu ${ displaystyle O (mn log ^ {6} n)}$ na grafech s ${ displaystyle m}$ vrcholy a ${ displaystyle n}$ hrany.^[11]Pro jednoduché grafy, ${ displaystyle m}$ je ${ displaystyle O (n ^ {2})}$, ale pro multigrafy, může být větší, takže je také zajímavé mít algoritmy s menší nebo žádnou závislostí na ${ displaystyle m}$ a horší závislost na ${ displaystyle n}$. V těchto případech je také možné vyřešit problém parity grafické matroid v náhodně očekávaném čase ${ displaystyle O (n ^ {4})}$nebo včas ${ displaystyle O (n ^ {3})}$ když každá dvojice hran tvoří cestu.^[1]

Přestože problém parity matroidů je NP-tvrdé pro libovolné matroidy to lze ještě efektivně aproximovat. Jednoduchý místní vyhledávací algoritmy poskytnout a schéma aproximace v polynomiálním čase pro tento problém a najděte řešení, jejichž velikost jako zlomek optimální velikosti řešení je libovolně blízká jedné. Algoritmus začíná na prázdná sada jako jeho řešení a opakovaně se pokouší zvětšit velikost řešení o jednu odstraněním maximálně konstantního počtu ${ displaystyle C}$ párů z řešení a jejich nahrazení jinou sadou ještě jednou dvojicí. Pokud již nejsou takové pohyby možné, je výsledné řešení vráceno jako aproximace optimálního řešení. K dosažení přibližného poměru ${ displaystyle 1- epsilon}$, stačí si vybrat ${ displaystyle C}$ být přibližně ${ displaystyle 5 ^ { lceil 1/2 epsilon rceil}}$.^[8]

Aplikace

Mnoho dalších optimalizačních problémů lze formulovat jako problémy s paritou lineárního matroidu a vyřešit je v polynomiálním čase pomocí této formulace.

Shoda grafů

A maximální shoda v grafu je podmnožina hran, žádné dvě nesdílejí koncový bod, který je co největší. Lze jej formulovat jako problém s paritou matroidu v matroidu oddílu, který má v grafu prvek pro každý výskyt vrcholů hran. V tomto matroidu jsou spárovány dva prvky, pokud jsou to dva výskyty pro stejnou hranu jako každý jiný. Podmnožina prvků je nezávislá, pokud má nejvýše jeden výskyt pro každý vrchol grafu. Dvojice prvků v řešení problému parity matroidu pro tento matroid jsou výskyty mezi hranami v maximální shodě a jejich koncovými body.^[2]

Průnik matroidů

Příklad úlohy průniku matroidů se skládá ze dvou matroidů na stejné sadě prvků; cílem je najít podmnožinu prvků, která je co největší a je nezávislá v obou matroidech. Chcete-li formulovat průnik matroidu jako problém parity matroidu, vytvořte nový matroid, jehož prvky jsou disjunktní sjednocení dvou kopií daných prvků, jedna pro každý vstupní matroid. V novém matroidu je podmnožina nezávislá, pokud její omezení na každou ze dvou kopií je nezávislé v každém ze dvou matroidů. Spárujte prvky nového matroidu tak, aby byl každý prvek spárován s jeho kopií. Dvojice prvků v řešení problému parity matroidu pro tento matroid jsou dvě kopie každého prvku v řešení problému průniku matroidů.^[2]

Velké planární podgrafy

V libovolném grafu lze problém nalezení největší sady trojúhelníků v daném grafu bez cyklů kromě vybraných trojúhelníků formulovat jako problém parity matroidu na grafickém matroidu, jehož prvky jsou hrany grafu, s jedním dvojice hran na trojúhelník (v případě potřeby duplikování hran, pokud patří do více než jednoho trojúhelníku). Dvojice prvků v řešení problému parity matroidu pro tento matroid jsou dva okraje v každém trojúhelníku optimální sady trojúhelníků. Stejný problém lze také popsat jako jeden z hledání největšího Berge-acyklický sub-hypergraf 3 uniformy hypergraf. Ve verzi problému s hypergrafem jsou hyperhrany trojúhelníky daného grafu.^[3]

A kaktusový graf je graf, ve kterém mají každé dva cykly nejvýše jeden společný vrchol. Ve zvláštním případě jsou grafy, ve kterých je každý cyklus trojúhelníkem, nutně kaktusové grafy. Největší trojúhelníkový kaktus v daném grafu lze najít přidáním dalších hran z a kostra, aniž by vytvářely nové cykly, aby výsledný podgraf měl stejné připojené komponenty jako původní graf. Kaktusové grafy jsou automaticky rovinné grafy, a problém najít trojúhelníkové kaktusové grafy tvoří základ pro nejznámější aproximační algoritmus k problému najít největší rovinný podgraf daného grafu, důležitý krok planarizace. Největší trojúhelníkový kaktus má vždy alespoň 4/9 počet okrajů největšího plošného podgrafu, což zlepšuje poměr přiblížení 1/3 získaný použitím libovolného kostry.^[5]

Kombinatorická tuhost

Kostra tuhých tyčí v Euklidovské letadlo, připojené na svých koncových bodech na pružných spojích, lze upevnit do jediné polohy v rovině připnutím některých jejích spojů k bodům roviny. Minimální počet spojů, které je třeba připnout k opravě konstrukce, se nazývá její číslo připnutí. Lze jej vypočítat z řešení přidruženého problému parity matroidu.^[3]

Vložení maximálního rodu

A Strom Xuong

A buněčné vkládání daného grafu na maximální plochu rod lze získat od a Strom Xuong grafu. Toto je překlenovací strom s vlastností, že v podgrafu hran, které nejsou ve stromu, je počet připojené komponenty s lichým počtem hran je co nejmenší.

Chcete-li formulovat problém s nalezením stromu Xuong jako problém parity matroidů, nejprve rozdělte každou hranu ${ displaystyle e}$ daného grafu do cesty, přičemž délka cesty se rovná počtu dalších hran, které na ni dopadly ${ displaystyle e}$. Poté spárujte okraje rozděleného grafu tak, aby každá dvojice okrajů v původním grafu byla představována jednou dvojicí hran v rozděleném grafu a každá hrana v rozděleném grafu byla spárována přesně jednou. Vyřešte problém parity matroidu se spárovanými hranami rozděleného grafu pomocí jeho grafického matroidu (lineární matroid, ve kterém je podmnožina hran nezávislá, pokud jeho odstranění neoddělí graf). Jakýkoli překlenovací strom původního grafu, který se vyhýbá hranám použitým v řešení paritní matroid, je nutně strom Xuong.^[6]

Propojená nadvláda

A propojená dominující sada v grafu je podmnožina vrcholů, jejichž indukovaný podgraf je spojeno, sousedí se všemi ostatními vrcholy. Je těžké najít nejmenší spojenou dominující množinu v libovolných grafech, ale lze ji najít v polynomiálním čase pro grafy maximálního stupně tři. kubický graf, je možné nahradit každý vrchol dráhou se dvěma okraji připojenou ke koncům jejích tří koncových bodů a formulovat problém parity matroidů na dvojicích hran generovaných tímto způsobem pomocí grafického matroidu rozšířeného grafu. Vrcholy, jejichž cesty se v řešení nepoužívají, tvoří minimální propojenou dominující množinu. V grafu maximálního stupně tři některé jednoduché další transformace snižují problém na jednu na kubickém grafu.^[7]

Sada vrcholů zpětné vazby

A sada vrcholů zpětné vazby v grafu je podmnožina vrcholů, která se dotýká všech cyklů. V kubických grafech existuje lineární rovnice vztahující se k počtu vrcholů, cyklomatické číslo, počet připojených komponent, velikost minimální připojené dominující množiny a velikost minimální sady vrcholů zpětné vazby.^[12] Z toho vyplývá, že stejný problém parity matroidů, který se používá k vyhledání propojených dominujících množin, lze také použít k vyhledání sad vrcholů zpětné vazby v grafech maximálního stupně tři.^[7]

Tvrdost

The klika problém, hledání a ${ displaystyle k}$-vrchol kompletní podgraf v daném ${ displaystyle n}$-vrcholový graf ${ displaystyle G}$, lze transformovat na instanci matroidní parity následovně. Vytvořte a dlažba matroid na ${ displaystyle 2n}$ prvky spárované tak, že na pár vrcholů je jeden pár prvků. Definujte podmnožinu ${ displaystyle S}$ nezávislost těchto prvků, pokud splňuje některou z následujících tří podmínek:

• ${ displaystyle S}$ má méně než ${ displaystyle 2k}$ elementy.
• ${ displaystyle S}$ má přesně ${ displaystyle 2k}$ prvků, ale není spojením ${ displaystyle k}$ dvojice prvků.
• ${ displaystyle S}$ je unie ${ displaystyle k}$ dvojice prvků, které tvoří kliky dovnitř ${ displaystyle G}$.

Pak existuje řešení problému parity matroidů pro tento matroid o velikosti ${ displaystyle 2k}$, právě když ${ displaystyle G}$ má velikost kliky ${ displaystyle k}$. Vzhledem k tomu, že hledání kliků dané velikosti je NP-úplné, vyplývá z toho, že určení, zda má tento typ paritního problému matice řešení velikosti ${ displaystyle 2k}$ je také NP-kompletní.^[13]

Tato transformace problému nezávisí na struktuře problému kliky žádným hlubokým způsobem a fungovala by pro jakýkoli jiný problém hledání velikosti -${ displaystyle k}$ podmnožiny větší sady, které splňují vypočítatelný test. Aplikováním na náhodně permutovaný graf, který obsahuje přesně jednu velikost kliky ${ displaystyle k}$lze ukázat, že jakýkoli deterministický nebo randomizovaný algoritmus pro paritu matroidu, který přistupuje k matroidu pouze pomocí testů nezávislosti, musí provést exponenciální počet testů.^[4]

Reference