Eftersom en riktad graf G och en lista (s1, t1),. .., (s k, t k ) av terminalpar, den Riktade Steiner Network problem ber om en minimikostnad subgraph av G som innehåller en riktad si → ti väg för varje 1 ≤ i ≤ k. Specialfallet Riktade Steiner Tree (när vi ber om vägar från en rot r till terminaler t1,. .., t k ) är känd för att vara fast-parameter dragbar parameteriserad av antalet terminaler, medan specialfallet Starkt ansluten Steiner Subgraph (när vi ber om en väg från varje ti till varje annan tj) är känd för att vara W[1]-hård parameteriserad av antalet terminaler. Vi undersöker systematiskt komplexiteten i Steiners problem för att till fullo förstå vilka andra specialfall som är FPT eller W[1]-hårda. Formellt, om H är en klass av riktade grafer, då tittar vi på specialfallet av Directed Steiner Network där listan (s1, t1),. ., (s k, t k ) förfrågningar bildar en riktad graf som är en medlem av H. Vårt huvudresultat är en fullständig karakterisering av klasserna H vilket resulterar i fast-parameter kantbara specialfall: vi visar att om varje mönster i H har den kombinatoriska egenskapen att vara "transitivt likvärdig med en avgränsad längd larv med ett begränsat antal extra kanter", då problemet är FPT, och det är W[1]-hård för varje rekursivt enumerable H inte har denna egenskap. Denna kompletta dikotomi förenar och generaliserar de kända resultaten som visar att Directed Steiner Tree är FPT [Dreyfus and Wagner, Networks 1971], q-Root Steiner Tree är FPT för konstant q [Suchý, WG 2016], Strongly Connected Steiner Subgraph är W[1]-hård [Guo et al., SIAM J. Discrete Math. 2011] och Directed Steiner Network är lösbar i polynom-tid för konstant antal terminaler [Feldman och Ruhl, SIAM J. Comput. 2006] och avslöjar dessutom en stor kontinent av traktatfall som inte var kända tidigare.
Ett nytt resultat Ref överväger generaliseringar av Riktat Steiner Tree och karakteriserar vilka av dessa problem som är FPT och som är W[1]-hårda för parameter.
The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}