Itemset Isomorphism: GI-Complete.
Martin Marinov, David P. Gregg · arXiv (Cornell University) · 2015
This paper addresses the problem of finding a class representative itemsets up to subitemset isomorphism. An efficient algorithm is of practical importance in the domain of optimal sorting networks. Although only super-exponential algorithms for solving the problem exist in the literature, the complexity classification of the problem has never been addressed. In this paper, we present a complexity classification of the itemset isomorphism and subitemset isomorphism problems. We prove that the problem of checking if two itemsets are isomorphic to each other is GI-Complete; the Graph Isomorphism (GI) problem is known to be in NP and LWPP, but widely believed to not be P nor NP-Complete. As an immediate consequence, we prove that finding a class representative itemsets up to subitemset isomorphism is GI-Hard --- at least as hard as the graph isomorphism problem.