Back to search

IS-AUR-Samarb.progr. Norge Frankrike

Efficient Algorithms for Graph Modification Problems

Awarded: NOK 95,323

Motivated by the identification of some hidden combinatorial structures on experimental data-sets, graph modification problems cover a broad range of classical graph optimization problems, among which are edge-completion, edge-deletion, edge-edition or ve rtex-deletion problems. These problems arise in various application fields, as biology (in particular phylogeny and DNA construction), data similarity in large sets, computer vision, sparse matrix computations, and image processing. Other variants of edg e modification problems such as graph sandwich problems have also been considered. Of course a graph modification problems are not limited to edge modification problems. In the classical feedback vertex set, one looks for the smallest vertex subset to del ete in order to transform the input graph into an acyclic one. Combinations of edge and vertex modifications are highly interesting to consider as well. Not much work has been done involving more complex graph modification operations such as contraction or pivoting, two operations arising in the context of the graph minor theory. With this background, our project aims to fill in particular these gaps in the theory of graph modification problems. The two collaborating groups in this project from Bergen, Norway, and Montpellier, France, are among leading experts in the field of graph modification problems. they have been focusing on the same kind of questions from different backgrounds. They have been applying mutually different techniques and toolboxes to attack the same kind of problems. Hence joining forces, the union of this expertise is expected to be extremely fruitful and will definitely result in many new results and insight in graph modification problems. So far the two project leaders have not had the opportunity to start a long term collaboration, and with this project we will be able to start such a collaboration.

Funding scheme:

IS-AUR-Samarb.progr. Norge Frankrike