On the NP-Completeness of Computing the Commonality Among the Objects Upon Which a Collection of Agents Has Performed an Action
Roberto Alonso, Raúl Monroy · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) · 2013
Abstract. We prove the NP-completeness of the so-called Social Group Commonality (SGC) problem which queries the commonality among the objects ‘touched ’ by collections of agents while executing an action. Although it naturally arises in several contexts, e.g., in profiling the behavior of a collection of system users, SGC (to the authors ’ knowledge) has been ignored. Our proof of SGC NP-completeness consists of a Karp reduction from the well-known Longest Common Subsequence (LCS) problem to SGC. We also prove that a special case of SGC which we call 2-SGC, where the commonality among actions is limited to agent pairs, remains NP-complete. For proving NP-completeness of 2-SGC though, our reduction departs from the well-known Hitting Set problem. Finally, we hypothesize that the optimality version of SGC is NP-hard, hinting on how to deal with the proof obligation.