Assessing the Computational Complexity of Multi-Layer Subgraph Detection

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

Abstract

Modern network analysis frequently involves multi-layer graphs where entities are connected by diverse relationship types across different layers. This paper investigates the computational complexity of the Multi-Layer Subgraph Detection problem: identifying a subset of vertices that induces a subgraph satisfying a specific property $\Pi$ in at least $\ell$ out of $t$ layers. We map the complexity landscape, demonstrating how properties that are tractable in single-layer graphs often become NP-hard or W[1]-hard in multi-layer settings. We identify a trichotomy for hereditary properties and highlight specific "islands of tractability" for non-hereditary properties like matching and connectivity.

Introduction

In data science, networks are rarely isolated. Multi-layer graphs (or multiplex networks) represent systems where a fixed set of vertices $V$ is connected by different edge sets across multiple layers. For instance, a biological network might have layers for protein-protein interactions, metabolic pathways, and gene regulation. A fundamental task in this context is finding a common structure—a subset of vertices—that exhibits a desired property across a significant number of these layers.

The core problem addressed is $\Pi$-ML-SUBGRAPH: Given a multi-layer graph $G = (V, E_1, \dots, E_t)$, an integer $k$, and a threshold $\ell$, does there exist a subset $S \subseteq V$ of size $k$ such that the subgraph induced by $S$ in at least $\ell$ layers satisfies property $\Pi$?

Methodological Framework

The authors utilize Parameterized Computational Complexity to provide a nuanced view of the problem's difficulty. Instead of a binary "P vs NP" classification, they analyze how the running time scales with respect to various parameters:

  • $k$: The number of vertices to be selected.
  • $t$: The total number of layers in the network.
  • $\ell$: The required number of layers satisfying property $\Pi$.

By applying techniques from Ramsey Theory, the authors classify hereditary properties—those preserved under vertex deletion (e.g., being a forest, planar, or bipartite). For non-hereditary properties like connectivity or the existence of $c$-cores, they introduce the concept of "staggered" properties and use gadget reductions to establish hardness.

Key Theoretical Insights

The Hereditary Trichotomy

For any hereditary property $\Pi$, the authors prove a clean three-way split in complexity:

  1. Polynomial-time solvable: If $\Pi$ contains only finitely many graphs.
  2. Fixed-Parameter Tractable (FPT): If $\Pi$ includes all complete and all edgeless graphs, the problem is FPT with respect to $(k, \ell)$.
  3. W[1]-hard: If $\Pi$ includes either all complete or all edgeless graphs (but not both), the problem is W[1]-hard with respect to $k$ for all $\ell$.

Staggered Properties and Hardness

The authors define a "staggered" property as one where the presence of the property can be controlled by adding specific "staggered" components. They demonstrate that if a property is staggered, finding a multi-layer subgraph with that property is generally W[1]-hard with respect to $(k, \ell)$. This provides a powerful diagnostic tool for identifying computationally difficult multi-layer problems.

The Complexity Jump in Matching

A particularly striking result concerns the Matching property. Finding a vertex set that admits a perfect matching in two layers ($\ell=2$) is solvable in polynomial time by reducing it to a Maximum Weight Matching problem in an auxiliary graph. However, as soon as the requirement increases to three layers ($\ell=3$), the problem jumps to W[1]-hardness.

Summary of Results

The following table summarizes the complexity classifications for various graph properties under the multi-layer subgraph detection framework, highlighting the transition from tractability to hardness as parameters change.

Summary of complexity results for various graph properties in the multi-layer subgraph detection problem.

Discussion and Future Work

While this work provides a comprehensive map of the complexity landscape for undirected graphs, several avenues remain for future research. The current model assumes "homogeneous" properties—the same property $\Pi$ must hold across layers. Real-world scenarios often require "heterogeneous" properties, such as finding a set of vertices that forms a clique in one layer and a connected component in another. Furthermore, extending this analysis to directed graphs or exploring structural parameters like treewidth could yield further insights into the "islands of tractability" within multi-layer network analysis.

Summary updated

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},
}
Figure