Paper published: Iteratively recognizing core-periphery structure

One-sentence summary: Recognizing graph properties can be done efficiently by adding vertices one-by-one, perhaps destroying the property, and then repairing it.

The original motivation of this paper is a problem related to checking for core-periphery structure in graphs [1], for example, in social networks. The idea is that such networks consist of a densely connected core, and a periphery which is sparsely connected within itself but relatively well connected to the core.

A simple model of core-periphery structure is that of a split graph, a graph which allows a partition into a clique and an edgeless graph. In our paper [2], among others, we study the generalization of multiple (but small number of) cores, that is, graphs that allow a partition into k cliques (pairwise not connected to each other) and an independent set. Such graphs are also called monopolar graphs.

Developing algorithms, we realized that an iterative strategy is helpful for such kinds of partitioning graph properties. Herein we maintain the partition while iteratively adding vertices. A new vertex may invalidate the partition, but then often we can algorithmically find a way to repair it. We were unaware that a similar strategy has been used before for other problems [3].

1. Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs, Kanj, I.A., Komusiewicz, C., Sorge, M., Leeuwen, E.J. van. Journal of Computer and System Sciences. 92, 22–47 (2018).
2. Core-Periphery Structure in Networks, Rombach, M., Porter, M., Fowler, J., Mucha, P. SIAM Journal on Applied Mathematics. 74, 167–190 (2014).
3. Fixed-Parameter Algorithms for Cochromatic Number and Disjoint Rectangle Stabbing via Iterative Localization, Heggernes, P., Kratsch, D., Lokshtanov, D., Raman, V., Saurabh, S. Information and Computation. 231, 109–116 (2013).