Introduction

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 ⊆ E G , such that meets all vertices of G. That is for any v ∈ V , it holds that E v ∩ C = ∅ where E v is the set of edges incident to v. The family of edge covers for the graph G wil be denoted by E G . The problem of computing the cardinality of E G is well known to be ♯P-complete problem. In [4], however, have designed to what they call a fully polynomial time approximation scheme (FPTAS) for counting edge covers of a simple graphs; same authors have extended the technique to tackle the weighted edge cover problem in [3]. In this paper, we study a novel algorithm for counting edge covers taking into account that there exists a time polynomial algorithm for non-intersecting cyclic graphs [2]. Having said that, the technique is basically to reduce a simple graph into a sequence of non-intersecting cyclic graphs. The complexity of the algorithm is also studied. Although, the complexity of our proposed algorithm remains exponential its complexity is comparatively low to the ones reported in the literature.

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 E v ∩ S = ∅.

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 [1]. The length of a path or a cycle is the number of its edges.

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.

The cycle space

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 [5]. The sum of cycles C i is defined as the subgraph C 1 ⊕ • • • ⊕ C k , where the edges are those contained in an odd number of C i 's, i ∈ {1, ..., k} with k ∈ N arbitrary; the sum is again a cycle. The aforementioned sum gives to the set of cycle or cycle space C the structure of a vector space under a given field k. The dimension of the cycle space C is dim k C = |B| where B is a basis for C. In particular, if G is a simple graph the field is taken to be k = F 2 , which is the case concerning this paper. Thus the field F 2 will be used through the entire paper to describe cycle space of graphs. The technique proposed in this paper, assumes that if the graph has cycles, it is always possible to calculate a cycle basis for the cycle space of the graph. The cycle basis to be considered in this paper can easily be constructed by using the well known depth first search algorithm (DFS) [1]. The proccess of getting a spanning tree for G by DFS algorithm will be denoted by G . By using depth first search an spanning tree or forest T = G can be constructed for any graph G. The cycle basis are the unique cycle formed with edges in the cotree T = G\T and edges in T . The dimension of C G is therefore | T |.

Non-intersecting cycle graph or basic graphs

In this paper we define basic graphs or non-intersecting cycle graphs as those simple graphs G with dim C G = 0 in such a way that any pair of basic cycles are edge disjoints. Let B = {C 1 , ..., C k } a basis for the cycle space C G ; if C k = (V k , E k ) let us define the sequence of intersections of the edge sets {E i } as

B p = i1 =••• =ip [E i1 ∩ • • • ∩ E ip ] (2.1)

for any

I p = {i 1 , ..., i p } ⊆ {1, ..., k}, it is clear that E i1 ∩ • • • ∩ E ip = E i σ(1) ∩ • • • ∩ E i σ(p)

for any permutation σ ∈ S p ; where S p 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 I p . 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 B 2 = ∅ then dim G ≥ 1 so G is called a basic graph. Let e ∈ E be an edge and define n e as the maximum integer such that e belongs to as many as n e edge sets E i . In other words, n e = max{p|B p = ∅}.

Splitting a graph into basic graphs

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 |E G |. 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}) ∪ w∈Nv {w ′ } and E ′ = (E − E v ) ∪ w∈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 u v or v u . 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 = E u ∪ E v − {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 ′ = {v 1 , ..., v r } ⊆ V , E ′ = {e 1 , ..., e s } ⊂ E, that is G ⊣ V ′ = (• • • ((G ⊣ v 1 ) ⊣ v 2 ) • • • ) ⊣ v r ; analogously, G⊥E ′ = (• • • ((G⊥e 1 )⊥e 2 ) • • • )⊥e s .

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 W 4 , therefore

• 2 3 1 • v 5 • • • • • 2 3 3 ′ v 1 • • 1 ′ v • • • 5 5 ′ v W4⊣ v • • 3 ′ v • • 2 3 3v 1 • 1v 1 ′ v • • • • 5 5 ′ v (W4⊣ v)⊥{33 ′ ,(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.

Edge covering sets for simple graphs

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 C G/e and C G 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. 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.

2 3 G 00 1 •4 5 • • • • G 10 • • • • • G 20 • • • • • G 30 • • • • • • G 31 • • • • • • G 21 • • • • • • • • • • • G 11 • • • • • • • • • •

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 ∈ E G and consider the split

⊔ e G of G. If a e = |(E u ∪ E v ) ∩ F | then (i) If e ∈ F then c(G\e) = c(G) and c(G/e) = c(G)+d F (u)+d F (v)+a e −b e −3. (ii) It holds that dim C G\e = dim C G − 1 and dim C G/e < dim C G .

(iii) There exists a bijective map ε : E ⊔eG → E G . 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

E G = E G\e ∪ ε(E G/e ). Thus, |E G | = |E G\e | + |E G/e |.

The family E G\e accounts for those edge covering sets S for G on which e / ∈ S whereas E G/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 ⊔ S G, is recursively defined in terms of the sequence of splits G ij = ⊔ ei G (i−1)j = G (i−1)j \e i ⊔ G (i−1)j /e i , i ∈ {1, ..., |S|} in particular for i = 1 we define G 11 = G 00 \e 1 ⊔ G 00 /e 1 where G 00 = G. By setting φ(i) = 2 i−1 − 1 and for 0 ≤ j ≤ φ(i) we have therefore,

⊔ S G = G |S| = 0≤j≤φ(|S|) G |S|j = 0≤j≤φ(|S|) G (|S|−1)j \e |S| ⊔ G (|S|−1)j /e |S|(2.2)

To short up the notation, we make

G * tj = G (t−1)j * e t , E tj = E Gtj and E * tj = E G (t−1)j * et = E G * tj with * ∈ {\, /}; under this notation we have that G tj = G \ tj ⊔ G / tj .

In general, the graph G tj is disconnected, if we denote by G tjs its connected components then E tjs will denote the family of edge covering sets for each graph G tj . For any given spanning tree T for a simple graph G, let us make t = |T | = dim C G , H j = s∈Stj E tjs for some set S tj ⊆ N, where denotes 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 ⊆ E Q by definition S meets all vertices of G then the induce graph of S becomes (V G , S). For the rest of the paper the family of edge covering sets, like E ijs 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. (iii) For every j, 0 ≤ j ≤ φ(t) there exist bijections ε t : j E tj −→ E t , ε tj : π js (H j ) .

E tj −→ E (t−1)j such that E (t−1)j = E \ (t−1)j ∪ ε tj [E / (t−

For every q, 1 ≤ q ≤ t, there exist bijections ε q

E q εq −→ E q−1 εq−1 −→ • • • ε2 −→ E 1 ε1 −→ E G (2.3) in such a way that if ε = ε 1 • • • • • ε q then E G = ε(E t )

and

|E G | = j |E tj | = j s∈Stj |E tjs | . (2.4)

3 The splitting algorithm

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 G ; by abuse of notation G also denotes the spanning forest. Its co-forest is therefore F = E − G . Algorithm 1 decompose a graph into non-intersecting independent graphs (a forest).

Time Complexity of the splitting Algorithm

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 E G . This reduction generates two new graphs H

= (V 1 , E 1 ) and Q = (V 2 , E 2 ) 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 E G . If nc denotes the maximum number of intersecting cycles in a graph associated with a node of E G , 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) = r 3 − r 2 − 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.

Conclusions

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. Split(H) 10: end if 11: if B2(Q) = ∅ then 12:

Split(Q) 13: end if 14: return ⊔SG {S is the set of edges where the splitting proccess is applied. By Theorem (1)(iv) we have that |EG| = j |Etj | and |Etj| can be calculated by the procedures presented in [2] for basic and acyclic graphs.}

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.