In this paper, we address three related problems. One is the enumeration of all the maximal edge-induced chain subgraphs of a bipartite graph. We give bounds on their number and use them to establish the input-sensitive complexity of the enumeration problem. The second problem we treat is the minimum chain subgraph cover. Finally, we approach the problem of enumerating all minimal chain subgraph covers and show that it can be solved in quasi-polynomial time.
Enumerating (listing) the subgraphs of a given graph plays an important role in analysing its structural properties. Thus, it is a central issue in many areas, notably in data mining and computational biology.
In this paper, we address the problem of enumerating without repetitions all maximal edge-induced chain subgraphs of a bipartite graph. These are graphs that do not contain a 2K2 as induced subgraph (i.e. there are no independent edge sets of size 2). From now on, we will refer to them as chain subgraphs for short when there is no ambiguity.
Bipartite graphs arise naturally in many applications, such as biology as will
be mentioned later in the introduction, since they enable to model the relations
between two different classes of objects. The problem of enumerating in bipartite
graphs all subgraphs with certain properties has thus already been considered in
the literature. These concern for instance maximal bicliques for which polynomial
delay enumeration algorithms in bipartite [
In this paper, we propose a polynomial delay algorithm to enumerate all
maximal chain subgraphs of a bipartite graph. We also provide an analysis of the
time complexity of this algorithm in terms of input size. In order to do this, we
prove some upper bounds on the maximum number of maximal chain subgraphs
of a bipartite graph G with n nodes and m edges. This is also of intrinsic interest
as combinatorial bounds on the maximum number of specific subgraphs in a
graph are difficult to obtain and have received a lot of attention (see for e.g.
[
We then address a second related problem called the minimum chain
subgraph cover problem. This asks to determine, for a given graph G, the minimum
number of chain subgraphs that cover all the edges of G. This has already been
investigated in the literature as it is related to other well-known problems such
as maximum induced matching (see e.g. [
We provide an exact exponential algorithm which runs in time O∗((2 + ε)m), for every ε > 0 (by O∗ we denote standard big O notation but omitting polynomial factors). Notice that, since a chain subgraph cover is a family of subsets of edges, the existence of an algorithm whose complexity is close to 2m is not obvious. Indeed, the basic search space would have size 22m , which corresponds to all families of subsets of edges of a graph on m edges.
Finally, we approach the problem of enumerating all minimal covers by chain subgraphs. To this purpose, we provide a quasi-polynomial time algorithm to enumerate all minimal covers by maximal chain subgraphs of a bipartite graph. To do so, we prove that this can be polynomially reduced to the enumeration of the minimal set covers of a hypergraph.
Besides their theoretical interest, the problems of finding one minimum chain
subgraph cover and of enumerating all such covers have also a direct application
in biology. Nor et al. [
Throughout the paper, we assume that the reader is familiar with the standard
graph terminology, as contained for instance in [
Given a bipartite graph G = (U ∪ W, E) and a node u ∈ U , we denote by NG(u) the set of nodes adjacent to u in G and by EG(u) the set of edges incident to u in G. Moreover, given U 0 ⊆ U and W 0 ⊆ W , we denote by G[U 0, W 0] the subgraph of G induced by U 0 ∪ W 0. A node u ∈ U such that NG(u) = W is called a universal node.
For a chain graph, an equivalent condition of not containing a 2K2 as an induced subgraph it is that for each two nodes v1 and v2 both in U (resp. in W ), it holds that either NG(v1) ⊆ NG(v2) or NG(v2) ⊆ NG(v1). Given a chain subgraph C = (X ∪ Y, F ) of G, with the largest neighbourhood of C, we mean the neighbourhood of a node x in X for which the set NC (x) ⊆ Y has maximum cardinality. A set Y 0 ⊆ Y is a maximal neighborhood of G, if there exists u ∈ U such that NG(u) = V 0 and there does not exist a node u0 ∈ U such that NG(u) ⊂ NG(U 0).
In this paper, we always consider edge-induced chain subgraphs of a graph G. Hence, we identify a chain subgraph C of G by its set of edges E(C) ⊆ E(G) and in that case its set of nodes will be constituted by all the nodes of G incident to at least one edge in C (sometimes abusing notation, we more simply write C ⊆ G or e ∈ C). A maximal chain subgraph C of a given bipartite graph G is a connected chain subgraph such that no superset of E(C) is a chain subgraph. We denote by C(G) the set of all maximal chain subgraphs in G. G.
A set of chain subgraphs C1, . . . , Ck is a cover for G if ∪1≤i≤kE(Ci) = E(G). Observe that, given any cover of G by chain subgraphs C = {C1, . . . Ck}, there exists another cover of same size C0 = {C10, . . . Ck0} whose chain subgraphs are all maximal; more precisely, for each i = 1, . . . , k, Ci0 is a maximal chain subgraph of G and Ci0 admits Ci as subgraph. In order to avoid redundancies, from now on, although not explicitly highlighted, we will restrict our attention to the covers by maximal chain subgraphs.
We denote by S(G) the set of all minimal chain covers of a bipartite graph
An enumeration algorithm is said to be output polynomial or total polynomial
if the total running time is polynomial in the size of the input and the output. It
is said to be polynomial delay if the time between the output of any one solution
and the next one is bounded by a polynomial function of the input size [
The following theorem characterizes the structure of a maximal chain subgraph and it is fundamental for all the other results of the paper. Theorem 1. Let C = (X ∪ Y, F ) be a chain subgraph of G = (U ∪ W, E), with X ⊆ U , Y ⊆ W and F ⊆ E, and let x ∈ X be a node with largest neighbourhood in C. Then C is a maximal chain subgraph of G if and only if: (i) NC (x) = NG(x) is a maximal neighbourhood of G, i.e. there does not exist a node u0 ∈ U such that NG(u) ⊂ NG(u0). (ii) C \ EG(x) is a maximal chain subgraph of G U \ {x}, NG(x) .
Theorem 1 is the basis of a new recursive algorithm which enumerates all maximal chain subgraphs of G with polynomial delay: Proposition 1 (Time Complexity and Polynomial Delay). Let G = (U ∪ W, E) be a bipartite graph. It is possible to enumerate all maximal chain subgraphs of G with a total running time of O(|C(G)|n2m). Moreover, the solutions are enumerated in polynomial time delay O(n2m).
These two statements allow us to achieve some other results briefly described in the following. 3.1
By Theorem 1(ii), a maximal chain subgraph can be found by recursively reducing the graph to one whose partition has size |U | − 1, so we obtain that the maximum number of chain subgraphs is bounded by min(|U |, |W |)! and that this bound is tight as e.g. the antimatching graph reach this bound.
We give also a bound on the number of maximal chain subgraphs for a bipartite graph with m edges: Theorem 2. Let G = (U ∪ W, E) be a bipartite graph with m edges; then |C(G)| ≤ 2 √m log m. 3.2
Exploiting Proposition 1, the bound obtained in Theorem 2 and the
inclusion/exclusion method [
Theorem 3. Let ck(G) be the number of chain subgraph covers of size k of a graph G. Given a bipartite graph G with m edges, for all k ∈ N∗ and for all ε > 0, ck(G) can be computed in time O∗((2 + )m).
The enumeration of all minimal chain subgraph covers can be polynomially
reduced to the enumeration of the minimal set covers of a hypergraph. This
reduction implies that there is a quasi-polynomial time algorithm to enumerate
all minimal chain subgraph covers. Indeed, the result in [
Let S = S(G) the set of its minimal chain subgraph covers. Notice that the minimal chain subgraph covers of G are the minimal set covers of the hypergraph H := (V, E ) where V = E and E = C. Unfortunately, the size of H might be exponential in the size of G plus the size of S. Indeed not every maximal chain subgraph in C will necessarily be part of some minimal chain subgraph cover. In order to obtain a quasi-polynomial time algorithm to enumerate all minimal chain subgraph covers, we need to enumerate only those maximal chain subgraphs that belong to a minimal chain subgraph cover.
Given an edge e ∈ E, let Ce be the set of all maximal chain subgraphs of G containing e and Me the set of all edges e0 ∈ E inducing a 2K2 in G together with e.
We call an edge e ∈ E non-essential if there exists another edge e0 ∈ E such that Ce0 ⊂ Ce. An edge which is not non-essential is said to be essential. Note that for every non-essential edge e, there exists an essential edge e1 such that Ce1 ⊂ Ce. Indeed, by applying iteratively the definition of a non-essential edge, we obtain a list of inclusions Ce ⊃ Ce1 ⊃ Ce2 . . ., where no Cei is repeated as the inclusions are strict. The last element of the list will correspond to an essential edge.
By the next Lemma we show that it is sufficient to consider the chain subgraphs which contain at least an essential edge.
Lemma 1. Let C be a maximal chain subgraph of a bipartite graph G = (U ∪ W, E). Then C belongs to a minimal chain subgraph cover of G if and only if C contains an essential edge.
In the following, we show how to detect essential edges.
Theorem 4. Given a bipartite graph G = (U ∪W, E), for any two edges e, e0 ∈ E, Ce ⊆ Ce0 if and only if Me ⊇ Me0 .
Notice that, given an edge e = (u, w) ∈ E, u ∈ U and w ∈ W , it is easy to determine the set Me, and checking whether Me ⊇ Me0 is also easy.
These results allow us to achieve the following result: Theorem 5. Given a bipartite graph G = (U ∪ W, E), one can enumerate all its minimal chain subgraph covers, i.e. all the elements in S, in time O(|S|log(|S|)+2).