Assessing the Computational Complexity of Multi-layer Subgraph Detection
Lists
Only you see this
Abstract
Multi-layer graphs consist of several graphs (layers) over the same vertex 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 multi-layer graphs, including fundamental problems such as maximum matching, finding certain clique relaxations (motivated by community detection), or path problems. Mostly encountering hardness results, sometimes even for two or three layers, we can also spot some islands of tractability.
BibTeX
@inproceedings{bredereck2017assessing,
author = {Robert Bredereck and Christian Komusiewicz and Stefan Kratsch and Hendrik Molter and Rolf Niedermeier and Manuel Sorge},
title = {{Assessing the Computational Complexity of Multi-layer Subgraph Detection}},
booktitle = {CIAC},
year = {2017},
doi = {10.1007/978-3-319-57586-5\_12},
}| Counting Subgraphs in Somewhere Dense Graphs | SIAM Journal on Computing · 2024 |
| FirmTruss Community Search in Multilayer Networks | arXiv · 2022 |
| Analysing Motifs in Multilayer Networks | arXiv · 2019 |
| Destroying Multicolored Paths and Cycles in Edge-Colored Graphs | arXiv · 2021 |
| Generalized Densest Subgraph in Multiplex Networks | arXiv · 2023 |
| On Finding Dense Common Subgraphs | arXiv · 2018 |