k -minimumspännande träd
k - minimum spännträd , studerat i teoretisk datavetenskap , frågar efter ett träd med lägsta kostnad som har exakt k hörn och bildar en subgraf till en större graf. Det kallas också k -MST eller kantviktat k- kardinalitetsträd . Att hitta detta träd är NP-hårt , men det kan approximeras till inom ett konstant approximationsförhållande i polynomtid .
Problemformulering
Ingången till problemet består av en oriktad graf med vikter på dess kanter och ett nummer k . Utdata är ett träd med k hörn och k − 1 kanter, där alla kanter på utdataträdet tillhör ingångsgrafen. Kostnaden för produktionen är summan av vikterna av dess kanter, och målet är att hitta det träd som har lägsta kostnad. Problemet formulerades av Lozovanu & Zelikovsky (1993) och av Ravi et al. (1996) .
Ravi et al. betraktas också som en geometrisk version av problemet, vilket kan ses som ett specialfall av grafproblemet. I det geometriska k -minimum spaning tree-problemet är ingången en uppsättning punkter i planet. Återigen bör utdata vara ett träd med k av punkterna som sina hörn, vilket minimerar den totala euklidiska längden på dess kanter. Det vill säga, det är en graf k -minimumspännande träd på en komplett graf med euklidiska avstånd som vikter.
Beräkningskomplexitet
När k är en fast konstant kan k -minimumspännande trädproblemet lösas i polynomtid med en brute-force sökalgoritm som försöker alla k -tuplar av hörn. Emellertid, för variabel k , har k - minimumspännande trädproblem visat sig vara NP-hårt genom en reduktion från Steinerträdproblemet .
Reduktionen tar som indata en instans av Steiner-trädproblemet: en viktad graf, med en delmängd av dess hörn valda som terminaler. Målet med Steinerträdet problemet är att ansluta dessa terminaler med ett träd vars vikt är så liten som möjligt. För att omvandla detta problem till en instans av k -minimum spaning tree problemet, Ravi et al. (1996) fäster vid varje terminal ett träd med nollviktskanter med ett stort antal t hörn per träd. (För en graf med n hörn och r terminaler använder de t = n − r − 1 adderade hörn per träd.) Sedan frågar de efter k -minimumspännande träd i denna utökade graf med k = rt . Det enda sättet att inkludera så många hörn i ett k -spännande träd är att använda minst en vertex från varje tillagt träd, för det finns inte tillräckligt med hörn kvar om ens ett av de tillagda träden missas. För detta val av k är det emellertid möjligt för k -spännande träd att endast inkludera så få kanter av den ursprungliga grafen som behövs för att ansluta alla terminaler. Därför k -minimumspännande träd bildas genom att kombinera det optimala Steinerträdet med tillräckligt många av de nollviktiga kanterna på de tillagda träden för att göra den totala trädstorleken tillräckligt stor.
Även för en graf vars kantvikter tillhör uppsättningen {1, 2, 3 } är testning av om det optimala lösningsvärdet är mindre än ett givet tröskelvärde NP-komplett . Det förblir NP-komplett för plana grafer . Den geometriska versionen av problemet är också NP-hård, men inte känd för att tillhöra NP, på grund av svårigheten att jämföra summor av kvadratrötter; istället ligger den i den klass av problem som kan reduceras till den existentiella teorin om verkligheten .
K - minimumspännande träd kan hittas i polynomtid för grafer med begränsad trädbredd och för grafer med endast två distinkta kantvikter.
Approximationsalgoritmer
På grund av den höga beräkningskomplexiteten för att hitta en optimal lösning på k -minimumspännande träd, har mycket av forskningen kring problemet istället koncentrerats på approximationsalgoritmer för problemet. Målet med sådana algoritmer är att hitta en ungefärlig lösning i polynomtid med ett litet approximationsförhållande . Approximationsförhållandet definieras som förhållandet mellan den beräknade lösningslängden och den optimala längden för ett värsta fall, en som maximerar detta förhållande. Eftersom NP-hårdhetsreduktionen för k -minimum spaning tree-problemet bevarar vikten av alla lösningar, bevarar den också hårdheten för approximation av problemet. I synnerhet eftersom Steiner-trädproblemet är NP-svårt att approximera till ett approximationsförhållande bättre än 96/95, gäller detsamma för k -minimumspännande trädproblem.
Den bästa approximationen som är känd för det allmänna problemet uppnår ett approximationsförhållande på 2, och är av Garg (2005) . Denna approximation förlitar sig starkt på primal-dual-schemat av Goemans & Williamson (1992) . När inmatningen består av punkter i det euklidiska planet (varav två som helst kan anslutas i trädet med kostnad lika med deras avstånd) finns det ett polynomtidsapproximationsschema utarbetat av Arora (1998) .
externa länkar
- Minsta k-spännande träd i "Ett kompendium av NP-optimeringsproblem"
- KCTLIB , KCTLIB -- Ett bibliotek för det kantvägda K-kardinalitetsträdet