Additive εn²-approximation for graph edit distance on VC-dimension-d graphs in n^{O(d/ε²)} time, with extensions to quadratic assignment problems and a Weisfeiler-Leman dimension bound for robust graph isomorphism.
32 Hung Le and Christian Wulff-Nilsen
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
citation-role summary
other 1
citation-polarity summary
fields
cs.DS 2verdicts
UNVERDICTED 2roles
other 1polarities
unclear 1representative citing papers
Conditional lower bound rules out O(n^{2-ε}) algorithms for isometric/convex subgraph testing on sparse graphs; subquadratic time for planar graphs and near-linear time for bounded-treewidth and certain plane graphs.
citing papers explorer
-
Robust Graph Isomorphism, Quadratic Assignment and VC Dimension
Additive εn²-approximation for graph edit distance on VC-dimension-d graphs in n^{O(d/ε²)} time, with extensions to quadratic assignment problems and a Weisfeiler-Leman dimension bound for robust graph isomorphism.
-
Testing whether a subgraph is convex or isometric
Conditional lower bound rules out O(n^{2-ε}) algorithms for isometric/convex subgraph testing on sparse graphs; subquadratic time for planar graphs and near-linear time for bounded-treewidth and certain plane graphs.