OV Graphs Are (Probably) Hard Instances.

Josh Alman Virginia Vassilevska Williams

Published in: ITCS (2020)

Keyphrases

random instances
graph matching
randomly generated
directed graph
graph databases
random graphs
subgraph isomorphism
constraint satisfaction problems
phase transition
learning algorithm
image segmentation
evolutionary algorithm
random walk
spanning tree
random sat