On the NP-Completeness of Computing the Commonality Amongst the Objects upon which a Collection of Agents has Performed an Action

Abstract

We prove the NP-completeness of a problem, we call Social Group Commonality (SGC), which queries the commonality amongst the objects ‘touched’ by a collections of agents while executing an action. Although it naturally arises in several contexts, e.g., to profile the behaviour of a collection of system users, SGC has, to the authors’ knowledge, 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, we call 2-SGC, where the commonality amongst 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. Before concluding the paper, we hypothesise that the optimality version of SGC is NP-hard, hinting on how to deal with the proof obligation.