  Search applications often display shortened sentences which must contain
certain query terms and must fit within the space constraints of a user
interface. This work introduces a new transition-based sentence compression
technique developed for such settings. Our query-focused method constructs
length and lexically constrained compressions in linear time, by growing a
subgraph in the dependency parse of a sentence. This theoretically efficient
approach achieves an 11X empirical speedup over baseline ILP methods, while
better reconstructing gold constrained shortenings. Such speedups help
query-focused applications, because users are measurably hindered by interface
lags. Additionally, our technique does not require an ILP solver or a GPU.
