Capacitated Vertex Cover admits no k^{o(k)} n^{O(1)} algorithm under ETH, n^{O(tw)} is optimal even for tree-depth, and vertex integrity admits a vi^{O(vi^2)} n^{O(1)} algorithm via N-fold IP.
An algorithmic theory of integer programming
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
fields
cs.DS 2years
2026 2roles
background 1polarities
background 1representative citing papers
Eliminating p-illusion by recoloring vertices is NP-hard even on directed grids and on bipartite DAGs, but polynomial on trees, cycles, outward grids, and lambda-outerplanar graphs.
citing papers explorer
-
Parameterized Capacitated Vertex Cover Revisited
Capacitated Vertex Cover admits no k^{o(k)} n^{O(1)} algorithm under ETH, n^{O(tw)} is optimal even for tree-depth, and vertex integrity admits a vi^{O(vi^2)} n^{O(1)} algorithm via N-fold IP.
-
Complexity of Eliminating (Majority) Illusion in Directed Networks
Eliminating p-illusion by recoloring vertices is NP-hard even on directed grids and on bipartite DAGs, but polynomial on trees, cycles, outward grids, and lambda-outerplanar graphs.