Assessing the Computational Complexity of Multi-Layer
Subgraph Detection
Robert Bredereck1 , Christian Komusiewicz2 , Stefan Kratsch3 , Hendrik Molter1 ,
Rolf Niedermeier1 , and Manuel Sorge1

arXiv:1604.07724v1 [cs.CC] 26 Apr 2016

1

Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Germany,
{robert.bredereck, h.molter, rolf.niedermeier, manuel.sorge}@tu-berlin.de
2
Institut fr Informatik, Friedrich-Schiller-Universitt Jena, Germany,
christian.komusiewicz@uni-jena.de
3
Institut für Informatik I, Universität Bonn, Germany, kratsch@cs.uni-bonn.de
April 27, 2016
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.

1

Introduction

Multi-layer graphs consist of several layers where the vertex set of all layers is the same but each layer
has an individual edge set [4, 27, 31]. They are also known as multi-dimensional networks [3], multiplex
networks [34], and edge-colored multigraphs [1, 9]. In recent years, multi-layer graphs have gained a lot
of attention in the social network analysis and data mining communities because observational data often
comes in a multimodal nature. Typical topics studied here include clustering [5, 14, 15, 23], detection of
network communities [26, 40], data privacy [37], and general network properties [3].
In several of these applications, researchers identify vertex subsets of a multi-layer graph that exhibit
a certain structure in each of the layers. For example, motivated by applications in genome comparison
in computational biology, Gai et al. [21] searched for maximal vertex subsets in a two-layer graph that
induce a connected graph in each of the layers. Jiang and Pei [23] and Boden et al. [5] searched for
vertex subsets that induce dense subgraphs in many layers. Such vertex subsets model communities in
a multimodal social network.
To the best of our knowledge, however, there is no systematic work on computational complexity
classification beyond typically observing the generalization of hardness results for the one-layer case to
the multi-layer one [5, 23]. Our aim in this article is hence to provide a general foundation for studying
multi-layer subgraph problems, and to provide some initial results that pave the way for more specific
complexity analyses.
We first give a general problem definition that encompasses the problems sketched above. Vaguely,
they can be phrased as finding a large vertex subset that induces graphs with an interesting property
in many layers. Motivated by the heterogeneity of the desired properties, our problem definition has as
parameter a graph property Π, that is, any fixed set of graphs.

1

Π Multi-Layer Subgraph (Π-ML-Subgraph)
Input: A set of graphs G1 , . . . , Gt all on the same vertex set V and two positive integers k
and ℓ.
Question: Is there a vertex set X ⊆ V with |X| ≥ k such that for at least ℓ of the input
graphs Gi it holds that Gi [X] ∈ Π?
We study Π-ML-Subgraph mostly in the context of parameterized complexity. As parameters we
use the most natural candidates: the number t of layers, the order k of the desired subgraph and the
number ℓ of layers in which we search for our subgraph, as well as their dual deletion parameters |V | − k
and t − ℓ. Observe that NP-hardness and W[1]-hardness to either k or |V | − k in the single-layer case
directly implies hardness of the multi-layer case.
Our analysis of Π-ML-Subgraph starts with several easy results on hereditary graph properties Π,
that is, Π is closed under taking induced subgraphs. Such properties Π have been well-studied in the
single-layer case. Using Ramsey arguments and Khot and Raman’s theorem [25], we get a trichotomy
for the complexity of Π-ML-Subgraph with respect to polynomial-time solvability and fixed-parameter
tractability with respect to k and ℓ (Proposition 1). Second, we generalize Cai’s FPT result [8], by
showing that, for graph properties Π characterized by a finite number of forbidden induced subgraphs,
Π-ML-Subgraph is fixed-parameter tractable with respect to t − ℓ and |V | − k combined, and that it
admits a polynomial-size problem kernel (Proposition 2).
Next, we turn to graph properties that are not necessarily hereditary. For finding connected graphs
of order at least k in ℓ of t layers, there is a simple fixed-parameter algorithm with respect to t which is
also an XP-algorithm with respect to t − ℓ or with respect to ℓ. This algorithm admits a generalization to
each graph property that implies certain good-natured partitions of the input graphs (Proposition 3), for
example c-cores and c-trusses. As a counterpart, we offer a W[1]-hardness result for Π-ML-Subgraph
for the combined parameter k and ℓ for a large class of graph properties Π that includes connected
graphs, c-cores, and c-trusses, for example (Theorem 1).
Finally, we exhibit simple graph properties Π for which already a small number of layers lead to NPhardness and W[1]-hardness of Π-ML-Subgraph: While finding a vertex subset that induces subgraphs
of order k with a perfect matching in two layers is polynomial-time solvable, it becomes NP-hard and
W[1]-hard with respect to k in three layers (Theorem 2). Intuitively, the reason for the computational
complexity transition from two layers to three layers is as follows. Overlaying two matchings one may get
cycles and paths but without connections between them. We can cope with this by finding a maximum
weighted matching in an auxiliary graph. Adding a third layer, however, allows arbitrary connections
between cycles and paths. While finding a k-path, that is, a k-vertex graph containing a Hamiltonian
path, is fixed-parameter tractable with respect to k in one layer [32], it becomes W[1]-hard in two layers
(Theorem 3).
Apart from aiming to provide a broad overview over the complexity of Π-ML-Subgraph, the main
technical contributions are conditions on Π that make Π-ML-Subgraph hard (Theorem 1) and understanding the transition from tractability to hardness for perfectly matchable subgraphs (Theorem 2) and
Hamiltonian subgraphs (Theorem 3).
Related Work. As mentioned in the beginning, despite the numerous practical studies related to
multi-layer networks, we are not aware of systematic work pertaining to the computational complexity
of Π-ML-Subgraph. The following special cases were studied from this viewpoint. Gai et al. [21] and
[7] studied the case where Π contains every connected graph and t = ℓ = 2. They showed that the
resulting problem is polynomial-time solvable. In contrast, Cai and Ye [9] studied a modified version
of this problem, where the desired vertex subset shall be of size exactly k instead of at least k. They
showed NP-hardness and W[1]-hardness with respect to k and with respect to |V | − k. Agrawal et al. [1]
gave a O(23tk · poly(n, t))-time algorithm for the case where Π contains all cycle free graphs and t = ℓ.
Edge-colored graphs and multigraphs, which are equivalent to multi-layer graphs, were studied extensively. For surveys, see Bang-Jensen and Gutin [2, Chapter 16] and Kano and Li [24]. Most of the results
therein, in the multi-layer terminology, pertain to paths and cycles which do not contain two consecutive
edges in the same layer and to related questions like connectedness and Hamiltonicity using this notion
of paths or cycles.

2

Preliminaries. We use the framework of parameterized complexity: Let p be a parameter for ΠML-Subgraph, that is, any integer depending on the input. We aim to prove fixed-parameter tractability
(FPT) by giving an algorithm that produces a solution in f (p)·poly(|V |, t) time, where f is a computable
function, or we aim to show that such an algorithm is unlikely (W[1]-hardness for p). A problem kernel
is a model for efficient data reduction. Formally, it is a polynomial-time many-one self-reduction such
that the size of each resulting instance is bounded by a function of the parameter p. For the precise
definitions and methodology we refer the reader to the literature [11, 16, 20, 35].
All graphs are undirected and without self loops or multiple edges. We use standard graph notation [13]. A graph property Π is hereditary if removing any vertex from a graph in Π results again in
a graph in Π. We use the following graph properties. A graph is a c-core if each vertex has degree at
least c [38]. A graph is a c-truss if each edge is contained in at least c − 2 triangles [10]. We say that
a graph is Hamiltonian if it contains a simple path that comprises all vertices in the graph. A c-factor
in a graph is a subset of the edges such that each vertex is incident with exactly c edges. In sans serif
font face we often denote graph properties. For example, c-Truss is the set of all c-trusses. By Matching
we refer to the set of all graphs containing a perfect matching and by c-Factor to the set of all graphs
containing a c-factor. For further definitions of graph properties, see Appendix A.
Organization. In Section 2 we give general results for hereditary graph properties Π. In Section 3
we give general results for large classes of graph properties Π, that are not necessarily hereditary. In
Section 4 we show that c-Factor-ML-Subgraph is polynomial-time solvable for two layers but NP-hard
and W[1]-hard with respect to k in three layers. In Section 5 we show that Hamiltonian-ML-Subgraph
is W[1]-hard with respect to k in two layers.

2

Hereditary Graph Properties

In this section we study the (parameterized) complexity of Π-ML-Subgraph with respect to hereditary
graph properties Π. We give a trichotomy with regard to polynomial-time solvability, NP-hardness, and
the complexity with respect to parameters k and ℓ, and we observe fixed-parameter tractability for the
deletion parameters |V | − k and t − ℓ.
Next, we investigate the computational complexity of Π-ML-Subgraph for hereditary properties Π.
Many natural graph properties fall into this category. The single-layer case has been studied by Lewis
and Yannakakis [29] as well as Khot and Raman [25], the latter studied the parameterized complexity of
the subgraph detection for hereditary properties. We generalize their results to the multi-layer case.
Proposition 1. If Π is a hereditary graph property, then the following statements are true.
1. If Π excludes at least one complete graph and at least one edgeless graph, then Π-ML-Subgraph
is solvable in polynomial time.
2. If Π includes all complete graphs and all edgeless graphs, then Π-ML-Subgraph is NP-hard and
FPT when parameterized by k and ℓ combined.
3. If Π includes either all complete graphs or all edgeless graphs, then Π-ML-Subgraph is NP-hard
and W[1]-hard when parameterized by k for all ℓ.
Note that every hereditary graph property falls into one of the three cases of Proposition 1.
Proof. In this proof we utilize the concept of Ramsey numbers. Herein, Ramsey number R(p, q) states
the minimum number of vertices such that any graph with said number of vertices
has either a clique of

size p or an independent set of size q. It is well-known that R(p, q) ≤ p+q−2
q−1 . We give separate proofs
for all three statements in the theorem. Note that for the second and third case, NP-hardness in the
single-layer case was shown by Lewis and Yannakakis [29].
1. Let p, q be the sizes of the smallest excluded complete and edgeless graph, respectively. Note that
any graph on at least R(p, q) vertices contains either a clique of size p or an independent set of size
q and hence is not included in Π. Therefore there are only finitely many graphs that have property
Π. Furthermore we have that if k ≥ R(p, q), we face a no-instance.
If k < R(p, q), we can check every vertex subset X of size k on every layer and check whether
G[X] ∈ Π on at least ℓ layers. The time to do that is bounded by t nk f (k) where f (k) the time
to check membership of Π. Note that k is bounded by R(p, q) and p and q are constants only
depending on Π. Hence, we get a polynomial running time.
3

2. For this proof, we introduce nested Ramsey numbers as follows.
R(1) (p, q) = R(p, q),
R(i) (p, q) = R(R(i−1) (p, q), R(i−1) (p, q)).
We show that if |V | ≥ R(l) (k, k) we face a yes-instance. Furthermore, we can find a vertex subset
X with G[X] ∈ Π for any ℓ layers. We prove this by induction on ℓ.
For ℓ = 1 we have that |V | ≥ R(k, k), hence every layer of the graph has either a clique of size k
or an independent set of size k. For |V | ≥ R(ℓ) (k, k) we know that any layer has either a clique of
size R(ℓ−1) (k, k) or an independent set of size R(ℓ−1) (k, k). Without loss of generality let X ′ ⊆ V
with |X ′ | = R(ℓ−1) (k, k) be either a clique or an independent set on layer 1. Consider G[X ′ ]: By
the induction hypothesis we know that we can find a vertex set X ⊆ X ′ with |X| ≥ k on any ℓ − 1
layers such that G[X] ∈ Π. Additionally, we have that G[X] ∈ Π on layer 1. Hence, G[X] ∈ Π on
at least ℓ layers.
If |V | < R(ℓ) (k, k), we can find a solution by brute-force, if it exits. Note that NP-hardness follows
from the NP-hardness of the single-layer case.
3. Khot and Raman [25] showed that for hereditary properties Π that include either all complete
graphs or all edgeless graphs, Π-Subgraph is W[1]-hard when parameterized by k. This directly
translates to the multi-layer case, as does NP-hardness.
In the following corollary, we give a number of hereditary properties Π and the corresponding complexity results for Π-ML-Subgraph implied by Proposition 1. For their definitions we refer to the
literature [6, 22] or to Appendix A. We remark that properties that fall into the first case are exactly
those containing only a finite number of graphs.
Corollary 1. Π-ML-Subgraph is NP-hard and FPT when parameterized by k and ℓ combined for
Π ∈ {Perfect Graph, Interval Graph, Chordal Graph, Split Graph, Asteroidal Triple Free Graph, Comparability
Graph, Permutation Graph}.
Π-ML-Subgraph is NP-hard and W[1]-hard when parameterized by k for all ℓ for Π ∈ {Edgeless
Graph, Complete Graph, Complete Multipartite Graph, Planar Graph, c-Colorable Graph, Forest}.
Now we consider properties Π, whose complements are hereditary. We can show that, for them,
polynomial-time solvability transfers to the multi-layer case.
Observation 1. Let Π be a graph property such that, if G ∈ Π for some graph G and H[X] = G for some
graph H and vertex set X, then H ∈ Π. Equivalently, the complement property (containing all graphs
not in Π) is hereditary. If Π can be decided in f (n) time for some function f , then Π-ML-Subgraph
can be decided in O(t · f (n)) for all k and ℓ.
Proof. Observe that if G ∈
/ Π then no induced subgraph of G can be in Π. Hence to decide Π-MLSubgraph, we decide Π on each graph G1 , . . . , Gt . We face a yes-instance if and only if there are at
least ℓ graphs that have property Π: We can set X = V , and hence |X| ≥ k, for any k ≤ n.
In the following corollary, we give two properties Π for which Π-ML-Subgraph is solvable in polynomial time.
Corollary 2. Π-ML-Subgraph is solvable in polynomial time for:
• Π = “The graph has maximum degree of at least x.”
• Π = “The graph has an h-index1 [17] of at least x.”
Finally, we consider the dual parameterizations for hereditary graph properties characterized by a
finite number of forbidden subgraphs. In the single-layer case, this problem has been studied by Lewis
and Yannakakis [29] as well as Cai [8].
Proposition 2. Let Π be a hereditary graph property that is characterized by finitely many forbidden
induced subgraphs. Then Π-ML-Subgraph is NP-hard and FPT when parameterized by the number t − ℓ
of layers to delete and the number |V | − k of vertices to delete combined. It also admits a polynomial-size
problem kernel with respect to these parameters.
1 See

Appendix A for a definition of h-index.

4

Proof. To see the fixed-parameter tractability, consider the search-tree algorithm that recursively searches
for a forbidden induced subgraph G′ in one of the layers, and branches, for each vertex v in G′ , into
the branch of deleting v and, additionally, into the branch of deleting the layer of G′ . Finding G′ takes
polynomial time because it has constant size. Furthermore, each node in the resulting search tree has a
constant number of children. Hence, the search-tree algorithm has a running time of ct−ℓ+|V |−k · poly(I),
where c is a constant, and I is the instance size, as required.
To see that Π-ML-Subgraph admits a polynomial kernel with respect to t − ℓ and |V | − k, we use
a (basically folklore) reduction to 2-Color Hitting Set, a variant of Hitting Set. Herein, we are
given two disjoint ground sets B and W , a family F of subsets of B ∪ W , and two integers b, w. We
are to decide whether there is a hitting set S ⊆ B ∪ W containing b elements from B and w elements
from W , that is, each subset F ∈ F has F ∩ S 6= ∅. Clearly, 2-Color Hitting Set is contained in NP.
The reduction works as follows. Given an instance of Π-ML-Subgraph, we put the ground set B := V
and put a distinct new vertex into W for each layer. For each layer, we enumerate all forbidden induced
subgraphs. This takes polynomial time, as the maximum size of these subgraphs is a constant. To
define F , for each forbidden induced subgraph G′ we add its vertex set V ′ plus the vertex v ∈ W
corresponding to the layer in which G′ is contained as a set V ′ ∪ {v} to F . Integer b is set to |V | − k and
integer w to t − ℓ. As mentioned, the reduction works in polynomial time. Since we have to “hit” each
forbidden induced subgraph by either deleting a vertex from it, or deleting its layer completely, it is not
hard to verify that the reduction is correct.
We now apply the so-called sunflower kernelization procedure [28, 33, 39] to the resulting 2-Color
Hitting Set instance. A sunflower in F is a subfamily F ′ ⊆ F such that there is a set C ⊆ B ∪ W
with the property that each pair F, F ′ ∈ F ′ has F ∩ F ′ = C. The size of a sunflower is |F ′ |. If there is
a sunflower of size b + w + 1 in F , then every hitting set contains at least one element of C. Hence, we
can safely remove one set out of every sunflower of size at least b + w + 2. This can be done exhaustively
in polynomial time [28, 33, 39]. After this procedure has been carried out, Erdös and Rado’s Sunflower
Lemma [18] guarantees that the remaining set family F has size O((b + w)c ), where c is the size of the
largest set in F . This is a polynomial because the sets in F have constant size. By removing elements of
B ∪ W which are not contained in any set in F , we obtain an overall size bound on the resulting instance
of 2-Color Hitting Set which is polynomial in b = |V | − k and w = t − ℓ.
Finally, we transfer the instance of 2-Color Hitting Set created in this way to an equivalent
instance of Π-ML-Subgraph by using a polynomial-time many-one reduction. Such a reduction exists
because 2-Color Hitting Set is in NP and Π-ML-Subgraph is NP-hard for ever graph property Π
that is characterizable by a finite number of forbidden induced subgraphs [29].
In the following corollary, we give a number of hereditary properties Π characterizable with a finite
number of forbidden subgraphs and, hence, for which Π-ML-Subgraph is fixed-parameter tractable
with respect to the number t − ℓ of layers to delete and the number |V | − k of vertices to delete combined.
For their definitions see Appendix A.
Corollary 3. Π-ML-Subgraph is NP-hard and FPT when parameterized by t − ℓ and |V | − k combined
for Π ∈ {Cluster Graph, Cograph, Line Graph, Split Graph}.

3

Non-hereditary Graph Properties

In this section, we give two results related to graph properties that are not necessarily hereditary. First,
motivated by Connectivity, we give an FPT-algorithm with respect to t for graph properties in which each
graph admits a certain nice vertex partitioning; this algorithm is also an XP-algorithm with respect to ℓ.
Second, we give a general W[1]-hardness reduction for the combined parameter k and ℓ, capturing many
classes of graph properties such as c-Core, c-Truss, Connectivity, and Matching.
Vertex-partitionable graphs. We start with investigating graph properties Π that allow for efficiently computable partitions of the graph into maximal components that each satisfy Π. It turns out
that finding large Π-subgraphs in all input networks is tractable. This can be seen as a generalization of
the component-detection algorithm in two layers by Gai et al. [21].
Proposition 3. Let Π be a graph property such that for every graph G = (V, E) there is a partition P :=
{X1 , . . . , Xx } of V such that:
5

• G[Xi ] ∈ Π for all Xi ∈ P,
• for all X ⊆ V such that G[X] ∈ Π, we have X ⊆ Xi for some Xi ∈ P, and
• P can be computed in T (|V |, |E|) timewhere T is non-decreasing in both arguments.
Then, Π-ML-Subgraph can be solved in ℓt · O(n · t) · max1≤i≤t (|Ei | + T (|V |, |Ei |)) time.

We call a partition P which fulfills the above conditions with respect to some graph property Π a
Π-partition.

Proof. We describe an algorithm that outputs all maximal sets X ⊆ V such that Gi [X] ∈ Π for all input
graphs Gi . We refer to these sets as solutions in the following. The algorithm maintains a partition P
of V where, initially P = {V }.
The algorithm checks whether there is a Y ∈ P such that Gi [Y ] ∈
/ Π. If this is the case, then it
computes in T (|V |, |Ei |) time a Π-partition PY of Gi [Y ]. The partition P is replaced by (P \ {Y }) ∪ PY .
If this is not the case, then the algorithm outputs all Y ∈ P.
To see the correctness of the algorithm, first observe that for each output Y , we have Gi [Y ] ∈ Π for all
input graphs Gi . To show maximality of each Y , we show that the algorithm maintains the invariant that
each solution X is a subset of some Y ∈ P. This invariant is trivially fulfilled for the initial partition {V }.
Now consider a set Y that is further partitioned by the algorithm. By the invariant, any solution X that
has nonempty intersection with Y is a subset of Y . Furthermore, since PY is a Π-partition of Gi [Y ],
there is no solution X that contains vertices of two distinct sets Y1 , Y2 of PY . Thus, each solution that
is a subset of Y is also a subset of some Y ′ ∈ PY . Hence, each output set X is a solution as it is an
element of the final partition P and all solutions are subsets of elements of P.
To bound the running time, observe that for each Y ∈ P, we can test in O(t · max1≤i≤t T (|V |, |Ei |))
time whether it needs to be partitioned further. At most n partitioning steps are performed and if a
set Y ∈ P does not need to be partitioned further, then it can be discarded for the remainder of the
algorithm. Thus, in O(n) applications of the “maximality test” the result is that Y is a solution and
in O(n) applications of the maximality test, Y is further partitioned. Hence, the overall number of sets Y
that are elements of P at some point is O(n). The overall running time now follows from the assumptions
on T and from the fact that the induced subgraphs for all Gi can be computed in O(t · max1≤i≤t |Ei |)
time for each Y .
Examples of graph properties covered by Proposition 3 are Connectivity, c-Connectivity, and c-EdgeConnectivity. If we assume that graphs on one vertex are considered as (trivial) c-cores, then the cCore property is covered: the nontrivial c-core of a graph is uniquely determined (it is the subgraph
remaining after deleting any vertex with degree less than c). Similarly, the c-Truss property is covered
by Proposition 3 if we allow one-vertex graphs to be considered as c-trusses. Observe that we can
easily choose to either incorporate or disregard connectivity from the c-core and c-truss definitions. For
definitions of the graph properties mentioned above and in the following corollary see Appendix A.
If T is a polynomial function, which holds for all examples described above, then Π-ML-Subgraph
is fixed-parameter tractable with respect to t and polynomial time-solvable if ℓ or t − ℓ are constants.
Corollary 4. Π-ML-Subgraph is FPT when parameterized by t and polynomial time-solvable if ℓ or t−ℓ
are constants for Π ∈ {Connectivity, c-Connectivity, c-Edge-Connectivity, c-Truss, c-Core}.
General hardness reduction. Finally, we aim to give a general description of properties Π for
which Π-ML-Subgraph is NP-hard and W[1]-hard when parameterized by k and ℓ combined. The
next theorem is somewhat technical but covers many natural graph properties which are not covered
by Proposition 1. Furthermore, it covers all graph properties from Corollary 4 and shows that for those
properties Π-ML-Subgraph becomes intractable when parameterized by ℓ instead of t. We list some of
them in Corollary 5.
Theorem 1. Let Π be a graph property. Π-ML-Subgraph is W[1]-hard when parameterized by k and
ℓ combined, if there is an algorithm A that takes as input a vertex set W , a vertex set W ′ ⊆ W and an
integer α and computes a graph G = (V, E), such that the following conditions hold.
• For each v ∈ W there is a vertex set Xv with |Xv | = f (α) for some function f ,
• {Xv | v ∈ W } ∪ {Y } is a partition of V for some Y with |Y | = f ′ (α) for some function f ′ ,

6

• for all X ⊆ V with |X| ≥ α · f (α) + f ′ (α) we have that
G[X] ∈ Π ⇔ ∃W ′′ ⊆ W ′ , such that X =

[

Xv ∪ Y,

v∈W ′′

• and A has running time f ′′ (α) · |W |O(1) , for some function f ′′ .
If f ′′ is polynomial, then we additionally get NP-hardness of Π-ML-Subgraph.
The intuition is that each set Xv corresponds to one vertex v ∈ W and every set X such that
G[X] ∈ Π either fully contains Xv or not. Furthermore, Y contains vertices that have to be included in
X in order to have that G[X] ∈ Π and all sets Xv that correspond to vertices in v ∈ W \ W ′ have to be
fully excluded from X in order to have that G[X] ∈ Π. For the proof, we reduce from Biclique, which
is W[1]-hard when parameterized by the size h of the biclique [30].
Proof. We give a parameterized reduction from Biclique which, given an undirected graph H and a
positive integer h, asks whether H contains a complete bipartite subgraph Kh,h . Let (H = (U, F ), h) be
an instance of Biclique and let h ≥ 2. We construct an instance of Π-ML-Subgraph in the following
way.
For all v ∈ U , let NH (v) be the neighborhood of v with respect to H. Run Algorithm A on input
(U, NH (v), h) to create graphs Gv for each v ∈ U . Set k = h · f (h) + f ′ (h) and ℓ = h. Now we show that
({Gv }, k, ℓ) is a yes-instance of Π-ML-Subgraph if and only if (H, h) is a yes-instance of Biclique.
⇒: Assume that (H, h) isSa yes-instance of Biclique and let (C, D) with C, D ⊆ U and |C| = |D| = h
be a biclique. Then for X = v∈C Xv ∪Y and v ′ ∈ D, we have that all v, such that Xv ⊂ X, are neighbors
of v ′ and hence Gv′ [X] ∈ Π. Note that |X| = h · f (h) + f ′ (h) and |{Gv | v ∈ D}| = h, therefore it is a
solution of Π-ML-Subgraph.
⇐: Assume that ({Gv }, k, ℓ) is a yes-instance of Π-ML-Subgraph, then we know that there are
graphs Gi , with i ∈ L, L ⊆ U , |L| ≥ h, and a vertex set S
X ⊆ V with |X| ≥ k, such that Gi [X] ∈ Π for
all i ∈ L. By the construction of Gi , we know that X = v∈W ′ Xv ∪ Y for some W ′ ⊆ U with |W ′ | ≥ h.
Furthermore, we know that if i ∈ L then for all j ∈ W ′ (that is Xj ⊂ X) we have that i is neighbor of j.
Lastly, we have that i ∈ L implies that Xi 6⊂ X and hence i ∈
/ W ′ . Therefore we have that (L, W ′ ) is a
biclique in H with |L| ≥ h and |W ′ | ≥ h.
In the following corollary, we give several properties that are polynomial-time solvable in the singlelayer case but NP-hard and W[1]-hard when parameterized by k and ℓ combined in the multi-layer case.
For their definitions see Appendix A.
Corollary 5. Π-ML-Subgraph is NP-hard and W[1]-hard when parameterized by k and ℓ combined for
Π ∈ {Connectivity, Tree, Star, c-Core, c-Connectivity, c-Truss, Matching, c-Factor}.
Proof Sketch. We sketch Algorithm A from Theorem 1 for all properties listed above.
• Connectivity, Tree, Star, 1-Core: Let Xv := {v} and Y := {u}. Create an edge {u, v} for each vertex
v ∈ W ′.
• c-Core, c-Connectivity, c > 1: Let Xv := {v} and Y := {u1 , . . . , uc }. Create all edges (u, v) with
u ∈ Y and v ∈ W ′ .
• c-Truss: Let Xv := {v} and Y := {u1 , . . . , uc+1 }. Create all edges (u, v) with u ∈ Y and v ∈ W ′ ∪Y
and u 6= v.
• Matching: Let Xv := {v1 , v2 } for each v ∈ W and create edge (v1 , v2 ) if v ∈ W ′ .
• c-Factor: For each v ∈ W ′ , add a connected c-regular graph of size f (c) to G, for each v ∈ W \ W ′ ,
add f (c) vertices to V , for some function f .
A particular consequence of Corollary 5 is that the connected component detection algorithm for two
layers by Gai et al. [21] does not generalize to Connectivity-ML-Subgraph with ℓ ≪ t without significant
running time overhead.

4

Matching and c-Factors

In this section we consider the problem of finding a set X of at least k vertices that induces in ℓ of
t layers a subgraph that has a perfect matching. We also consider the more general c-factor property,
7

asking for a subset of edges such that each vertex is incident with exactly c edges. A perfect matching is
a 1-factor. Finding c-factors is polynomial-time solvable for all c (see Plummer [36] for an overview on
graph factors).
Corollary 5 states that Matching-ML-Subgraph is W[1]-hard when parameterized by k and ℓ combined. Through closer inspection we can get a stronger result. We show that Matching-ML-Subgraph
is polynomial-time solvable for ℓ ≤ 2 and becomes W[1]-hard when parameterized by k already for ℓ ≥ 3.
For c-Factor-ML-Subgraph we show that it is already W[1]-hard when parameterized by k if ℓ ≥ 2.
For ℓ = 1, we can simply check whether there is a c-factor in any of the layers. For ℓ = 2 Matching-MLSubgraph can be solved by reducing it to Maximum Weight Matching. To this end, let G1 = (V, E1 )
and G2 = (V, E2 ) be two input graphs for which we would like to know whether there is an X ⊆ V of
size at least k such that both G1 [X] and G2 [X] have a perfect matching. We solve the problem by a
simple reduction to Maximum Weight Matching, where we assume that the graph has edge weights
and the task is to find a matching with maximum edge weights.
Lemma 1. Given two graphs G1 = (V, E1 ) and G2 = (V, E2 ), define a graph G′ = (V ′ , E ′ ) as follows:
• V ′ = {v1 , v2 | v ∈ V } and
• E ′ = {{v1 , v2 } | v ∈ V } ∪ {{ui , vi } | {u, v} ∈ Ei }.
Define a weight function w : E ′ → N as follows; let n := |V |:
(
n
if i 6= j and u = v,
w({ui , vj }) =
n + 1 if i = j (and u 6= v).
Let k ∈ N. Then there is a set X ⊆ V of size at least k such that both G1 [X] and G2 [X] have a perfect
matching if and only if the graph G′ has a matching of w-weight at least n2 + k.
Proof. Assume that G′ has a matching M ′ ⊆ E ′ with w(M ′ ) ≥ n2 + k. Let us first check that M ′ is in
fact a perfect matching: If |M ′ | ≤ n − 1 then w(M ′ ) ≤ (n + 1)(n − 1) = n2 − 1 < n2 + k, which would
contradict the choice of M ′ . Thus |M ′ | ≥ n but then M ′ must have exactly n edges since G′ has 2n
vertices. That is, M ′ is a perfect matching. Let Y := {v | v ∈ V ∧ {v1 , v2 } ∈ M ′ }, that is, Y is the set of
vertices of V whose copies in G′ are matched under M ′ . Let X := V \ Y . It can be easily checked that
both G1 [X] and G2 [X] have perfect matchings; we show this for G1 [X]: For any v ∈ X we know that
{v1 , v2 } ∈
/ M ′ , or else we would have v ∈ Y and v ∈
/ X. Thus, using that M ′ is a perfect matching, v1
must be matched to another vertex u1 , which is then also in X, by definition. It follows that M ′ induces
a perfect matching on G1 [X1 ] where X1 := {v1 | v ∈ X}. Since G1 [X] is an isomorphic copy of G′ [X]
under canonical isomorphism φ : v 7→ v1 , we get that G1 [X] also has a perfect matching.
It remains to check that X has size at least k: Observe that |X| + |Y | = n since every vertex of V
is either in X or in Y . Each v ∈ Y corresponds to a matching edge {v1 , v2 } ∈ M ′ which has weight
n under w. Thus, if |X| < k then |Y | > n − k, which implies that w(M ′ ) ≤ |X| · (n + 1) + |Y |n <
kn + k + (n − k)n = n2 + k, contradicting the choice of M ′ .
Assume now that both G1 [X] and G2 [X] have perfect matchings M1 and M2 for some X of size at
least k. Clearly, the size of X must be even. Define a matching M ′ of G′ by M ′ := {{v1 , v2 } | v ∈
V \ X} ∪ {{ui , vi } | {u, v} ∈ Mi }. In other words, M ′ is obtained by copying M1 and M2 to G′ in the
obvious way and matching all leftover vertices by the edges between the copies of the same vertex.
Clearly, for each vertex v ∈ V \ X this adds an edge {v1 , v2 } of weight n to M ′ . From M1 and M2
′
we copied |X|
2 edges each, which results in exactly |X| ≥ k edges of weight n + 1 in M . Thus, the total
′
2
weight of M is n + k, as claimed.
To show that Matching-ML-Subgraph remains W[1]-hard when parameterized by k for ℓ ≥ 3, we
reduce from Multicolored Clique which is known to be W[1]-hard when parameterized by the solution
size [19].
Theorem 2. Matching-ML-Subgraph can be solved in polynomial time if ℓ ≤ 2. It is NP-hard and
W[1]-hard when parameterized by k for all ℓ ≥ 3 and t ≥ ℓ.
For c ≥ 2, c-Factor-ML-Subgraph is NP-hard and W[1]-hard when parameterized by k for all ℓ ≥ 2
and t ≥ ℓ.

8

Proof. The proof is split into two parts. First we prove the statement about Matching-ML-Subgraph
and then the statement about c-Factor-ML-Subgraph.
Matching. We get the polynomial-time solvability of Matching-ML-Subgraph for the case of ℓ ≤ 2
from Lemma 1. For the case of ℓ ≥ 3 we give a parameterized reduction from Multicolored Clique.
This reduction can be adapted to the c-factor case.
In Multicolored Clique, we are given an h-partite graph H = (U1 ⊎ . . . ⊎ Uh , F ) and need to
determine whether it contains a clique of size h. (Note that such a clique necessarily contains exactly one
vertex from each set Ui and cliques of more than h vertices are impossible.) Without loss of generality,
we assume that the number h of colors is even. We construct an instance of Matching-ML-Subgraph
for t = ℓ = 3 as follows and then argue that the construction is easily generalizable.
Vertices. First, create h − 1 vertices for each vertex in graph H (one vertex for each color other than
his own color). Formally, for each color 1 ≤ j ≤ h and each ui ∈ Uj create the vertex set Vi consisting of
the vertices v(i,j ′ ) , j ′ ∈ ({1, . . . , h} \ {j}). Second,
create one color vertex wj for each color j ∈ {1, . . . , h}.
S
We denote the set of color vertices as W := 1≤j≤h {wj }.
Vertex selection gadget by graph G1 and G2 . For each color 1 ≤ j ≤ h create for each ui ∈ Uj one
cycle on {wj } ∪ Vi in the graph G1 ∪ G2 such that the edges are alternating from G1 and from G2 . These
|Uj | cycles are all of length h and share only color vertex wj . To realize this, create the following edges.
For each 1 ≤ z ≤ h − 2 create an edge in graph G(z mod 2)+1 between v(i,z) and v(i,z+1) if z < j − 1,
between v(i,z+1) and v(i,z+2) if z ≥ j, and between v(i,z) and v(i,z+2) if z = j − 1. Create an edge between
wj and v(i,1) in graph G2 , between v(i,h) and wj in graph G1 if j 6= h, and between v(i,h−1) and wj in
graph G1 if j = h.
Validation gadget by graph G3 . For each adjacent vertex pair ui , ui′ with ui ∈ Uj and ui′ ∈ Uj ′ ,
we create an edge between v(i,j ′ ) and v(i′ ,j) in G3 . Furthermore, create the edge {wj , wj+h/2 } for each
1 ≤ j ≤ h/2.
Finally, by setting k = h2 and t = ℓ = 3 we complete the construction, which can clearly be performed
in polynomial time. It remains to show that graph H has a clique that contains each color exactly once if
and only if there is a vertex set X ⊆ V with |X| ≥ k such that graph Gz [X] contains a perfect matching
for each 1 ≤ z ≤ 3.
Correctness. ⇒: Assume that graph H has a clique K := {u1 , u2 , . . . , uh } and, without loss of
generality, ui ∈ Ui for all 1 ≤ i ≤ h. We show that X := W ∪ V1 ∪ V2 ∪ . . . ∪ Vh is a solution for our
Matching-ML-Subgraph instance. By construction, X is of size k = h + h · (h − 1) = h2 . It remains
to show that graph Gz [X] has a perfect matching for each 1 ≤ z ≤ 3. Recall that we created for each
color 1 ≤ j ≤ h and for each vertex ui ∈ Uj one cycle on {wj } ∪ Vi in the graph G1 ∪ G2 such that the
edges are alternating from G1 and from G2 . Since X only contains one of these cycles for each color, a
perfect matching is easy to find for graph G1 [X] and for graph G2 [X]. For graph G3 [X], we can find the
matching {{v(i,j) , v(j,i) } | 1 ≤ i, j ≤ h ∧ i 6= j} ∪ {{wj , wj+h/2 } | 1 ≤ j ≤ h/2}, since, by construction,
v(i,j) is adjacent to v(j,i) if ui is adjacent to uj , and ui ∈ Ui and uj ∈ Uj (which is the case since the
vertices from K form a clique).
⇐: Assume that there is a vertex set X ⊆ V with |X| ≥ k such that graph Gz [X] contains a perfect
matching for each 1 ≤ z ≤ 3. First, consider the graph G1 ∪ G2 and some pair of vertices {x1 , x2 } ⊆ X
that is matched in G1 or in G2 . Then, these two vertices must be from the same cycle {wj } ∪ Vi for
some 1 ≤ j ≤ h and ui ∈ Uj , since otherwise there is no edge between them in any of the two graphs.
Furthermore, if two vertices from {wj } ∪ Vi are in X, then all vertices from {wj } ∪ Vi must be in X
because otherwise there is no matching either in G1 or in G2 : Every vertex except wj has exactly one
neighbor in G1 and one neighbor in G2 which are both enforced to be also contained in X—this enforces
the whole cycle {wj } ∪ Vi to be contained in X. However, X contains the vertices from {wj } ∪ Vi for at
most one i for every color 1 ≤ j ≤ h, because wj can only be matched to one vertex in G1 and to one
vertex in G2 . This implies that X contains for each 1 ≤ j ≤ h all vertices from {wj } ∪Vi for exactly one i,
since |X| ≥ k = h2 and |{wj } ∪ Vi | = h. Without loss of generality, let Vi ⊆ X for all 1 ≤ i ≤ h and let
ui be the vertex in graph H corresponding to Vi . We show that K = {u1 , u2 , . . . , uh } is a clique in H. In
graph G3 [X] each color vertex wj must be matched to its only neighbor: wj+h/2 if j ≤ h/2 and wj−h/2
if j > h/2 (and cannot be matched to v(i,j) -vertices). Assume towards a contradiction that there is a
pair of vertices {ui , ui′ } ⊆ K, with ui ∈ Uj and ui′ ∈ Uj ′ , that is not adjacent. Then, note that v(i,j ′ )
and v(i′ ,j) must be matched, since, by construction of G3 , vertex v(i,j ′ ) is only adjacent to vertex v(i′ ,j) .
Moreover, if v(i,j ′ ) is adjacent to v(i′ ,j) in G3 , then ui is adjacent to ui′ in H—a contradiction.
Note that in order to make this reduction work for any t ≥ ℓ ≥ 3, we can insert ℓ − 3 additional layers
9

of complete graphs and t − ℓ layers of edgeless graphs.
c-Factor. In the following, we prove that for c ≥ 2, c-Factor-ML-Subgraph is W[1]-hard when
parameterized by k for t = ℓ = 2 and then argue that the construction is easily generalizable. Again,
we give a parameterized reduction from Multicolored Clique. Here we are given an h-partite graph
H = (U1 ⊎ . . . ⊎ Uh , F ) and need to determine whether it contains a clique of size h. (Note that such a
clique necessarily contains exactly one vertex from each set Ui and cliques of more than h vertices are
impossible.) We say that vertices from Ui have color i. Assume that h ≥ c + 1 and that c · h is even.
Note that the idea of the reduction is similar to the one of matching but already works for ℓ = 2 in
the c-factor case (c ≥ 2). One of the reasons is that we can construct connected c-regular graphs for
c ≥ 2 of almost arbitrary size and this allows us to construct a vertex selection gadget with only one
layer.
Vertices. For each color j, 1 ≤ j ≤ h, we do the following: We create a color vertex wj and for each
vertex ui in Uj , we create a set of h − 1 vertices Vi = {v(i,j ′ ) | 1 ≤ j ′ ≤ h and j ′ 6= j}. Note that we have
one vertex in Vi for each color except the color of ui . Let W = {wj | 1S≤ j ≤ h}. Furthermore,
for each
S
edge f ∈ F we create a set of vertices Vf with |Vf | = c − 1. Let VF = f ∈F Vf and V = i Vi ∪ W ∪ VF .
Vertex selection gadget by graph G1 . For every 1 ≤ j ≤ h and every ui in Uj we do the following:
We create a connected c-regular graph on the vertex set Vi ∪ {wj }. Note that this can be done in the
following way: Order the vertices in Vi ∪{wj } arbitrarily and connect each vertex to the ⌊c/2⌋ subsequent
vertices, wrapping around at the end. If c is odd, additionally connect each vertex v with the vertex at
position (x + h/2) mod h in the ordering, where x is the position of vertex v. Furthermore, we create a
complete graph on the vertices in VF .
Validation gadget by graph G2 . For all edges f ∈ F we do the following: Let f be the edge between
ui and ui′ , and ui ∈ Uj and ui′ ∈ Uj ′ . We create a complete graph on the vertices in Vf ∪ {v(i,j ′ ) , v(i′ ,j) }.
Note that this complete graph has order c + 1 and hence is a c-regular graph. Furthermore, we create a
complete graph on all vertices in W .
By setting k = h2 + 12 h(h − 1) · (c − 1) we complete the construction, which can clearly be performed
in polynomial time.
Correctness. ⇒: Assume graph H has an h-colored clique K and without loss of generality
S K =
{u1 , u2 , . . . , u
}.
Let
F
denote
the
set
of
all
edges
in
the
clique
K.
Furthermore,
let
V
=
h
K
K
1≤i≤h Vi
S
and VFK = f ∈FK Vf . We show that X = W ∪ VK ∪ VFK is a solution for c-Factor-ML-Subgraph.
Note that by construction, |X| = h2 + 21 h(h − 1) · (c − 1). It remains to show that G1 [X] and G2 [X] each
have c-factors. Observe that for any graph G = (V, E) and any partition P = {P1 , P2 , . . . , Pp } of V we
have that if G[Pi ] has a c-factor for all i, 1 ≤ i ≤ p, then G has a c-factor as well.
1. Note that G1 [VFK ] is a complete graph of order 21 h(h − 1) · (c − 1) ≥ 2c + 1 and hence has a
c-factor. Furthermore, let ui ∈ K and assume that ui ∈ Uj . Then we have that G1 [Vi ∪ {wj }] is
by construction a c-regular graph and hence also has a c-factor. Since K is an h-colored clique,
{Vi ∪ {wj } | ui ∈ K and ui ∈ Uj } is a partition of VK ∪ W .
2. Note that G2 [W ] is a complete graph of size h ≥ c + 1 and hence has a c-factor. Let f ∈ FK be the
edge connecting ui and ui′ , and let ui ∈ Uj and ui′ ∈ Uj ′ . Then we have that G2 [Vf ∪{v(i,j ′ ) , v(i′ ,j) }]
is by construction a complete graph of order c + 1 and hence also has a c-factor. Since K is an
h-colored clique, {Vf ∪ {v(i,j ′ ) , v(i′ ,j) } | f ∈ FK and f = {ui , ui′ }} is a partition of VFK ∪ VK .
Notably, PK = {{v(i,j ′ ) , v(i′ ,j) } | {ui , ui′ } = f for some f ∈ FK } is a partition of VK , since any ui
is connected to h−1 other vertices with a different color each and therefore {v(i,j ′ ) | {v(i,j ′ ) , v(i′ ,j) } ∈
PK } = Vi .
⇐: Assume there is a vertex set X ⊆ V such that |X| ≥ k and Gi [X] has a c-factor for ℓ different layers
i. By construction of the layers we have that G1 [X] and G2 [X] both have c-factors. Furthermore, we
show the following facts:
Fact 1: If v(i,j ′ ) ∈ X and ui ∈ Uj then Vi ⊆ X and wj ∈ X: By construction G1 [Vi ∪ {wj }] is a
connected c-regular graph and each v(i,j ′ ) ∈ Vi is only connected to other vertices in Vi ∪ {wj } in
G1 . Notice that any proper subgraph of a connected c-regular graph is not c-regular and does not
have a c-factor. It follows that as soon as any v(i,j ′ ) ∈ Vi is included in X, all other vertices in Vi
have to be included as well as wj , the vertex corresponding to the color of ui .
Fact 2: If Vi ⊆ X and Vi′ ⊆ X and ui ∈ Uj , then ui′ ∈
/ Uj : Note that G1 [Vi′ ] does not have a c-factor:
By construction we get a connected c-regular graph by adding the vertex corresponding to the
color of ui′ , hence G1 [Vi′ ] is a proper subgraph of a connected c-regular graph. Furthermore, we

10

have that wj is already part of the c-regular spanning graph of G1 [Vi ∪ {wj }], therefore ui′ cannot
have color j, that is ui′ ∈
/ Uj .
Fact 3: If X ∩ Vf 6= ∅ for some f ∈ F , then Vf ∪ {v(i,j ′ ) , v(i′ ,j) } ⊆ X, where ui ∈ Uj and ui′ ∈ Uj ′ are
the endpoints of f : By construction G2 [Vf ∪ {v(i,j ′ ) , v(i′ ,j) }] is a clique of size c + 1 and hence a
connected c-regular graph. Furthermore, this clique is disconnected from the rest of G2 and hence
as soon as one of its vertices is included in X, all of them are.
Now we show that K = {ui | Vi ⊆ X} is an h-colored clique in H. First, we show that there must be
some v(i,j) ∈ X: Since |X| ≥ h2 + 21 h(h − 1) · (c − 1) we have that X 6= W and from Fact 4 we get that
X 6⊆ W ∪ VF .
By Fact 4 we know that any Vi is either a subset of X or X ∩ Vi = ∅. Furthermore, if Vi ⊆ X and
ui ∈ Uj , so is wj . Fact 4 yields that we cannot have two vertices of the same color in K. This yields the
following inequality.
[
|
Vi ∪ W | ≤ h2
(1)
Vi ⊆X

Note that |X| ≥ h2 + 21 h(h − 1) · (c − 1) and Inequality 1 imply that X ∩ VF 6= ∅. By Fact 4 we get that
X can only include vertices corresponding to edges between vertices ui and ui′ , such that Vi ∪ Vi′ ⊆ X.
Therefore we get the following inequality.
|X ∩ VF | ≤

1
h(h − 1) · (c − 1)
2

(2)

Note that we get |X| = h2 + 12 h(h − 1) · (c − 1) if and only if both Inequalities 1 and 2 are equalities.
This implies that we have |K| = h, all vertices in K have different colors and all colors are present
(Inequality 1), and K is a clique in H (Inequality 2).
Note that in order to make this reduction work for any t ≥ ℓ ≥ 2, we can insert ℓ − 2 additional layers
of complete graphs and t − ℓ layers of edgeless graphs.

5

Hamiltonian Paths

In this section we investigate the problem variant of finding Hamiltonian subgraphs. Note that this
property is not captured by any of the meta theorems in Section 3. Hamiltonian-Subgraph is known to
be FPT when parameterized by the size of the subgraph k [32]. For the multi-layer case, we can show
that it is already intractable for any ℓ ≥ 2.
Theorem 3. Hamiltonian-ML-Subgraph is NP-hard and W[1]-hard when parameterized by k for all
ℓ ≥ 2 and t ≥ ℓ.
We reduce from the Multicolored Biclique problem. A simple reduction from Clique shows
that Multicolored Biclique is W[1]-hard [12].
Proof. In Multicolored Biclique we are given a bipartite graph H = (U ∪ W, F ) and a coloring that
partitions vertices in U and W in h parts each, that is, U = U1 ⊎ . . . ⊎ Uh and W = W1 ⊎ . . . ⊎ Wh . We
call these parts colors. We need to determine whether H contains a biclique of size 2h that consists of
one vertex of each color. Observe that the vertex-coloring implies that any solution contains h vertices
from U and h vertices from W . We will call the vertices from U low, and the vertices from W high.
Similarly, we call colors Ui low and colors Wi high. Given an instance H of Multicolored Biclique,
we construct an instance of Hamiltonian-ML-Subgraph for t = ℓ = 2 as follows and then argue that the
construction is easily generalizable.
Vertices. The vertex set V consists of the following subsets:
• All vertices U ∪ W of H,
• {s1 , s2 }, where we assume that s1 and s2 are not vertices of H,
• Ai,j , 1 ≤ i ≤ h, 1 ≤ j ≤ h, where Ai,j := {α{u,w} | {u, w} ∈ F ∧ u ∈ Ui ∧ w ∈ Wj }, and
• Di,j , 1 ≤ i ≤ h, 1 ≤ j ≤ h, where Di,j := {δ{w,u} | {w, u} ∈ F ∧ w ∈ Wi ∧ u ∈ Uj }.
Informally, the latter two sets are constructed by adding two vertices for each edge of H, each corresponding to one orientation of the undirected edge. The vertices are then assigned to the vertex sets according

11

to the colors of their endpoints and the orientations. Oriented edges from U to W (and their corresponding vertices in V ) are called ascending, oriented edges from W (and their corresponding vertices) are
called descending.
Now we describe how to construct a vertex and edge selection gadget by graph G1 and a validation
gadget by graph G2 . Both graphs consist of 2h2 +2h+2 levels with edges only between neighboring levels;
each Ui , Wi , Ai,j and each Di,j forms one level, the two remaining levels contain s1 and s2 , respectively.
Vertex and edge selection gadget by graph G1 . Informally, the graph G1 is constructed by putting
all low vertices and their incident ascending edges into low levels, then adding two levels for s1 and s2
and then putting all high vertices and their incident descending edges into high levels. More precisely, U1
is the first level of G and A1,1 is the second level. Then edges are added from each u ∈ U1 to all vertices
of A1,1 that correspond to an edge incident with u. Then, the ascending vertices “incident” with vertices
from U1 are added for increasing colors of the high endpoints. Afterwards, the vertices from U2 are added
and then the vertices corresponding to their incident edges, and so on. The special vertices s1 and s2
are added in two middle levels, separating the levels containing low vertices from those containing high
vertices. Formally, the graph G1 is constructed as follows:
• For each u ∈ Ui , 1 ≤ i ≤ h add the edge {u, α{u,w} } if w ∈ W1 ,
• for each α{u,w} ∈ Ai,h , 1 ≤ i < h, add an edge to each u′ ∈ Ui+1 ,
• for each α{u,w} ∈ Ai,j , 1 < j < h, add an edge to each α{u,w′ } ∈ Ai,j+1 ,
• for each α{u,w} ∈ Ah,h an edge to s1 ,
• add the edge {s1 , s2 },
• for each w ∈ W1 , add the edge {s2 , w},
• for each w ∈ Wi , 1 < i ≤ h, add the edge {w, δ{w,u} } if u ∈ U1 ,
• for each δ{w,u} ∈ Di,h , 1 ≤ i < h, add an edge to each w′ ∈ Wi+1 , and
• for each δ{w,u} ∈ Di,j , 1 ≤ j < h, add an edge to each δ{w,u′ } ∈ Di,j+1 .
The idea behind the construction is that any path from the first level to the last level corresponds to a
selection of 2h vertices and of 2h2 edges incident with these vertices.
Validation gadget by graph G2 . With the second graph G2 we enforce that the selected ascending
and descending edges between each color pair Ui and Wj correspond to the same edge in H and that any
path of length 2h + 2h2 passes through each level of G1 and each level of G2 . Formally, G2 is constructed
as follows, herein, assume an arbitrary but fixed ordering on pairs of low and high colors.
• Level 1 contains s1 ,
• level 2i, 1 ≤ i ≤ h2 , contains all ascending vertices of the i-th color pair,
• level 2i + 1, 1 ≤ i ≤ h2 , contains all descending vertices of the i-th color pair,
• level 2h2 + 2 contains s2 ,
• level 2h2 + 2 + i, 1 ≤ i ≤ h, contains the vertices from Ui , and
• level 2h2 + h + 2 + i, 1 ≤ i ≤ h, contains the vertices from Wi .
All edges between consecutive levels are added except for the levels 2i and 2i + 1, 1 ≤ i ≤ h2 : here
we add only an edge between vertices that correspond to the same edge, that is, we add the edge
set {α{u,w} , δ{w,u} | {u, w} ∈ F }.
To finish the construction we set k = 2h + 2h2 + 2. The reduction runs clearly in polynomial time and
the new parameter k depends only on the parameter h of the Multicolored Biclique instance. Thus
it remains to show equivalence of the instances. Correctness. ⇒: Let K = {u1 , . . . , uh , w1 , . . . , wh } be
a multi-colored biclique in H. Let X be the vertex set containing K, s1 and s2 , and for each edge e
of H[K], the ascending and the descending vertex corresponding to e. We show that G1 [X] and G2 [X]
have a Hamiltonian path. In G1 , this path starts at u1 , then visits αu1 ,w1 , then αu1 ,w2 until αu1 ,wh . Then
it visits u2 and the ascending vertices corresponding to edges incident with u2 in the same fashion, that
is, first αu2 ,w1 , then αu2 ,w2 and so on. This is continued until αuh ,wh is visited. Then, the path visits s1
and s2 . Then it visits the high vertices and the descending vertices for their incident edges in the same
fashion. By construction, all the necessary edges are present: neighboring edge vertices correspond to
edges that share one endpoint, and after a vertex αi , the next visited edge vertex is incident with αi .
In G2 , the path visits each level exactly once, going from level 1 through level k. The necessary
edges are present since the only neighboring levels that are not complete bipartite graphs are those that
contain ascending and descending vertices of the same color pair. Since for each color pair the ascending
and descending vertex in S correspond to the same edge in H, they are adjacent
S in G2 .
⇐: Observe that any vertex set consisting only of vertices from {s1 , s2 } ∪ 1≤i≤h (Ui ∪ Wi ) is disconnected either in G1 or in G2 . Thus, the set X contains at least one ascending or descending vertex. In
12

either case it must also contain an edge vertex of the other type: in G2 , the levels containing ascending
and descending vertices alternate and any set containing either only vertices of the first two levels of G2 or
only of vertices of the last 2h+2 levels is disconnected in G1 . Now since X contains an ascending and a descending vertex and since G1 [X] is connected, the vertices s1 and s2 are contained in X. Thus, the vertex
set X contains a vertex from the first and the last level of 2h+2h2 +2 levels in G2 . This implies that it contains exactly one vertex of each level of G2 . Thus, the vertex set X contains exactly h low vertices and h
high vertices with different colors and it contains for each color pair an ascending and a descending vertex.
By construction of G2 and since G2 [X] has a Hamiltonian path visiting each level exactly once, these two
vertices are the same, that is, the 2h2 ascending and descending vertices correspond to h2 edges in H. By
construction of G1 and since G1 [X] has a Hamiltonian path visiting each level of G1 exactly once, these
edges are incident only with vertices of (U ∪ W ) ∩ X. Thus, H[(U ∪ W ) ∩ X] is a multicolored biclique.
Note that in order to make this reduction work for any t ≥ ℓ ≥ 2, we can insert ℓ − 2 additional layers
of complete graphs and t − ℓ layers of edgeless graphs.

6

Conclusion

We have initiated a systematic study of subgraph detection problems in multi-layer networks. In particular, we have shown hardness results for many multi-layer subgraph detection problems that are solvable
in polynomial time in the single-layer case. In the following, we list some possibilities for obtaining
positive algorithmic results. For example, the case of two-layer graphs should receive special attention.
We showed that Matching-ML-Subgraph is solvable in polynomial time in the two-layer case, whereas
it is W[1]-hard when parameterized by k for 3 or more layers. Considering cycle-free subgraphs Agrawal
et al. [1] also showed specialized algorithms for the two-layer case. Thus, it would be interesting to
systematically determine which subgraph detection problems become tractable in the two-layer case and
to identify problems that behave differently for two and three layers. Finally, in many applications the
input graphs are directed. One of our hardness results transfers directly to this case: The construction
in the reduction from Multicolored Biclique to Hamiltonian-ML-Subgraph (proof of Theorem 3)
can be easily adapted to yield directed acyclic graphs by orienting all edges from lower levels to higher
levels. Hence, for directed acyclic graphs the complexity gap between the cases with one and two layers
is even bigger because finding a longest path in a directed acyclic graph is polynomial-time solvable.

References
[1] A. Agrawal, D. Lokshtanov, A. E. Mouawad, and S. Saurabh. Simultaneous feedback vertex set: A parameterized perspective. In Proceedings of the 33rd International Symposium
on Theoretical Aspects of Computer Science (STACS ’16), 2016. To appear, available at
http://arxiv.org/abs/1510.01557.
[2] J. Bang-Jensen and G. Gutin. Digraphs: Theory, Algorithms and Applications. Springer, 2nd
edition, 2002.
[3] M. Berlingerio, M. Coscia, F. Giannotti, A. Monreale, and D. Pedreschi. Multidimensional networks:
foundations of structural analysis. Proceedings of the 22nd International Conference on World Wide
Web (WWW ’15), 16(5-6):567–593, 2013.
[4] S. Boccaletti, G. Bianconi, R. Criado, C. I. del Genio, J. Gmez-Gardees, M. Romance, I. SendiaNadal, Z. Wang, and M. Zanin. The structure and dynamics of multilayer networks. Physics Reports,
544(1):1–122, 2014.
[5] B. Boden, S. Günnemann, H. Hoffmann, and T. Seidl. Mining coherent subgraphs in multi-layer
graphs with edge labels. In The 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’12), pages 1258–1266, 2012.
[6] A. Brandstädt, V. B. Le, and J. P. Spinrad. Graph Classes: A Survey, volume 3 of SIAM Monographs
on Discrete Mathematics and Applications. SIAM, 1999.
[7] B. Bui-Xuan, M. Habib, and C. Paul. Competitive graph searches. Theoretical Computer Science,
393(1-3):72–80, 2008.
[8] L. Cai. Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters, 58(4):171–176, 1996.

13

[9] L. Cai and J. Ye. Dual connectedness of edge-bicolored graphs and beyond. In Proceedings of
the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS ’14),
volume 8635 of LNCS, pages 141–152. Springer, 2014.
[10] J. Cohen. Trusses: Cohesive subgraphs for social network analysis. National Security Agency
Technical Report, page 16, 2008.
[11] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and
S. Saurabh. Parameterized Algorithms. Springer, 2015.
[12] H. Dell and D. Marx. Kernelization of packing problems. In Proceedings of the Twenty-Third Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA ’12), pages 68–81. SIAM, 2012.
[13] R. Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer, 3rd edition,
2005.
[14] X. Dong, P. Frossard, P. Vandergheynst, and N. Nefedov. Clustering with multi-layer graphs: A
spectral perspective. IEEE Transactions on Signal Processing, 60(11):5820–5831, 2012.
[15] X. Dong, P. Frossard, P. Vandergheynst, and N. Nefedov. Clustering on multi-layer graphs via
subspace analysis on Grassmann manifolds. IEEE Transactions on Signal Processing, 62(4):905–
918, 2014.
[16] R. G. Downey and M. R. Fellows. Fundamentals of Parameterized Complexity. Springer, 2013.
[17] D. Eppstein and E. S. Spiro. The h-index of a graph and its application to dynamic subgraph
statistics. Journal of Graph Algorithms and Applications, 16(2):543–567, 2012.
[18] P. Erdös and R. Rado. Intersection theorems for systems of sets. Journal of the London Mathematical
Society, 35(1):85–90, 1960.
[19] M. R. Fellows, D. Hermelin, F. A. Rosamond, and S. Vialette. On the parameterized complexity of
multiple-interval graph problems. Theoretical Computer Science, 410(1):53–61, 2009.
[20] J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, 2006.
[21] A.-T. Gai, M. Habib, C. Paul, and M. Raffinot. Identifying common connected components of
graphs. Technical report, Technical Report RR-LIRMM-03016, LIRMM, Université de Montpellier
II, 2003.
[22] M. C. Golumbic. Algorithmic graph theory and perfect graphs, volume 57 of Annals of Discrete
Mathematics. Elsevier B. V., 2nd edition, 2004. First edition Academic Press, 1980.
[23] D. Jiang and J. Pei. Mining frequent cross-graph quasi-cliques. ACM Transactions on Knowledge
Discovery from Data, 2(4), 2009.
[24] M. Kano and X. Li. Monochromatic and Heterochromatic Subgraphs in Edge-Colored Graphs - A
Survey. Graphs and Combinatorics, 24(4):237–263, 2008.
[25] S. Khot and V. Raman. Parameterized complexity of finding subgraphs with hereditary properties.
Theoretical Computer Science, 289(2):997–1008, 2002.
[26] J. Kim and J. Lee. Community detection in multi-layer graphs: A survey. SIGMOD Record, 44(3):
37–48, 2015.
[27] M. Kivel, A. Arenas, M. Barthelemy, J. P. Gleeson, Y. Moreno, and M. A. Porter. Multilayer
networks. Journal of Complex Networks, 2(3):203–271, 2014.
[28] S. Kratsch. Polynomial kernelizations for MIN F+ Π1 and MAX NP. In Proceedings of the 26th
International Symposium on Theoretical Aspects of Computer Science (STACS ’09), pages 601–612.
IBFI Dagstuhl, Germany, 2009.
[29] J. M. Lewis and M. Yannakakis. The node-deletion problem for hereditary properties is NP-complete.
Journal of Computer and System Sciences, 20(2):219–230, 1980.
[30] B. Lin. The parameterized complexity of k-biclique. In Proceedings of the Twenty-Sixth Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA ’15), pages 605–615. SIAM, 2015.
[31] M. Magnani and L. Rossi. The ML-model for multi-layer social networks. In Proceedings of the
International Conference on Advances in Social Networks Analysis and Mining (ASONAM ’11),
pages 5–12. IEEE Computer Society, 2011.
[32] B. Monien. How to find long paths efficiently. North-Holland Mathematics Studies, 109:239–254,
1985.
[33] H. Moser. Finding Optimal Solutions for Covering and Matching Problems. PhD thesis, Institut für
Informatik, Friedrich-Schiller Universität Jena, 2009.
[34] P. J. Mucha, T. Richardson, K. Macon, M. A. Porter, and J.-P. Onnela. Community structure in
time-dependent, multiscale, and multiplex networks. Science, 328(5980):876–878, 2010.
[35] R. Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006.
14

[36] M. D. Plummer. Graph factors and factorization: 1985-2003: A survey. Discrete Mathematics, 307
(7-8):791–821, 2007.
[37] L. Rossi, M. Musolesi, and A. Torsello. On the k-anonymization of time-varying and multi-layer
social graphs. In Proceedings of the 9th International Conference on Web and Social Media (ICWSM
’15), pages 377–386. AAAI Press, 2015.
[38] S. B. Seidman. Network structure and minimum degree. Social Networks, 5(3):269–287, 1983.
[39] R. van Bevern. Towards optimal and expressive kernelization for d-hitting set. Algorithmica, 70(1):
129–147, 2014.
[40] Z. Zeng, J. Wang, L. Zhou, and G. Karypis. Out-of-core coherent closed quasi-clique mining from
large dense graph databases. ACM Transactions on Database Systems, 32(2):13, 2007.

A

Definitions

Asteroidal Triple Free Graph An independent set of size three where each pair of vertices is joined
by a path that avoids the neighborhood of the third is called an asteroidal triple. A graph is
asteroidal triple-free if it does not contain asteroidal triples.
c-Colorable Graph A graph is c-colorable if there is a way of coloring the vertices with at most c
different colors such that no two adjacent vertices share the same color.
c-Connectivity A graph is called c-connected if it contains at least c + 1 vertices, but does not contain
a set of c − 1 vertices whose removal disconnects the graph.
c-Core A graph is called a c-core if each vertex has degree at least c.
c-Edge-Connectivity A graph is called c-edge-connected if it does not contain a set of c − 1 edges
whose removal disconnects the graph.
c-Factor A graph has a c-factor if it has a c-regular spanning graph.
c-Regular Graph A graph is called c-regular if every vertex has degree c.
c-Truss A graph is called a c-truss if each edge is contained in at least c − 2 triangles.
Chordal Graph A graph is called chordal if each induced cycle has at most three vertices.
Cluster Graph A graph is called a cluster graph if it is a collection of cliques.
Cograph A graph is called a cograph if it does not contain any induced path of length four.
Comparability Graph A graph is called a comparability graph if there is a partial order over the
vertices such that each pair of vertices is adjacent if and only if it is comparable.
Complete Multipartite Graph A graph is called complete multipartite if the vertex set can be partitioned such that each vertex pair is adjacent if and only if the two vertices are in different partitions.
Edgeless Graph A graph is called edgeless is it does not contain any edges.
Forest A graph is called a forest if it is a collection of trees.
Hamiltonian Graph A graph is called Hamiltonian if it contains a Hamiltonian path, that is a path
that visits each vertex exactly once.
h-Index The h-index of a graph is the largest integer h such that the graph contains at least h vertices
with degree at least h.
Interval Graph A graph is called a interval graph if an interval of the real numbers can be assigned to
each vertex such that two vertices are adjacent if and only if the intervals overlap.

15

Line Graph A graph is called a line graph if there is another graph such that each vertex of the line
graph corresponds to an edge of the other graph and two vertices in the line graph are adjacent if
the corresponding edges in the other graph share a common endpoint.
Matching A graph has a matching if it has an 1-factor.
Perfect Graph A graph is called perfect if the chromatic number of every induced subgraph equals the
size of the largest clique of that subgraph. The chromatic number of a graph is the smallest c such
that the graph is c-colorable.
Permutation Graph A graph is called a permutation graph if there is a permutation of the vertices
such that two vertices are adjacent if and only if they are reversed by the permutation.
Planar Graph A graph is called planar if it can be embedded in the plane, that is it can be drawn on
the plane such that its edges only intersect at their endpoints.
Split Graph A graph is called a split graph if its vertices can be partitioned into a clique and an
independent set.
Star A graph is called a star if it is a tree with only one internal node.

16

