Approximate Graph Products

• Applicant: Professor Dr. Peter Florian Stadler
• Subject Area: Security and Dependability, Operating-, Communication- and Distributed Systems
• Term: from 2006 to 2012
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 25023853

Graph products arise in a variety of different contexts, from computer science to theoretical biology and computational engineering. At the abstract level, one arrives at the same set of mathematical and algorithmic questions. For each of the four standard products, the Cartesian product, the strong product, the direct product, and the lexicographic product, one may ask a series of questions of increasing complexity: How much can graph products be perturbed such that the product structure is still recognizable and unique? How can we recognize that a given graph contains a factorizable subgraph as an induced subgraph, isometric subgraph, or convex subgraph? What happens if we only require approximate factorizability? Given the practical interest in approximate graph factorizations in computational biology, and for example in computational engineering, it may come as a surprise that this topic has received little systematic attention so far. Here we propose to investigate both the mathematical structure of approximate graph products as well as their algorithmic aspects. While it is likely that many of the problems mentioned above will turn out to be NP-complete it is nevertheless of interest to investigate exact algorithms, exact approximations, and heuristic approaches.

• DFG Programme: Research Grants
• International Connection: Austria
• Participating Person: Professor Dr. Wilfried Imrich