Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.