# Paper published: Iteratively recognizing core-periphery structure

News ·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].

- 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).
- Core-Periphery Structure in Networks, Rombach, M., Porter, M., Fowler, J., Mucha, P. SIAM Journal on Applied Mathematics. 74, 167–190 (2014).
- 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).