Assessing the computational complexity of multi-layer subgraph detection

DOI10.1007/978-3-319-57586-5_12MaRDI QIDQ5283362zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1604.07724, http://edoc.hu-berlin.de/18452/22388

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)

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.

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

Cites work

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

Cited in

(2)

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

Describes a project that uses

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)