期刊名称：IAENG International Journal of Computer Science
印刷版ISSN：1819-656X
电子版ISSN：1819-9224
出版年度：2021
卷号：48
期号：2
语种：English
出版社：IAENG - International Association of Engineers
摘要：In this paper we define and solve the following new problem: Given a set of n elements, we are interested in determining the largest number of subsets of size k that have at most m elements in common. We prove that in the worst-case scenario, a brute force solution requires a double exponential time with respect to n. Afterwards, we show that our problem is in the class NEXP by reducing it to the succinct K-coloring problem. We use in our proof ordered binary decision diagrams to determine whether there is an edge between two nodes of a graph that corresponds to an instance of our problem. We also show that it is at least EXP-hard.
