论文标题
参数图模板：属性和算法
Parametric Graph Templates: Properties and Algorithms
论文作者
论文摘要
层次结构和重复在源自自然或工程的图中普遍存在。这些模式可以用一类参数结构图表示，这些图形由通过重复实例化生成结构的模板定义。我们提出了一类参数图模板，这些模板可以简洁地代表各种各样的图形。使用参数图模板，我们开发了最大流量，最小切割和树子学同构的结构 - 参数算法变体。我们的算法是最大流量和最小切割的多项式时间，当通过树子图的大小参数化时，可用于树子图的固定参数。通过推理重复子图的结构，我们避免了实例化的明确结构。此外，我们展示了如何从图形某些参数边界时从准多项式时间中的实例化图中恢复参数图模板。因此，参数图形模板和提出的算法技术为推理图的生成结构而不是其实例创造了机会。
Hierarchical structure and repetition are prevalent in graphs originating from nature or engineering. These patterns can be represented by a class of parametric-structure graphs, which are defined by templates that generate structure by way of repeated instantiation. We propose a class of parametric graph templates that can succinctly represent a wide variety of graphs. Using parametric graph templates, we develop structurally-parametric algorithm variants of maximum flow, minimum cut, and tree subgraph isomorphism. Our algorithms are polynomial time for maximum flow and minimum cut and are fixed-parameter tractable for tree subgraph isomorphism when parameterized by the size of the tree subgraph. By reasoning about the structure of the repeating subgraphs, we avoid explicit construction of the instantiation. Furthermore, we show how parametric graph templates can be recovered from an instantiated graph in quasi-polynomial time when certain parameters of the graph are bounded. Parametric graph templates and the presented algorithmic techniques thus create opportunities for reasoning about the generating structure of a graph, rather than an instance of it.
