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<r<s$ )?

- 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.