# Algorithm for undirected projective dependency parsing

I am looking for an algorithm that will get an optimal projective undirected dependency parse.

That is, given the sentence ‘Mary does love John’, and an edge-weight function $$f$$ (that is, a function from pairs of words in the sentence to real numbers), like

$$f$$(Mary,does) = 1

$$f$$(Mary,love) = 5

$$f$$(Mary,John) = 2

$$f$$(does,love) = 2

$$f$$(does,John) = 3

$$f$$(love,John) = 5

I want an algorithm that will give the edges of the maximum projective spanning tree as: {(Mary,love), (does,love), (love,John)} with a total weight of 12. That is, it should give this:

Crucially, the algorithm shouldn’t give {(Mary,love), (does,John), (love,John)}, even though it has a higher weight of 13, because in that case the dependencies are not projective (the arcs (Mary,love), (does,John) cross each other). That is, it should not give this:

Equivalently, I am asking: what algorithms exist for finding a Minimum/Maximum Spanning Tree on an ordered graph, such that the resulting structure is projective? A bit more formally: given a totally ordered set of nodes $$(S,<)$$, and a edge weight function $$W: S × S → ℝ$$, is there a good algorithm for finding the optimal-weight spanning tree over this set of nodes, such that the resulting structure has the property that every sub-tree is contiguous in the ordering (for any subtree $$T$$, for all $$t,s$$ in $$T$$ there is no $$r$$ not in $$T$$ such that $$t)?

• Without the projectivity requirement, any classic MST algorithm will do (such as Prim’s, or Kruskal’s).
• With the projectivity requirement, but for directed graphs/dependencies Eisner’s algorithm (a faster version of Arc-factored Projective Parsing) is standard for getting the optimal directed projective dependency parse.

I am looking for a (probably CYK-like) algorithm like Eisner’s, but which will work on undirected dependency parsing. That is, an algorithm for finding the maximum projective spanning tree for undirected ordered graphs. Or, perhaps, a proof that Eisner’s algorithm will with some modification to work on undirected graphs will be guaranteed to give the optimal projective spanning tree.