A procedure for counting edge covers of simple graphs is presented. The procedure splits simple graphs into non-intersecting cycle graphs. This is the first “low exponential” exact algorithm to count edge covers for simple graphs whose upper bound in the worst case is O(1.465575(m−n) × (m + n)), where m and n are the number of edges and nodes of the input graph, respectively.
A graph is a pair G = (V, E), where V is a set of vertices and E is a set of edges
that associates pairs of vertices. The number of vertices and edges is denoted by
v(G) and e(G), respectively. A simple graph is an unweighted, undirected graph
containing no graph loops or multiple edges. Through the paper only simple
finite graphs will be considered, where G is a finite graph if |v(G)| < ∞ and
|e(G)| < ∞. An edge cover of a graph G is a set of edges C ⊆ EG, such that
meets all vertices of G. That is for any v ∈ V , it holds that Ev ∩ C 6= ∅ where Ev
is the set of edges incident to v. The family of edge covers for the graph G wil be
denoted by EG. The problem of computing the cardinality of EG is well known to
be ♯P-complete problem. In [
A subgraph of a graph G is a graph G′ = (V ′, E′) such that V ′ ⊆ V and E′ ⊆ E. If e ∈ E, e can simply be removed from graph G, yielding a subgraph denoted by G\e; this is obviously the graph (V, E − e). Analogously, if v ∈ V , G\v is the graph (V − v, E′) where E′ ⊆ E consists of the edges in E except those incident at v. A spanning subgraph is a subgraph computed by deleting a number of edges while keeping all its vertices covered, that is if S ⊂ E is a subset of E, then a spanning subgraph of G = (V, E) is a graph (V, S ⊆ E) such that for every v ∈ V it holds Ev ∩ S 6= ∅.
A path in a graph is a linear sequence of adjacent vertices, whereas a cycle in
a graph G is a simple graph whose vertices can be arranged in a cyclic sequence in
such a way that two vertices are adjacent if they are consecutive in the sequence,
and are nonadjacent otherwise [
An acyclic graph is a graph that does not contain cycles. The connected acyclic graphs are called trees, and a connected graph is a graph that for any two pair of vertices there exists a path connecting them. The number of connected components of a graph G is denoted by c(G). It is not difficult to infer that in a tree there is a unique path connecting any two pair of vertices. Let T (v) be a tree T with root vertex v. The vertices in a tree with degree equal to one are called leaves. 2.1
A cycle basis is a minimal set of basic cycles such that any cycle can be written
as the sum of the cycles in the basis [
In this paper we define basic graphs or non-intersecting cycle graphs as those simple graphs G with dim CG 6= 0 in such a way that any pair of basic cycles are edge disjoints. Let B = {C1, ..., Ck} a basis for the cycle space CG; if Ck = (Vk, Ek) let us define the sequence of intersections of the edge sets {Ei} as Bp =
[ i16=···6=ip [Ei1 ∩ · · · ∩ Eip ] (2.1) for any Ip = {i1, ..., ip} ⊆ {1, ..., k}, it is clear that Ei1 ∩ · · · ∩ Eip = Eiσ(1) ∩ · · · ∩ Eiσ(p) for any permutation σ ∈ Sp; where Sp is the symetric group of permutations. The number of different terms to consider in Equation (2.1) is given by k!/(k − p)!p! which is the number of different combinations of the index set Ip. Thus, we can establish the conditions of whether a graph G has not an intersecting cycle basis. If the graph G is not acyclic and B2 = ∅ then dim G ≥ 1 so G is called a basic graph. Let e ∈ E be an edge and define ne as the maximum integer such that e belongs to as many as ne edge sets Ei. In other words, ne = max{p|Bp 6= ∅}. 2.3
Computing edge covers for simple graphs lies on the idea of splitting a given graph G into acyclic graphs or basic graphs. It will be shown, that calculating edge covers for simple graphs can be reduced to the computation of edge covers for acyclic graphs or basic graphs thus being able to fully compute |EG|. The definition below describes in detail the process of splitting a graph into smaller graphs, which eventually leads to a decomposition of simple graphs into acyclic graphs or basic graphs.
Definition 1. For a given graph G = (V, E), 1. the split at vertex v ∈ V is defined as the graph G ⊣ v = (V ′, E′) where V ′ = (V − {v}) ∪ Sw∈Nv {w′} and E′ = (E − Ev) ∪ Sw∈Nv {ww′} with w′ ∈/ V , 2. the subdivision operation at edge e = uv ∈ E is defined as the graph G⊥e = (V ∪ {z}, (E − e) ∪ {uz, zv}) with z ∈/ V , and z can be written either as uv or vu. 3. If e = uv ∈ E is an edge, G/e will denote the resulting graph after performing the following operation
(((G\e)⊥S)⊣ u)⊣ v where S = Eu ∪ Ev − {e}. The subdivide operation (G\e)⊥S means tacitly (· · · ((G\e)⊥f )⊥g · · · )) where f, g, ... ∈ S.
Above definition can be easily extended to subsets V ′ = {v1, ..., vr} ⊆ V , E′ = {e1, ..., es} ⊂ E, that is G ⊣ V ′ = (· · · ((G ⊣ v1) ⊣ v2) · · · ) ⊣ vr; analogously, G⊥E′ = (· · · ((G⊥e1)⊥e2) · · · )⊥es. It must be noted, that the order on which the operations to obtain G/e are performed is unimportant as long as one keeps track of the labels used during the process.
Example 1. Consider the star graph W4, therefore 3• 2• 1• • v W4⊣v If H, Q are graphs not necessarily edge or vertex disjoint we define a formal union of H and Q as the graph H ⊔ Q by properly relabelling VH and VQ; this can be accomplished by defining VH⊔Q = {(u, 1)|u ∈ H} ∪ {(u, 2)|u ∈ Q}. The edge set EH⊔Q could be defined as follows: if a, b ∈ VH⊔Q such that a = (u, i), b = (v, j) for some i, j ∈ {1, 2} and u, v ∈ VH ∪ VQ then ab ∈ EH⊔Q if and only if uv ∈ EH ∪ EQ and i = j. Others labelling systems might work out just fine, as long as they respect the integrity of graphs H and Q. To recover the original graphs, we define the projections πX , as πH (H ⊔ Q) = H and πQ(H ⊔ Q) = Q; that is the projections πX revert the relabelling process to the original for both graphs H and Q.
Definition 2. Let G = (V, E) be a simple graph. Let us define the split operator ⊔e as (i) the graph ⊔eG = G\e ⊔ G/e, that is the graph G splits into the graph G\e and the graph G/e if e ∈ E. If e ∈/ E then ⊔eG = πG(G\e ⊔ G/e) = πG(G ⊔ G) = G. (ii) if H, Q are arbitrary graphs then ⊔e(H⊔Q) = ⊔eH⊔⊔eQ with e ∈ EH ∪EQ. Example 2. Figure (2) shows an example of how a simple graph can be decomposed into acyclic graphs. 2.4
The following lemma and propositions summarizes the main properties of the split operator ⊔e, necessary for the calculation of the edge covering sets for simple graphs. The first result is regarding the dimension of the cycle spaces CG/e and CG for an edge e in the cotree of G. The proposition is rather simple in the sense that the resulting graph after applying G/e its dimension must diminishes certain amount which allow us to conclude that the operator ⊔ will split the graph G into non-intersecting cyclic graph.
Proposition 21 Let G be a simple graph, B a fundamental cycle base, e = uv ∈ T an edge in the cotree of G. If be = |Bu ∪ Bv| where Bu = {C ∈ B|u ∈ C} and Bv = {C ∈ B|v ∈ C} then 1. If e ∈ T¯ then be + dim CG/e = dim CG. 2. If e ∈ T we have that (G/e)\hG/ei ⊂ T¯. • G10 •
• • 1• •5
•G11• • • • • • • • •
• 3• 2• • • • • G21 •
• • • • • • • • G20 •
• •
• •G30 •
• • • • • G31 •
• • •
• Proof. Every fundamental cycle containing either u or v must disappear under the operation G/e then those edges in T that do not contain u or v are the only ones that contribute to the dimension of the graph G/e, therefore dim CG/e = dim CG − be.
The proposition above allow us to explicitly calculate the number of connected components into which the graph G/e is being decomposed, on the other hand is providing a rather efficient way of testing whether or not G/e is a nonintersecting cyclic graph. The lemma below assumes that the graph in consideration is not connected, that is G has multiple conected components, thus we must consider an spanning forest for G instead of its spanning tree. Lemma 1. Let G = (V, E) be a simple graph, F , F are an spanning forest and its corresponding coforest for G, respectively; let us choose an edge e = uv ∈ EG and consider the split ⊔eG of G. If ae = |(Eu ∪ Ev) ∩ F | then (i) If e ∈ F then c(G\e) = c(G) and c(G/e) = c(G)+dF (u)+dF (v)+ae−be−3. (ii) It holds that dim CG\e = dim CG − 1 and dim CG/e < dim CG. (iii) There exists a bijective map ε : E⊔eG → EG. That is, if S is an edge covering set for G\e or G/e then ε(S) is an edge covering set for G, which is equivalent to EG = EG\e ∪ ε(EG/e). Thus, |EG| = |EG\e| + |EG/e|. The family EG\e accounts for those edge covering sets S for G on which e ∈/ S whereas EG/e stands for those edge covering sets where e is always a member.
Let S ⊆ E be a subset of edges, from Definiton (2)(i) the split of G along S, denoted by ⊔SG, is recursively defined in terms of the sequence of splits Gij = ⊔ei G(i−1)j = G(i−1)j \ei ⊔ G(i−1)j /ei, i ∈ {1, ..., |S|} in particular for i = 1 we define G11 = G00\e1 ⊔ G00/e1 where G00 = G. By setting φ(i) = 2i−1 − 1 and for 0 ≤ j ≤ φ(i) we have therefore, ⊔S G = G|S| = h G|S|j
i =
G (2.2) To short up the notation, we make Gt∗j = G(t−1)j ∗ et, Etj = EGtj and Et∗j = EG(t−1)j∗et = E ∗ with ∗ ∈ {\, /}; under this notation we have that Gtj =
Gtj Gt\j ⊔ Gtj . In general, the graph Gtj is disconnected, if we denote by Gtjs its / connected components then Etjs will denote the family of edge covering sets for each graph Gtj . For any given spanning tree T for a simple graph G, let us make t = |T | = dim CG, Hj = ` Etjs for some set Stj ⊆ N, where ` denotes s∈Stj the cartesian product and the projections will be denoted by πsj , for every s, j. Every edge covering set of a graph G induces a subgraph; if S ⊆ EQ by definition S meets all vertices of G then the induce graph of S becomes (VG, S). For the rest of the paper the family of edge covering sets, like Eijs will also denote the family of induced graphs by this sets. Therefore, the calculation of edge cover for a graph G is equivalent to calculate the induced graphs by edge covering sets, since most of the operations to be performed are graph operation like vertex splitting and edge subdivision.
Theorem 1. Let G be a finite, connected simple graph, T an spanning tree for G and T denotes its cotree and t = |T | then (i) the family {Gt\j, Gt/j}, appearing in the expansion ⊔T G, are all acyclic graphs or non-intersecting cycle graphs for all j satisfying 0 ≤ j ≤ φ(t). (ii) If Gt∗js denotes the connected components of Gt∗j , then Gt∗js are edge and vertex disjoint for every j, and Gt∗j = L Gt∗js for some set of indices s∈Stj
Stj ∈ N. (iii) For every j, 0 ≤ j ≤ φ(t) there exist bijections εt : Sj Etj −→ Et, εtj : Etj −→ E(t−1)j such that E(t−1)j = E(t−1)j ∪ εtj[E(/t−1)j] and therefore Et = \ εth Sj Etji. (iv) Let H = (H1, ..., H|St|j) ∈ Hj be a vector of graphs of the cartesian product of family Etjs of induced graphs by edge covering sets, then Etj = SH∈Hj [Ls∈Stj πjs(H)] and
Et = εt [
[ h M πjs(Hj )i . 0≤j≤φ(t) Hj∈Hj s∈Stj For every q, 1 ≤ q ≤ t, there exist bijections εq in such a way that if ε = ε1 ◦ · · · ◦ εq then EG = ε(Et) and
Eq −ε→q Eq−1 ε−q→−1 · · · −ε→2 E1 −ε→1 EG |EG| = X |Etj| = X h Y |Etjs|i.
j j s∈Stj (2.3) (2.4) 3
The algorithm for counting edge covers is based on the reduction Definiton (1). The operation of computing an spanning forest of a given graph G is denoted by hGi; by abuse of notation hGi also denotes the spanning forest. Its co-forest is therefore F¯ = E − hGi. Algorithm 1 decompose a graph into non-intersecting independent graphs (a forest). 3.1
Let G = (V, E) be the input graph of the algorithm Split, m = |E|, n = |V |. It can be said that the maximum number of intersecting cycles in G is not greater than nc = m − n because, at most, only one cycle is not an intersecting cycle.
The step 3 has time complexity O(nm log m). The step 6 has time complexity O(m + n). The recursive application of the algorithm (steps 9 and 12) generates an enumerative tree EG. This reduction generates two new graphs H = (V1, E1) and Q = (V2, E2) from G.
The time behaviour of the algorithm resides on steps 9 and 12, which corresponds with the number of intersecting cycles on the graph associated with each node of EG. If nc denotes the maximum number of intersecting cycles in a graph associated with a node of EG, then the time complexity of the algorithm can be expressed by the recurrence:
T (nc) = T (nc − 1) + T (nc − 3) (3.1) such recurrence ends when nc = 1.
This recurrence has the characteristic polynomial p(r) = r3 − r2 − 1 which has the maximum real root r ≈ 1.46557. This leads to a worst-case upper bound of O(r(m−n) ∗ (m + n)) ≈ O(1.465571(m−n) ∗ (m + n)). We believe that it is the first non trivial upper bound obtained for the #Edge Covers problem.
Sound algorithms have been presented to compute the number of edge covers for
graphs. It has been shown that if a graph G has simple topologies: paths, trees
or only independent cycles appear in the graph; then the number of edge covers
can be computed in polynomial time over the graph size.
Algorithm 1 Procedure that decompose a graph G into ⊔G compose of basic
or acyclic graphs.
1: procedure Split(G) {Decomposition of G into basic or acyclic graphs}
2: Input: G = (V, E)
3: Output: ⊔S G
4: Select an edge e = uv ∈ E such that e ∈ Bp(G) 6= ∅ for some p. {Notice that if the
edge e exists can be found in O(nm log m).}
5: if e exists then
6: Calculate ⊔eG = G\e ⊔ G/e by applying the splitting reduction rule over e
generating H and Q
7: end if
8: if B2(H) 6= ∅ then
9: Split(H)
10: end if
11: if B2(Q) 6= ∅ then
12: Split(Q)
13: end if
14: return ⊔S G {S is the set of edges where the splitting proccess is applied. By
Theorem (1)(iv) we have that |EG| = Pj |Etj | and |Etj| can be calculated by the
procedures presented in [
Regarding the cyclic graphs with intersecting cycles, a branch and bound procedure has been presented, it reduces the number of intersecting cycles until basic graphs are produced (subgraphs without intersecting cycles).
Additionally, a pair of recurrence relations have been determined that establish an upper bound on the time to compute the number of edge covers on intersecting cycle graphs. It was also designed a “low-exponential” algorithm for the #Edge Covers problem whose upper bound is O(1.465571(m−n) ∗ (m + n)), m and n being the number of edges and nodes of the input graph, respectively.