Approximate Graph Products

图形产品出现在各种不同的环境中，从计算机科学到理论生物学和计算工程。在抽象层面上，人们会遇到相同的一组数学和算法问题。对于四个标准产品，笛卡尔产品、强产品、直接产品和词典产品中的每一个，人们可能会问一系列日益复杂的问题：图产品可以被干扰到什么程度，以使产品结构仍然可识别和唯一？我们如何识别一个给定的图包含一个作为导出子图、等角子图或凸子图的可因式分解子图？如果我们只需要近似因式分解，会发生什么呢？考虑到在计算生物学和例如计算工程中对近似图因式分解的实际兴趣，到目前为止，这个主题几乎没有得到系统的关注，这可能会令人惊讶。在这里，我们建议研究近似图积的数学结构以及它们的算法方面。虽然上面提到的许多问题很可能最终被证明是NP完全的，但研究精确算法、精确近似和启发式方法仍然是有意义的。

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.