Suppose you work for a company that is giving a smartphone to each of its employ

Question

Suppose you work for a company that is giving a smartphone to each of its employees. Unfortunately, the companies that make apps for these smartphones are constantly suing each other over their respective intellectual property. Say that two apps, A and B, are litigation-conflicting if A contains some disputed technology that is also contained in B. Your job is to pre-install a set of apps on the company smartphones, but you have been asked by the company lawyers to avoid installing any litigationconflicting apps. To make your job a little easier, these lawyers have given you a graph, G, whose vertices consist of all the possible apps you might want to install and whose edges consist of all the pairs of litigation-conflicting apps. An independent set of such an undirected graph, G = (V, E}, is a subset, I, of V, such that no two vertices in I are adjacent. That is, if u, v E I, then (u, v) ft. E. A maximal independent set Mis an independent set such that, if we were to add any additional vertex to M, then it would not be independent any longer. In the case of the graph, G, of litigation-conflicting apps, a maximal independent set in G corresponds to a set of nonconflicting apps such that if we were to add any other app to this set, it would conflict with at least one of the apps in the set. Give an efficient algorithm that computes a maximal independent set for such a graph, G. What is the running time of your algorithm?

Explanation / Answer

In Graph, G

vertices consist of all the possible apps you might want to install.

edges consist of all the pairs of litigation-conflicting apps.

An independent set of such an undirected graph,

G = (V, E}

Maximal Independent Set: An independent set is maximal if it is not properly contained in any other independent set in .

A simple greedy strategy will achieve a constant bound. Pick any vertex. Remove it and all of its neighbors from G. Repeat until no vertices are left. The set will be an independent set, because when we choose a vertex none of its neighbors will remain in the graph to be chosen later. At each step we remove at most d + 1 vertices, so we can repeat this at least |V | d+1 times. Thus we have an algorithm with c = 1 d+1 . In the case where G consists of k complete graphs on d + 1 vertices |V | = k(d + 1) and the maximum independent set has size k, so the size of the largest independent set is exactly |V | d+1 . Therefore the constant cannot be improved, although choosing a vertex of smallest degree at each step would be a good heuristic.

This algorithm can be easily implemented to run in O(n+m)time, where n is the number of vertices and m is the number of edges.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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