Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph.

Venkatesan Guruswami Rajsekar Manokaran Prasad Raghavendra

Published in: FOCS (2008)

Keyphrases

np hard
approximation algorithms
np complete
graph databases
lower bound
randomly generated
uniformly distributed
neural network
search space
worst case
graph mining
database schemes
graph properties