Suppose you are computer security expert working for a major company, CableClock

Question

Suppose you are computer security expert working for a major company, CableClock, any you have just discovered that many of the computers at CableClock are infected with malware that must have come from users visiting unsafe websites. For each infected computer, you are given a log file that lists all websites it has visited since the last time it was scanned for malware. Unfortunately, as you look over these log files, you notice that there isn’t a single website that they all visited. You conclude, therefore, that there must be a number of websites that are able to inject this malware, and the most likely candidates would be in a smallest collection that is visited by all the infected computers. Show that the decision version of the problem of determining such a collection is NP-complete.

Explanation / Answer

The given problem can be mapped to the set cover problem which is an NP-complete problem.

The set cover problem states that given a universe U = {1,2,3,......,n} of n elements and m sets S1, S2, S3,....,Sm such that the union of the sets S1 U S2 U S3 U ..... U Sm is equal to the universe U.

The problem is to pick the minimum number of sets whose union is equal to the universe U.

In the above scenario, the universe U is equal to the number of infected computers and the set represents the m number of websites. The website set contains m elements. Each element represents the computers which has visited that website.

for example:

Given the computers {c1, c2, c3, c4} and the website set W = {(c1,c2), (c1,c2,c3), (c2), (c3,c4)}, the task is to pick the minimum number of elements from the website set such that all the computers are covered.

Hence, it is an NP-Complete problem.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.