Approximate Graph Products

点击翻译按钮获取中文摘要

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.