Shellability is NP-complete.

Xavier Goaoc Pavel Paták Zuzana Patáková Martin Tancer Uli Wagner

Published in: CoRR (2017)

Keyphrases

np complete
np hard
satisfiability problem
randomly generated
computational complexity
constraint satisfaction problems
conjunctive queries
np complete problems
data complexity
pspace complete
polynomial time complexity
data sets
metadata
branch and bound
polynomially solvable