Abstrakt. Vi studerar multicut och de glesaste skärproblemen i riktade grafer. I multicut problem, vi är en given n-vertex graf G tillsammans med k källa-sänka par, och målet är att hitta den minsta kardinalitet delmängd av kanter vars avlägsnande separerar alla källsänka par. Det glesaste skär problemet har samma ingång, men målet är att hitta en delmängd av kanter att ta bort för att minimera förhållandet mellan antalet raderade kanter till antalet käll-sänka par som separeras genom denna radering. Den naturliga linjära programmeringsavslappningen för multicut motsvarar, genom LP-dualitet, det välstuderade maximala (fraktionella) flödet problem, medan standard LP-avslappning för glesaste snitt motsvarar maximalt samtidigt flöde. Därför är integralitetsgapet i den linjära programmeringsavslappningen för multicut/sparsest skär också det flödesavskurna gapet: det största gapet, som kan uppnås för alla grafer, mellan det maximala flödesvärdet och den lägsta kostnadslösningen för motsvarande skärproblem. Vårt första resultat är att det flödesavskurna gapet mellan maximalt multicommodityflöde och minsta multicut är (n 1/7 ) i riktade grafer. Vi visar ett liknande resultat för gapet mellan maximalt samtidigt flöde och glesaste snitt i riktade grafer. Dessa resultat förbättras på en långvarig lägre gräns (log n) för båda typerna av flödesavskurna luckor. Vi märker att dessa polynomiskt stora flödesavskurna luckor står i skarp kontrast till den oriktade inställningen där båda dessa flödesavskurna luckor är kända för att vara (log n). Vårt andra resultat är att både riktade multicut och glesaste snitt är svåra att approximera till inom en faktor på 2 (log 1— n) för alla konstanter > 0, om inte NP  på ZPP. Detta förbättrar på senaste (log n/ log log n)- hårdhet resultat för dessa problem. Vi visar också att förekomsten av PCP: s för NP med perfekt fullständighet, polynomiellt liten ljudstyrka, och konstant antal frågor skulle innebära en polynom faktor hårdhet approximation för båda dessa problem. Alla våra resultat håller för riktade acykliska grafer.
Dessutom är det känt från arbetet i Chuzhoy och Khanna REF att problemet i riktade grafer är ouppskattbart till en faktor som är bättre än (2 log 1−ε n ).
Polynomial flow-cut gaps and hardness of directed cut problems
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}