Matroids Hitting Sets and Unsupervised Dependency Grammar Induction
This addresses a graph theory problem with applications in computational linguistics, but it appears incremental as it builds on existing methods without broad SOTA impact.
The paper tackles the problem of finding the minimal edge subset in a fully connected graph that contains all spanning trees for specified sub-graphs, motivated by unsupervised grammar induction, and presents a reduction to known graph problems, complexity results, and an approximation algorithm.
This paper formulates a novel problem on graphs: find the minimal subset of edges in a fully connected graph, such that the resulting graph contains all spanning trees for a set of specifed sub-graphs. This formulation is motivated by an un-supervised grammar induction problem from computational linguistics. We present a reduction to some known problems and algorithms from graph theory, provide computational complexity results, and describe an approximation algorithm.