Consideration of the decoding problem in natural language semantic dependency parsing as finding a maximum spanning DAG of a weighted directed graph carries many complexities.
the computational complexity (and approximability) of the problem has not been addressed in the literature to date.