摘要：En este trabajo demostramos que el problema que llamamos Comunalidad de grupos ́ sociales (SGC por sus siglas en ingles) es NP-completo. Este problema consulta la comunalidad entre los objetos ́ tocados por una coleccion de agentes que ejecutan acciones. Aunque se presenta naturalmente en varios contextos e.g., perfilar el comportamiento de un conjunto de usuarios de un sistema, SGC ha sido, acorde al conocimiento de los autores, ignorado. Nuestra ́ ́ demostracion consiste en una reduccion de Karp a partir del problema conocido como Longest Common ́ Subsequence (LCS). Probamos tambien que un caso especial, al que llamamos 2-SGC, donde la comunalidad ́ entre las acciones esta limitada a pares de agentes, sigue siendo NP-completo. Para probar 2-SGC, nuestra ́ reduccion parte del problema conocido como Hitting Set. Antes de concluir con el art ́culo, especulamos ı ́ ́ que la version de optimizacion de SGC es NP-duro, ́ dando indicaciones de como realizar la demostracion necesaria.
其他摘要：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.
关键词：Social Group Commonality; complexity theory; social networks; graphs;Comunalidad de grupos sociales; teoría de la complejidad; redes sociales; grafos
