Assessing the computational complexity of multilayer subgraph detection

Robert Bredereck, Christian Komusiewicz, Stefan Kratsch, Hendrik Molter, Rolf Niedermeier and Manuel Sorge

Network Science, 2019, vol. 7, issue 2, 215-241

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.

Date: 2019
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.cambridge.org/core/product/identifier/ ... type/journal_article link to article abstract page (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cup:netsci:v:7:y:2019:i:02:p:215-241_00

Access Statistics for this article

More articles in Network Science from Cambridge University Press Cambridge University Press, UPH, Shaftesbury Road, Cambridge CB2 8BS UK.
Bibliographic data for series maintained by Kirk Stebbing ().