Assessing the Computational Complexity of Multi-layer Subgraph Detection

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

TL;DR

This paper maps the computational landscape of finding common subgraphs across multiple layers of a network (e.g., social, biological, or transport layers). While many of these problems are easy in a single-layer graph, the authors demonstrate that adding just two or three layers often pushes them into the realm of NP-hardness and W[1]-hardness, though they identify specific "islands of tractability" where efficient algorithms still exist.

What Problem Does This Paper Address?

In modern data science, we rarely look at a single network in isolation. We study "multi-layer graphs" (or multiplex networks) where the same set of entities (vertices) are connected by different types of relationships (edges) across various layers. For example, in a social network, layers might represent Facebook friendships, LinkedIn connections, and physical proximity.

The core challenge is Multi-Layer Subgraph Detection: finding a large subset of vertices that induces a subgraph with a specific property $\Pi$ (like being connected, forming a clique, or having a perfect matching) in at least $\ell$ out of $t$ total layers. While we understand these problems well for single graphs, this paper systematically investigates how the complexity explodes when you require a solution to work across multiple layers simultaneously.

Methods

The authors employ the framework of Parameterized Computational Complexity. Instead of just asking if a problem is "hard" (NP-hard), they look at how the running time scales with specific parameters like the number of layers ($t$), the number of vertices to select ($k$), or the number of layers to satisfy ($\ell$).

Key techniques include:

  • Ramsey Theory: Used to classify the complexity of "hereditary" properties (properties that stay true if you delete vertices, like being a forest or planar).
  • Gadget Reductions: The authors develop a novel "staggered" property framework to prove hardness for a wide class of non-hereditary properties (like connectivity or $c$-cores).
  • Algorithmic Reductions: For specific cases like Matching, they reduce the multi-layer problem to Maximum Weight Matching in an auxiliary graph to find polynomial-time solutions for the two-layer case.

Datasets

As a theoretical computer science paper, no empirical datasets were used. The work focuses on formal proofs, complexity classifications, and algorithm design rather than benchmarking on real-world data.

Key Insights and Ideas

  • The "Staggered" Property: The authors define a technical condition called being "staggered." If a graph property is staggered, finding a multi-layer subgraph with that property is almost certainly hard (W[1]-hard). This provides a powerful "shortcut" for researchers to identify hard problems.
  • The Complexity Jump in Matching: One of the most elegant findings is the transition for the Matching property. Finding a common set of vertices that admits a perfect matching in two layers is solvable in polynomial time. However, as soon as you require it for three layers, the problem becomes W[1]-hard.
  • Hereditary Trichotomy: For properties that are closed under vertex deletion, the authors prove a clean three-way split: the problem is either (1) trivial/poly-time, (2) FPT (fixed-parameter tractable) when considering both $k$ and $\ell$, or (3) W[1]-hard.
  • Islands of Tractability: Despite the general hardness, the authors show that if the property allows for a "nice" vertex partitioning (like finding connected components or $c$-cores), the problem remains tractable if the total number of layers $t$ is small.

Key Results

The paper provides a comprehensive "cheat sheet" (Table 1) for the complexity of various properties:

Graph Property $\Pi$ Complexity of Multi-Layer Version
Hereditary (e.g., Planar, Forest) Varies (Trichotomy); often W[1]-hard wrt $k$.
Connectivity / $c$-Core FPT wrt total layers $t$; W[1]-hard wrt $(k, \ell)$.
Matching Poly-time for $\ell \leq 2$; W[1]-hard for $\ell \geq 3$.
Hamiltonian Path W[1]-hard for $\ell \geq 2$.
Finite Forbidden Subgraphs FPT wrt "deletion" parameters ($|V|-k$ and $t-\ell$).

Limitations and Future Work

  • Undirected Focus: The current work focuses almost entirely on undirected graphs. The authors note that directed graphs might show even wider complexity gaps (e.g., finding a longest path is easy in a DAG but hard in undirected graphs).
  • Homogeneous Properties: The model assumes we want the same property $\Pi$ in every layer. Real-world applications often require different properties in different layers (e.g., "connected in layer A and a clique in layer B").
  • Parameter Exploration: While they covered the most "natural" parameters, other structural parameters (like treewidth or degree constraints of the layers) remain unexplored.

This paper serves as a foundational map for anyone designing algorithms for multi-layer networks, warning them where they will likely hit a wall of NP-hardness and showing them the narrow paths toward efficient solutions.

Summary updated

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.
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