Assessing the computational complexity of multilayer subgraph detection
Assessing the computational complexity of multilayer subgraph detection
复制标题
DOI：
10.1017/nws.2019.13
复制
发表时间：
2016-04
期刊：
影响因子：
1.7
通讯作者：
Robert Bredereck;Christian Komusiewicz;Stefan Kratsch;Hendrik Molter;R. Niedermeier;Manuel Sorge
中科院分区：
文献类型：
--
作者：
Robert Bredereck;Christian Komusiewicz;Stefan Kratsch;Hendrik Molter;R. Niedermeier;Manuel Sorge
抽象多层图由几个称为层的图组成，其中所有层的顶点集是相同的，但每层都有一个单独的边集。它们的动机是真实世界的问题，其中实体(顶点)通过多种类型的关系(不同层中的边)相关联。我们画出了多层图上一类子图检测问题的计算可处理性的边界，包括最大基数匹配、寻找某些团松弛或路径问题等基本问题。大多数情况下都会遇到困难的结果，有时甚至是两层或三层，我们也可以发现一些计算可处理性的孤岛。
Abstract Multilayer graphs consist of several graphs, called layers, where the vertex set of all layers is the same but each layer has an individual edge set. They are motivated by real-world problems where entities (vertices) are associated via multiple types of relationships (edges in different layers). We chart the border of computational (in)tractability for the class of subgraph detection problems on multilayer graphs, including fundamental problems such as maximum-cardinality matching, finding certain clique relaxations, or path problems. Mostly encountering hardness results, sometimes even for two or three layers, we can also spot some islands of computational tractability.