I den klassiska Node-Dis joint Paths (NDP) problem, vi ges en n-vertex graf G = (V, E), och en samling M = {(s 1, t 1 ),. ., (s k, t k )} par av sina hörn, kallas källa-destination, eller efterfrågan par. Målet är att leda så många av efterfrågeparen som möjligt, där vi måste välja en väg som förbinder det, så att alla valda vägar är åtskilda i sina hörn. Den bästa aktuella algoritmen för NDP uppnår en O( ε n)-uppskattning, medan det bästa negativa resultatet fram till nyligen var en faktor (log 1/2−ε n)-hårdhet approximation, för varje konstant ε, om inte NP  och ZPTIME(n poly log n ). I ett nyligen verk, författarna har visat en förbättrad 2  på ( hårdhet approximation för NDP, om inte NP  på DTIME(n O (log n) ), även om den underliggande grafen är en del-graf av ett rutnät graf, och alla källor hörn ligger på gränsen till rutnätet. Tyvärr, detta resultat sträcker sig inte till rutnät diagram. Tillnärmningen av NDP-problemet på rutnätsdiagram har förblivit en lockande öppen fråga, med den bästa nuvarande övre gränsen av Õ(n 1/4 ), och den bästa nuvarande nedre gränsen av APX-hårdhet. I ett nyligen publicerat verk visade författarna en 2Õ ( ε log n) - approximationsalgoritm för NDP i rutnätsdiagram, om alla källa hörn ligger på gränsen till rutnätet - ett resultat som kan ses som tyder på att en sub-polynom approximation kan vara möjligt för NDP i rutnät. I detta dokument visar vi att detta sannolikt inte kommer att bli fallet, och vi är nära att lösa tillnärmningen av NDP i allmänhet, och av NDP i synnerhet i rutnät. Vårt huvudsakliga resultat är att NDP är 2 (log 1−ε n) - svårt att approximera för någon konstant ε, förutsatt att NP RTIME(n poly log n ), och att det är n  på (1/(log log n) 2 ) - svårt att approximera, förutsatt att för vissa konstant δ > 0, NP RTIME(2 n δ ). Dessa resultat innehåller även rutnätsdiagram och * En fullständig version av detta dokument finns på https://arxiv.org/abs/1711.01980 † Stöds delvis av NSF beviljar CCF-1318242 och CCF-1616584. CCF-1318242 och CCF-1616584 stöds delvis av NSF. § Stöds delvis av NSF-bidrag CCF-1318242. Tillstånd att göra digitala eller papperskopior av hela eller delar av detta arbete för personligt bruk eller klassrum beviljas utan avgift, förutsatt att kopiorna inte görs eller distribueras för vinst eller kommersiella fördelar och att kopiorna är försedda med detta meddelande och den fullständiga hänvisningen på första sidan. Upphovsrätt till delar av detta verk som ägs av andra än ACM måste hedras. Abstraktering med kredit är tillåten. För att kopiera på annat sätt, eller återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. Begär tillstånd från authoritys@acm.org. vägggrafer, och sträcker sig till de nära besläktade Edge-Dis joint Paths problem, även i vägggrafer. Vår hårdhet bevis utför en minskning från 3COL (5) problem till NDP, med hjälp av en ny graf partitionering problem som en proxy. Till skillnad från den mer standardiserade metoden att använda Karp minskningar för att bevisa hårdhet approximation, är vårt bevis en Cook-typ minskning, där, med tanke på en input instans 3COL (5), vi producerar ett stort antal fall av NDP, och tillämpa en approximation algoritm för NDP för var och en av dem. Uppbyggnaden av varje ny instans av NDP är avgörande beroende av lösningarna på de tidigare fall som konstaterades av approximationsalgoritmen. • Teori om beräkning → Nätverksflöden; Routing och nätverksdesign problem; Problem, minskningar och fullständighet;
När dessutom alla efterfrågekanter har en ändpunkt vid väggens gräns, finns det en 2 O( ε log n·log log n) approximation REF.
Almost polynomial hardness of node-disjoint paths in grids