Assessing the computational complexity of multi-layer subgraph detection

DOI10.1007/978-3-319-57586-5_12zbMATH Open1486.68126arXiv1604.07724OpenAlexW2963760377MaRDI QIDQ5283362FDOQ5283362

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

Publication date: 21 July 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1604.07724

Recommendations

• Multivariate algorithmics for finding cohesive subnetworks
• scientific article; zbMATH DE number 2117153
• Algorithms by layer-decomposition for the subgraph recognition problem with attributes
• Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations
• Finding highly connected subgraphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Graph Classes: A Survey
• Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey
• The node-deletion problem for hereditary properties is NP-complete
• Algorithmic graph theory and perfect graphs
• Simultaneous feedback vertex set: a parameterized perspective
• Parameterized algorithms
• Title not available (Why is that?)
• The parameterized complexity of \(k\)-biclique
• On the parameterized complexity of multiple-interval graph problems
• The h-Index of a Graph and its Application to Dynamic Subgraph Statistics
• Graph factors and factorization: 1985--2003: a survey
• Parameterized complexity of finding subgraphs with hereditary properties.
• Dual connectedness of edge-bicolored graphs and beyond
• Competitive graph searches

Cited In (2)

• Approximating multistage matching problems
• An appraisal of the performance of the MMSC subgraph generation algorithm on a Cyber system 170/720

Uses Software

• GenLouvain

This page was built for publication: Assessing the computational complexity of multi-layer subgraph detection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5283362)