Integer programming models for detecting graph bipartitions with structural requirements

The graph bipartitioning problem consists of dividing a graph into two disjoint subgraphs, such that each node is highly similar to others in the same subgraph, but also different from members of the other subgraph, according to some homogeneity criterion. This problem has received significant attention over the last few years because of its applicability in areas as diverse as data classification, image segmentation, and social network analysis. In this article we study a variation of the graph bipartitioning problem in which, in addition to considering homogeneity criteria for generating the partition, we also ensure that one of the subgraphs satisfies a set of predefined structural properties—that is, such a subgraph is required to induce a given motif. We focus our attention on imposing structural constraints that force one of the subgraphs to induce stars, cliques, and clique relaxations (quasi-cliques) and discuss some specific applications for such particular cases. We tackle this problem by modeling it as a general fractional programming optimization problem and study several solution approaches. Moreover, we discuss additional algorithmic enhancements to tackle some of the aforementioned cases, and provide two greedy algorithms for the specific cases of induced cliques and stars, showing the approximation ratio for induced stars. Finally, we test the quality of our approach by solving a collection of several real-life and randomly generated instances with various configurations, analyzing the benefits of the proposed models, as well as possible further extensions.