N Bourgeois
email: bourgeois@lamsade.dauphine.fr

B Escoffier
email: escoffier@lamsade.dauphine.fr

V Th

Paschos
email: paschos@lamsade.dauphine.fr

Efficient approximation by "low-complexity" exponential algorithms

This paper proposes a way to bring together two seemingly "foreign" domains that are the polynomial approximation and the exact computation for NP-hard problems. We show how one can match ideas from both areas in order to design approximation algorithms achieving ratios unachievable in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower (though super-polynomial) than that of an exact computation. We then apply these ideas to two famous combinatorial optimization problems, namely, the max independent set and the min vertex cover, as well as to some other problems mainly linked to max independent set by simple approximation preserving reductions.

Introduction

The two most known paradigms to come up with NP-hard problems are either the exact computation (i.e., the computation of optimal solutions for them), or the heuristic resolution, i.e., the development of fast algorithms that compute hopefully near-optimal solutions. Notable part of the heuristic paradigm is the so-called polynomial approximation where one tries to devise polynomial algorithms for NP-hard problems computing feasible solutions that are close to optimal under an a priori criterion called approximation ratio.

Both exact computation and polynomial optimization are very active areas in theoretical computer science and combinatorial optimization. Dealing with the former, very active research has been conducted around the development of optimal algorithms with non-trivial worst-case complexity. As an example, let us consider max independent set. Any optimal algorithm can solve it with complexity O * (2 n ) (where O * (•) is as O(•) ignoring polynomial factors), where n is the order of G (i.e, the cardinality of V ) by exhaustively examining all the subsets in 2 V and by taking the largest among them that forms an independent set; hence, an interesting question is if we can compute a maximum independent set with complexity O * (γ n ), for γ < 2. More about such issues for several combinatorial problems can be found in the seminal paper by [START_REF] Woeginger | Exact algorithms for NP-hard problems: a survey[END_REF]. This area has known a renew of the researcher's interest due to numerous pessimistic results in polynomial approximation, but also due to the fantastic increase of the computational power of modern computers.

On the other hand, dealing with polynomial approximation, very intensive research since the beginnings of 70's has lead to numerous results exhibiting possibilities but also limits to the approximability of NP-hard problems. Such limits are expressed as statements that a given problem cannot be approximated within a certain approximation level (for instance, within a constant approximation ratio) unless a very unlikely complexity condition (e.g., P = NP) holds. A very rich landscape of the polynomial approximation area can be found in [START_REF] Ausiello | Complexity and approximation[END_REF][START_REF] Hochbaum | Approximation algorithms for NP-hard problems[END_REF][START_REF] Vazirani | Approximation algorithms[END_REF]. Since the beginning of 90's, and using the celebrated PCP theorem ( [START_REF] Arora | Proof verification and intractability of approximation problems[END_REF]), numerous natural hard optimization problems are proved to admit more or less pessimistic inapproximability results. For instance, max independent set is inapproximable within approximation ratio better than n ǫ-1 , unless P = NP ( [START_REF] Håstad | Clique is hard to approximate within n 1-ǫ[END_REF]).

These two areas has remained foreign until now. Researchers in any of them produced results fitting the corresponding paradigm and without links with the other one. Staring point of this work is the idea that both of them can be linked by mutual exchanges of tools and concepts, in order that new results and ideas are established handling solution mechanisms of NP-hard problems. For instance, it is interesting to efficiently approximate such problems by devising algorithms that achieve approximation ratios that cannot be achieved in polynomial time, with a worst-case complexity that is significantly lower (though super-polynomial) than the complexity of a exact computation. This issue is called efficient approximation in what follows.

Preliminaries

An optimization problem Π is in NPO if the decision version of Π is in NP. Formally, an NP optimization problem Π is defined as a four-tuple (I, sol, m, opt) such that: I is the set of instances of Π and it can be recognized in polynomial time; given x ∈ I, sol(x) denotes the set of feasible solutions of x; for every y ∈ sol(x), |y| is polynomial in |x|; given any x and any y whose length is polynomial in |x|, one can decide in polynomial time if y ∈ sol(x); given x ∈ I and y ∈ sol(x), m(x, y) denotes the value of y for x; m is polynomially computable and is commonly called feasible value, or objective value; finally, opt ∈ {max, min} denotes the optimization goal for Π. The set of NP optimization problems forms the class NPO. Given an instance x of an NPO problem Π = (I, sol, m, opt), and a feasible solution y for x, we denote by opt(x) the value of an optimal solution of x.

For an approximation algorithm A computing a feasible solution y for x with value m A (x, y), its approximation ratio on y is defined as ρ A Π (x, y) = m A (x, y)/ opt(x). The approximation ratio ρ A Π of A is then defined as the worst 1 over any instance x ∈ I, of ρ A Π (x, y). In what follows, whenever it is understood, references to problem Π and/or A will be dropped.

Polynomial approximation is a very active area since the beginning of the 70's. The celebrated paper by [START_REF] Johnson | Approximation algorithms for combinatorial problems[END_REF] is considered as the startpoint of this research programme that has dominated a large part of the research conducted in complexity theory. On the other hand, exact solution of combinatorial problems is a natural requirement for these problems that remains in the heart of the research in combinatorial optimization and in operational research more generally. These two approaches are complementary in the sense that, informally, the former gives priority to fast computation of feasible solutions against optimality, while, for the latter, priority is given to solutions' optimality against speed of such computation.

If the area of exact computation is in the heart of combinatorial optimization since the beginnings of this domain, the main concerns of a large majority of its researchers were rather about the design of clever solution algorithms (mainly based upon tree-search procedures, dynamic programming, etc.) than the precise estimation of their running-time. Before the middle of 90's, when a broad research programme around such concerns has been built, fairly little research has been dedicated to this issue. On the other hand, numerous open questions, posed since the beginnings of polynomial approximation, as for example, the approximation of max independent set 2 within constant ratio, have received strongly negative answers at the beginnings of 90's with the proof of the famous PCP theorem (carrying over a novel and fine characterization of NP, [START_REF] Arora | Proof verification and intractability of approximation problems[END_REF]). Similar answers, known as inapproximability or negative results in polynomial approximation theory, have been provided for numerous other paradigmatic optimization problems, as min set cover, min vertex cover3 , min coloring, etc. ratio polynomial algorithms algorithms

n ǫ-1 exact 1 (??)
Figure 1: The approximability gap for max independent set. These results exhibit large gaps between what it is possible to do in polynomial time and what becomes possible in exponential time. Let us take, once again, the case of max independent set. It is proved in [START_REF] Håstad | Clique is hard to approximate within n 1-ǫ[END_REF] that this problem is inapproximable within ratio better than O(n ǫ-1 ), unless P = NP (note that any approximation algorithm trivially achieves approximation ratio O(n) in polynomial time). We so are faced with a huge gap impossible to be bridged in polynomial time (Figure 1).

Hence, a natural question is how much time takes the computation of an r-approximate solution, for r ∈ [n ǫ-1 , 1[? Of course, we have a lower bound to this time (any polynomial to the size of the instance) and also an upper bound (the running time of exact computation). But:

• can we devise, for some ratio r, an r-approximate algorithm with an improved running time located somewhere between these bounds?

• is this possible for any ratio r, i.e., can we specify a global relationship between running time and approximation ratio?

In this paper, we try to bring answers to these questions by matching ideas and results from exact computation (mainly dealing with improved worst-case complexities of optimal algorithms for the problems handled) and from polynomial approximation (mainly around approximation preserving reductions). This issue has been also handled very recently by [START_REF] Cai | Fixed-parameter approximation: conceptual framework and approximability results[END_REF][START_REF] Chen | On parameterized approximability[END_REF][START_REF] Downey | Parameterized approximation problems[END_REF], though in a different setting and with different objectives oriented towards development of fixed-parameter algorithms.

Note finally that tradeoffs between approximation ratio and running time have already been studied for polynomially solvable problems (but with practically long running times) such as maximum matching.

In what follows, in Section 3, we give some easy examples of approximation algorithms for max independent set that is the pivot problem of this paper. The algorithms given can achieve ratios impossible to be polynomially achieved with non-trivial super-polynomial or exponential worst-case complexity.

In Section 4, we give efficient approximation results of a broad class of maximization graphproblems where their solutions are subgraphs of the input-graph that satisfy some non-trivial hereditary property 4 .

In Section 5 we develop efficient non-polynomial approximation algorithms for another paradigmatic problem in combinatorial optimization, the min vertex cover. Results in these two sections are obtained by a basic technique consisting of optimally solving the problems handled in subgraphs of the input graph obtained by partition of its vertices.

In Section 6, we propose randomized approaches that improve complexity results obtained in Sections 4 (in particular for the case of max independent set) and 5.

In Section 7, we consider specific classes of graphs where max independent set is polynomially approximable. We show there how approximation algorithms for max independent set can be improved in order to guarantee any approximation ratio with low exponential complexity. The method presented in this section is somewhat complementary to the one in Sections 4 and 5.

Here, we partition the input-graph into two subgraphs and we apply an exhaustive search to one of them and an approximation algorithm in the other one.

Finally, in Section 8, we present approximation results for other combinatorial problems linked to max independent set by simple approximation-preserving reductions. In particular, for one of the problems handled in this section that is max clique, we also produce an exact computation parametric result that is interesting per se.

Note that the algorithms devised in Sections 4 to 8 use as subroutines exact algorithms for computing optimal solutions of hard problems. In this sense, the major part of these results can be seen as reductions from approximate computation to exact computation on "small" instances. In particular, any improvement of the running times of exact algorithms for the problems handled, would immediately result in improvements of running times of our approximation algorithms. Besides, this is one of the reasons for which we study sometimes several algorithms whose complexity depends on several parameters.

Before closing this section we give some notations that will be used later. Let T (•) be a super-polynomial and p(•) be a polynomial, both on integers. In what follows, using notations in [START_REF] Woeginger | Exact algorithms for NP-hard problems: a survey[END_REF], for an integer n, we express running-time bounds of the form p(n) • T (n) as O * (T (n)) by ignoring, for simplicity, polynomial factors. We denote by T (n) the worst-case time required to solve the considered combinatorial optimization problem with n variables. We recall (see, for instance, [START_REF] Eppstein | Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction[END_REF]) that, if it is possible to bound above T (n) by a recurrence expression of the type T (n)

T (n -r i ) + O(p(n)), we have T (n -r i ) + O(p(n)) = O * (α(r 1 , r 2 , . . .) n ) where α(r 1 , r 2 , . . .) is the largest zero of the function f (x) = 1 -x -r i .
Given a graph G(V, E), we denote by n the size of V , by α(G) the size of a maximum independent set of G and by τ (G) the size of a minimum vertex cover of G. Also, we denote by ∆(G) the maximum degree of G. Given a subset V ′ of V , G[V ′ ] denotes the subgraph of G induced by V ′ . Sometimes, for a graph G, we denote by V (G) its vertex-set.

3 Simple efficient approximation results for max independent set 3.1 Generating a "small" number of candidate solutions Consider a graph G(V, E) of order n and run the following algorithm:

• generate all the √ n-subsets (subsets of cardinality √ n) of V ;

• if one of them is independent, then output it;

• otherwise output a vertex at random.

It is easy to see that the approximation ratio of this algorithm is n -1/2 . Indeed, if algorithm's output is done at the second item, i.e., an independent set of size √ n is discovered, then, since α(G) n, the approximation ratio achieved is at least √ n/n = n -1/2 . On the other hand, if no independent set is found at the second step, then α(G) √ n and the approximation ratio guaranteed in third step is at least 1/ √ n = n -1/2 , impossible for polynomial algorithms according to [START_REF] Håstad | Clique is hard to approximate within n 1-ǫ[END_REF]. The complexity of the algorithm above is roughly bounded above by

O * ( n √ n ) = O * (2 √ n log n ),
much lower than the best known exact complexity for max independent set that is O * (1.18 n ) due to [START_REF] Robson | Finding a maximum independent set in time O(2 n/4 )[END_REF].

Approximating by pruning the search tree

The most common tool used to devise exponential algorithm with non-trivial worst case complexity consists of pruning the search tree ( [START_REF] Woeginger | Exact algorithms for NP-hard problems: a survey[END_REF]). We show in this section that pruning can be properly adapted to devise approximation algorithms with improved worst-case complexity. The running times that we obtain via this method are worse than the ones obtained in the next sections. But our goal here is to illustrate on a simple example how to approximate by pruning. Consider a simple search tree-based algorithm for solving max independent set, which consists of recursively applying the following rule (see for instance [START_REF] Woeginger | Exact algorithms for NP-hard problems: a survey[END_REF]):

1. if ∆(G) 2, then output a maximum independent set; 2. else, branch on a vertex v with degree at least 3 as follows:

(a) either take v and solve max independent set in the subgraph surviving after the removal of v and its neighbors;

(b) or do not take v, and solve max independent set in the subgraph surviving after the removal of v.

Step 1 can be done in polynomial time. On the other hand, when branching, we have to solve a subproblem of size either n -∆(v) -1 n -4, or n -1. This leads to a running time T (n) T (n-1)+T (n-4)+p(n), for some polynomial p, which comes up to T (n) O * (1.381 n ).

We now explain how one can get a 1/2-approximation algorithm based on the above algorithm, with running time much better than O * (1.381 n ). The idea is that, when a branching occurs, in case 2a both our algorithm and an optimum solution take v. In this case, if we only seek a 1/2-approximate solution, then roughly speaking, the algorithm can make an error on another vertex (not taking it in the solution while an optimal solution takes it). Indeed, vertex v taken in both solutions compensates this error. So, when applying the branching, in case 2a we can remove any other vertex of the graph. We then get a subproblem of size n -5 instead of n -4. More generally, consider an edge (v i , v j ) in the surviving graph (or even a clique K). Since an optimal solution can take at most one vertex of a clique, then when branching in case 2a, we can remove vertices v i and v j (resp., the whole clique K).

A second improvement deals with step 1. Indeed, we do not need to deal with cases where the optimum can be polynomially reached, but with cases where a 1/2-approximate solution can be found in polynomial time. For instance, max independent set can be approximately solved in polynomial time within approximation ratio (∆(G) + 3)/5 [START_REF] Berman | On the approximation properties of independent set problem in degree 3 graphs[END_REF]. Hence, if ∆(G) 7, then max independent set is 1/2-approximable in G. This leads to the following algorithm:

1. if ∆(G) 7, then run the algorithm by [START_REF] Berman | On the approximation properties of independent set problem in degree 3 graphs[END_REF];

2. else, branch on a vertex v with degree at least 8 as follows:

(a) either take v, and solve max independent set in the subgraph surviving after the removal of v, of its neighbors and and of two other adjacent vertices v i , v j ;

(b) or do not take v, and solve the problem in the subgraph surviving after the removal of v.

It is easy to recursively verify that the algorithm above guarantees an approximation ratio 1/2. Concerning its running time, during step 2a we remove 11 vertices (note that if there is no edge (v i , v j ) to be removed, the surviving graph is an independent set per se); hence, T (n)

T (n -1) + T (n -11) + p(n). This leads to T (n) = O * (1.185 n ).
Note that the above algorithm can be generalized to find a 1/k-approximation algorithm (for any integer k) in time T (n) T (n-1)+T (n-7k +3)+p(n). Obviously, improved running times would follow from considering, for example, either modifications of algorithms more sophisticated than the one presented in this section, or a more efficient counting technique such as the one presented in [START_REF] Fomin | Measure and conquer: domination -a case study[END_REF]. However, up to now, the techniques presented in next sections give better results.

Maximum induced subgraph problems with property π

We handle in this section a large class of graph-problems that is defined as follows: given a graph G(V, E) and some hereditary property π, find a subset V ′ ⊆ V , of maximum size, such that the subgraph of G induced by V ′ satisfies the property π. For a fixed property π we denote by max hereditary-π the particular NPO problem resulting when considering π. For instance, if π is "independent set", then max hereditary-"independent set" is exactly max independent set.

The idea of the method proposed consists in splitting the instance into several subinstances (of much smaller size) and in solving the problem on these subinstances using an exact algorithm. The ratio obtained is directly related to the size of the subinstances, hence to the global running time of the algorithm.

Proposition 1. Fix a hereditary property π and assume that there exists an exact algorithm A for max hereditary-π with worst-case complexity O * (γ n ) for some γ ∈ R, where n is the order of the input-graph, for max hereditary-π. Then for any ρ ∈ Q, ρ 1, there exists a ρ-approximation algorithm for max hereditary-π that runs in time O * (γ ρn ).

Proof. Consider a graph G of order n and fix a rational ρ 1. Since ρ ∈ Q, it can be written as ρ = p/q, p, q ∈ N, p q.

Consider now the following algorithm, called with parameters G and ρ:

1. arbitrarily partition G into q induced subgraphs G 1 , . . . , G q of order (except eventually for G q ) n/q;

2. build the q subgraphs G ′ 1 , . . . G ′ q that are unions of p consecutive subgraphs G i+1 , . . . , G i+p , i = 1, . . . , q (where of course G q+1 = G 1 ); 3. optimally solve max hereditary-π in every G ′ i , i = 1, . . . , q;

4. output the best of the solutions computed in step 3.

Denote by S the solution output by the algorithm and fix an optimal solution S * of G (following notations in Section 2,

|S * | = opt(G)). Then, |S| (p/q) opt(G) = ρ opt(G). Indeed, let S * i = S * ∩ G i . Then, by heredity, |S * i+1 | + |S * i+2 | + . . . + |S * i+p | opt(G ′ i ) |S|. Summing up for i = 1, 2, . . . , q, we get: p|S * | = p q i=1 |S * i | q|S|, that proves the approximation ratio claimed.
It is easy to see that the above algorithm involves q executions of A (the exact algorithm for max hereditary-π) on graphs of order roughly pn/q = ρn. Hence, its complexity is of O * (γ ρn ), that proves the running time claimed and the proposition.

Obviously, Proposition 1 holds for several hereditary properties as "independent set", "clique", "planar graph", "bipartite graph", etc.

Let us now focus on the most notorious among these properties that is "independent set". Denote by IS the instantiation of the algorithm above to "independent set" and assume that it is parameterized by two parameters: the input-graph G and the ratio ρ to be achieved. For the rest of the paper assume that there exists an exact algorithm for max independent set with worst-case running time O * (γ n ) (to the best of our knowledge, the best γ currently known for general graphs is 1.18 due to [START_REF] Robson | Finding a maximum independent set in time O(2 n/4 )[END_REF]). We then have the following immediate corollary.

Corollary 1. For any ρ 1, Algorithm IS(G, ρ) computes a ρ-approximation of max independent set with running time O * (γ ρn ).

From Proposition 1 we can note the following two interesting facts:

1. the algorithm of Proposition 1 can be implemented to use polynomial space provided that the exact algorithms used do so;

2. any improvement to the basis γ of the exponential for the running time of the exact algorithm for max hereditary-π is immediately transferred to Proposition 1.

Note also that the result of Corollary 1 slightly improves the result in Section 3.1 for ρ = √ n, as well as the result in Section 3.2 (dealing with pruning the search tree) for ρ = 1/2.

Efficient approximations for min vertex cover

There exists a very close and well-known relation between a vertex cover and an independent set in a graph G(V, E) ( [START_REF] Berge | Graphs and hypergraphs[END_REF]): if S is an independent set of G, then the set V \ S is a vertex cover of G. The same complementarity relation holds obviously for a maximum independent set S * and the set C * = V \ S * that is a minimum vertex cover of G. min vertex cover is approximable within approximation ratio 2 and one of the most known open problems in polynomial approximation is either to improve this ratio, or to prove that such an improvement is impossible until a strong unlikely complexity condition (e.g., P = NP) holds. A recent result by [START_REF] Khot | Vertex cover might be hard to approximate to within 2ε[END_REF] gives a strong evidence that the latter alternative might be true.

On the other hand, from an exact computation point of view, the relation between min vertex cover and max independent set has as immediate corollary that an optimal vertex cover can be determined in O * (γ n ). Furthermore, the following parameterized complexity result is proved by [START_REF] Chen | Vertex cover: further observations and further improvements[END_REF].

Theorem 1. ( [START_REF] Chen | Vertex cover: further observations and further improvements[END_REF]) For any k n, there exists an algorithm that determines if a graph G contains a vertex cover of size k or not and, if yes, it computes it with complexity O * (δ k ). The currently best δ known for general graphs is equal to 1.28.

We now recall the seminal result by [START_REF] Nemhauser | Vertex packings: structural properties and algorithms[END_REF] characterizing the polytope of max independent set (or, equivalently, of min vertex cover). Before, for readability, let us recall the integer linear program of max independent set (denoted also by is) as well as the mathematical program of its linear programming relaxation (LP-relaxation), denoted by max independent set-r. Given a graph G, denoting by A its incidence matrix:

max independent set =    max 1 • x A x 1 x ∈ {0, 1} n max independent set-r =    max 1 • x A x 1 x ∈ (Q n ) +
Obviously, solution of max independent set-r can be done in polynomial time.

Theorem 2. ( [START_REF] Nemhauser | Vertex packings: structural properties and algorithms[END_REF]) The basic optimal solution of the LP-relaxation of max independent set is semi-integral, i.e., it assigns to the variables values from {0, 1, 1/2}. Let V 0 , V 1 and V 1/2 be the subsets of V associated with 0, 1 et 1/2, respectively. There exists a maximum independent set

S * such that V 1 ⊆ S * and V 0 ⊆ C * = V \ S * .
Obviously, Theorem 2 identically holds for min vertex cover also.

Corollary 2. α(G[V 1/2 ]) |V 1/2 |/2, τ (G[V 1/2 ]) |V 1/2 |/2.
Also, denoting by S ′ and C ′ an independent set and a vertex cover of

G[V 1/2 ], S = V 1 ∪ S ′ is an independent set of G and C = V \ S = V 0 ∪ C ′ is a vertex cover of G.
The following lemma that links approximabilities of max independent set and min vertex cover will be extensively used in what follows.

Lemma 1. If max independent set is approximable within approximation ratio ρ, then min vertex cover is approximable within ratio 2ρ.

Proof. Let A be an max independent set-algorithm computing an independent set S guaranteeing |S| ρα(G) for some ρ < 1. Run the following algorithm for min vertex cover:

1. solve the LP-relaxation of max independent set in G to produce sets V 0 , V 1 and V 1/2 ; 2. run A in G[V 1/2 ]; 3. return C = V 0 ∪ (V 1/2 \ A(G[V 1/2 ]). By Corollary 2, V 1 ∪ A(G[V 1/2 ]) is an independent set of G and C = V \ (V 1 ∪ A(G[V 1/2 ])) = V 0 ∪ (V 1/2 \ A(G[V 1/2 ]
)) is a vertex cover. Then, the approximation ratio of C is:

|C| τ (G) = |V 0 | + V 1/2 \ A G V 1/2 |V 0 | + τ G V 1/2 V 1/2 \ A G V 1/2 τ G V 1/2 (1) V 1/2 -A G V 1/2 V 1/2 -α G V 1/2 V 1/2 -ρα G V 1/2 V 1/2 -α G V 1/2 = 1 + 1 -ρ |V1/2| α(G[V 1/2]) -1 (2) According to Corollary 2, |V 1/2 |/α(G[V 1/2 ]) 2.
Putting this together with (2), we get, after some easy algebra: |C|/τ (G) 2ρ, q.e.d.

Let us note that, as it can be immediately seen from ( 1), when tackling approximation of max independent set and of min vertex cover, we can restrict ourselves to subgraph

G[V 1/2 ], instead of the whole G. By Corollary 2, α(G[V 1/2 ]) |V 1/2 |/2 and τ (G[V 1/2 ]) |V 1/2 |/2.
According to Corollary 2 and Lemma 1, min vertex cover can be approximately solved by the following algorithm called VC1:

1. solve the LP-relaxation of max independent set to obtain sets V 1 , V 0 and V 1/2 (this step runs in polynomial time);

2. set G = G[V 1/2
] and run IS(G, ρ);

3. output V \ (V 1 ∪ IS(G, ρ)).
Combination of Corollary 1 and Lemma 1, immediately derives the following result.

Theorem 3 . For any ρ 1, Algorithm VC1(ρ, G) computes a 2ρ-approximation of min vertex cover with running time O * (γ ρn ).

In other words, any approximation ratio r ∈ [1, 2[ for min vertex cover can be attained by Algorithm VC1, with complexity O * (γ

(2-r)n ).
In what follows in this section, we first improve the result of Theorem 3, by showing that ratio r > 1 for min vertex cover can be achieved with lower worst case complexity (function of n). Next, we give a parameterized approximation result analogous to the one of Theorem 1.

Improving running time for min vertex cover's approximation

Our goal in this section is to improve Theorem 3, i.e., to show how we can get approximation ratio ρ, for every ρ > 1, in time smaller than O * (γ (2-ρ)n ).

For this, we propose a method based upon a tradeoff between the exact algorithm in O * (γ n ) for max independent set and the fixed-parameter algorithm in O * (δ k ) for min vertex cover. Indeed, if τ (G) is small, then of course the latter algorithm is fast (see Lemma 3). On the other hand, if τ (G) is large, then the result of Theorem 3 can be further improved (see Lemma 2).

Recall that, in the sequel, we suppose that we work on graph

G[V 1/2 ]. For simplicity we use V instead of V 1/2 and G instead of G[V 1/2 ].
Lemma 2. If, for some λ < 1/2, α(G) λn, then a ρ-approximation for min vertex cover can be found in O * (γ (ρ-(ρ-1)/λ)n ).

Proof. Note first that, if λ < 1/2, then ρ -((ρ -1)/λ) < 2 -ρ.
Fix a ratio ρ to be achieved for min vertex cover and denote by α ′ (G) the cardinality of some independent set of G. From (2), setting

r = α ′ (G)/α(G), τ ′ (G)/τ (G) (1 -rλ)/(1 -λ).
So, a ratio ρ for min vertex cover can be achieved for some r verifying:

ρ = 1 -rλ 1 -λ =⇒ r = ρ - ρ -1 λ λ<1/2 < 2 -ρ (3)
We distinguish two cases depending on the sign of r, namely r 0 and r > 0.

If r 0, then λ (ρ -1)/ρ. In this case, the whole vertex-set of the input-graph is a vertex cover per se guaranteeing approximation ratio ρ. Indeed, apply (2) with r = α ′ (G)/α(G) = 0 and remark that it is increasing with λ = α(G)/n. Some very easy algebra shows that V guarantees by itself an approximation ratio ρ for min vertex cover.

Assume now that r 0. Take V \ IS(G, r), with r = ρ -((ρ -1)/λ), as min vertex coversolution. By Corollary 1, this can be done with complexity

O * (γ rn ) = O * (γ (ρ-(ρ-1/λ))n ) < O * (γ (2-ρ)n
) and, from (3), it guarantees ratio ρ. Lemma 3. If, for some λ < 1/2, α(G) λn, then a ρ-approximation of min vertex cover can be found in O * (δ (2-ρ)(1-λ)n ).

Proof. Fix a ρ > 1, set p/q = 2ρ, denote by OPT_VC(G, k) the algorithm of Theorem 1 and run the following algorithm denoted by PROCEDURE_VC(G, ρ):

1. partition G(V, E) into q induced subgraphs G 1 , . . . , G q of order n/q (except eventually for G q ); 2. build subgraphs G ′ 1 , . . . G ′ q that are the unions of p consecutive subgraphs G i+1 , . . . , G i+p ;

3. for i = 1, . . . , q, run OPT_VC(G ′ i , (1λ)(2ρ)n) and store the best (say

C ′ i * ) among the covers satisfying τ (G ′ i ) (1 -λ)(2 -ρ)n (if any); 4. if such a cover C ′ i * has been computed in Step 3 for G ′ i * , then output C = C ′ i * ∪(V \V (G ′ i * )), else exit.
We now prove the following fact.

Fact 1. If α(G)
λn, then there exists a graph G ′ i * where a cover

C ′ i * satisfying τ (G ′ i * ) (1 -λ)(2 -ρ)n has been computed during step 3 of Algorithm PROCEDURE_VC.
Indeed, as shown in the proof of Proposition 1, there exists a subgraph

G ′ i * (among those built in step 2) for which α(G ′ i * ) (p/q)α(G) (2 -ρ)λn.
Hence, the following holds for G ′ i * :

|C i * | = τ (G ′ i * ) (2 -ρ)n -(2 -ρ)λn = (1 -λ)(2 -ρ)n, that proves Fact 1. According to Lemma 1, since S ′ i * = V (G ′ i * ) \ C ′ i * is a 2 -ρ
approximation for max independent set, then the cover C returned by PROCEDURE_VC is a ρ-approximation for min vertex cover.

Finally, assuming that ρ is constant, the running time of Algorithm PROCEDURE_VC(G, ρ)

is O * (δ (2-ρ)(1-λ)n ) as claimed.
Consider now the following algorithm denoted by VC2 in what follows and run with parameters G and ρ:

1. fix ρ > 1 and determine λ satisfying γ (ρ-(ρ-1/λ)) = δ (1-λ)(2-ρ) (the first increases, while
the second decreases with λ);

2. solve the LP-relaxation of max independent set, store V 0 and V 1 and set

G = G[V 1/2 ]; 3. set ρ -((ρ -1)/λ) = p/q and compute C 0 = V 0 ∪ (V \ IS(G, 2 -ρ));
4. set p/q = 2ρ and compute C = V 0 ∪ PROCEDURE_VC(G, ρ);

5. output the best among C 0 and C.

Based upon Lemmata 2 and 3, the following theorem holds and concludes the section.

Theorem 4. For any ρ > 1, min vertex cover can be solved approximately by Algorithm VC2 within ratio ρ and with running time O * (γ (ρ-(ρ-1)/λ)n ).

Revisit now step 1 of Algorithm VC2 where parameter λ were determined as solution of the equation -ρ) . This equation is, indeed, a second-degree equation whose solution is given by:

γ ρ-ρ-1 λ = δ (1-λ)(2
λ = r log δ -ρ log γ + ρ 2 log 2 γ + (2 -ρ) 2 log 2 δ -2 log γ log δ 2(2 -ρ) log δ
The improvement obtained with this algorithm is illustrated in Table 1 (at the end of Section 5).

To conclude, note that this improvement cannot be transferred to max independent set, since it is based upon Lemma 1 that does not work in both directions.

Another efficient approximation algorithm for min vertex cover

As we have already mentioned (Theorem 1), there exists an exact algorithm for min vertex cover (denoted by OPT_VC), with worst-case complexity O * (δ k ) that decides if a graph G has a vertex cover of size k or not and, if yes, it computes it. In this section, we extend this result to deal with efficient approximation of min vertex cover. The technique used is the same as in Proposition 1, up to the facts that the problem is not hereditary and the algorithm upon which it is based is parameterized.

Theorem 5. For every graph G and for any r = p/q ∈ Q, if there exists a solution for minimal vertex cover whose size is less than k, it is possible to determine with complexity O * (δ rk ) a 2r-approximation of it.

Proof. As we have pointed out in Lemma 1, anything we do can be w.l.o.g. with respect to the graph

G[V 1/2 ].
Consider the following algorithm, denoted by VC3 and called with parameters r and G:

1. arbitrarily partition G into q induced subgraphs G 1 , . . . , G q of order (except eventually for G q ) n/q;

2. form the subgraphs G ′ 1 , . . . G ′ q that are the unions of p consecutive subgraphs G i+1 , . . . , G i+p and set k = 1;

3. run OPT_VC(G, k) in G ′ i , i = 1, . . . , q in order to compute a minimum vertex cover C ′ i of G ′ i ; if no vertex cover is found, repeat step 3 with k = k + 1; otherwise, let i * be such that a vertex cover C ′ i * has been computed in G ′ i * ; 4. output C = C ′ i * ∪ (V \ V (G ′ i * )).
As seen in the proof of Proposition 1, α(G ′ i * ) (p/q)α(G). Then, the solution returned is such that

|C| = n -α(G ′ i * ) n -(p/q)α(G) = n(1 -(p/q)) + (p/q)τ (G). Since τ (G) n/2, we get: |C|/τ (G) 2(1 -(p/q)) + (p/q) = 2 -(p/q).
It is easy to see that the running time of Algorithm VC3 is of O * (δ rτ (G) ), that completes the proof of the theorem.

In Table 1, we give running times for Algorithms VC1, VC2 and VC3, for some values of ratios achieved and with γ = 1.18 and δ = 1.28 (the best known values for max independent set and min vertex cover (see [START_REF] Robson | Finding a maximum independent set in time O(2 n/4 )[END_REF][START_REF] Chen | Vertex cover: further observations and further improvements[END_REF]), respectively. Furthermore, for Algorithm VC2, we also give the value of λ for which the corresponding time is get.

Randomized algorithms

We give in this section randomized algorithms for max independent set and min vertex cover that, with probability 1 -exp{-cn} for some constant c, turn to efficient approximation algorithms with running-time lower (though exponential) than the one of the deterministic algorithms seen in Sections 4 and 5.

max independent set

In the deterministic algorithm for max independent set seen previously, we split the instance into subinstances of size rn to get a r-approximation algorithm. Here, we show that by splitting into subinstances of smaller size βn, with β < r, we can achieve the same ratio by iterating the splitting a very large (exponential) number of times (this is Algorithm RIS1). The tradeoff between the size of the subinstances and the number of times we iterate splitting to get the ratio is given in Theorem 6. Next, we determine the optimal choice for β (for Algorithm RIS1).

Finally, we further improve Algorithm RIS1 by combining it with the fixed-parameter Algorithm OPT_VC for min vertex cover in order to devise Algorithms RIS2 and RIS3.

Theorem 6. For any ρ < 1 and for any β, ρ/2 β ρ, it is possible to find an independent set that is, with probability 1 -exp{-cn} some constant c), a ρ-approximation for max independent set, with running time O * (K n γ βn ), where:

K n = n n n/2 βn ρn/2 n-βn ((1-ρ)n/2)
Proof. By Corollary 2, we can assume α(G)/n 1/2. Fix a maximum independent set S * of G and consider a subgraph B of G (for simplicity, denote also by B the vertex-set of B), whose size is βn ρn/2 ρα(G). Probability that B contains ρα(G) vertices from S * is given by the following formula:

p β,α = Pr [|S * ∩ B| = ρα(G)] = βn ρα(G) n-βn (1-ρ)α(G) n α(G) (4)
If we take at random K n such different subgraphs B i , the probability that |S * ∩ B| is never greater than ρα(G) is bounded above by:

Pr [|S * ∩ B i | < ρα(G), ∀i K n ] = (1 -Pr [|S * ∩ B i | ρα(G)]) Kn (1 -Pr [|S * ∩ B i | = ρα(G)]) Kn exp {K n log (1 -p β,α )} exp {-K n p β,α } exp - np β,α p β,n/2
We now study p β,α to show that the the previous probability is bounded by exp{-cn}. Fix λ = α(G)/n. From Stirling's formula we get:

p β,α = (βn)!(n -βn)!(λn)!(n -λn)! (βn -ρλn)!(ρλn)!(λn -ρλn)!(n -βn -λn + ρλn)!n! = θ q β,α / √ n (5)
where:

q β,α = β β (1 -β) 1-β λ λ (1 -λ) 1-λ (β -ρλ) β-ρλ (ρλ) ρλ ((1 -ρ)λ) (1-ρ)λ (1 -β -(1 -ρ)λ) 1-β-(1-ρ)λ n (6)
Consider now function:

f (ρ, λ, β) = -log (q β,λn ) n ( 7
)
Function f is continuously differentiable on {(ρ, λ, β) ∈]0, 1[×]0, 1/2[ 2 ; λρ β ρ} and its derivatives are:

∂f ∂λ = ρ log ρ + (1 -ρ) log(1 -ρ) -ρ log(β -ρλ) -(1 -ρ) log(1 -β -(1 -ρ)λ) + log(1 -λ) (8) ∂ 2 f ∂λ∂β = β -ρ (β -ρλ)(1 -β -(1 -ρ)λ) 0 (9)
where in ( 9) inequality holds because β-ρ 0, β-ρλ 0 and

1-β-(1-ρ)λ 1-ρ-(1-ρ)λ 0.
From ( 8) and ( 9) we get:

∂f ∂λ ∂f ∂λ (β = ρ) = 0 (10)
From ( 10), f grows with λ and q β,λn decreases with λ. Thus, the minimum for q β,α is reached for λ = 1/2, and p β,α /p β,n/2 > c, for some constant c. This fact derives that

Pr[max i Kn |S * ∩ B i | rm * ] 1 -exp{-cn}.
Consider now the following straightforward algorithm (denoted by RIS1 and called with parameters G and ρ), that is the randomized counterpart of Algorithm IS of Section 4 and where by OPT_IS we denote an exact max independent set-algorithm:

1. solve the LP-relaxation of max independent set, store sets

V 0 and V 1 and set G = G[V 1/2 ]; 2. for i = 1 to K n , compute S i+1 = max{S i , V 1 ∪ OPT_IS(B i )}; 3. output S Kn .
It is easy to see that the running time of Algorithm RIS1 is O * (K n γ βn ), while the probability that it returns a ρ-approximation of the optimal is 1 -exp{-cn}.

Let us now try to determine the optimal value for β. Note that if we choose β = ρ, then K n (β = ρ) is polynomial. In this case the running time of Algorithm RIS1 is as the running time of Algorithm IS (Section 4) multiplied by a polynomial term. We now show that, according to a good choice of β, it is possible to decrease overall running time of Algorithm RIS1 by an exponential term.

Fix g(ρ, β) = f (ρ, 1/2, β) + β log(γ). According to the definition of f (7)) and to [START_REF] Cai | Fixed-parameter approximation: conceptual framework and approximability results[END_REF], running time becomes O * (K n γ βn ) = O * (exp{g(ρ, β)}). Function g is derivable for any (ρ, β) such that ρ/2 < β < ρ:

∂g ∂β = log β - ρ 2 -log 1 2 -β + ρ 2 -log β + log(1 -β) + log γ ∂g ∂β ⇔ β - ρ 2 (1 -β)γ -β 1 2 -β + ρ 2 0 (11)
Expression ( 11) is a second degree inequality P (β) 0, so it has at most two zeros. Since P (β = ρ/2) = -ρ/4 < 0 and P (β = ρ) = (ρ(ρ -1)/2)(γ -1) > 0, it has exactly two solutions, β + greater than ρ and In Table 2, we give running times for Algorithms IS, and RIS1, for some values of ratios achieved. For Algorithm RIS1, we also give the value of β -for which the corresponding time is got.

β -∈ [ρ/2, ρ].
We now improve Algorithm RIS1 in two different ways, leading to Algorithms RIS2 and RIS3, respectively.

The way the first improvement is obtained (leading to Algorithm RIS2 is somehow analogous to that of Theorem 4. The basic idea is to show that, informally, the smaller the independent set, the higher the probability of finding a good approximation by splitting. In other words, when α(G) is small, we need a smaller running time to get the same approximation ratio with high probability, i.e., Algorithm RIS1 is more efficient. But, on the other hand, when α(G) is large, the fixed-parameter Algorithm OPT_VC fast. Then, Algorithm RIS2 combines these two algorithms. Let us note that this result cannot be used to improve the deterministic algorithm given in Proposition 1.

Proposition 2. For any ρ < 1 and any β such that ρ/2 β ρ, it is possible to compute an independent set that realizes with probability 1-exp{-cn} (for some constant c) a ρ-approximation of the optimum with running time O * (δ (1-λ)ρn ), where λ is defined by:

γ β exp{f (ρ, λ, β)} = δ (1-λ)ρ ( 12
)
and f is as in [START_REF] Chen | Vertex cover: further observations and further improvements[END_REF].

Proof. As previously, denote by S * a maximum independent set in G. Assume first that |S * | λn. Then, revisiting Lemma 3, Algorithm VC2 is able to find out with with running time O * (δ (1-λ)ρn ) in some subgraph G ′ 0 of G with size ρn where a a vertex cover C 0 of G ′ 0 , is associated with an independent set S 0 verifying |S 0 | ρ|S * |.

Consider now the case |S * | λn and set L n = n/p β,α . Quantity K n defined in the proof of Theorem 2 is indeed the restriction of L n to the case λ = 1/2. According to [START_REF] Downey | Parameterized approximation problems[END_REF], q β,λn (defined by ( 6)) decreases with λ; hence, p β,α /p β,λn c (for some constant c) when α λn. Then:

Pr [|S * ∩ B i | < ρα(G); ∀i L n ] (1 -p β,α ) Ln exp -n p β,α p β,λn exp{-cn}
The discussion above forwardly derives the following algorithm, denoted by RIS2:

1. fix ρ and β and determine λ satisfying (12);

2. solve the LP-relaxation of max independent set, store V 0 and V 1 and set

G = G[V 1/2 ]; 3. store S 1 = RIS1(G, ρ); 4. compute S 2 = V 1 ∪ (V 1/2 \ PROCEDURE_VC(G, ρ));
5. output the best among S 1 and S 2 .

Obviously, if |S * | λn, S 2 realizes a ρ-approximation of S * (Lemma 3), otherwise, by Theorem 6, S 1 realizes a ρ-approximation of S * with probability 1 -exp{-cn}.

For the case of Proposition 2, β -has to verify [∂(f + β log(γ)))/∂β](β -) = 0, i.e.:

(γ -1)β 2 -+ (1 -(1 -ρ)λ -γ(1 + ρλ))
β -+ γρλ = 0 Some easy algebra as in [START_REF] Eppstein | Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction[END_REF] 3: Running times of Algorithms IS and RIS2 with γ = 1.18 and δ = 1.28.

In Table 3, we perform a comparative study of running times for Algorithms IS, and RIS2, for some ratio values. As one can see from Tables 2 and3, Algorithm RIS2 dominates Algorithm RIS1 since, in fact, the former is a refinement of the latter.

The second improvement follows a different approach, based upon an exhaustive lookup of all the candidate values for α(G), and using an exact algorithm for min vertex cover rather than for max independent set. Informally, the underlying idea for this approach (leading to Algorithm RIS3) is that randomization allows to split the input graph into "small" subgraphs, on which a fixed-parameter algorithm can be efficiently used to reach both a good overall running time and any a priori fixed approximation ratio. Then, Algorithm RIS3 consists of running Algorithm OPT_VC on subgraphs of size βn < rn taken at random and for a sufficient number of times, where β is optimally determined as a function of α(G).

Theorem 7. For any ρ < 1, it is possible to compute an independent set that realizes with probability 1 -exp{-cn} (for some constant c) a ρ-approximation of the optimum, in time:

O * exp {nf (ρ, β, λ)} δ (β-λρ)n
where f is as in [START_REF] Chen | Vertex cover: further observations and further improvements[END_REF] and β and λ are defined by the following system:

(1 -β)(β + δ -δβ)ρ ρ (1 -ρ) 1-ρ = β ρ (1 -β) 1-ρ (13) (δ -1)β(1 -β) ρ -β + (δ -1)ρ(1 -β) = λ (14)
Proof. Assume that |S * | = α(G) = α, for some α n/2. Consider any set B ⊂ V where ρα |B| ρn. For convenience, set b = |B|/n. Then, according to Theorem 6, probability that B contains exactly ρα vertices from S * is p b,α , and, if we take at random L n = n/p(β, k) different subsets (B i Ln ) having the same size, the probability that one of them contains at least ρα vertices from S * is greater than 1 -exp{-cn}.

At this step, algorithms we have seen previously use an exact max independent setalgorithm running in O * (γ bn ). However, if we know that |S * | = α, it is possible to find out a minimal vertex cover of B i with complexity O * (δ bn-ρα ).

We now search for a value for β(λ) that minimizes expression exp{nf (ρ, β, λ)}δ (β-λρ)n . Fix ϕ(β, λ) = f (ρ, β, λ) + (βρλ) log δ. Then:

∂ϕ ∂β = ∂f ∂β + log(δ) ∂ϕ ∂β = 0 ⇔ δ = (1 -β -λ + ρλ)β (1 -β)(β -ρλ) ⇔ β(1 -β)(δ -1) ρ -β + ρ(1 -β)(δ -1) = λ (15)
Equation in ( 15) is a second-degree equation on β that admits one and only one, the smaller, feasible solution in [ρλ, ρ]. Checking signs of this interval bounds ensures that β(λ) is indeed a minimum.

Let us estimate the value of α that maximizes complexity. Since f with λ and ϕf decreases with λ, we cannot state, as previously, that the worst case is when λ = 1/2 (and this is not, actually, the case). Since β(λ) is a local minimum for β → ϕ(β, λ), then:

dϕ(β(λ), λ) dλ (λ) = ∂ϕ(β, λ) ∂λ (β(λ), λ)
= log ρ ρ (1 -ρ) 1-ρ (1 -β(λ))(β(λ) + δ -β(λ)δ) β ρ (λ)(1 -β(λ)) 1-ρ
Thus, the worst case corresponds to a solution of [START_REF] Fürer | A faster algorithm for finding maximum independent sets in sparse graphs[END_REF].

Consider now the following algorithm denoted by RIS3:

• solve the LP-relaxation of max independent set, store V 0 and V 1 and set

G = G[V 1/2 ];
• for α = 1 to n do:

1. determine β(α/n) satisfying (14); 2. set L n = n/p(β, α/n)} and S 0 = ∅; 3. for i = 1 to L n , set S i = max{S i-1 , B i \ OPT_VC(B i , α)}; 4. set S α = S Ln ; • output V 1 ∪ argmax{|S α |}.
It can be immediately seen that Algorithm RIS3 meets the statement of the theorem and concludes its proof. Table 4 presents a comparative study of running times for Algorithms IS, and RIS3. For approximation ratios smaller than 0.75, the latter algorithm dominates all the previous ones. But, as far as ratios greater than 0.75 are dealt, it is dominated by Algorithm RIS2 and even by IS.

Ratio

min vertex cover

Obviously, Lemma 1 still holds for randomized algorithms. Hence, the complements of the solutions provided by Algorithms RIS1, RIS2 and RIS3 are vertex covers for G achieving ratios 2ρ with probability 1-exp{-cn}. In what follows we propose randomized efficient approximation algorithms for min vertex cover with running times better than those get in Section 6.1.

Underlying ideas are similar to the previous ones but, taking into account once again Lemma 1, a more involved computation leads to better results. In Proposition 3 below, we simply mix the randomization technique of Algorithm RIS1 and the fixed-parameter approximate Algorithm VC3. Proposition 3. For any r < 1 and any β such that rλ < β < r, it is possible to compute with probability 1 -exp{-cn} (for some constant c) a (2r)-approximation of min vertex cover in time O * (δ (1-λ)rn ), where λ is solution of:

δ (1-λ)r = γ β exp f r ′ λ , λ, β
and r ′ λ is a function of λ defined by:

r ′ λ = 2 -r - 1 -r λ
Proof. Consider the following algorithm, denoted by RVC1:

• set C 1 = VC3(G, 2 -r); • set C 2 = V \ RIS1(G, r); • output C = argmin{|C 1 |, |C 2 |}. Assume first that |S * | λn. Then, C * (1 -λ)n. According to Theorem 5, C 1 is a 2 -r approximation of C * computed in O * (δ (1-λ)rn ).
Assume next that |S * | λn. Then, according to Theorem 6, Algorithm RIS1 can compute in time O * (γ β exp{f (r ′ λ , λ, β)}) and with probability 1 -exp{-cn}, an r-approximation for max independent set which, according to Lemma 1, turns to a 2-r-approximation for min vertex cover.

We now conclude this section by further improving the result of Proposition 3. The idea is similar to the one for Algorithm RIS3: we use the fixed-parameter algorithm OPT_VC on subinstances of size βn < rn, where β is optimally determined as a function of α(G). Proposition 4. For any r < 1, and any β such that rλ < β < r, it is possible to compute with probability 1 -exp{-cn} (for some constant c) a (2r)-approximation of min vertex cover in O * (δ (1-λ)r ′ λ n ), where β and λ are defined by the following system:

β(1 -β)(δ -1) r ′ λ -β + r ′ λ (1 -β)(δ -1) = λ (16) dϕ (β(λ), λ, r ′ λ ) dλ = 0
and r ′ λ is a function of λ defined by:

r ′ λ = 2 -r - 1 -r λ
Proof. Consider the following algorithm, denoted by RVC2, that is devised in the same spirit as Algorithm RIS3:

1. solve the LP-relaxation of max independent set, store

V 0 and V 1 and set G G[V 1/2 ];
2. for any k n do:

(a) set λ = k/n and determine β(λ) satisfying ( 16);

(b) set L n = n exp{f (r ′ λ , k/n, β)n} and S 0 = ∅; (c) for i = 1 to L n , compute S i = max{S i-1 , B i \ OPT_VC(B i , k)}; (d) set S k = S Ln 3. output V 0 ∪ (V 1/2 \ argmax{|S k |}.
According to the analysis of Algorithm RIS3, S |S * | is an independent set whose size is at least

r ′ |S * |/n |S * |. Then, according to Lemma 1, V 1/2 \ S |S * | is a vertex cover whose size is at most (2 -r)|C * |.
The complexity of Algorithm RVC2 is determined by the worst value for λ. Computing such a value amounts to study the function ϕ(β(λ), λ, r ′ λ ). But, unfortunately, this does not lead to a simple expression for λ. For this reason analytic computation of λ is omitted. In Table 5, the running times of Algorithms VC1, VC2, RVC1 and RVC2 are shown for some ratios and for γ = 1.18 and δ = 1.28.

Ratio

Efficient approximation of max independent set in particular classes of graphs

In this section we consider particular classes of max independent set-instances admitting polynomial approximation algorithms achieving some ratio ρ. For instance, a notable example of such a class is the class of bounded-degree graphs. For these graphs, denoting by ∆(G) the bound on the degrees, max independent set can be polynomially approximated within ratio ρ = 5/(∆(G) + 3) ( [START_REF] Berman | On the approximation properties of independent set problem in degree 3 graphs[END_REF]).

Consider some class C of graphs where max independent set is approximable in polynomial time within approximation ratio ρ by an algorithm called APIS in what follows. We show that the graph splitting technique used previously can be efficiently applied to get interesting tradeoffs between running times and approximation ratios (greater than ρ).

Proposition 5 . For any rational r < 1, it is possible to compute, for any graph G ∈ C a (r + (1r)ρ)-approximation of max independent set, with running time O * (2 rn ).

Proof. Let G(V, E) be a graph in C and S * be a maximum independent set of G. Fix r = p/q. Run the following algorithm, denoted by EIS1, where Γ(H) denotes the set of neighbors of H in V \ H:

1. arbitrarily partition G into q induced subgraphs G 1 , . . . , G q of order (except eventually for G q ) n/q;

2. build subgraphs G ′ 1 , . . . G ′ q that are the unions of p consecutive subgraphs G i+1 , . . . , G i+p ; let V ′ i be the vertex set of G ′ i , i = 1, . . . , q; 3. for any V ′ i and any

H ⊆ V ′ i , if H is independent, then S = H ∪ APIS(G[V \ (H ∪ Γ(H))
]); 4. output the best among S's computed at step 3.

According to Proposition 1, one of the graphs G ′ i i = 1, . . . q, built at step 2 contains a set S 0 ⊆ S * with at least r|S * | vertices. Since Γ(S 0 ) ∩ S * = ∅, the set S * \ S 0 is contained in V \ (S 0 ∪ Γ(S 0 )). Algorithm APIS is also called by Algorithm EIS1 on the subgraph induced by V \(S 0 ∪Γ(S 0 )) and, in this case, the independent set computed has size is at least ρ(|S * | -|S 0 |) + |S 0 | and the same holds for the largest of the so-computed sets S returned by step 4. Hence, the approximation ratio finally achieved is at least:

|S 0 | + ρ (|S * | -|S 0 |) |S * | r + (1 -r)ρ
Obviously, Algorithm EIS1 runs q2 pn/q times a polynomial algorithm. Hence, its complexity is O * (2 rn ).

Let us note that the algorithm is only interesting if its ratio is better than that of IS that has the same running time. For this the following must hold:

r + (1 -r)ρ log 2 log γ r ⇐⇒ r ρ log γ log 2 -(1 -ρ) log γ
For instance, for graphs whose degree is bounded above by 3, this means that:

r 5 log γ 6 log 2 -log γ ⇔ r + (1 -r)ρ 5 log 2 6 log 2 -log γ ≈ 0.870
Now, we show how to improve this result. It is easy to see that in the analysis of Proposition 5 if, roughly speaking, S * is not "uniformly" distributed over the G ′ i 's, then the ratio improves. In the following proposition, we deal with the problematic case of a uniform distribution and show that, informally, generating only "small" subsets of G ′ i 's is sufficient.

Proposition 6. For any r < 1, it is possible to compute on any graph G ∈ C a (r + (1r)ρ)approximation of max independent set, with running time O * (2 βrn ), where β < 1 is a solution of:

2 β = β λ λ β (β -λ) 1-λ β ( 17
)
and λ is such that it verifies:

2 βr = δ (1-λ)(r+(1-r)ρ) (18)
if some solution of this equation is less than 1/2, λ = 1/2 otherwise.

Proof. Fix a rational r < 1 as well as β < 1, and λ < 1/2. Assume first that |S * | λn. Then, according to Theorem 4 (see, in particular Fact 1), Algorithm VC2(G, 2r -(1r)ρ) returns in time O * (δ (1-λ)(r+(1-r)ρ) ) a (r + (1r)ρ)-approximation for max independent set. Consider now the case |S * | λn. Set p/q = r and arbitrarily partition G into q induced subgraphs G 1 , . . . , G q of order (except eventually for G q ) n/q. Build the q subgraphs G ′ 1 , . . . G ′ q that are unions of p consecutive subgraphs G i+1 , . . . , G i+p , i = 1, . . . , q. Denote by V ′ i the vertex set of G ′ i , S * a maximum independent set of G and assume that there exists some i 0 ∈ {1, . . . , q}, such that:

α = S * ∩ V ′ i 0 r |S * | β
Then, fix p ′ /q ′ = β, arbitrarily partition G ′ i 0 into q ′ subgraphs of the same order and build the q ′ subgraphs G ′′ 1 , . . . G ′′ q ′ that are unions of p ′ consecutive subgraphs G ′′ i+1 , . . . , G ′′ i+p ′ , i = 1, . . . , q ′ . According to Proposition 1, there exists one of these graphs that contains at least β α = r|S * | vertices from S * ∩ V ′ i 0 . Computing any subset of any combination of a specific partition of any V ′ i 0 has cost:

q ′ × 2 βpn q × q = O * 2 βrn
It remains now to handle the case where for any i ∈ {1, . . . , q}:

α r |S * | β rλn β
Then, Algorithm EIS1 achieves the claimed ratio up to the fact that it does only consider subsets smaller than rλn/β. Thus, in this case its running time is only:

rn λrn/β = O * β λ λ β (β -λ) 1-λ β rn
The discussion above directly leads to the following algorithm, denoted by EIS2:

1. solve the LP-relaxation of max independent set, store

V 0 and V 1 and set G = G[V 1/2 ];
2. fix r = p/q and compute λ and β according to [START_REF] Khot | Vertex cover might be hard to approximate to within 2ε[END_REF] and [START_REF] Nemhauser | Vertex packings: structural properties and algorithms[END_REF], respectively; fix

β = p ′ /q ′ ; 3. if λ < 1/2, then set S ′ = V 1/2 \ PROCEDURE_VC(G, 2 -r -ρ(1 -r));
4. if λ 1/2, replace λ by 1/2 and β by 1; set S ′ = ∅;

5. arbitrarily partition G into q induced subgraphs G 1 , . . . , G q of order (except eventually for G q ) n/q; build the q subgraphs G ′ 1 , . . . G ′ q that are unions of p consecutive subgraphs G i+1 , . . . , G i+p , i = 1, . . . , q; let V ′ i be the vertex set of G ′ i , i = 1, . . . , q;

6. for any V ′ i and any H ⊆ V ′ i such that |H| λrn/β, if H is an independent set, then set S ′ = max{H ∪ APIS(V \ (H ∪ Γ(H))), S ′ }; 7. for any V ′ i :

(a) arbitrarily partition V ′ i into q ′ induced subgraphs of the same order and build the q ′ subgraphs G ′′ 1 , . . . G ′′ q ′ that are unions of p ′ consecutive subgraphs G ′′ i+1 , . . . , G ′′ i+p ′ , i = 1, . . . , q ′ ; (b) for any G ′′ i and any

H ⊆ V (G ′′ i ), if H is an independent set, then set S ′ = max{H ∪ APIS(V \ (H ∪ Γ(H))), S ′ }; 8. output S = V 1 ∪ S ′ .
It is easy to see that Algorithm EIS2 perfectly fulfils the statement of the proposition.

We conclude this section by a comparative study of the running times of Algorithms EIS1 and EIS2 with respect to Algorithm IS(G, r + ρ(1r)), called with ρ = 5/6, γ = 1.112 ( [START_REF] Fürer | A faster algorithm for finding maximum independent sets in sparse graphs[END_REF]), δ = 1.194 ( [START_REF] Chen | Labeled search trees and amortized analysis: improved upper bounds for np-hard problems[END_REF]), for ∆(G) = 3, ρ = 5/7, γ = 1.17 ([3]), δ = 1.28, for ∆(G) = 4, and ρ = 0.5, γ = 1.18, δ = 1.28, ∆(G) = 7. Results are shown in Table 6.

max set packing, max clique and max bipartite subgraph

We show in this section how the results obtained in previous sections can be applied also to efficiently approximate other combinatorial problems. Let us first note that all these problems are hereditary problems, hence Proposition 1 is applied to each of them with a parameter γ, the basis of the exponential, depended on the particular problem. But in what follows, we show that for the problems handled in this section, namely, max set packing, max clique and max bipartite subgraph, any of the results of the former sections identically apply with parameters γ ′ and δ ′ that depend on those of max independent set and min vertex cover, respectively.

max set packing

Let us first handle the case of max set packing5 that is quite simple. Given an instance I(S, C) of max set packing with S = {S 1 , . . . , S m }, S i ⊆ C, i = 1, . . . , m, and C = {c 1 , . . . , c n }, we construct the graph G(V, E) as follows:

• V = {v 1 , . . . , v m }, in other words |V | = |S|; • E = {(v i , v j ) : S i ∩ S j = ∅}.
In other words, if two sets in S have non-empty intersection then the corresponding vertices in G are adjacent. It is easy to see that any set packing in I transforms into an independent set of the same size in G and vice-versa. So the following result holds directly. Proposition 7. max set packing is as efficiently approximable as max independent set. Parameters γ and δ of max set packing are the same as max independent set and min vertex cover, respectively. The exponent for max set packing is the cardinality m of the set-family S. for ∆(G) = 3, ρ = 5/7, γ = 1.17, δ = 1.28 for ∆(G) = 4 and ρ = 0.5, γ = 1.18, δ = 1.28 for ∆(G) = 7.

max clique

We handle in this section another famous combinatorial optimization problem that is max clique 6 . It is very well known that an independent set in a graph G becomes a clique of the same size in the complement Ḡ of G where we keep vertices we delete E and we add an edge (v i , v j ) if and only if i = j and (v i , v j ) / ∈ E. So, results of previous sections for independent set trivially apply to max clique. In what follows, we improve these results replacing exponent n, the order of the input graph G for max clique, by ∆(G), the maximum degree of G.

Consider the following reduction from max clique to max independent set. Let G(V, E) be the input graph of max clique, V = {v 1 , . . . , v n } and, for i = 1, . . . , n, denote by Γ(v i ) the neighbors of v i . Build the n graphs

G i = G[{v i } ∪ Γ(v i )].
Since in any clique of G any vertex is a neighbor of any other vertex of a clique, any of these cliques are subsets of the neighborhood of each of their vertices. So, a maximum clique is a subset of the neighborhood of some graph G i just built. For every G i , build its complement Ḡi and solve max independent set in Ḡi . Let S i , i = 1, . . . , n, the independent sets so computed. These sets are cliques of G i . Then, take the largest of these sets as solutions.

Obviously, if an exact algorithm for max independent set is used, then the largest among the sets S i is a maximum clique in G. By taking into account that the order of any of the graphs G i is bounded above by ∆(G) + 1, we immediately deduce that computing a maximum clique in a graph G takes time O(nγ ∆(G)+1 ) = O * (γ ∆(G) ), where γ is the basis of the exponential of max independent set.

Discussion just above derives, at very first, the following parametric complexity result for the exact computation of max clique, interesting per se.

Theorem 8. max clique can be exactly solved in O * (γ ∆(G) ), where ∆(G) is the maximum degree of the input graph.

Also, any of the results dealing with max independent set seen in the previous sections, identically applies to max clique also. So; the following theorem holds and concludes this section.

Theorem 9 . For the efficient approximation of max clique, parameters γ and δ are the same as max independent set and min vertex cover, respectively. The exponent for max clique is the maximum degree ∆(G) of the input-graph.

max bipartite subgraph

Consider the following reduction from max bipartite subgraph7 to max independent set ( [START_REF] Simon | On approximate solutions for combinatorial optimization problems[END_REF]). Let G(V, E) be an instance of max bipartite subgraph of order n. Construct a graph G ′ (V ′ , E ′ ) for max independent set by taking two distinct copies of G (denote them by G 1 and G 2 , respectively) and adding the following edges: a vertex v i 1 of copy G 1 is linked with a vertex v j 2 of G 2 , if and only if (v i , v j ) / ∈ E. In other words, we link any vertex v of one copy, to the vertices of the other one with which v is not linked in G. is easy to see that the so-constructed graph G ′ is regular with vertex-degree n.

Consider an independent set S of G ′ and denote by S i the subset of S that belong to G i and by V i the corresponding set of V , i = 1, 2. Then, V 1 and V 2 are two independent sets in G that are completely linked one to the other, i.e., they form a complete bipartite graph of the same size as S. Conversely, if V 1 and V 2 are independent sets that form a complete bipartite graph in G then their copies V 1 1 and V 2 2 form a whole independent set (of size |V 1 1 ∪ V 2 2 |) in G ′ . So, any solution for max independent set in G ′ can be transformed into a solution, of the same size, for max bipartite subgraph in G.

Observe finally that according to the reduction just above, an instance of size n for max bipartite subgraph transforms into an instance of size 2n for max independent set. So the following result can be forwardly derived. Proposition 8. For the efficient approximation of max bipartite subgraph, parameters γ and δ of max independent set and min vertex cover, are transformed into γ 2 and δ 2 respectively. The exponent for max bipartite subgraph is the size n of the input-graph.

In other words, considering γ = 1.18 and δ = 1.28, the corresponding bases for max bipartite subgraph become 1.39 and 1.64, respectively.

Conclusion

We have proposed an approach matching polynomial approximation and exact computation, that can be seen as a further tool for handling intractability. This approach allows, as we have seen, to approximately solve hard combinatorial optimization problems within approximation ratios unachievable in polynomial time and with non-trivial running times faster than those of exact computation.

It can be easily seen that all the algorithms proposed in this paper use polynomial space. Also, as the results are parameterized by the bases of the best worst-case complexity known for the problems handled, any improvement of these bases is immediately transferred to them.

The most of the results presented is based upon appropriate splittings of the initial instance into smaller ones in such a way that solution of the latter allow recovering of a solution of the former. This method is quite general and works for other problems such as max sat problems.

The issue considered is this paper deserves to our opinion further research. A main direction could be to devise other efficient methods, either for improving our results or handling other paradigmatic problems such as min tsp. These methods could be, for instance, inspired by exact algorithms (for example by a sharp pruning of the search tree), or could be direct approximation algorithms based upon some non-polynomial computations rather than exact computations on subinstances.

In another order of ideas, revisit for a while Section 8.3. The result is obtained there via an approximation preserving reduction. The important parameters of this reduction are not only the ratio's expansion (this is the case in the polynomial approximation framework), but also the instance size amplification (that is crucial for efficient approximation). Defining appropriate notions of approximation preserving reductions involving, for instance, small linear instance size amplifications, may be also an interesting issue that deserves further investigations.

Table 1 :

 1 Running times of Algorithms VC1, VC2 and VC3 with γ = 1.18 and δ = 1.28, for some values of ρ.

	Ratio	VC1	VC2 Time	λ	VC3
	1.9	1.017 n 1.013 n 0.493 1.025 k
	1.8	1.034 n 1.026 n 0.486 1.051 k
	1.7	1.051 n 1.039 n 0.477 1.077 k
	1.6	1.068 n 1.054 n 0.468 1.104 k
	1.5	1.086 n 1.069 n 0.457 1.131 k
	1.4	1.104 n 1.086 n 0.443 1.160 k
	1.3	1.123 n 1.104 n 0.427 1.189 k
	1.2	1.142 n 1.124 n 0.407 1.218 k
	1.1	1.161 n 1.148 n 0.378 1.249 k

Table 2 :

 2 Thus, β -is a global minimum in ]ρ/2, ρ[. Running times of Algorithms IS and RIS1 with γ = 1.18.

	Ratio 0.1	RIS1 Time 1.017 n 1.016 n 0.088 IS β -
	0.2	1.034 n 1.032 n 0.177
	0.3	1.051 n 1.048 n 0.269
	0.4	1.068 n 1.065 n 0.363
	0.5	1.086 n 1.083 n 0.459
	0.6	1.104 n 1.101 n 0.559
	0.7	1.123 n 1.119 n 0.662
	0.8	1.142 n 1.139 n 0.769
	0.9	1.161 n 1.159 n 0.882

  concludes that there always exists one and only one feasible (with respect to the interval ]ρλ, ρ[) value β -to this equation, and this value is actually a minimum.

	Ratio 0.1	RIS2 β -1.017 n 1.015 n 0.082 0.394 IS Time λ
	0.2	1.034 n 1.031 n 0.166 0.390
	0.3	1.051 n 1.047 n 0.252 0.386
	0.4	1.068 n 1.063 n 0.341 0.381
	0.5	1.086 n 1.080 n 0.433 0.375
	0.6	1.104 n 1.098 n 0.529 0.369
	0.7	1.123 n 1.117 n 0.631 0.362
	0.8	1.142 n 1.136 n 0.739 0.353
	0.9	1.161

n 1.157 n 0.859 0.343 Table

Table 4 :

 4 Running times of Algorithms IS and RIS3 with δ = 1.28.

		IS	Time	RIS3 β(λ)	λ
	0.1	1.017 n 1.013 n 0.059 0.226
	0.2	1.034 n 1.027 n 0.121 0.224
	0.3	1.051 n 1.042 n 0.183 0.221
	0.4	1.068 n 1.057 n 0.250 0.218
	0.5	1.086 n 1.075 n 0.319 0.215
	0.6	1.104 n 1.093 n 0.393 0.211
	0.7	1.123 n 1.115 n 0.472 0.206
	0.8	1.142 n 1.139 n 0.561 0.199
	0.9	1.161 n 1.169 n 0.664 0.190

Table 5 :

 5 Running times of Algorithms VC1, VC2, RVC1 and RVC2 with γ = 1.18 and δ = 1.28.

		VC1	VC2	RVC1	RVC2
	1.9	1.017 n 1.013 n 1.013 n 1.010 n
	1.8	1.034 n 1.026 n 1.026 n 1.021 n
	1.7	1.051 n 1.039 n 1.039 n 1.032 n
	1.6	1.068 n 1.054 n 1.053 n 1.043 n
	1.5	1.086 n 1.069 n 1.068 n 1.056 n
	1.4	1.104 n 1.086 n 1.085 n 1.069 n
	1.3	1.123 n 1.104 n 1.102 n 1.083 n
	1.2	1.142 n 1.124 n 1.122 n 1.099 n
	1.1	1.161 n 1.148 n 1.146 n 1.127 n

Table 6 :

 6

Running times of Algorithms IS, EIS1, and EIS2 with: ρ = 5/6, γ = 1.112, δ = 1.28

The min if Π is a maximization problem, the max, otherwise.

Given a graph G(V, E), max independent set consists of finding a set S ⊆ V of maximum size such that for any (u, v) ∈ S × S, (u, v) / ∈ E.

Given a graph G(V, E), min vertex cover consists of finding a set C ⊆ V of minimum size such that, for every (u, v) ∈ E, either u, or v belongs to C.

A graph G is said to satisfy a hereditary property π if every subgraph of G satisfies π whenever G satisfies π. Furthermore, π is non-trivial if it is satisfied for infinitely many graphs and it is false for infinitely many graphs; for instance, properties "independent set", "clique", "planar graph", "k-colorable graph", etc., are non-trivial hereditary properties.

Given a ground set C and a family S of n subsets of C (i.e., S ⊆ 2 C ), max set packing consists of determining a maximum-size collection S ′ ⊆ S such that sets in S ′ are pairwise disjoint.

Given a graph G(V, E), max clique consists of determining a maximum-size subsetV ′ ⊆ V such that G[V ′ ] is a complete graph.

Given a graph G(V, E), max bipartite subgraph consists of finding a maximum-size subset V ′ ⊆ V such that the graph G[V ′ ] is a complete bipartite subgraph.


Nicolas Bourgeois
email: bourgeois@lamsade.dauphine.fr

Bruno Escoffier
email: escoffier@lamsade.dauphine.fr

Vangelis Th

Paschos
email: paschos@lamsade.dauphine.fr

An improved exact algorithm for maximum independent set in sparse graphs

Introduction

Very active research has been recently conducted around the development of optimal algorithms for NP-hard problems with non-trivial worst-case complexity. In this paper we handle max independent set3, that is the max independent set problem in graphs with maximum degree 3.

Given a graph G(V, E), max independent set consist of finding a maximum-size subset V ′ ⊆ V such that for any (v i , v j ) ∈ V ′ × V ′ , (v i , v j ) / ∈ E. max independent set is a paradigmatic problem in theoretical computer science and numerous studies carry either on its approximation or on its solution by exact algorithms with non-trivial worst-case complexity. The best such complexity is, to our knowledge, the O * (1.18 n ) algorithm by [START_REF] Robson | Finding a maximum independent set in time O(2 n/4 )[END_REF].

One of the most studied versions of max independent set is its restriction in graphs with maximum degree 3, denoted by max independent set3 in what follows. Dealing with exact computation of max independent set3, several algorithms have been devised successively improving worst case complexity of its solution. Let us quote here the O * (1.1259 n ) algorithm by [START_REF] Beigel | Finding maximum independent sets in sparse and general graphs[END_REF], the O * (1.1254) algorithm by [START_REF] Chen | Labeled search trees and amortized analysis: improved upper bounds for NP-hard problems[END_REF], the O * (1.1225 n ) algorithm by [START_REF] Fomin | Pathwidth of cubic graphs and exact algorithms[END_REF], the O * (1.1120) algorithm [START_REF] Fürer | A faster algorithm for finding maximum independent sets in sparse graphs[END_REF] and the O * (1.1034 n ) algorithm by [START_REF] Razgon | A faster solving of the maximum independent set problem for graphs with maximal degree 3[END_REF]. In this paper, based upon a refined branching with respect to [START_REF] Fürer | A faster algorithm for finding maximum independent sets in sparse graphs[END_REF], we devise an exact algorithm for max independent set-3 with worst-case running time of O * (1.0977 n ). As it hopefully will be understood from the analysis, our result remains valid also for graphs where the maximum degree is higher but the average degree is bounded by 3.

Let T (•) be a super-polynomial and p(•) be a polynomial, both on integers. In what follows, using notations in [START_REF] Woeginger | Exact algorithms for NP-hard problems: a survey[END_REF], for an integer n, we express running-time bounds of the form p(n) • T (n) as O * (T (n)), the asterisk meaning that we ignore polynomial factors. We denote by T (n) the worst-case time required to exactly solve the considered combinatorial optimization problem with n variables. We recall (see, for instance, [START_REF] Eppstein | Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction[END_REF]) that, if it is possible to bound above T (n) by a recurrence expression of the type

T (n) ≤ T (n-r i )+O(p(n)), we have T (n-r i )+O(p(n)) = O * (α(r 1 , r 2 , . . .) n ) where α(r 1 , r 2 , . . .) is the largest zero of the function f (x) = 1 -x -r i .
Consider a graph G(V, E). Denote by α(G) the size of an optimal solution for max independent set on G. For convenience, if H ⊆ V , we will denote by α(H) the cardinality of an optimal solution on the subgraph of G induced by H. For any vertex v, we denote by Γ(v) the set of its neighbors and by deg(v) = |Γ(v)| its degree. We denote by α(G|v) (resp., α(G|v)) the size of the optimal solution if we include v (resp. if we do not include v).

Preprocessing

The max independent set-3-instance tackled is parameterized by d = mn, where n = |V | and m = |E|; T (d) will denote the maximum running time of our algorithm on a graph whose parameter is smaller than or equal to d.

Before running the algorithm, we perform a preprocessing of the graph, in order to first remove vertices of degree 1 and 2 as well as dominated vertices. Some of the properties this preprocessing is based upon are easy and already known, mainly from [START_REF] Fürer | A faster algorithm for finding maximum independent sets in sparse graphs[END_REF]. We keep them for legibility.

Lemma 1. Assume that there exists v ∈ V such that deg(v) = 1. Then, there exists a maximal independent set S * such that v ∈ S * Proof. Let w be the only neighbor of v. If v is not selected, then w must be selected (else the solution would not even be maximal for inclusion). Then:

α(G|v) = α(V -{v, w}) + 1 ≥ α(V -{v, w} -Γ(w)) + 1 = α(G|v) Lemma 2. Let v, w ∈ V , such that v ∈ Γ(w) and Γ(w) -{v} ⊆ Γ(v) -{w}.
Then, there exists a maximal independent set S * such that v / ∈ S * .

Proof. Since V -{v} -Γ(v) ⊆ V -{w} -Γ(w), α(G|v) ≤ α(G|w).
We say that v is dominated by w and we can remove it from our graph. If v both dominates and is dominated by w, we choose at random the only one we keep.

w 1 2 w w 1 v Figure 1: Vertex folding Lemma 3. Let v, w 1 , w 2 ∈ V , such that deg(v) = 2, Γ(v) = {w 1 , w 2 }
and w 1 is not a neighbor of w 2 . Then max independent set on G(V, E) is equivalent to the following problem:

1. form the subgraph G ′ (V ′ , E ′ ) induced by V -{v, w 2 }. For any x = v such that {x, w 2 } ∈ E, add {x, w 1 } to E ′ (see Figure 1); 2. compute a solution, say S, for max independent set on G ′ (V ′ , E ′ );

3. if w 1 ∈ S, S * = S ∪ {w 2 }. Else S * = S ∪ {v}.
Proof. Notice at first that, according to lemma 1:

α(G|v) = α(G|w 1 , w 2 ) = α(G ′ |w 1 ) + 1 α(G|v) = α(G| w1 , w2 ) = α(G ′ | w1 ) + 1 From what it holds α(G) = α(G ′ ) + 1.
This reduction is called vertex folding in [START_REF] Chen | Labeled search trees and amortized analysis: improved upper bounds for NP-hard problems[END_REF]. Summing up the previous properties, we are now able to operate a reduction as soon as the graph has a vertex of degree 1 or 2.

Proposition 1. Assume that there exists some vertex v such that 1 ≤ deg(v) ≤ 2. Then, there exists a graph

G ′ (V ′ , E ′ ) with |V ′ | < |V | and d ′ = |E ′ | -|V ′ | ≤ d such that it is equivalent to compute max independent set on G or on G ′ .
Proof. The following holds:

• if deg(v) = 1, according to lemma 1 we may add it to the solution and remove its neighbor w from the graph.

d ′ = d -deg(w) + 2 ≤ d; • if deg(v) = 2
and its neighbors w 1 , w 2 are adjacent to each other, then v dominates them.

According to lemma 2 we may remove w 1 from the graph; then lemma 1 allows us to add v to the solution and remove w 2 .

d ′ = d -deg(w 1 ) -deg(w 2 ) + 4 ≤ d;
• finally, if deg(v) = 2 and its neighbors w 1 , w 2 are not adjacent to each other, the equivalent graph we built in lemma 3 verifies d ′ ≤ d.

In other terms, we can always consider any vertex from our graph has at least degree 3.

We conclude this section by a remark that will be helpful later in the branching analysis.

Remark 1. Note that in the last case of Proposition 1 (deg(v) = 2 and its neighbors w 1 , w 2 are not adjacent to each other) then (at least) one of the two following cases occurs when reducing the graph: either (i) d ′ ≤ d -1 (if w 1 and w 2 are both adjacent to a third vertex x = v), or (ii) a vertex of degree at least 4 is created in G ′ .

Branching

In this section, we consider that the whole preprocessing described in Section 2 has been computed as long as possible. That means no vertex has degree 2 or less, and no vertex is dominated.

Lemma 4. Fix some vertex v. The number N of edges that are adjacent to at least one of its neighbors is bounded below by:

deg(v) + 1 2 w∈Γ(v)
deg(w)

Proof. Let I (resp. Ω) the inner (resp. outer) edges of Γ(v), that means edges linking two vertices from Γ(v) (resp. one vertex from Γ(v) and one vertex from V -Γ(v)). Then:

N = |Ω| + |I| w∈Γ(v) deg(w) = |Ω| + 2|I|
From what we get:

N = w∈Γ(v) deg(w)/2 + |Ω|/2 (1)
Notice that any w ∈ Γ(v) has at least one neighbor in V -{v} -Γ(v); else w would dominate v. Moreover, w is adjacent to v. Thus, |Ω| ≥ 2deg(v).

Proposition 2 . Assume that there exists some vertex v whose degree is at least 5. Then,

T (d) ≤ T (d -4) + T (d -7).
Proof. We branch on v. If we choose not to add v to the solution, then we can remove v and any vertex incident to him, that means

d ′ = d -deg(v) + 1 ≤ d -4.
On the other hand, if v belongs to optimal, we remove from our graph v and all its neighbors, that means (according to lemma 4):

n ′ = n -1 -deg(v) m ′ ≤ m -deg(v) - 1 2 w∈Γ(v) deg(w) d ′ ≤ d + 1 - 1 2 w∈Γ(v) deg(w)
And w∈Γ(v) deg(w) ≥ 15. Since d ′ has to be an integer, this leads to the expected result.

Proposition 3 . Assume that there exists some vertex v whose degree is 4.

Then, T (d) ≤ T (d -3) + T (d -5).
Moreover, assume that one of the following cases holds:

1. one neighbor of v has degree 4;

2. any neighbor has degree 3 but the subgraph induced by Γ(v) contains at most one edge.

Then, T (d) ≤ T (d -3) + T (d -6).
Proof. We branch on v. If we choose not to add v to the solution, then we can remove v and any vertex incident to him, that means

d ′ = d -deg(v) + 1 ≤ d -3.
On the other hand, if v belongs to optimal, we remove from our graph v and all its neighbors: Proposition 4. Assume now that the degree of any vertex in our graph is exactly 3. Assume also that G contains some 3-clique {a, b, c}. Then, T (d) ≤ 2T (d -4).

d ′ ≤ d + 1 - 1 2 w∈Γ(v) deg(w)
Proof. Let v the third neighbor of a and u, w the two other neighbors of v. Note that u (and w) differs from b and c, otherwise a would dominate b or c. We branch on v. If v does not belong to the optimal, it is removed, and so are its incident edges. In the remaining graph, a is dominated by b and c (see Figure 2). According to lemma 2 we may add it to the optimal and remove the whole clique. Eventually,

d ′ = (m -8) -(n -4) = d -4
On the other hand, if v has to be added to the solution, we may remove it and its neighbors from the graph. That means, according to lemma 4,

d ′ ≤ (m -3 -9/2) -(n -4) = d -7/2
Since d ′ has to be an integer, that leads to the expected inequality.

Proposition 5. Assume now that G is a 3-clique-free graph where any vertex has degree exactly 3. Assume also that G contains the subgraph described in Figure 3 Proof. In this proposition, instead of branching on a single vertex as previously, we successively branch on several vertices. First of all, consider any v ∈ V . As we saw previously, since there is no 3-clique, if we add v to the solution, we decrease d by 5, else we decrease d by 2. Thus, we can write

T (d) ≤ T (d -5) + Q(d -2)
, for some function Q ≤ T . If we had no further information about the remaining graph, we would have no choice but to write

T (d) ≤ T (d -5) + T (d -2).
But our graph is not any graph; in particular some higher than 3 degree vertices may have been created during our first branching. From now on, the proof will focus on refining analysis of Q thanks to our graph properties. Let w 1 , w 2 , w 3 the neighbors of v. Once v and its incident edges have been removed, they all have degree 2. Moreover, no couple of them can be adjacent, else they would form a clique with v. According to lemma 3, we now reduce our graph. We distinguish some different cases.

Consider at first an easy case, where there exists a couple of vertices u 1 , u 2 both adjacent to, say, w 1 and w 2 (see Figure 4). We can easily see that taking u 1 and/or u 2 is never interesting, it is never worse to take w 1 and w 2 . So, we can add {w 1 , w 2 } to optimal and delete {u 1 , u 2 }. This operation decreases d by 2: 4 vertices and 6 edges are removed. Indeed, u 1 and u 2 cannot be adjacent otherwise u 1 would dominate u 2 (and vice-versa) before branching on v. In other words, Q(d) ≤ T (d -2). Eventually, Assume now that there exists one single vertex u that is adjacent to, say, w 1 and w 2 . Let us denote s and t the third neighbor of respectively w 1 and w 2 (see Figure 5). Notice that in this case u cannot be adjacent to w 3 , else it would dominate v. When operating reductions of w 1 and w 2 , s, u and t are merged together in a single vertex. Two cases may occur (see Remark 1): either 2 of them have another common neighbor and d decreases by at least one, or our graph contains a vertex of degree 5. In the first case, we get Q(d) ≤ T (d -1) and finally (d) ≤ T (d -5) + T (d -3). In the latter case, we now branch on the degree 5 vertex; according to proposition 2, Q(d) ≤ T (d -4) + T (d -7), that means: Let us now focus on the main case, where Γ(w i )'s are disjoint. Let us denote u 1 i and u 2 i the two other neighbors of w i . When reducing vertex w i , going back to Remark 1, either d decreases by at least one, or a vertex -say u i -degree 4 is created. If for at least one w i d decreases, then Q(d) ≤ T (d -1) and eventually T (d) ≤ T (d -5) + T (d -3). Otherwise, when reductions of degree 2 vertices w i 's have been proceeded, the remaining graph contains exactly three vertices whose degree is 4, namely u 1 , u 2 , u 3 . Since our graph is not fully reduced (branching may have disturbed it), it is possible that some neighbor of some u i dominates it. In this case we can remove it and its incident edges without branching; Q(d) ≤ T (d -3), that means

T (d) ≤ T (d -5) + T (d -4) v w 1 w 2 u 1 u 2
T (d) ≤ T (d -5) + T (d -6) + T (d -9) v w 1 w 2 w 3 u s t
T (d) ≤ 2T (d -5)
we may now assume that no u i is dominated. We have to consider wether they are adjacent or not.

If say u 1 and u 2 are adjacent, then we apply Proposition 3 (in the specific case the vertex we branch has at least one neighbor of degree 4): if we add u 1 to the solution, we decrease d by at least 6; on the other hand,if u 1 does not belong to optimal, we decrease it by 3. Hence, we could write

Q(d) ≤ T (d -6) + T (d -3).
If no u i is adjacent to any other u j , this time if we try to use proposition 3 we cannot assert that two degree 4 vertices are adjacent, that would mean decreasing d only by 5. Fortunately, it is possible to prove that Γ(u 1 ) does not have more than one inner edge. Indeed, assume that it has two inner edges; since, before branching on v, we assumed that the graph does not contain any 3-clique, then the unique possibility is described in Figure 6. It means that, before branching on v, our graph contained two pentagons sharing two edges (edges (w 1 , u 1 1 ) and (w 1 , u 2 1 )). This is in contradiction with hypothesis of proposition 6. Hence, in this case also

Q(d) ≤ T (d-6)+T (d-3). v w 1 u 2 1 u 1 1
(d) ≤ T (d -5) + Q(d -2) ≤ 2T (d -5) + T (d -8). This sums up to T (d) = O * (1.2076 d ).
We make a final remark that further improves the running time. Indeed, we will see that after performing the branching on u 1 , then there exists another vertex of degree 4 in the remaining graph (or an even better case occurs). By branching on it, we decrease d either by 3 or by 5 (Proposition 3). This leads to Q(d) ≤ T (d-6)+T (d-3-3)+T (d-3-5) = 2T (d-6)+T (d-8), and finally T (d) ≤ T (d -5) + 2T (d -8) + T (d -10), as claimed in the proposition. To see this, consider two cases. If say u and u 2 are not adjacent, then when branching along the branch "take u 1 ", u 2 will still have degree at least 4 (or would have been deleted by domination which is even better).

The difficult case occurs when u 1 , u 2 and u 3 form a clique. Let s and t the two neighbors of u 1 with degree 3 (see Figure 7).

Dealing with trees

As noticed in [START_REF] Fürer | A faster algorithm for finding maximum independent sets in sparse graphs[END_REF], we have to be careful with our previous analysis. Indeed, the adopted measure d = mn creates a somehow unexpected problematic situation, occurring when several connecting components are created when branching, one or several of them being tree(s). Indeed, applying preprocessing rules immediately reduces a tree to a single vertex, which can be added to the solution. However, when removing this vertex (i.e. when dealing with the tree), the measure mn increases. In other words, when creating a tree, if the measure globally decreases by say x, it decreases only by x -1 in the remaining graph, tree excepted.

To deal with this situation, we study the situations when one or several tree(s) are created when branching. We show that in these particular cases the number of edges deleted is sufficient to compensate the loss induced by the tree(s).

To obtain this, we use a property shown by Fürer [START_REF] Fürer | A faster algorithm for finding maximum independent sets in sparse graphs[END_REF] that handles the case where there is a separator of size one or two in the graph. More precisely, if there exists one vertex u or a couple of vertex (u 1 , u 2 ) the deletion of which disconnects the graph, creating one connecting component of say constant size, then this connected component can be eliminated before branching. This reduction, not increasing d, can be added for instance to the preprocessing step.

Let us consider that we branch on a vertex v. As pointed out by Fürer [START_REF] Fürer | A faster algorithm for finding maximum independent sets in sparse graphs[END_REF], if we don't take v, then no tree can be created (since every vertex of the graph has degree at least 3).

Let us concentrate now on the case when taking v. Note that since each vertex in the graph has degree 3, when a tree with r vertices is created, at least r + 2 edges link one vertex of the tree to one vertex of Γ(v). If v has degree 3 (the graph is three regular), if a tree is created, this tree is a single vertex w linked to the 3 vertices in Γ(v). Indeed, each vertex in Γ(v) has at least one edge linking it to the rest of the graph (else there would be a separator of size 2), hence at most one edge linking it to the tree. In this case, the graph reduces (before branching on v): we delete v and w and merge the vertices in Γ(v) in a single vertex. We delete 6 edges and 4 vertices, hence d decreases.

Assume now that deg(v) ≥ 4.

Let us note by:

• |I| (as previously) the number of edges linking two vertices in Γ(v);

• l the number of trees created when branching on v (taking v);

• t the number of edges linking a vertex in Γ(v) to a vertex in one of the trees created;

• e the number of edges linking one vertex of Γ(v) to the rest of the graph;

• D = deg(w) for w ∈ Γ(v).

When branching on v, either we don't take v and d ′ = ddeg(v) + 1 ≤ d -3, or we take v. In this latter case: we delete 1 + deg(v) vertices v and Γ(v), deg(v) + |I| + t + e edges adjacent to vertices in Γ(v), and we loose 1 for each tree created. Hence, after handling the tree(s), d has globally decreased by: δ = |I| + t + e -1l. Note that t ≥ 3 (or we have a separator of size 2 or less) and e ≥ 3l (at least 3 edges for each tree). Hence: δ ≥ |I| + 3 + 3l -1l ≥ 2 + 2l. In particular, if l > 1 then δ ≥ 6.

If l = 1, then δ = |I| + t + e -2. D = 2|I| + t + e + 4. Then δ = D/2 + t/2 + e/2 -4. Since e ≥ 3 and t ≥ 3, if D ≥ 13 then δ ≥ 13/2 -1. Since it is an integer, δ ≥ 6.

The only remaining case is D = 12 (hence deg(v) = 4 and each vertex in Γ(v) has degree 3), t = 3 and e = 3 (see Figure 8). But in this case, the tree separated has only one vertex w. Then, the only inner edge in Γ(v) is incident to the vertex s in Γ(v) non adjacent to w (otherwise there would be a dominated vertex), as depicted in Figure 8. Hence, it is never interesting to take s in the solution (take either v or t instead), and we don't need to branch.

The concluding theorem

The analysis provided in Sections 2,3 and 4 allows to state the following result.

Theorem 1 .

On any graph, it is possible to solve max independent set with running time O * (1.2048 m-n ). In particular, a solution to 3-MIS may be computed with running time O * (1.0977 n ).

Figure 2 :Figure 3 : 3 Proposition 6 .

 2336 Figure 2: Clique {a, b, c}

Figure 4 :

 4 Figure 4: u 1 , u 2 both adjacent to w 1 and w 2

Figure 5 :

 5 Figure 5: u adjacent to w 1 and w 2

Figure 6 :

 6 Figure 6: Two pentagons sharing two consecutive edges

••

  If s and t are adjacent, then in Γ(u 1 ) there are only 2 edges (the other one being (u 2 , u 3 )), otherwise s or t would dominate u 1 . Hence, when taking u 1 , we delete 12 edges and 5 vertices, which meansQ(d) ≤ T (d -3) + T (d -7), i.e. T (d) ≤ 2T (d -5) + T (d -9). If s and t are not adjacent, Q(d) ≤ T (d -3) + T (d -6)but when reducing s and t (after taking u 1 ), we are in one of the two cases of Remark 1, i.e. either d decreases and Q(d) ≤ T (d -3) + T (d -7), or a degree 4 vertex is created. The analysis of the solutions of the equations induced by the previous analysis shows that the worst case running time corresponds to the case T (d) ≤ T (d -5) + 2T (d -8) + T (d -10), which sums up to T (d) = O * (1.2048 d )

Figure 7 :

 7 Figure 7: u 1 , u 2 and u 3 is a clique

Figure 8 :

 8 Figure 8: Taking s is never interesting