## Narmina Baghirova

Assistant and PhD Student

T: +41 26 300 8329

Address: Bd de Pérolles 90, 1700 Fribourg

Office: C 310

Email

### Short bio

I completed my bachelor’s degree program in Mathematics at the University of Primorska, Koper, Slovenia. Further, I obtained a master’s degree in Mathematical Sciences from the same institution. Currently, I am pursuing a PhD under supervision of Prof. Bernard Ries at the University of Fribourg.

My research interests:

• Algorithmic Graph Theory
• Computational Complexity
• Structural Graph Theory
• Combinatorial Optimization

### What my PhD thesis is about

We investigate the problem of finding k-community structures in graphs. A k-community structure is a partition of the vertex set of a graph into k “communities”, where each community is an induced subgraph such that each vertex has proportionally as many neighbours in its own community as in any other. One of the motivations behind is the following. Any social network such as Facebook or Instagram can be modeled as a graph, where vertices represent members of the social network and edges represent the relations between the members. Intuitively, whenever we are interested in finding an induced subgraph in such a model such that each vertex has more “relations” inside of the subgraph rather than outside, we are looking for a “community”.

There are only few known results about the existence of k-communities in a graph and the complexity of finding one. The notion of community structure is closely related to the notion of PDS (proportionally dense subgraph). When k=2, finding a 2-community in a graph is equivalent to partitioning the graph into 2 PDS. In addition, another related problem we currently work on is the Max PDS problem. The goal is to determine the size of a maximum (with respect to the number of vertices) PDS. Our goal is to obtain new results in this direction.

PhD advisors: Dr. David Schindl, Prof. Bernard Ries

### Publications

• Locally checkable problems parameterized by clique-width, N. Baghirova, C. Gonzalez, B. Ries, D. Schindl, Leibniz International Proceedings in Informatics 248 31:1 - 31:20 (2022), 33rd International Symposium on Algorithms and Computation (ISAAC 2022) Open Access
• Finding k-community structures in special graph classes, N. Baghirova, C. Dallard, B. Ries, D. Schindl, submitted (available on arxiv)