The complexity of finding the maximum spanning DAG and other restrictions for DAG parsing of natural language

Proceedings of the Fourth Joint Conference on Lexical and Computational Semantics (*SEM 2015), pages 259–268, Denver, Colorado, June 4–5, 2015. The complexity of finding the maximum spanning DAG and other restrictions for DAG parsing of natural language Natalie Schluter Center for Language Technology University of Copenhagen Copenhagen, Denmark natalie.elaine.schluter@jur.ku.dk Abstract Recently, there has been renewed interest in semantic dependency parsing, among which one of the paradigms focuses on parsing di- rected acyclic graphs (DAGs). Considera- tion of the decoding problem in natural lan- guage semantic dependency parsing as find- ing a maximum spanning DAG of a weighted directed graph carries many complexities. In particular, the computational complexity (and approximability) of the problem has not been addressed in the literature to date. This pa- per helps to fill this gap, showing that this general problem is APX-hard, and is NP-hard even under the planar restriction, in the graph- theoretic sense. On the other hand, we show that under the restriction of projectivity, the problem has a straightforward O(n3) algo- rithm. We also give some empirical evidence of the algorithmic importance of these graph restrictions, on data from the SemEval 2014 task 8 on Broad Coverage Semantic Depen- dency Parsing. 1 Introduction 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 that have not been addressed in the literature to date. Amongst these are the problem’s computational complexity (and its approximability). The decoding problem for seman- tic dependency parsing was first introduced as the maximum spanning directed acyclic graph problem (MSDAG) by McDonald and Pereira (2006), where it is stated to be NP-hard.1 The MSDAG problem asks for the highest weighted spanning sub-DAG of an input weighted digraph. In this paper, we explain the APX-hardness of MSDAG, by relating it to the almost identical min- imum weighted feedback arc set and maximum weighted acyclic subgraph problems. The proof of MSDAG’s APX-hardness seems to discourage its use for decoding in semantic dependency pars- ing. However, unlike in syntactic dependency (tree) parse decoding, where projective decoding given by Eisner (1996)’s algorithm has a slightly higher computational complexity (O(n3)) than the non- projective (Tarjan) maximum spanning tree algo- rithm (O(n2)) (Tarjan, 1977; Chu and Liu, 1965; Edmonds, 1967; McDonald et al., 2005), finding the maximum spanning projective dependency DAG is tractable and can be found in time O(n3), contrary to its APX-hard non-projective counterpart. Projective MSDAG has been referred to in the semantic dependency parsing literature as “planar MSDAG”, which is an unfortunate mismatch with long-established graph theoretical terminology, that we need in this paper. As we discuss below, the planar MSDAG problem is in fact NP-hard, where “planar” is used in the graph theoretical sense. We generalise the definition of projectivity from tree models of syntax theory, which forbids crossing edges, to digraphs. The projectivity restriction itself has not been lin- guistically motivated to date. However, an efficient 1McDonald and Pereira (2006) provide a reference to (Heckerman et …

Content truncated to 500 words