Sara Cohen Research Projects

"If we knew what we were doing, it would not be called research, would it?"

k-plex Enumeration

The problem of enumerating (i.e., generating) all maximal cliques in a graph has received extensive treatment, due to the plethora of applications in various areas such as data mining, bioinformatics, network analysis and community detection. However, requiring the enumerated subgraphs to be full cliques is too restrictive in common real-life scenarios where "almost cliques" are equally useful. Hence, the notion of a k-plex, a clique relaxation that allows every node to be "missing" k neighbors, has been introduced. But this seemingly minor relaxation casts existing algorithms for clique enumeration inapplicable, for inherent reasons. This paper presents the first provably efficient algorithms, both for enumerating the maximal k-plexes and for enumerating the maximal connected k-plexes. Our algorithms run in polynomial delay for a constant k and incremental FPT delay when k is a parameter. The importance of such algorithms is in the areas mentioned above, as well as in new applications. Extensive experimentation over both real and synthetic datasets shows the efficiency of our algorithms, and their scalability with respect to graph size, density and choice of k, as well as their clear superiority over the state-of-the-art.

 

Enumerating Minimal Weight Set Covers

The weighted set cover problem is defined over a universe U of elements, and a set S of subsets of U, each of which is associated with a weight. The goal is then to find a subset C of S that collectively covers U, while having minimal weight. The decision version of this well-known problem is NP-complete, but approximation algorithms have been presented that are guaranteed to find a θ(S)-approximation of the optimal solution, where θ(S) is the harmonic sum of the size of the largest set in S. Finding minimal weight set covers is an important problem, used, e.g., in facility location, team formation and transaction summarization. This paper studies the enumeration version of this problem. Thus, we present an algorithm that enumerates all minimal weight set covers in polynomial delay (i.e., with polynomial time between results) in θ(S)-approximate order. We also present a variant of this algorithm in order to enumerate non-redundant set covers in θ(S)-approximate order. Experimental results show that our algorithms run well in practice over both real and synthetic data.