Biography

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. Moreover, I have done an exchange semester at Universidad del Pais Vasco in Spain and Eötvös Lorand University in Hungary.
Currently, I am pursuing a PhD under the supervision of Prof. Bernard Ries at the University of Fribourg. 

My research interests are:

• 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: Prof. Bernard Ries and Dr. David Schindl.