2
$\begingroup$

Here is the context of the problem I am struggling with.

I have a set of strings, for example:

"my name is john",
"i like cheese",
"what is your name",
"the cheese is in the kitchen",
"john likes cheese"

Let $S$ be union of all words appearing in the previous strings. my,name,is,john,i,like,cheese,what,your,the,in,kitchen,likes

The problem seeks an optimal combination of words, that construct the maximum number of strings from the initial set, under the following conditions :

  • Words are separated by a comma.
  • The sum of the lengths of selected words is bounded by a constant number (say 25).
  • A sting can be rebuilt only if all words occurring in this string are contained in the selected combination.

For example, the combination john,cheese,like,likes,i uses 24 characters and allows to rebuild both "i like cheese" and "john likes cheese".

Here is what I have tried to implement.

First, I sort every single word by the number of strings it's contained in. In this example:

is      (3)
cheese  (3)
john    (2)
name    (2)
my      (1)
i       (1)
like    (1)
what    (1)
your    (1)
...

So I'm now using this array: [is, cheese, john, name, my, i, like, ...], let us call it initial_array

And here is the idea of the algorithm I amm using. First, I initialize another array of strings containin of all the strings g the first word from initial_array, let's call it new_array:

[is]

Then, while the total length of all the strings of new_array plus the commas does not exceed the limit of 25 chars, I append them:

[is,cheese] (9)
[is,cheese,john] (14)
[is,cheese,john,name] (19)
[is,cheese,john,name,my] (22)
[is,cheese,john,name,my,i] (24) --> best potential combination so far, can rebuild 1 string: "my name is john"
[is,cheese,john,name,my,i,like] (29) --> up to 25 chars

When I reach a length up to 25 chars, I try to replace the last element of new_array by the following of initial_array:

[is,cheese,john,name,my,i,what] (29) --> up to 25 chars
[is,cheese,john,name,my,i,your] (29) --> up to 25 chars
...

And when I reach the last word of initial_array, I remove it from new_array and replace the previous one by the next one of initial_array:

// if the last word of initial_array is "likes"
[is,cheese,john,name,my,i,likes] --> we reached the last word
[is,cheese,john,name,my,like] 
[is,cheese,john,name,my,like,what]
etc...

If this solution allows me to try all the possible combinations without repetitions, the running time increases exponentially as words are being added to the initial_array, and quickly becomes unusable. So I am looking for a better idea to improve this algorithm.

Thank you for your help.

$\endgroup$
1
$\begingroup$

I am going to prove that a special case of this problem is NP-hard and hence we can not aim for a polynomial time algorithm for the general case (unless P=NP).

Assuming each word has length exactly 1. This means each word is only one letter and each sentence is a combination of letters. We are looking now for a set of at most $k$ letter that construct as many sentences as possible. In other words, we are looking for the maximum number of sentences that can be constructed with $k$ letters and hence have union at most $k$. This problem is very similar to the NP-hard minimum $k$-union problem and can also be proven hard using the NP-Hard maximum clique problem (See this question for more information).

Note that heuristics can be used to improve the running time if you are not looking for an optimal algorithm. However, a better greedy heuristic than sorting the words from the largest frequency is looking for sentences with the shortest total lengths and high number of intersections with other strings. In this case however, it would only make sense if your algorithm breaks before trying all possible values.

$\endgroup$
  • 1
    $\begingroup$ P=NP doesn't imply ETH, which is necessary for the implication of the first sentence to be true. See cs.stackexchange.com/a/9814/1960 $\endgroup$ – Peter Taylor Nov 13 at 10:46
  • $\begingroup$ ETH is a stronger hypothese than P$\neq$NP. If P=NP (which is probably not) then ETH does not make sense, since 3-SAT would have a polynomial algorithm. However, ETH and SETH are useful to prove a lower-bound on the exponent (SETH for lower-bounds on the constant factor of the exponent). On the other hand proving NP-hardness is enough to prove that exponential running time is the best we can hope for assuming P$\neq$NP which is a precondition for ETH and SETH $\endgroup$ – narek Bojikian Nov 13 at 11:45
  • $\begingroup$ Well but if you mean I should have written non-polynomial instead exponential you are right. $\endgroup$ – narek Bojikian Nov 13 at 21:20
  • $\begingroup$ However, this is not the point of the answer. In my answer I only wanted to show that minimum k-union is a special case of the problem and hence it is at least as hard as minimum k-union. There is conjecture very related to this problem about minimum bipartite expansion which and densest k-subgraph. You can look them up for further information. $\endgroup$ – narek Bojikian Nov 14 at 0:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.