# find the smallest set of ordered components within a larger set

Let's consider a query set $Q$ and a larger superset $S$. Each element of $Q$ exists in $S$. The goal is to express $Q$ using the smallest number of (connected) "components" of $S$.

Here is a concrete example: $Q=\{\textrm{I love France and wine}\}$ $S=\{(\textrm{I live here}), (\textrm{I love you and her}), (\textrm{France is beautiful}), (\textrm{cheese and wine})\}$

A solution for $Q$ might: - "I" from "I live here" - "love" from "I love you and her" - "France" from "France is beautiful" - "and" from "I love you and her" - "wine" from "cheese and wine" This results in 5 "components", i.e. "I", "love", "France", "and", "wine"

A better solution is: - "I love" from "I love you and her" - "France" from "France is beautiful" - "and wine" from "cheese and wine" This results in 3 "components", i.e. "I love", "France", "and wine" which might be the optimal solution for this example. We want to minimize this number of "components".

Is there anyone who knows how such algorithm is called? I searched in text parsing, text mining and so on but I did not find anything appropriate.

-
If Q={A B C} and S = {ADC, B}, is the answer going to be "two components" (since ADC covers both A and C) or "three components"? If the latter, the problem can be solved using a simple "greedy" approach, if the former, it can be reduced to something called "minimum vertex cover" (which is a known NP-hard problem; although I'm not sure whether yours would be equivalent to it or not). – Peter Košinár May 22 '13 at 17:48