Collective Behaviour - Winter Seminar Series 2021/22
Joint session with ZUKO Herz Fellows Mahsa Mozafarinia and Anteneh Getachew Gebrie
Mahsa Mozafarinia: Bounds for the Path Vertex Cover Problem via Graph Coloring
In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. In this context, the objects are called nodes or vertices and the relations are represented as lines (also called edges). Extremal graph theory as a branch of graph theory is studying some properties of graphs. One of the goals is to identify lower or upper bounds for a given property. In this research project, we are going to improve known lower and upper bounds for the k-path vertex cover problem by considering certain types of graph coloring. Graph coloring is a concept in extremal graph theory in which we assign (color) labels to vertices of the graph subject to some constraints, for example, that no two vertices connected with an edge share the same color. In the k-path vertex cover problem, the goal is covering all paths of length k or more in a given graph using a concise subset of vertices. The size of the smallest set with this property is called the k-path vertex cover number of the graph. The k-path vertex cover problem is a generalization of the classical vertex cover problem and naturally inherits its hardness. However, it is likely that the problem is even harder to approximate than the vertex cover special case. Star coloring and defective coloring are two types of vertex coloring that appear to be connected to the concept of path vertex cover problems. We are investigating these colorings on certain graph classes to learn more about the relationships between those two problems. Moreover, we are looking for path vertex cover number of special graphs such as Kneser graphs KG(n, r). So far we have found the exact k-path vertex cover number of KG(n, 2).
Mahsa Mozafarinia is a Zukunftskolleg Herz Fellow at the University of Konstanz and a member of the CASCB doctoral network.
Anteneh Getachew Gebrie: Decentralized accelerated algorithms for hierarchical optimization problems
The purpose of the research work is to introduce accelerated algorithms using the proximal conjugate gradient method for distributed constrained optimizations given as minimization of a function decomposed as a sum of M number of functions over the common fixed points of M number of nonlinear mappings. Exploiting the special structure of the each cost component functions of the objective function and each nonlinear mapping of the constraint problem, we present two new inertial accelerated algorithms, incremental and parallel computation type algorithms, involving combinations of proximal, conjugate gradient and Halpern iteration methods. Some numerical experiments and comparisons are given to illustrate our results.
Anteneh Getachew Gebrie is ZUKOnnect Fellow at the University of Konstanz.
Datum: 2022-02-07