Almost polynomial hardness of node-disjoint paths in grids.

Julia Chuzhoy David H. K. Kim Rachit Nimavat

Published in: STOC (2018)

Keyphrases

disjoint paths
approximation algorithms
directed graph
undirected graph
np hard
worst case
computational complexity
np hardness
phase transition
grid computing
low order
fixed parameter tractable
data sets
neural network
minimum cost