On the Node-Averaged Complexity of Locally Checkable Problems on Trees.

Alkida Balliu Sebastian Brandt Fabian Kuhn Dennis Olivetti Gustav Schmid

Published in: DISC (2023)

Keyphrases

tree structure
np complete
graph structure
computational issues
decision problems
solving problems
polynomial hierarchy
evolutionary algorithm
computational cost
tree nodes