Mathias Weller

Annie Chateau

Clément Dallard

Rodolphe Giroudeau

Scaffolding problems revisited: Complexity, Approximation and Fixed Parameter Tractable algorithms, and some special cases

Keywords: Scaffolding Problems Revisited: Complexity, Approximation and Fixed Parameter Tractable Algorithms, and Some Special Cases

HAL is

Introduction

A lot of problems inspired by bioinformatics concerns may be formalized as combinatorial optimization problems on graphs. We focus in this paper on the genome scaffolding problem, which is of great importance when producing a genomic sequence from the real DNA molecule. Sequencing produces a huge amount of small sequences on the nucleotide alphabet {A, T, G, C}, called reads, whose overlaps are exploited to produce numerous sequences of various length, called contigs, during the assembly process. To complete the whole genome sequence, those contigs must be relatively ordered and oriented. In previous work on scaffolding, this problem has been modeled as a combinatorial problem on graphs which is, unfortunately, computationally hard [START_REF] Chateau | A complexity and approximation framework for the maximization scaffolding problem[END_REF]. Some methods use heuristic ways to simplify the graph [START_REF] Gao | Opera: Reconstructing Optimal Genomic Scaffolds with High-Throughput Paired-End Sequences[END_REF], others use a decomposition of the problem into two separate steps (orienting and ordering), whose difficulty could be bypassed under certain restrictions [START_REF] Dayarian | SOPRA: Scaffolding algorithm for paired reads via statistical optimization[END_REF]. A good presentation of the mainly used recent methods can be found in [START_REF] Hunt | A comprehensive evaluation of assembly scaffolding tools[END_REF].

The following work is based on a simple formulation of input data and problem. We introduce the notion of scaffold graph, that is, an undirected graph for which an initial perfect matching is given. Edges in the matching represent the contigs, whereas other edges represent witnesses for the relative locations of the contigs. These latter edges are weighted by a flexible confidence measure that can be read from the sequencing data or mixed with, for example, ancestral support in a phylogenetic context. Then, the scaffolding problem consists in finding at most a number of σ p paths and σ c cycles that, together, cover all matching edges (contigs). We formally describe this problem in Section 2.

In previous works, we stated that the problem is N P-complete, even in bipartite and planar graphs, and initiated the quest to the frontier between polynomial-time solvability and N P-completeness [START_REF] Chateau | Complexity and Polynomial-Time Approximation Algorithms around the Scaffolding Problem[END_REF][START_REF] Chateau | A complexity and approximation framework for the maximization scaffolding problem[END_REF]. The beginnings of these results are presented in [START_REF] Weller | On the complexity of scaffolding problems: From cliques to sparse graphs[END_REF]. Aiming to circumvent the problem, we consider two classes of graphs, described in Section 2.

Exploring the structure of the scaffold graphs on real instances, we noted that many vertices of the scaffold graph have small degrees, leading to overall sparsity [START_REF] Weller | Exact approaches for scaffolding[END_REF][START_REF] Weller | On the implementation of polynomial-time approximation algorithms for scaffold problems[END_REF]. We aim to exploit this property to design algorithms tuned to instances occurring in practice. Since Scaffolding can be solved in polynomial time on graphs that are close to trees by measure of "treewidth" [START_REF] Weller | Exact approaches for scaffolding[END_REF], we are interested in other distance measures to trees. To this end, we consider the class of graphs that can be turned into a (linear) forest by removing the edges of the given perfect matching M * from it ("quasi forest"). In this paper, we consider Scaffolding on graphs G such that G -M * is a linear forest, a forest, a tree, or a path and show that the problem remains N P-hard even for very restricted inputs. We reduce the N P-complete Weighted 2-SAT problem to it, allowing the inheritance of various hardness results of this problem. We are also tackling the problem from the angle of the parameterized complexity, exploring the existence or non-existence of polynomial kernel for the problem in the hope of developing an fixed-parameter tractable algorithm. Section 3.3 describes how cross-composition leads to a negative result in quasi-forests. We consider also dense graphs who we know are susceptible to polynomial-time approximation algorithms [START_REF] Chateau | Complexity and Polynomial-Time Approximation Algorithms around the Scaffolding Problem[END_REF][START_REF] Chateau | A complexity and approximation framework for the maximization scaffolding problem[END_REF]. We focus on dense graphs which are not entirely complete, yet allow encoding some structure, namely cobipartite and split graphs. On co-bipartite graphs, the unweighted version of the scaffolding problem becomes polynomial-time solvable, which is a first step towards designing algorithms for the general problem on these graphs. We consider a slightly relaxed version of the problem to improve the known approximation algorithm on complete graphs [START_REF] Chateau | A complexity and approximation framework for the maximization scaffolding problem[END_REF] to a ratio of two.

To complete this overview of the various tracks allowing relevant results on the subject, we have also been interested in variations of the problem, inspired by the work on the minimum spanning tree and other classical combinatorial optimization problems [START_REF] Bazgan | Critical edges/nodes for the minimum spanning tree problem: complexity and approximation[END_REF][START_REF] Bazgan | Blockers for the stability number and the chromatic number[END_REF][START_REF] Bazgan | A refined complexity analysis of finding the most vital edges for undirected shortest paths[END_REF]. These variants aim to detect critical subsets of edges or nodes in the graph, which can be used to detect a skeleton that we do not further question, and decrease the time consumption of an exact search on remaining edges. Unfortunately, we show that the problem to find such set of edges is also a difficult problem in Section 5.

The complexity and approximation results are respectively summarized in Table 1 and Table 2. Next section is devoted to formal description of problems.

The paper is organized as follows: Section 2 is devoted to a global presentation of problems, classes of graphs and technical issues. In Section 3 overview of the problems which remains hard, even with very strong constraints on parameters of the problem, structure of the graphs, or weights. After this depressing review, we focus on the hopeful part of the work, in Section 4. Afterwards, we enlarge our point of view by considering several variants of the problem, unfortunately all N P-complete, in Section 5.

Notation and problem description

Let G = (V, E) be a graph. For a vertex set V ⊆ V , let G[V ] denote the subgraph of G induced by V and let G -V := G[V \ V ].
Further, for any S ⊆ E, we define Gr(S) := ( e∈S e, S) and G -S := (V, E \ S). An edge-set M * of a graph is called matching if no two of its edges intersect, that is, e 1 ∩ e 2 = ∅ for all distinct e 1 , e 2 ∈ M * . A matching M * is perfect if it covers all the vertices, that is V = e∈M * e. A pair (G, M * ) where M * is a perfect matching on G is called a scaffold graph. For a matching M * and a vertex u, we define M * (u) as the unique vertex v with uv ∈ M * if such a v exists, and M * (u) = ⊥, otherwise. We abbreviate X -{x} =: X -x for any set X of elements of the same type as x. Slightly abusing notation, we identify a path with the set of its edges. A path p is alternating with respect to a matching M * if, for all vertices u of p, also M * (u) is a vertex of p. Thus, alternating paths have an even number of vertices. If M * is clear from context, we do not mention it explicitly. For a function ω : E → N and a set S ⊆ E, we abbreviate e∈S ω(e) =: ω(S) and we let ω max := max e∈E ω(e). Thus, ω max = 1 (resp. = 0) means that the weights can take only two values (resp. one value). The center of this work is the following problem.

Scaffolding (SCA)

Input: G = (V, E), ω : E → N, perfect matching M * in G, σ p , σ c , k ∈ N Question:
Is there an S ⊆ E \ M * such that Gr(S ∪ M * ) is a collection of ≤ σ p alternating paths and ≤ σ c alternating cycles and ω(S) ≥ k?

If ω is uniform, that is, all edges have same weight, then we call the problem unweighted Scaffolding (USCA). The variant of the problem that asks for exactly σ p paths and exactly σ c cycles is called Strict Scaffolding (SSCA). When we want to precise particular values for σ p and σ c , we refer to the problem as (σ p , σ c )-Scaffolding. If we are looking for paths and cycles of fixed lengths p and c , we replace σ p and σ c by pairs (σ p , p ) and (σ c , c ) (length means the number of edges). We refer to the optimization variants of Scaffolding that ask to minimize or maximize ω(S) as Min Scaffolding and Max Scaffolding, respectively.

Classes of graphs.

A graph is bipartite if it does not contain an odd cycle or, equivalently, if it admits a proper vertex two-coloring. It is usually given by a partition X = X 1 X 2 . A tripartite graph is similarly defined as a graph which can be colored with three colors, so that no two endpoints of an edge have the same color. A graph is co-bipartite if its complement is bipartite. Thus, a co-bipartite graph can also be considered as a pair of disjoint cliques, with some edges between them. A co-tripartite graph is a graph whose complement is tripartite. For disjoint I and C, a graph G = (I ∪ C, E) such that I is an independent set, and C induces a clique in G, is called split graph. A scaffold graph (G, M * ) is called quasi-forest (resp. quasi-tree or quasi-path) if G -M * is a forest (resp. tree or path). The scaffold graph on Figure 1 is a quasi-forest. A quasi-forest is linear if it is a collection of paths.

Approximation algorithm. The main issue in approximation point of view consists in determining how close a polynomial-time algorithm can approach the optimal solution. Such polynomial-time algorithms producing solutions that are provably within a certain margin of the optimal are called approximation algorithms. Formally, the approximation-ratio of an algorithm A for a maximization problem is defined as ρ := max I A(I)

OP T (I) , where OP T (I) is the optimal value of the instance I.

Lower bounds. The Exponential-Time Hypothesis [START_REF] Impagliazzo | On the Complexity of k-SAT[END_REF][START_REF] Impagliazzo | Which problems have strongly exponential complexity?[END_REF] states that there is some c > 1 such that n-variable 3-Satisfiability cannot be solved in c n poly(n) time. Using polynomial reductions, it is possible to deduce some lower bounds on time-complexity for other problems.

Parameterized algorithms. An interesting way to tackle N P-hard problems is parameterized complexity. A parameterized problem Q is a subset of Σ * × N, where the second component is called the parameter of the instance. A fixed-parameter tractable (FPT for short) problem is a problem for which there exists an algorithm which, given 1) for some computable function f . Such an algorithm becomes efficient with an hopefully small parameter. A kernel is a polynomial algorithm which, given

(x, k) ∈ Σ * × N, decides whether (x, k) ∈ Q in time f (k)|x| O(
(x, k) ∈ Σ * × N, outputs an instance (x , k ) such that (x, k) ∈ Q ⇔ (x , k ) ∈ Q and |x | + k ≤ f (k)
for some computable function f . For decidable problems, the existence of a kernel is equivalent to the existence of an FPT -algorithm. Nevertheless one can ask the function f to be a polynomial. If so, then the kernel is called a polynomial kernel. If a problem admits a polynomial kernel, then it roughly means that we can, in polynomial time, compress the initial instance into an instance of size poly(k) which contains all the hardness of the instance.

When it is hard

In this section, we focus on hard cases that we met during our attempts to determine the frontier between polynomiality and N P-completeness. In all those attempts to simplify the problem, we use polynomial reduction from very well-known problems, such as Directed Hamiltonian Path, Partition into Triangle, or Weighted 2-SAT.

In the following paragraphs, we use a reduction from the Directed Hamiltonian Path (resp. Directed Hamiltonian Cycle) ( [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]) and some variations of this reduction. Thus, we define a basic construction that is a starting point to other constructions.

Directed Hamiltonian Path/ Cycle (DHP / DNC) Input: A directed graph G without self loop Question: Does G contain a simple path visiting all vertices? E) as follows (see Figure 2).

v 0 v 1 v 2 v 3 v 1 0 v 2 0 v 3 0 v 4 0 v 1 1 v 2 1 v 3 1 v 4 1 v 1 2 v 2 2 v 3 2 v 4 2 v 1 3 v 2 3 v 3 3 v 4 3
Construction 1. Let G = (V = {v 1 , v 2 , . . . , v n }, A) be an instance of DHC. We construct G = (V 1 V 2 ,
V 1 := {v 1 i , v 3 i | v i ∈ V } V 2 := {v 2 i , v 4 i | v i ∈ V } E := {v 1 i v 2 i , v 2 i v 3 i , v 3 i v 4 i | v i ∈ V } ∪ {v 4 i v 1 j | v i v j ∈ A}.
Finally, let

M * := {v 1 i v 2 i , v 3 i v 4 i | v i ∈ V }, let ω : E → {0}
, and let k := 0.

To solve

3.1.1 Decision problem with strong constraints on (σ p , p ) and (σ c , c )

In [START_REF] Chateau | A complexity and approximation framework for the maximization scaffolding problem[END_REF], we proved that, when the number of edges in the matching is equal to σ p + 2σ c , the (σ p , σ c )-Strict Scaffolding problem is polynomial, because it forces cycles to have length four. We also proved that, for cycle length equal to six, it is N P-complete. We investigate in this section the complexity of (σ p , σ c )-Strict Scaffolding (decision problem) in planar bipartite graphs in presence of one path and cycles of length four. We show that the problem remains N P-complete. The reduction relies on the following polynomial-time transformation, based on Construction 1. Notice that DHP remains N P-complete for planar directed maximumdegree-3 graphs ( [START_REF] Plesník | The np-completeness of the hamiltonian cycle problem in planar digraphs with degree bound two[END_REF]). Let K be an arbitrary constant.

Construction 2. Let G = (V, A) an instance of the Directed Hamiltonian Path problem. We construct the following graph G = (V , E), obtained from G by Construction 1 and add cycles (y 1 j , y 2 j , y 3 j , y 4 j ), ∀j ∈ {1, . . . , K}, add arbitrary edges {{u 1 y 1 j }, ∀j ∈ {1, . . . , K} to E, add edges {y 1 j , y 2 j } and {y 3 j , y 4 j } in M * , ∀j ∈ {1, . . . , K} Theorem 1. The problem ((σ p , p ), (σ c , c ))-Strict Scaffolding with parameters (σ p , p ) = (1, |V | -4K -1) and (σ c , c ) = (K, 4)) is N P-complete, even if the graph is a planar cubic bipartite graph. Assuming the Exponential-Time Hypothesis, there exists no hope to find a algorithm in O(2 o( √ n) ) time for the ((σ p , p ), (σ c , c ))-Strict Scaffolding in presence of a bipartite planar graphs even with cycle of length four.

Proof. Since in the transformed instance there is no other cycles of length four than the added ones, it is clear that it exists a positive solution for Directed Hamiltonian Path if and only if it exists a positive solution for ((σ p , p ), (σ c , c ))-Strict Scaffolding with (σ p , p ) = (1, |V | -4K -1) and (σ c , c ) = (K, 4)). Moreover, the previous polynomial-time transformation is linear which implies the results for subexponentialtime algorithm.

Corollary 1. There is no hope to find a polynomial-time approximation algorithm within a ratio ρ < 5/4 (resp. a X P-algorithm for Scaffolding parameterized by number of cycles).

Again, using Construction 1, we can show that Scaffolding is N P-complete on a very restricted class of graphs.

Theorem 2. Unweighted Scaffolding is N P-complete on bipartite planar graph with maximum degree three, even if σ p = 0 and σ c = 1.

Proof. The problem is clearly in N P. We show that it is also N P-hard by proving that G has a Hamiltonian cycle if and only if G has an alternating Hamiltonian cycle with respect to M * . "⇒": Let C be a Hamiltonian cycle in G. Then,

S := {v 2 i v 3 i | v i ∈ V } ∪ {v 4 i v 1 j | v i v j ∈
C} is a feasible solution, and Gr(S ∪ M * ) is an alternating Hamiltonian cycle with respect to M * . "⇐": Let S be a matching in G -M * such that C := Gr(S ∪ M * ) is an alternating Hamiltonian cycle in G with respect to M * . Since C contains v 3 i v 4 i for each v i ∈ V (because they are all in M * ) and C is a cycle, we know that S contains n edges of the form v 4 i v1 j for v i v j ∈ A. Since S is a matching in G -M * , no two of these edges are adjacent. Now, C := {v i v j | v 4 i v 1 j ∈ S } is a collection of cycles covering all vertices of V in G. However, if C induces more than one cycle in G, then so does S ∪ M * in G . Therefore, C is a Hamiltonian cycle in G.

By construction, G is a bipartite planar graph with Max-Degree 3 according to Transformation 1 since Directed Hamiltonian Cycle remains N P-complete for planar graph with Max-Degree 3 (see [START_REF] Plesník | The np-completeness of the hamiltonian cycle problem in planar digraphs with degree bound two[END_REF]).

Weighted cases in dense graphs

Note that we can change Construction 1 such that ω : E → {1} and k := 4n. This further enables us to add any number of edges of weight 0 without affecting the correctness argument. This implies that Scaffolding is N P-complete on, for example, split graphs and co-bipartite graphs.

Corollary 2. Let G be a class of graphs such that, for each bipartite graph G there is a supergraph of G in G. Scaffolding is N P-complete on G, even if σ p = 0 and σ c = 1 and ω max = 1.

Construction 1 also implies subexponential lower bounds for our problems based on the widely believed complexitytheoretic hypothesis known as the "Exponential-Time Hypothesis" 1 (ETH, see [START_REF] Impagliazzo | Which problems have strongly exponential complexity?[END_REF][START_REF] Woeginger | Exact algorithms for np-hard problems: A survey[END_REF]). In fact, the lower bound is established directly from the fact that (planar) Directed Hamiltonian Cycle does not admit a O(2 o(|E(G)|) )-time algorithm [START_REF] Lokshtanov | Lower bounds based on the exponential time hypothesis[END_REF]Theorem 3.5] and that Construction 1 only linearly blows up the instance size.

Corollary 3. Let G be a class of graphs such that, for each bipartite graph G there is a supergraph of G in G. Assuming ETH, there is no 2 o(|E(G)|) -time algorithm for Scaffolding on G, even if σ p = 0 and σ c = 1 and ω max = 1.

Weighted cases in sparse graphs

The hardness of Scaffolding for dense graphs proved by Theorem 2 motivates the search for tractable cases among classes of sparse graphs. It is known that Scaffolding is polynomial-time solvable on graphs that are close to being a forest (constant treewidth) [START_REF] Weller | Exact approaches for scaffolding[END_REF], so we consider a different sparsity measure here. We investigate whether Scaffolding becomes polynomial-time solvable if the result of removing the given perfect matching M * from G forms a forest. We call this class of graphs "quasi forests". Remark that real scaffold graphs are not always quasi-forest, however this is a first step towards their structure. We start off by modifying Construction 1 to make the resulting graph a quasi tree (see Construction 3 and Figure 3). Unfortunately, this requires fixing the length of the sought Hamiltonian cycle. To circumvent this, we present another construction, reducing the N P-complete Weighted 2-SAT to Scaffolding, that does not require fixing the lengths.

Construction 3. Let G = (V, A) be an instance of Directed Hamiltonian Cycle, with V = {v 1 , v 2 , . . . , v n }.
We construct G = (V , E) from G as follows:

• For each u ∈ V , we construct a "vertex-path" P 4,u = (u 1 , u 2 , u 3 , u 4 ), and we call {u 2 , u 3 } an inner edge.

The set of all such paths is denoted by P 4 = u∈V P 4,u

• For each (u, v) ∈ A, we construct an "edge-path" with four vertices, denoted P E 4,uv = (uv 1 , uv 2 , uv 3 , uv 4 ) and the two edges {u 4 , uv 1 }, {uv 4 , v}.

• We add a path Z = (z 1 , z 2 , z 3 , z 4 ) plus the edges {z 1 , z 3 } and {z 2 , z 4 }.

• For each vertex u ∈ V , we add the edges

{u 1 , z 1 }, {u 2 , z 1 }, {u 4 , z 1 }. For each (u, v) ∈ A, we add the edge {uv 2 , z 1 }. • M * := {{u 1 , u 2 }, {u 3 , u 4 } | u ∈ V } ∪ {{uv 1 , uv 2 }, {uv 3 , uv 4 } | (u, v) ∈ A} ∪ {{z 1 , z 2 }, {z 3 , z 4 }}. Lemma 1. G -M * is a tree.
Proof. First, G -M * is a connected graph since all vertices, except z 1 are connected to z 1 . To show that G -M * has no cycles, we count the number of edges in G -M * . For each v ∈ V , we have the edges x 1

{z 1 , v 1 }, {v 2 , v 3 }, {z 1 , v 2 },
x 5 u 3 1 v 3 1 u 3 1 v 3 1 v 2 1 u 4 1 v 2 1 u 4 1 ε 3 1 ε 3 1 e 3 1 C 3 a 3 1 d 3 1 b 3 1 c 3 1 b 3 5 c 3 5 a 3 5 d 3 5 (a) x1 ∨ x5 satisfied by x1 = 1.
x 1 Proof. Clearly, the problem is in N P. We show that Construction 3 is correct, that is, G has a Hamiltonian cycle if and only if (G , M * ) can be covered by |E| -n + 1 paths of length 3 and 1 cycle of length 8n. "⇒": Let C = (v 1 , v 2 , . . . , v n ) be a directed Hamiltonian cycle in G. We construct a solution for the Scaffolding-instance as follows: The alternating cycle of length 8n consists of the vertex-paths P 4,vi for all i ≤ n and the edge-paths P E 4,uv with (u, v) ∈ C. A path of length 3 is given by Z, the remaining paths are given by the paths-edges P E 4,uv such that (u, v) / ∈ C. "⇐": Suppose there is a set of one alternating cycle C of length 8n and |E| -n + 1 alternating paths of length 3. Clearly, the vertices of Z are not in C and therefore, they are included in a path of length 3. Thus, the edges {z 1 , x} for each x ∈ V \ {z 2 , z 3 , z 4 } cannot be used in the covering. By construction, vertex-paths (resp. edge-paths) cannot appear consequently in C. Since each vertex-and edge-path contains exactly four vertices and C has 8n vertices, C alternately contains n vertex-paths and n edge-paths. Then, a Hamiltonian cycle in G is given by the order of the vertex-paths in C.

Note that we had to fix the lengths of the paths and cycles we are looking for in the Scaffolding-instance.

To show that Scaffolding is also hard on quasi-forests without restricting the lengths, we give another reduction from the N P-complete Weighted 2-SAT problem (see [START_REF] Alimonti | On the complexity of approximating weighted satisfiability problems[END_REF]) to Scaffolding.

Weighted 2-SAT Input: n variables x i with weights w i ≥ 0, m size-two clauses, k ∈ N Question: Is there a truth assignment β s.t.,

i | β(xi)=1 w i ≥ k?
The optimization variants of Weighted 2-SAT that ask to find a satisfying assignment β that minimizes or maximizes i | β(xi)=1 w i are called Min W2SAT and Max W2SAT, respectively. Construction 4. Let (ϕ, k) be an instance of Weighted 2-SAT with n variables x 0 , x 1 , . . . , x n-1 and m clauses C 0 , C 1 , . . . , C m-1 . We produce the following instance (G, ω, M * , n, 0, k) of Scaffolding (see Figure 4), that we denote Γ(ϕ, k). For each variable x i and for each 0

≤ j ≤ m, introduce • vertices u j i , u j i , v j-1 i ,v j-1 i , • edges u j i u j i ,v j-1 i v j-1 i that are also added to M * , • edges ε j-1 i := v j-1 i u j i , and ε j-1 i := v j-1 i u j i . • for j < m, if C j contains x i , the edge e j i := u j i v j i , otherwise, e j i := u j i v j i .
For each clause C j on the variables x 0 and x 1 , introduce

• for each i ∈ { 0 , 1 }, -vertices a j i , b j i , c j i , d j i -edges a j i b j i and c j i d j i that are added to M * and b j i c j i , -if C j contains x i , edges u j i a j i , v j i d j i , otherwise, u j i a j i , v j i d j i , • edges a j 0 c j 1 , c j 0 a j 1 , b j 0 d j 1
, and d j 0 b j 0 . Finally, set ω(ε m-1 i ) := 1 for each variable x i and set the weights of all other edges to 0. Lemma 2. Construction 4 is correct, that is, ϕ has a satisfying assignment of weight k if and only if (G, ω, M * , n, 0, k) is a yes-instance of Scaffolding.

Proof. "⇒": Let β denote a solution for (ϕ, k). Then, we construct a solution S for (G, ω, M * , n, 0, k) as follows. For each variable x i and each 0

≤ j ≤ m, if β(x i ) = 1 then include {e j i , ε j i } ∩ E(G) in S, otherwise include {e j i , ε j i } ∩ E(G) in S.
For all clauses C j , if exactly one of its literals is true, include edges according to Figure 4a, if both its literals are true, include edges according to Figure 4b in S. Then, S ∪ M * contains exactly 1 alternating path for each of the n variables and, since ε m-1 i ∈ S for each x i with β(x i ) = 1, the weight of S equals the weight of β, which is at least k.

"⇐": Let S be a solution for (G, ω, M * , n, 0, k). Note that S ∪ M * contains at most n paths and no cycles. Since Gr(S ∪ M * ) does not contain cycles, for each i < n and j ≤ m we have ε j i / ∈ S or ε j i / ∈ S. This implies that, for each i < n there is a path ending at u m i or u m i and there is a path ending at v -1 i or v -1 i . Since there are at most n paths in Gr(S ∪ M * ), the "or" above are exclusive and all other vertices have degree exactly two in Gr(S ∪ M * ), implying that all other vertices are incident to exactly one edge in S.

(

Next, we show for all i < n and j < m that

u j i a j i ∈ S ⇐⇒ v j i d j i ∈ S. (2)
To show u j i a j i ∈ S ⇒ v j i d j i ∈ S, assume u j i a j i ∈ S and v j i d j i / ∈ S. Then, either b j i c j i ∈ S or b j i d j ∈ S for some = i. In the first case, we have d j i b j ∈ S and, thus, c j cannot have an incident edge in S without violating (1). In the second case, note that the only edges incident to c j i and d j i that could be in S without violating (1) are c j i a j and d j i b j , respectively. However, if both are in S, then Gr(S ∪ M * ) contains a forbidden cycle. The direction v j i d j i ∈ S ⇒ u j i a j i ∈ S can be shown analogously. Next, we show for each i < n and j ≤ m, that ε j i ∈ S or ε j i ∈ S, implying

ε j i ∈ S ⇐⇒ ε j i / ∈ S. (3)
This is easy to see for j = m since one of u m i and u m i has degree 2 in Gr(S ∪ M * ). So let the claim hold for j + 1 but not for j, that is, Next, we show for each i < n and j < m that

ε j i , ε j i / ∈ S. If x i is not contained in C j ,
ε j i ∈ S ⇐⇒ ε j-1 i ∈ S. (4)
Note that, by (3) it is sufficient to prove

ε j i ∈ S ⇒ ε j-1 i ∈ S and ε j i ∈ S ⇒ ε j-1 i ∈ S.
Consider some i < n and j < m such that ε j i ∈ S. Then, by (1), we have v j i d j i / ∈ S and e j i / ∈ S. By (2), it follows that u j i a j i / ∈ S and, thus, by (1), ε j-1 i ∈ S. Note that ε j i ∈ S ⇒ ε j-1 i ∈ S can be shown analogously. Finally, we define the assignment β for ϕ as β(

x i ) = 1 ⇐⇒ ε m-1 i ∈ S. Then, since ω(ε m-1 i ) = 1
for all i < n, we know that β assigns 1 to at most k variables. It remains to show that β satisfies ϕ. To this end, assume that a clause C j is not satisfied and let x i and x denote the variables occuring in C j . Note that at least one of the edges u j i a j i , u j i , u j a j , and u j a j is in S since, otherwise, none of the n paths ending in the variable gadgets can visit the clause gadget of C j . Since the prove is symmetric in all four cases, let us assume u j i a j i ∈ S. Then, C j contains x i non-negated. By (1), we have ε j-1 i / ∈ S, which, by (3) implies ε j-1 i ∈ S and, by (4), we arrive at ε m-1 i ∈ S. Thus, β(x i ) = 1 and, thus, C j is satisfied by β.

Since Weighted 2-SAT is known to be W [START_REF] Alimonti | On the complexity of approximating weighted satisfiability problems[END_REF]-hard with respect to k (that is, an algorithm that is exponential only in k is unlikely to exist [START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF]), by Lemma 2, so is Scaffolding.

Theorem 4. Scaffolding is N P-hard and W[1]-hard with respect to k, even on bipartite graphs G with G -M * being a linear forest, ω max = 1 and σ c = 0. Construction 4 can be modified to restrict the problem even further: consider two paths p = (v 0 , v 1 , . . .) and q := (u 0 , u 1 , . . .) in G -M * . We can add new vertices α j , β j , γ j with j ∈ {u, v} with matching edges α u α v , β u γ u , β v γ v and non-matching edges γ u γ v , v 0 α v , u 0 α u of weight 0 and non-matching edges α u β u , α v β v of weight n + 1. Finally, we ask for a solution of weight 2n(n + 1) + k containing σ p := 2n paths. Then, since all solutions have to contain the heavy edges α u β u and α v β v , no solution can contain either u 0 α u or v 0 α v and, thus, any solution contains a solution for the original instance. In analogy with Corollary 3, Construction 4 implies subexponential-time lower bounds for exact algorithms.

Corollary 5.

• Assuming ETH, there is no 2 o(|E(G)|) -time algorithm for Scaffolding, and,

• assuming W[1] = FPT , there is no n o(k) -time algorithm for Scaffolding, even if σ c = 0, ω max = 1, and G -M * is a linear forest.

Proof. We modify Construction 4 slightly such that the gadget for each variable x i contains a "module" (subgraph induced by u j i , u j i , v j i , and v j i ) only for the clauses it is actually contained in. Thus, the number of vertices and edges in the produced instance can be bounded linearly in the number of clauses of the Weighted 2-SAT instance. Then, since Independent Set does not have a 2 o(m) -time algorithm [START_REF] Impagliazzo | Which problems have strongly exponential complexity?[END_REF] (with m denoting the number of edges), Scaffolding does not have a 2 o(m) -time algorithm (unless the ETH fails).

Furthermore, note that k-Independent Set ≡ k-Weighted 2-SAT and that k-Weighted 2-SAT reduces to k-Scaffolding by Construction 4. Thus, since Independent Set does not have an n o(k) -time algorithm [START_REF] Chen | Tight lower bounds for certain parameterized NP-hard problems[END_REF], Scaffolding does not have an n o(k) -time algorithm (unless W[1] = FT P).

Note that all results in this section hold for any numbers σ p ≥ n and σ c ≥ 0 since we can add more paths artificially by adding isolated matching edges and we can add more cycles by adding new 4-cycles. Clearly, the isolated matching edges must constitute isolated paths. Further, if any isolated 4-cycle is covered by two paths, there are only (n -2) paths and a cycle to cover all of the u m i , u m i , v -1 i , v -1 i , which can be seen to be impossible.

To approximate

Furthermore, we derive inapproximability of Scaffolding from Construction 1.

Corollary 6. Let G be a class of graphs such that, for each bipartite graph G there is a supergraph of G in G.

For all ρ ∈ N, Min Scaffolding on G is N P-hard to approximate to within a factor of ρ, even if σ p = 0 and σ c = 1 and ω max = 1.

Proof. Suppose that there is a polynomial-time approximation algorithm A for this problem with approximation ratio ρ > 1. Let G = (V, E) be an instance of Directed Hamiltonian Cycle with |V | = n. We use Construction 1 to construct a bipartite graph G with matching M * . Then, we let ω : E → N such that ω(E 1 ) = 0 and set k := 0. Then, we can add any number of edges of weight 1 and no solution computed by A can contain any of these edges. Then, replacing 4n by 0 in 3.1.2 yields a proof for Corollary 6. Indeed, if G has a Hamiltonian cycle, then A finds a solution of weight ρ • 0 = 0. Conversely, if G does not have a Hamiltonian cycle, then at least one edge of weight 1 must be taken in a solution produced by A. Thus, A decides the N P-complete Directed Hamiltonian Cycle problem in polynomial time.

While there is little hope of finding a constant-factor polynomial-time approximation algorithm for Min Scaffolding, there is a linear-time algorithm with approximation ratio ωmax wmin (where ω max and ω min denote the respective maximum and minimum edge weights) on complete bipartite graphs with σ p = 0 and σ c = 1. This algorithm repeatedly chooses the lowest weighted edge that does not close the cycle.

Since Max W2SAT is N P-hard to approximate to within a factor of n 1-for any > 0 [START_REF] Alimonti | On the complexity of approximating weighted satisfiability problems[END_REF][START_REF] Håstad | Clique is hard to approximate within n 1-ε[END_REF] and the number of vertices in the instance produced by Construction 4 is bounded in the number of variables, we conclude that, in contrast to the factor-3 approximation for Scaffolding in complete graphs [START_REF] Chateau | A complexity and approximation framework for the maximization scaffolding problem[END_REF] (and the factor-2 approximation presented in subsubsection 4.1.1), the problem is hard to approximate in the restricted class described above.

Corollary 7. Max Scaffolding is N P-hard to approximate to within a factor of n 1 2for any > 0, even on bipartite graphs G with G -M * being a linear forest, ω max = 1 and σ c = 0.

For the minimization version, Min Scaffolding, we derive approximation hardness as well. To see this, note that Construction 4 is an S-reduction (see [START_REF] Crescenzi | A short guide to approximation preserving reductions[END_REF]) and Min W2SAT is APX -complete [START_REF] Alimonti | On the complexity of approximating weighted satisfiability problems[END_REF]. Thus, Min Scaffolding is APX -hard.

Corollary 8. Min Scaffolding is APX -hard even on bipartite cubic graphs G with G -M * being a linear forest, ω max = 1 and σ c = 0.

Curiously, the approximation hardness result for Min Scaffolding is weaker than that for Max Scaffolding, which contrasts earlier observations on general graphs [START_REF] Chateau | A complexity and approximation framework for the maximization scaffolding problem[END_REF]. Thus, we suspect that Corollary 8 can be strengthened to at least the same hardness-level as we have for Max Scaffolding (Corollary 7). To this end, we conjecture existence of a gap-preserving reduction from an N P-complete problem Π to Min Scaffolding with a nonconstant gap.

To find a polynomial kernel

In order to rule out polynomial kernels, we will use the recent technique of cross-composition [START_REF] Bodlaender | Kernelization lower bounds by cross-composition[END_REF]. Roughly speaking, a cross-composition is a polynomial reduction from t instances of a (non-parameterized) problem A to a single instance of a parameterized problem B such that the constructed instance is positive if and only if one of the input instances is positive. In addition, the parameter of the constructed instance must be of size polynomial in maximum size of the input instances and logarithm of t. It is known that if A is N P-hard and A cross-composes into B, then B cannot admit a polynomial kernel unless N P ⊆ coN P/poly2 .

Definition 1 (Polynomial equivalence relation [START_REF] Bodlaender | Kernelization lower bounds by cross-composition[END_REF]). An equivalence relation R on Σ * is called a polynomial equivalence relation if both following conditions hold:

• There is an algorithm that given two strings x, y ∈ Σ * , decides whether x and y belong to the same equivalence class in (|x| + |y|) O(1) time.

• For any finite set S ⊆ Σ * , the equivalence relation R partitions the elements of S into at most (max x∈S |x|) O (1) classes.

Definition 2 (OR-cross-composition (resp. AND) [START_REF] Bodlaender | Kernelization lower bounds by cross-composition[END_REF]). Let L ⊆ Σ * be a set and let Q ⊆ Σ * × N be a parameterized problem. We say that L OR-cross-composes (resp. AND-cross-composes) into Q if there is a polynomial equivalence relation R and an algorithm which, given t strings belonging to the same equivalence class of R, computes an instance

(x * , k * ) ∈ Σ * × N in time polynomial in t i=1 |x i | such that: • (x * , k * ) ∈ Q ⇔ x i ∈ L for some 1 ≤ i ≤ t (resp. for all 1 ≤ i ≤ t)
• k * is bounded by a polynomial in max t i=1 |x i | + log t Theorem 5 ([5]). If a set L ⊆ Σ * is N P-hard and L AND-cross-composes into the parameterized problem Q, then there is no polynomial kernel for Q unless N P ⊆ coN P/poly.

We now consider the following problem, which is a variant of Weighted 2-SAT, called Global Verification, in which we want to find a solution for a given value k, which is not a solution for k -1:

Weighted 2-SAT(GV) Input: ϕ a formula in 2 -CN F n variables x i with weights w i ≥ 0, m size-two clauses, k ∈ N Question: Is there a truth assignment β s.t.,

i | β(xi)=1 w i ≤ k and such that (ϕ, ω, k -1) / ∈ Weighted 2-SAT? Lemma 3. The problem Weighted 2-SAT(GV) is N P-complete.
Proof. The proof is based on a reduction from the N P-complete problem Vertex Cover(GV).

Vertex Cover(GV)

Input: G = (V, E) a graph, k ∈ N, and s.t. ∃|V C(G)| ≤ k -1 Question: Is there a vertex-cover V C(G) ⊆ V s.t. |V C(G)| ≤ k?
The N P-completeness of Vertex Cover(GV) cames from a reduction from the classic problem 3 -SAT : let I be a instance of 3 -SAT , and G = R(ϕ) the graph with 2n + 3m vertices, one vertex labelled in positive (resp. negative) form for each variable in 3 -SAT , and one triangle for one clause and n + 6m edges: 3m for triangles, n for the two labelled-joined vertices and 3m for the relation between vertices-triangles and labelled vertices such that if x occurs in clause C then it exists a edge (x, y) with y ∈ C-triangle. With this construction Vertex Cover(GV) is N P-complete by considering k = 2m + n. Now, we will prove the N P-completeness of Weighted 2-SAT(GV). Let G = (V, E) be a graph with n = |V | and m = |E| and k ∈ N * . An instance of Weighted 2-SAT(GV) is constructed the following way: ∀v ∈ V we create a weighted boolean variable ω(x v ) = c. ∀(u, w) ∈ E we add a clause of length two (x u ∨ x w ). The instance admits n variables and m clauses of length two. Notice that an instance may be designed as monotone Weighted 2-SAT(GV).

So, it is obvious that it ∃V C(G) ≤ k and ∃V C(G) ≤ k -1 if and only if there is a truth assignment β s.t.,

i | β(xi)=1 ω(x i ) ≥ k × c by considering V C = {v ∈ V |x v = 1}.
Construction 5. Let F = {(ϕ 1 , k), (ϕ 2 , k), ..., (ϕ t , k)} a set of t equivalent instances of Weighted 2-SAT(GV) (according to Definition 1). We use the Γ-transformation defined in Construction 4, in order to obtain the set of graphs S = {S 1 , S 2 , ..., S t }, with ∀i ∈ [1, t], S i = Γ(ϕ i , k). We note S = Λ(F), and G(S) = t i=1 S i . Lemma 4. Let F = {(ϕ 1 , k), (ϕ 2 , k), ..., (ϕ t , k)} and S = Λ(F).

Then (ϕ i , k) ∈ Weighted 2-SAT(GV) ∀i ∈ [1, t] iff G(S) ∈ Scaffolding with σ p = n × t, σ c = 0 and cost = k × t.
Proof. By definition of Weighted 2-SAT(GV), we know that ∀i, (ϕ i , k -1) is not satisfiable. Moreover, (ϕ, k) ∈ Weighted 2-SAT(GV) if and only if Γ(ϕ, k) ∈ Scaffolding with σ p = n × t, σ c = 0 and cost = k since Γ is a S-réduction, which is a strict reduction preserving the optimal cost (see Construction 4).

Therefore, we have Γ(ϕ, k -1) / ∈ Scaffolding with σ p = n × t, σ c = 0 and cost = k -1.

• If (ϕ i , k) ∈ Weighted 2-SAT(GV), ∀i ∈ [1, t], then Γ(ϕ i ) ∈ Scaffolding, ∀i ∈ [1, t] with σ p = n, σ c = 0 k = k i , and obviously G(S) ∈ SCA with σ p = n, σ c = 0, cost = k × t.
• If G(S) ∈ Scaffolding with σ p = n × t, σ c = 0 and cost = k × t: consider costs k i with Γ(ϕ i ) ∈ Scaffolding with σ p = n, σ c = 0, cost = k i , and

t i=1 k i = k×t. Since (ϕ i , k-1) / ∈ Weighted 2-SAT(GV), k i ≥ k, then ∀i, k i = k in
order to satisfy the sum. Theorem 6. Scaffolding in quasi-trees does not admit a polynomial kernel parameterized by treewidth, unless N P ⊆ coN P/poly.

Proof. Let F = {(ϕ 1 , k), (ϕ 2 , k), ..., (ϕ t , k)} be a set of t instances of Weighted 2-SAT(GV), equivalent according to Definition 1. Using Construction 4, we obtain the set of graphs S = {S 1 , S 2 , ..., S t }, with S i = Γ(ϕ i ), ∀i ∈ [1, t], and the graph G(S) = ∪ t i=1 S i . The graph G(S being the union of disjoint connected components, we have tw(G(S)) = max i∈[t] tw(S i ). The Γ-transformation ensures that for a formula ϕ i with n variables and m clauses, then S i possesses 4(n + m) vertices. Since all treewidth may be bounded by the number of vertices (minus one), and the size of a formula instance of Weighted 2-SAT(GV) polynomially depends on the number of clauses/variables, we have, for a polynomial P (•, •), tw(G(S)) ≤ P (max i∈[t] |ϕ i |, log t). Definition 3. A connector is a polynomial operator which connects two disjoints paths p 1 and p 2 of G, such that p 1 et p 2 belong to a same path.

The connector ⊕ is defined for two paths p 1 and p 2 of a quasi-tree, where P = (p 1 ⊕ p 2 ) is a path such that p 1 , p 2 ⊆ P and P respects the property of the quasi-tree. Theorem 7. There is no hope to find a connector ⊕ for Scaffolding unless N P ⊆ coN P/poly.

Proof. Let F = {(ϕ 1 , k), (ϕ 2 , k), . . . , (ϕ t , k)} a set of t instances of Weighted 2-SAT(GV), equivalent according to Definition 1, and G(S) the graph obtained by Construction 4. Each S i possesses exactly n paths, since ∀i ∈ {1, . . . , t}, ϕ i admits a solution of weight at least k. Thus there are n × t paths in G(S, and p j i designates the jth path of S i .

Suppose that it exists a connector ⊕ which connect two paths respecting the quasi-tree property. Therefore, we may extend the process for all G(S)-paths. G c (S) is the resulting graph, with only one path P containing all paths p j i , ∀i, j. Thus ∀i, (ϕ i , k) ∈ Weighted 2-SAT(GV) iff Γ(ϕ) ∈ Scaffolding with σ p = 1, σ p = 0 and cost = k. Since all instances in F are equivalent according to R kn , and σ p = 1 is polynomial in max i=1,...,t |x i | + log t, Scaffolding does not admit a polynomial kernel in σ p on the quasi-tree, unless N P ⊆ coN P/poly. Nevertheless, for σ p = c ∈ IN it exists a polynomial-time algorithm for the Scaffolding in presence in quasitree. So there is no hope to find a connector. [START_REF] Bazgan | A refined complexity analysis of finding the most vital edges for undirected shortest paths[END_REF] There is still hope to find

Polynomial cases

In dense graphs

To solve Strict Scaffolding (decision) in nearly complete graphs, we use a maximum matching in an auxiliary graph. In the following, let G be a co-bipartite graph and M * a perfect matching in G. Let H be the graph on the vertex set M * that contains an edge (uv, xy) if and only if G[uvxy] contains an alternating cycle of length four. Note that, since G is co-bipartite with partition X Z = V (G), we know that H is co-tripartite on partition

Weighted 2-SAT-formula ϕ 1 ϕ 2 . . . ϕ t cross-composition Scaffolding-instance S 1 S 2 . . . S t • • • • • • • •
E X E Y E Z = V (H) with E X = X 2 ∩ M * , E Z = Z 2 ∩ M * , and E Y = {uv | u ∈ X ∧ v ∈ Z} ∩ M * .
In the following, let M H be a maximum matching in H. Sketch. Clearly, a maximal matching M H in a co-tripartite graph H can be computed in linear time. Further, by Observation 1, at most one vertex in each partition is not covered by M H . Then, by the graph structure of H, if M H is augmentable, it can be augmented by an easy-to-find augmenting path.

Lemma 5. Let H be a co-tripartite graph and let M H be a maximum matching in H. Let u and v be vertices of H that are uncovered by M H . Then, H does not contain an edge between the partition of u and the partition of v. Further, if a third vertex is uncovered by M H , then H consists of three disjoint cliques.

Proof. We suppose that u and v are uncovered by M H . If there is an edge xy between the partition of u and the partition of v, with x in the partition of u and y in the partition of v, we consider both following cases:

• if the edge xy is in M H , then uxyv would be an augmenting 3-path, contradicting optimality of M H .

• if the edge xy is not in M H : if u = x, then there is some z matched with x by M H and, by the first part, z is in the same partition as x and u. Thus, there is an alternating (wrt. M H ) path from u to y in H ending with xy. By symmetry, there is an alternating path from v to x in H ending with xy. Thus, there is also an alternating path from u to v in H, contradicting optimality of M H .

If a third vertex of H is uncovered by M H , it implies that all three cliques are disjoint. In a first step, we extend the cycles represented by M H to cover the edges represented by the uncovered vertices in H. To this end, we first slightly modify M H :

1. If u ∈ E X (or E Z ) is not covered by M H and H has an alternating (wrt. M H ) path from u to some z ∈ E Y , then flip this path with respect to M H . 2. If u ∈ E X (or E Z ) is not covered by M H and H has an alternating (wrt. M H ) path from u to some z ∈ E Z not intersecting E Y , and with an edge between E X and E Z not in M H , then flip this path.

If H has an alternating (wrt. M

H ) 4-cycle intersecting E Y 2 , but not E Y 2
∩ M H , then flip this 4-cycle. As the result is also a maximum matching in H, we assume in the following that M H has been modified in this way. Further, these modifications can also be done in linear time.

With this modification, we can discuss the case where σ p = 0. We define the following covering procedure: 4. If there is some uv ∈ E Y that is not covered by M H , then we cover all edges of M * ∩ E Y that are not covered by M H using a single alternating path by extending one initial covered path uv ∈ E Y . At this step, either E Y is entirely covered, or it is empty and there are still σ p paths to cover. 5. The following cases occur only if E Y is empty: If X is totally uncovered, then cover one matching edge in X. If Z is totally uncovered and their remains at least one path available, cover one matching edge in Z. 6. If we have just covered k < σ p distinct paths yet, thus the k covered paths are constituted each by a single matching edge, and there remains sufficiently uncovered matching edge. We cover σ p -k of them arbitrarily. 7. If there is an uncovered edge uv in E X (resp E Z ), and an extremity of a covered path ending in X (resp.

Z), then extend this path with uv. 8. If there is uncovered edge uv in E X (resp E Z ), and a non-matching edge xy of a covered path or cycle entirely in X (resp. Z), then switch xy with xuvy to cover uv. After this last step, the only case where there is still uncovered matching edge is when X and Z are disjoint, σ c = 0 and σ p = 1. Thus, the instance is a no-instance.

In the following, we assume σ p = 0. We design the second covering procedure as follows: Let C be initialized as the set of alternating (wrt. M * ) cycles in G that correspond to M H . We extend C to cover the edges of M * that have not been covered by M H . Next, for each edge uv ∈ E X ∪ E Z that is not covered by M H , find a 3-path uxyv in G -M * such that xy is in a cycle C ∈ C. Then, augment C by uv, that is, exchange xy for ux, uv, and vy in C. If, after this, there is at most one edge in E X ∪ E Z that is not covered by C, then repeat this procedure for an edge uv ∈ E Y that is not covered by M H . Lemma 7. Let C be the result of the above augmentation procedure and let σ c ≤ |M H |. If there is at least one edge of M * that is not covered by C, then the instance is a no-instance.

Proof. Let S be a solution for (G, M * , σ p , |M H |). We consider cases depending on σ p .

Case 1: σ p = 0. Let uv be an edge of M * that is not covered by C and let C be a cycle of S containing uv. If it neighbour is in E Y , we can also conclude, since it is also connected to uv. If its neighbour is in E Z , then by the second augmenting procedure, zt would have been covered by M H . In any case, it leads to a contradiction.

σ p = 0, σ c = 1, even if |V (G)| ≥ 4σ c + 2σ p . • If uv is in X,
• The case where uv ∈ E Z is totally symmetric.

• If uv ∈ E Y , we use a very similar discussion. Indeed, xy and zt may be equal or one in E X and one in E Z , and we find again a case like above.

In any case, it leads to a contradiction, so uv can not be in a solution and the instance is a no-instance. Case 2: σ p = 0. We suppose that there is at least one edge not covered by C. Let uv be an edge of M * that is not covered by C. We saw above that the only case where there are uncovered edges in M * is when X and Z are disjoint, σ c = 0 and σ p = 1, and the instance is a no-instance. Theorem 8. Unweighted Scaffolding can be solved in O(n + m) time on co-bipartite graphs.

In sparse graphs

We show that, if G is a quasi forest and σ p = 0, then Scaffolding, and even Strict Scaffolding, can be solved in linear time. To this end, we employ the following reduction rule. Rule 1. Let u be a leaf in G -M * such that the parent v of u in G -M * is not a leaf. Then, delete all edges incident with v in G -M * that are not uv.

Correctness of Rule 1. The proof is based on the argument that any solution S for G is a perfect matching (that is, Gr(S ∪ M * ) has no degree-1 vertices). Since uv is the only edge of G -M * incident with u, it is apparent that uv ∈ S and, thus, no other edge incident with v is in S. Right: an optimal solution of weight 4.

If we maintain a list of leaves on each edge-deletion, we can apply Rule 1 exhaustively in linear time. Moreover, if it is no longer applicable to G -M * , then G -M * is a matching and checking whether G has the correct number of cycles can be done in linear time. Finally, we can extend this idea to work for any σ p and σ c by guessing all 2σ p end points of paths in the solution and deleting the non-matching edges incident with them.

Clearly, the result of this operation remains a quasi-forest and all vertices having a parent in G -M * have degree two in the solution, so the correctness of Rule 1 remains valid.

Corollary 9. Strict Scaffolding can be solved in O(n 2σp+1 ) time on quasi forests.

Polynomial approximation algorithms

Unfortunately, Theorem 8 holds only for unweighted instances. As we have seen in 3.1.2, Scaffolding is N P-hard if we allow weights to be 0 or 1. However, we can still show a simple factor-2 approximation, that is, Algorithm 1 produces a solution of weight at least half the optimum weight, for Max Scaffolding in case G is a complete graph or a complete bipartite graph. Algorithm 1 starts with a maximal-cardinality maximum-weight matching S of G-M * , implying that Gr(S ∪ M * ) is a collection of cycles. Then, it merges cycles, two at a time. Finally, it turns cycles into paths until the correct numbers of paths and cycles are reached. Lemma 8. If G is a complete graph, Algorithm 1 produces a solution whose weight is at least half the optimum.

Proof. Let S org denote the set S as computed in line 1 and let S denote the set S returned in line 14. First, we show that S is a solution. To this end, note that S org is a matching in G -M * and Gr(S org ∪ M * ) is a collection of cycles since S org is maximal-cardinality (and, thus, perfect). Since the only times S changes is when its symmetric difference with a 4-cycles is formed (line 7) or when edges are removed from S (line 12), the set S is a matching in G-M * . Thus, Gr( S∪M * ) has maximum degree two. Further, note that "X ⊆ S" and "Gr(S∪M * ) is a collection of cycles" are invariants of the first while loop. Since, in line 9, we know that Gr(S ∪ M * ) has at most σ p + σ c connected components, all of which are cycles, we conclude that Gr( S ∪ M * ) is a collection of at most σ p paths and at most σ c cycles.

Next, we show that the weight of the set S returned in line 14 is at least half the weight of a maximum matching in G -M * , which is an upper bound on the solution weight and which is equal to ω(S org ). To this end, note that for all cycles C of Gr(S org ∪ M * ), we selected a minimum-weight edge e C of C into X in line 3. Thus, ω(C) ≥ |C|/2 • ω(e C ) for each cycle C in Gr(S org ∪ M * ). Finally, let X org denote the set X as computed in line 3. Then, since |C| ≥ 4 for each C,

ω(X org ) = ω( C e C ) ≤ C ω(e C ) ≤ C 2ω(C)/|C| ≤ C ω(C)/2 ≤ 1 2 ω(S org ).
Since Algorithm 1 never touches any edge of S org except edges in X org , we know that S org ⊆ S ∪ X org and, thus, ω( S) ≥ ω(S org ) -ω(X org ) ≥ ω(S org )/2.

Note that all arguments remain valid for complete bipartite graphs. Furthermore, Figure 9 gives an example of a configuration in which Algorithm 1 gives a solution of weight half the optimum, implying that the bound of two is tight.

Theorem 9. If G is a complete bipartite graph or a clique, then Max Scaffolding can be approximated to within a factor 2 in asymptotically the same time as it takes to compute a bipartite matching in G (currently O(|V | 3 )). This factor is tight.

Variant problems for Scaffolding

When considering a weighted graph, we studied the problem of identifying a subset of edges whose removal from the graph causes the largest cost increase. This problem is denoted as k most vital edges problem. A dual problem consists of determining a set of edges of minimum cardinality whose removal causes the cost of solution to become greater than a given a threshold. This problem is denoted by min edge blocker problem. Those problems have been studied for various classes of combinatorial problems in [START_REF] Bazgan | Critical edges/nodes for the minimum spanning tree problem: complexity and approximation[END_REF][START_REF] Bazgan | Blockers for the stability number and the chromatic number[END_REF][START_REF] Bazgan | A refined complexity analysis of finding the most vital edges for undirected shortest paths[END_REF]. The underlying idea is that, for Scaffolding, it may be related to the quest of a "core partial solution", on which we may have a greater confidence, since it has the most impact on the score of an optimal solution. This partial solution may be extended further into a complete solution, by exhaustive exact search for instance. Unfortunately, the problem is already difficult for constrained cases. Notice that E ∩ M * = ∅. We first consider cases where the lengths of the cycles and paths are fixed, namely ((σ p , p ≥ 1), (σ c , 6))-Strict Scaffolding. We now consider a reduction from the Partition Into Triangles [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF].

Partition Into Triangles (PT)

Input: G = (V, E), with |V | = 3q = n, q ∈ IN and |E| = m. Question: Can the vertices of G be partitioned into q disjoints sets containing exactly three vertices, T 1 , T 2 , . . . , T q , such that for each

T i = {u i , v i , w i }, i ∈ {1, . . . , q}, all three edges {u i , v i }, {u i , w i }, {w i , v i } belong to E?
We define a polynomial-time transformation from an instance of Partition Into Triangles to an instance of ((σ p , p ≥ 1), (σ c , 6))-Strict Scaffolding (see Figure 10).

= (V = V 0 ∪ V 1 , E = E 0 ∪ E 1 ∪ E 2 ∪ E 3 ): • We consider two copies of G denoted by G 0 = (V 0 , E 0 ) and G 1 = (V 1 , E 1 )
with vertices respectively denoted by x 0 and x 1 for x ∈ V .

• ∀x ∈ V , {x 0 , x 1 } ∈ E 2 .

• ∀{x, y} ∈ E, {x 0 , y 1 } ∈ E 3 and {x 1 , y 0 } ∈ E 3 .

The perfect matching M * consists in the edges of E 2 . We also add the following weights on edges outside M * : ω Proof. The proof is based on Construction 2. We add to this construction, the set of edges E 2 = {(y 1 j y 4 j ), (y Notice that all previous results may be extended to the problem of k Least vital edges.

3 j y 2 j )}, ∀j ∈ [1, σ c ] ω(e) = M, ∀e ∈ E 1 , ω(e) = M , ∀e ∈ E 2 with M > M , otherwise ω(e) = 1.
Corollary 12. The minimization problem for k-MV-Strict Scaffolding is non-approximable for all previous problems.

The following problem is close to previous ones, but aims to minimize the size of the removed edge set. Proof. It is sufficient to consider the E -edges set of the solution given by S in the proof of Theorem 10 and put k = 6qM .

Existence of two disjoints solutions

In the following, we consider the problem concerning the existence of two disjoints solutions. Two solutions S 1 and S 2 are edge-disjoint (disjoint in the following) according to a perfect matching

M * if (S 1 \M * ) ∩ (S 2 \M * ) = ∅.
Two Disjoint Solutions for Scaffolding (2-Scaffolding)

Input: G = (V, E), ω : E → N, perfect matching M * in G, σ p , σ c , k ∈ N Question:
Is there an S 1 , S 2 ⊆ E \ M * , two disjoint solutions such that Gr(S i ∪ M * ), for i = 1, 2 is a collection of ≤ σ p paths and ≤ σ c cycles and ω(S i ) ≥ k?

We consider the following polynomial-time construction from Directed Hamiltonian Path, illustrated by Figure 12. Notice that the produced graph G is planar if G is planar. Construction 8. Let G = (V, A) an instance of the Directed Hamiltonian Path problem. We construct the following graph G = (V 0 ∪ V 1 , E 0 ∪ E 1 ):

• ∀u ∈ V , we construct a graph with six vertices P 6,u = (u 1 , u 2 , u 3 , u 4 , u 5 , u 6 ) with edge between u i and u i+1 for i = 1, . . . , 5. This set of edges are denoted by E 0 . Moreover, we add to E 0 these two edges (u 2 , u 4 ) and (u 3 , u 5 ).

x y (a) Original arc.

x 1 x 2

x 3

x 4

x 5 • ∀(u, v) ∈ A, we construct a graph PE u,v with two vertices (u, v) 0 and (u, v) 1 , and add following edges {u 6 , (u, v) 0 }, {(u, v) 0 , (u, v) 1 }, {(u, v) 1 , v 1 }, {u 6 , (u, v) 1 } and {(u, v) 0 , v 1 }. Such vertices are in V 1 and the corresponding edges in E 1 .

We construct the perfect matching M * on G , consisting in the edges of the kind {u 1 , u 2 }, {u 3 , u 4 }, {u 5 , u 6 }, ∀u ∈ V and {(u, v) 0 , (u, v) 1 }, ∀(u, v) ∈ A.

Theorem 11. The problem 2-Scaffolding is N P-complete, even if the graph is planar and σ c = 0. Assuming the Exponential-Time Hypothesis, there exists no hope to find a algorithm in O(2 o( √ n) ) time for the 2-Scaffolding in presence of a planar graph.

Proof. Clearly, there are two disjoint paths according to the perfect matching M * for the path P 6,u i.e. u 1 → u 2 → u 3 → u 4 → u 5 → u 6 (denoted by P6,u ) and u 1 → u 2 → u 4 → u 3 → u 5 → u 6 (denoted by P 6,u ). Similarly, for an edge-path of length three PE (u,v) , we may consider the two disjoint paths u 6 → (u, v) 0 → (u, v) 1 → v 1 (denoted by PE (u,v) ) or u 6 → (u, v) 1 → (u, v) 0 → v 1 (denoted by PE (u,v) ).

Therefore according to previous discussion, it is clear that it exists a positive solution for Directed Hamiltonian Path if and only if it exists a positive solution for 2-Scaffolding, i.e. two disjoint solutions S 1 and S 2 . Indeed, each solution S i use the P6,u or P 6,u and PE (u,v) or PE (u,v) paths.

Moreover, the previous polynomial-time transformation is linear which implies the results for subexponentialtime algorithm.

Conclusion

In this article, we presented an overview of the negative and positive results in terms of complexity and approximation for Scaffolding. Refining previously obtained results, we were particularly interested in different classes of graphs, some of them because they have a resemblance to real scaffold graphs, particularly due to their sparsity, and others because we hope to generalize in these "almost complete" graphs, the results of complexity and approximation obtained in complete graphs. Negative results concern strong restrictions on the problem, including the number of cycles, paths, their length, the maximum degree of the graph, and gives little hope of finding a polynomial case whose configuration looks like a real graph. In addition, in the side of dense graphs, but also in quasi-forest, we prove several N P-completeness results for the optimization problem as soon as we allow two different weights on the edges of the graph. We complement these results with lower bounds on the complexity of exact algorithms for these problems under the Exponential-Time-Hypothesis. Negative results for approximation are also exposed, especially for the minimization problem, even in quasi-forests and graphs containing a bipartite graph. Continuing the quest for effective angle of attack for the problem, we have also been sought in FPT algorithms, in particular, we looked if there was a polynomial kernel to the problem parameterized by treewidth. We proved that it could not exist.

However, we also found promising positive results. Regarding dense graphs, we proved that the decision problem is polynomial for co-bipartite graphs, and exhibited an approximation algorithm with a factor of 2 for scaffolding in the cliques and bipartite complete graphs.

Finally, we have shown that it is equally difficult to find a subset of "vital" edges for Scaffolding, as the problem itself.

These results raise interesting new questions which have to be explored if we want to approach the boundaries of the problem. Thus, we hope to get a result of polynomiality in split graphs for the decision problem, in a manner similar to that obtained in co-bipartite graphs. From these results, we also wish to infer approximation algorithms with a performance guarantee for Scaffolding in these graph classes, for example by adapting a greedy strategy or using a maximum perfect matching like in the case of cliques. If these results are confirmed, it is hoped to extend them in classes of graphs which generalize the concept of cliques and stable, that is (r, l)-graphs, which are graphs which are decomposable into r independent sets and l cliques [START_REF] Brandstädt | Partitions of graphs into one or two independent sets and cliques[END_REF].

Also, results for approximation in complete graphs requires a series of tests, on real and simulated dataset, to examine if the ratio obtained in practice would be better than 2. It is expected indeed that he is, since actual scaffold graphs are rather sparse and many edges will be of weight zero. On theoretical level, one wonders if this approximation algorithm can be generalized to a PT AS.

As for FPT algorithms, we can look closer to other parameters, or search for FPT approximation algorithms that would be a first step towards a practical tackling of the problem. It was also the underlying idea of considering the k-Most Vital edges problems. These issues would deserve a little extra exploration, particularly on sparse graphs.

N

  Pc, W[1]-h wrt. k (Thm. 4) no 2 o(m) -or n o(k) -time algorithm (Corollary 5) P (Cor. 9) open P (Cor. 9)

Figure 1 :

 1 Figure 1: An example of instance of Scaffolding. Matching edges are strong. With (σ p , σ c ) = (2, 2), it is positive for Scaffolding, but negative for Strict Scaffolding. A solution is given in gray.

Figure 2 :

 2 Figure 2: Example of Construction 1, transforming the left instance of Directed Hamiltonian Cycle to the right graph with edges of M * in bold and edges of the form v 4 i v 1 j dashed. A corresponding solution is highlighted.

Theorem 3 . 4 Figure 3 :

 343 Figure 3: Illustration of Construction 3.

x 5 C 3 (

 53 b) x1 ∨ x5 satisfied by x1 = 1 and x5 = 0.

Figure 4 :

 4 Figure 4: Example of Construction 4 for the clause x 1 ∨ x 5 . Bold edges are in M * . Gray paths are solution paths corresponding to the respective assignments.

  this means that both e j+1 i and e j+1 i are in S, forming a forbidden cycle. Thus, by symmetry, let C j contain x i non-negated. Then, S contains both e j+1 i and u j+1 i a j+1 i and, by (2), also v j+1 i d j+1 i . Then, by (1), none of ε j+1 i and ε j+1 i are in S, contradicting that the claim holds for j + 1. Thus, (3) holds by induction.

Corollary 4 .

 4 Scaffolding is N P-hard and W[1]-hard with respect to k, even on bipartite cubic graphs G with G -M * being a path, ω being tristate, and σ c = 0.

Figure 5 :

 5 Figure 5: Illustration of the Cross-composition with a connector.

  Original co-bipartite graph G. Edges in M * are strong. Transformed co-tripartite graph H. Edges in MH appears in gray.

Figure 6 :Observation 1 .

 61 Figure 6: Transformation of a co-bipartite graph G with a perfect matching M * (left) into a co-tripartite graph H (right) on the vertex set M * .

Observation 2 .

 2 Let (G, M * , σ p , σ c ) be a yes-instance. Then, |V (G)| ≥ 4σ c + 2σ p .Note that M H corresponds to a set of alternating 4-cycles in G and, by Observation 1, at most three edges of M * are not covered by these 4-cycles: one in each of E X , E Y and E Z . Lemma 6. Let (G, M * , σ p , σ c ) be a yes-instance, let H and M H be as defined above and let σ c > |M H |. Then, σ c = |M H | + 1, σ p = 0 and G contains an alternating 6-cycle intersecting E X , E Y and E Z . Moreover, the result of removing any such 6-cycle from G and M H can be covered with exactly σ c -1 alternating 4-cycles. Proof. Assume that G can be covered by a collection S of > |M H | alternating cycles and any number of alternating paths. Note that, by optimality of M H , at least one of the cycles of S contains at least 6 vertices of G. Thus, S covers at least 4|M H | + 6 vertices of G. But by Observation 1, we have |V (G)| ≤ 4|M H | + 6, implying that S contains no paths, |M H | 4-cycles, and one 6-cycle C of G. Furthermore, M H covers all but exactly three vertices of H.

  Graph H. The covering after the covering procedure is in gray.

Figure 7 :

 7 Figure 7: Case where σ c ≤ |M H | and σ p = 0 and there are uncovered M * -edges. Notice that it is a no-instance for σ p = 1,σ c = 0, even if |V (G)| ≥ 4σ c + 2σ p . Assume that C does not intersect E Y . Then, |E Y | is even since S \ C isa collection of 4-cycles. But, since M H covers all but one edge of E Y , it covers an odd number of edges in E Y . But then, some edge in E Y is matched with an edge of E X or E Z by M H , contradicting Lemma 5. Assume that C does not intersect E X . Then, since C intersects E Y , all but one vertex of C are in E Z , implying that G has an alternating 4-cycle intersecting E Y and E Z , contradicting Lemma 5. Finally, we show that the result of removing any 6-cycle C intersecting E X , E Y and E Z can be covered by σ c -1 alternating cycles. To this end, it suffices to observe that, by Lemma 5, |E X \ C |, |E Y \ C | and |E Z \ C | are all even and each induces a clique in H. Since we can find a 6-cycle as described in Lemma 6 in linear time, we can solve Strict Scaffolding in linear time if σ c > |M H |. Thus, in the following, we assume σ c ≤ |M H |. In a first step, we extend the cycles represented by M H to cover the edges represented by the uncovered vertices in H. To this end, we first slightly modify M H : 1. If u ∈ E X (or E Z ) is not covered by M H and H has an alternating (wrt. M H ) path from u to some z ∈ E Y , then flip this path with respect to M H . 2. If u ∈ E X (or E Z ) is not covered by M H and H has an alternating (wrt. M H ) path from u to some z ∈ E Z not intersecting E Y , and with an edge between E X and E Z not in M H , then flip this path. 3. If H has an alternating (wrt. M H ) 4-cycle intersecting E Y 2 , but not E Y

  Graph H. The covering after the covering procedure is in gray.

Figure 8 :

 8 Figure 8: Case where σ c ≤ |M H | and σ p = 0 and there are uncovered M * -edges. Notice that it is a no-instance for σ p = 0, σ c = 1, even if |V (G)| ≥ 4σ c + 2σ p .

Algorithm 1 : 6 Y 7 S ← S∆Y ; 8 e 9 X 12 S ← S -e; 13 XFigure 9 :

 1678912139 Figure 9: An example with σ c = 1 for which Algorithm 1 gives a solution of half optimal weight. Drawn edges (solid and dashed) have weight 1, all other edges have weight 0. The solid edges are a maximal-cardinality maximum-weight matching. Left: Algorithm 1 replaces e and e to form the highlighted solution of weight 2. Right: an optimal solution of weight 4.

5. 1

 1 Hardness results for the k Most/Least vital edges Scaffolding Here is the formal definition of the problem, adapted to Scaffolding. k Most / Least vital edges of Scaffolding (k-MV / LV-Scaffolding) Input: G, ω : E → N, perfect matching M * in G, σ p ∈ N, σ c ∈ N, k ∈ N. Question: Does it exist a subset E ⊆ E, |E | = k with G -E have a σ p -σ c -cover S (resp. G have a σ p -σ c -cover S) with respect to M * such that (ω(S) -ω(S )) is ≥ l / ≤ l ?

Construction 6 .

 6 Let G = (V, E) be an instance of Partition into Triangles. We consider the graph G

1 (

 1 e) = M, e ∈ E 0 ∪ E 1 , otherwise ω(e) = M with M < M . We set k = 2m with m is the number of edges in the graph G. b) Transformed instance of ((σp, p ≥ 1), (σc, 12))-Strict Scaffolding. Edges in M * are strong. Plain edges have weight M , dotted edges have weight M .

Figure 11 :

 11 Figure 11: Illustration of Construction 7.

  Finally, we put k = 2σ c . As previously, there is a positive solution for Directed Hamiltonian Path if and only if there are two solutions S and S of k-MV-Strict Scaffolding such that ω(S) -ω(S ) = 2(M -M )σ c .

  MIN/MAX Edge Blocker Scaffolding (Min/Max-EB-Scaffolding)Input: G, ω : E → N, perfect matching M * in G, σ p ∈ N, σ c ∈ N, k ∈ N. Question: A subset E ⊆ E of minimum cardinality with G -E have a σ p -σ c -cover S with respectto M * such that ω(S ) is at least / most k i.e. ω(S ) ≥ k / ω(S ) ≤ k?Both problems k-MV-Scaffolding and Min-EB-Scaffolding are polynomial-time equivalent.Corollary 13. The problem k-MB-Scaffolding is N P-complete for bipartite graph and the result remains true even if σ p = 0.

x 6 P 6

 66 Transformed instance of the arc. Matching edges are strong.

Figure 12 :

 12 Figure 12: Example of Construction 8.

Table 1 :

 1 Complexity results for Scaffolding on various graph classes depending on ω max , σ p , and σ c .

	G		max	min
	clique, complete bipartite	2-approx. (Theorem 9)	/ ∈ APX (Cor. 6 & [8]),
	co-bipartite, split		open	ωmax/ωmin-
	quasi forest	no n	1 2 --approx. (Cor. 7)	approximation APX -hard (Cor. 8)

Table 2 :

 2 Complexity to approximate Scaffolding.

  1. If σ c < |M H | and there is an edge in M H incident with a vertex of E Y , then remove this edge from M H . 2. If σ c < |M H | and no edge in M H is incident with a vertex of E Y , arbitrarily remove edges from M H until reaching σ c . At this step, there is exactly σ c cycles of length four covered by M H . We set C this set of cycles. Since |V (G)| ≥ 4σ c + 2σ p , we have at least σ p edges in M * which are still uncovered. 3. Cover σ p of these edges of M * by one path each, beginning with edges in E Y .

  and at least one other edge in M * is in X, say xy, then xy is covered by M H . Let zt ∈ M * be a neighbour of xy (wrt M H ). If zt is in E X , then by the augmenting procedure above, uv would have been covered by M H . If zt is in E Y , then by the first modification of M H , the path uv -xy -zt would have been flipped, and uv covered by M H . If zt is in E Z , again by the first modification of M H , uv would have been covered by M H . Thus, uv is the lonely edge in E X (resp. E Z ). Let xy and zt be the neighbours of uv in M * ∩ C. We suppose that ux ∈ E(G) and vz ∈ E(G). We have to consider the following excluding cases:1. xy = zt and this edge is in E Z . Then E X is connected to E Z ,and the edge xy is covered by M H . It neighbour by M H is either in E Z , then by the second modification of M H , the path between xy and this edge would have been flipped, and xy covered by M H , or it is in E Y , and then by first modification of M H , again this path would have been flipped. In any case, xy would have been covered by M H . 2. xy ∈ E Z , zt ∈ E Z , and xy = zt. Thus by the augmenting procedure, they are covered by M H . Indeed, the argument is similar as above. If they belong to a same cycle of C, then the edge xz is such uxzv ∈ G \ M * and xz is in a cycle. Thus by above augmenting procedure, uv would have been covered by M H . 3. xy ∈ E Y and zt ∈ E Y . Then, one of them is covered by M H , say xy. If its neighbour by M H is in E Y , then without loss of generality, we can suppose that it is zt, since this neighbour is then also connected to uv. In this case, by augmenting procedure above, uv would have been covered by M H . If the neighbour is not in E Y , then it is in E Z , and then by the second augmenting procedure, zt would have been included in the cycle. By first augmenting procedure, so does uv. 4. xy ∈ E Z , zt ∈ E Y (and symmetric case). If none of xy and zt is covered by M H , it means |M H | = 0, which is not possible since σ c ≥ 1 and σ c ≤ |M H | by hypothesis. Again, if zt is covered by M H , by a similar discussion as above, we conclude that uv would have been covered by M H through one of the augmenting procedure. Suppose now that zt is not covered by M H , and that xy is covered by M H .

The ETH states: there is a constant c > 1 such that no O(c n )-time algorithm for n-variable 3-SAT exists.

coN P/poly is the class of decision problems refutable by a family of polynomial-size Boolean circuits.

http://www.ibc-montpellier.fr/

Acknowledgements. This work was supported by the Institut de Biologie Computationnelle 3 (ANR Projet Investissements d'Avenir en bioinformatique IBC).

• Suppose there exists a positive solution for the problem k-MV-((σ p , p ≥ 1), (σ c , 6))-Strict Scaffolding such that ω(S) -ω(S ) = 2(M -M )q. Clearly in S at most two edges with weight M in each triangle may be chosen. So ω(S) ≤ (2M + 4M )q. Moreover, ω(S ) = 6M q. Notice that ω(S) is equal to (2M + 4M ) if two edges of weight M are included in each cycle of length six, and the solution S uses the cycle {x 0 , y 0 , y 1 , z 0 , z 1 , x 1 , x 0 } whereas S uses the cycle {x 0 , x 1 , y 0 , y 1 , z 0 , z 1 , x 0 }. The union of corresponding triangles in G, ∪{x, y, z} is a G-cover.

• Conversely, we suppose that there exists in G a partition into triangles, let us construct a positive solution for the k-MV-((σ p , p ≥ 1), (σ c , 6))Strict Scaffolding in the graph G .

1. The value of ω(S) = (2M + 4M )q iff G admits a partition into triangle. For a triangle {x, y, z}, we consider the following alternating-cycle of length six: {x 0 , y 0 , y 1 , z 0 , z 1 , x 1 , x 0 }. It is clear that all alternating-cycles cover the vertices of G .

2. For any another solution S = S, we have ω(S ) ≥ 6qM , indeed it is sufficient to consider the following alternating-cycle of length six: {x 0 , x 1 , y 0 , y 1 , z 0 , z 1 , x 0 }.

Therefore, we have ω(S) -ω(S ) = 2(M -M )q.

The previous result can be extended to the bipartite case, with c = 12.

Corollary 10. The problem k-MV-((σ p , p ≥ 1), (σ c , 12))-Strict Scaffolding remains N P-complete for bipartite graphs with bounded degree at most four.

Proof. The proof is very similar to the previous one, and is based on the slightly different Construction 7, which construct a bipartite graph, where the bound on degree is same as in the original instance of Partition Into Triangles. Notice that Partition Into Triangles remains N P-complete even for maximum degree at most four, yielding this part of the result. This construction is illustrated by Figure 11.

Construction 7. Let G = (V, E) be an instance of Partition Into Triangles. We consider the graph

• We consider two copies of G denoted by G 0 = (V 0 , E 0 ) and G 1 = (V 1 , E 1 ) with vertices respectively denoted by x 0 and x 1 for x ∈ V .

• For each edge e ∈ E 0 ∪ E 1 , e is split into two edges by adding a new vertex i.e. ∀{x 0 , y 0 } ∈ E 0 (resp. ∀{x 1 , y 1 } ∈ E 1 ), we add x 0 y 0 (resp. x 1 y 1 ) and two new edges {x 0 , x 0 y 0 } and {x 0 y 0 , y 0 } (resp. {x 1 , x 1 y 1 } and {x 1 y 1 , y 1 }). The set of vertices V i , and edges E i , i ∈ {0, 1} are updated.

• We add all the edges of the form {x 0 , x 1 } and {x 0 y 0 , x 1 y 1 } to the set of edges denoted E 2 .

The perfect matching consists in the edges of E 2 .We set the following weights: every edge e in G is incident to a vertex xy 0 or xy 1 . If ω(x 0 xy 0 ) = M , we set ω(xy 1 y 1 ) = M and ω(xy 0 y 0 ) = ω(x 1 xy 1 ) = M with M < M . We let k = 2m where m is the number of edges in the graph G.

Clearly by construction the graph G is bipartite. It is sufficient to consider l = 2q(M -M ).


Ali-Mohamed Mohamed Nassur

Marie Lefevre

Anne-Sophie Evrard

Maxime Elbaz

Damien Leger

Fanny Mietlicki

Philippe Nguyen

Carlos Ribeiro

Matthieu Sineau

Bernard Laumon

Marie Lefèvre

Damien Léger

Aircraft noise exposure and objective sleep quality in the population living near airports in France

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Transportation noise is a major source of environmental noise pollution, and it represents a major public health issue. According to the World Health Organization (WHO), transportation noise is estimated to cause at least one million healthy life years lost every year in Western Europe, and sleep disorders are the most serious consequence with more than 900 thousand years of life lost every year, mostly related to road traffic noise [START_REF] Who | Burden of disease from environmental noise: quantification of healthy life years lost in Europe (World Health Organization[END_REF] .

Near airports, aircraft noise is perceived as a major environmental stressor. It also constitutes a major issue for public health, particularly in terms of sleep disturbance [START_REF] Who | Burden of disease from environmental noise: quantification of healthy life years lost in Europe (World Health Organization[END_REF] . Several studies have been conducted to assess the effect of aircraft noise on sleep. Aircraft noise has been shown to disrupt sleep. Exposure to night time aircraft noise leads to an increased frequency of awakening, increased motility, decreased slow wave sleep, changes in sleep structure, use of sleep drugs or sedatives, and a poor quality of sleep [START_REF] Perron | Review of the effect of aircraft noise on sleep disturbance in adults[END_REF] .

Most studies conducted near airports have used integrated noise indicators, often estimated outside the dwellings using modelling software. However, according to a literature review by Michaud et al, indoor sound levels are more closely associated with sleep disturbance than outdoor measures [START_REF] Michaud | Review of field studies of aircraft noise-induced sleep disturbance[END_REF] . Moreover, noise event indicators are rather recommended because they could better characterize aircraft noise [START_REF] Gadal | Final Report of the ENNAH (European Network on Noise and Health) project[END_REF] .

In this context, the aim of the present study was to investigate the association between measured both outdoor and indoor exposure to aircraft noise and objective sleep quality in the population living near airports in France. Noise integrated indicators (related to energetic average calculated on different periods of time) and noise event indicators were taken into account.

METHODS

In total, 112 individuals older than 18 and living near two major French airports agreed to participate in the study: 92 participants around Paris-Charles de Gaulle airport and 20 around Toulouse-Blagnac airport. These subjects were selected after an interview with an investigator at their home as part of the DEBATS longitudinal study [START_REF] Nassur | Aircraft Noise Exposure and Subjective Sleep Quality: The Results of the DEBATS Study in France[END_REF] .

Assessment of aircraft noise exposure

Aircraft noise exposure was assessed based on acoustic measurements performed outside and inside the bedroom of each participant. The measurements have been carried out for eight days in order to cover the different activities of the airport. Two sonometers were placed in the subjects' dwellings in order to collect accurate and reliable data on the acoustic impact of aircraft overflights in the bedroom. The first sonometer located in the participants' bedroom recorded their noise exposure at night. The second sonometer set up outside (at the bedroom façade) allowed us to identify the aircraft noise and to evaluate the impact of this noise in the participants' bedroom. Bruitparif (Noise Observatory of the Paris region), partner of the DEBATS project, developed an algorithm allowing us to derive the noise level from aircraft only inside the bedroom.

Based on these measurements, integrated noise indicators (related to energetic average calculated on different periods of time) and noise event indicators were estimated during the sleep period, that is between sleep onset and final awakening. Among integrated noise indicators, the equivalent continuous sound pressure level (LAeq) inside (LAeq,int) and outside (LAeq,ext) of the bedroom have been calculated. Among the noise event indicators, the total number of aircraft noise events inside (NA,int) and outside (NA,ext) of the bedroom have been determined.

Assessment of objective sleep quality

A wrist-worn actigraph, Motionwatch 8 (CamNtech Ltd), was used in order to evaluate objective sleep quality of the participants. Measurements, from both actigraph and sleep diary, were performed for eight consecutive days, the same eight days as those of acoustic measurements. These two measures allow the identification of objective and accurate sleep quality. Actigraph records movements during sleep that can be used to estimate sleep parameters with specialized algorithms in computer software programs. Some parameters related to sleep schedules (beginning, end, duration) can then be assessed. The following sleep parameters were derived from the actigraph measurements: sleep onset latency (SOL), total sleep time (TST), wake after sleep onset (WASO) and sleep efficiency (SE). These parameters were dichotomized in order to be linked to aircraft noise exposure. SOL ≥ 30 minutes, TST < 6 hrs, WASO ≥ 30 min and SE < 90% can be considered as insomnia characteristics.

Statistical analysis

Logistic regression models with repeated measurements were used in order to estimate the relationship between aircraft noise exposure and objective sleep quality. The following potential confounders were taking into account in the models: age, gender, marital status, education and body mass index (BMI).

RESULTS

Almost 58% of the participants in our study were women and near half of the participants were married (Table 1). Nearly 45% of participants had sleep latency greater than 30 minutes. 18% slept less than 6 hours per night, 35% have a wake time after sleep onset higher than 30 minutes and 13% have a poor sleep efficiency.

Table 1 -Description of the study population

During the sleep period, the equivalent continuous aircraft noise level was 47 dB(A) outside the bedroom and 18 dB(A) inside the bedroom (Table 2). The number of aircraft noise events was 37 outside the bedroom and 29 inside the bedroom.

Table 2. Description of noise indicators

The Odds-Ratios (ORs) and their 95% confidence intervals (CIs) for objective parameters of sleep quality in relation to aircraft noise exposure are presented in Table 3. A significant positive association was found between both integrated aircraft noise indicators and both aircraft noise event indicators and TST: an increase in the aircraft noise level or in the number of aircraft noise events, outside and inside the bedroom, decreased the probability of sleeping less than 6 hours. A positive and significant association was also found between both integrated indicators, outside and inside the bedroom, and SOL. The association was even higher inside the bedroom: a 10 dB(A)-increase in the equivalent continuous noise level inside the bedroom (LAeq, int) was associated with an increase in SOL with an OR of 1.45 (95% CI: 1.12-1.88). A positive and significant association was found between noise event indicators, outside and inside the dwellind, and WASO: an increase of 10 aircraft noise events inside the bedroom was associated with an increase in the total duration of waking time after sleep onset with an OR of 1.11 (95% CI: 1.01-1.22). ORs between acoustic indicators and sleep efficiency indicated deterioration in sleep efficiency related to an increase in the level or number of aircraft noise events. However, these associations were not significant.

DISCUSSION

The present study investigated the effects of aircraft noise exposure on objective sleep quality evaluated with an actigraph in the vicinity of French airports (Paris-Charles de Gaulle and Toulouse-Blagnac). Objective sleep quality was characterized through four parameters: SOL, TST, WASO and SE. The prevalence of short sleepers (TST < 6 hours) estimated in this study was similar to the one estimated in 2010 in the Health Barometer survey (18%) for the French population [START_REF] Leger | The risks of sleeping 'too much'. Survey of a National Representative Sample of 24671 adults (INPES health barometer)[END_REF] .

The present study confirms in the results of most studies in the literature: aircraft noise exposure leads to an increase in SOL and WASO [START_REF] Passchier-Vermeer | Sleep disturbance and aircraft noise exposure : Exposure-effect relationships[END_REF][START_REF] Basner | Aircraft noise effects on sleep: application of the results of a large polysomnographic field study[END_REF] . However in contrast to most studies that found a decrease in TST associated to transportation noise exposure [START_REF] Muzet | Environmental noise, sleep and health[END_REF] , this study showed an increased TST. We hypothesized that it could be an adaptation behavior to sleep deprivation. Individuals would stay longer in bed to try to sleep more and recover. A previous study in a laboratory also found an increased TST following exposure to aircraft noise [START_REF] Basner | Effects of Nocturnal Aircraft Noise on Sleep Structure[END_REF] . The authors also explained this result with adaptation mechanisms to partial sleep deprivation during previous nights exposed to noise 10. Acoustic measurements were performed in the present study in order to estimate aircraft noise exposure not only in terms of integrated noise indicators but also in terms of noise event indicators, whereas almost all epidemiological studies on the subject used integrated indicators. However, noise event indicators are rather recommended because they could better characterize aircraft noise [START_REF] Gadal | Final Report of the ENNAH (European Network on Noise and Health) project[END_REF] . Several indicators (not shown) have been calculated and event indicators were significantly associated with almost all the objective parameters of sleep quality studied, contrary to integrated indicators. This confirms the study by Griefahn and al which showed that energy indicators such as LAeq do not seem to be appropriate predictors for the quality of sleep evaluated objectively [START_REF] Griefahn | Noise emitted from road, rail and air traffic and their effects on sleep[END_REF] . Ohrstrom and Rylander also showed that the number of road noise events had a significantly greater effect on objective and subjective sleep quality than continuous noise level [START_REF] Ohrstrom | Sleep disturbance effects of traffic noise -a laboratory study on after effects[END_REF] .

In the present study, acoustic measurements were performed outside and inside the bedroom. Acoustic indicators were associated with objective sleep parameters, whatever they were estimated outdoors or indoors. This result does not support the hypothesis of a literature review which states that aircraft noise levels measured indoors are more closely associated with sleep disturbances than levels measured outside buildings 3 .

CONCLUSIONS

The findings of the present study contribute to the overall evidence suggesting that aircraft noise exposure at night-time may decrease objective quality of sleep. Adaptation mechanisms to sleep deprivation could be observed. Aircraft noise exposure affects objective parameters of sleep quality not only in terms of noise levels but also in terms of number of events. Noise event indicators have been shown to be more often associated with sleep disturbances than integrated indicators.

Table 3 -Odds ratios for the relationship between noise indicators and objective sleep parameters.

 3

	1 Per 10 dBA increase
	2 Per 10 events increase
	Bold values are statistically significant p ≤ 0.05


Sébastien Richeter

Aurélie Hadj-Aïssa

Céline Taffin

Arie Van Der Lee

Dominique Leclercq

Synthesis and Structural Characterization of the First N-Heterocyclic Carbene Fused to a Porphyrin

The fonctionalization of two neighboring β-pyrrolic positions of a porphyrin by a fused N-heterocyclic carbene, the subsequent metallation of this external coordination site by palladium(II) and the structural characterization of the compounds obtained

are presented.

The synthesis of multiporphyrin systems is of great interest because of their wide potential applications in catalysis, [START_REF] Mansuy | [END_REF] molecular materials 2 and medicine. 3 A lot of synthetic strategies have been developed to built multiporphyrin systems through covalent 4 and non-covalent bonds 5 . The use of coordination bonds to link porphyrins together opened exciting opportunities to built systems with different shapes, such as linear, 6 cyclic, 7 2D 8 and 3D 9 geometries. The classical building blocks employed for this strategy are porphyrins bearing one or more peripheral 20 coordination sites, as it is well illustrated by the examples of porphyrins liked to pyridyl derivatives. 8,10 Surprisingly, the number of examples of porphyrins bearing Nheterocyclic carbene (NHC) ligands as external coordination site remains limited 11 and, to our knowledge, there is no example of NHC conjugated with the aromatic core of the porphyrin. Stable N-heterocyclic carbenes (NHCs), first isolated by Arduengo et al. 12 are versatile ligands for transition metal complexes and remain very important in the field of organometallic chemistry and homogeneous catalysis. 13 Beyond catalysis, NHCs are 30 emerging as relevant components in materials science. 14 It is obvious that there is a considerable potential for NHCs containing functional or tunable groups in conjugation with the carbene moiety. 15 Thus, we focused our attention in the design of the porphyrin 1 containing an imidazole ring fused across a β,β'-35 pyrrolic position and fully conjugated to the macrocycle. The formation of the imidazolium salt 2 gives a synthetic access to the porphyrin 3 fused to an NHC (Figure 1).

The peripheral functionnalization of porphyrins is of great interest in order to access to new chromophores or to new 40 multiporphyrin systems. [START_REF] Jaquinod | The Porphyrin Handbook[END_REF] Crossley and co. prepared fused porphyrin-imidazole systems by the condensation of porphyrin-2,3-diones with an arylaldehyde in the presence of ammonia. 17 Following this procedure, the compounds obtained have a 2'arylimidazole ring. Herein, we report an other synthetic approach 45 to access to the fused porphyrin-imidazole 1 with a non functionnalized 2'-imidazole carbon (Scheme 1).

The synthetic porphyrin used as starting material is the complex 4. 18 First, a nitration reaction was realized according to the literature procedure to yield the β-nitroporphyrin 5. 19 The 50 electron withdrawing group NO 2 switched the reactivity of the neighboring pyrrolic β-carbon to an electrophilic center. Callot and co. showed that the 4-amino-4H-1,2,4-triazole is a powerful amination reagent for α,β-unsaturated ketones and aldehydes conjugated with the porphyrin core. 20 This can also be applied to 55 5 and it was possible to get the compound 6 in good yield (81%). The β-NH 2 1 H NMR signal of 6 could be detected as a broad singlet at δ = 6.55 ppm in CDCl 3 . Its UV-visible absorption bands are bathochromically shifted compared to 5. The lowest energy absorption band of 6 shifts to 600 nm (587 nm for 5). Then, we investigated the possibility to generate the carbene fused to the porphyrin 3. As a proof of its existence, we performed the direct metallation of 2 with the basic metal precursor Pd(OAc) 2 in refluxing toluene. 23 This reaction 90 proceeded smoothly leading to the formation of the complex 10 which was purified by chromatography on silica gel (Scheme 3). No signal corresponding to the iminium proton was observed by 1 H NMR spectroscopy (CDCl 3 ) showing the formation of the NHC-Pd(II) bond. The evidence of the formation of the complex 95 10 was also provided by FAB + mass spectrometry. The molecular pic corresponding to the dimer was observed at m/z = 2289. Two fragments were observed at m/z = 2162 and 1324 and correspond to the dimer whose one ligand was removed, respectively the iodine and the porphyrin-NHC. The signal observed at m/z = 963 100 corresponds to the cationic porphyrin 2. The UV-visible absorption bands of 10 are slightly broadened and red-shifted compared to those of the imidazolium 2. This result trends to show that there is negligible ground state electronic communication between the prophyrins through the palladium 105 center.

The single-crystal X-ray analysis † unambiguously establish the structure of the complex 10 and the trans geometry around the palladium (II) (Figure 2). The two porphyrin moieties are not flat but are ruffled because the C( 5)-Ni-C( 15) and C( 10)-Ni-C (20) 110 angles are close to 165°. Despite this distorded geometry of the aromatic core of the porphyrin, the additional imidazoylidene ring and the adjacent pyrrole are coplanar. The nickel (II) was found in an slightly distorded square planar geometry: the four Ni-N distances are almost equivalent (1.900, 1.906, 1.924, and 115 1.960 Å) and the four N-Ni-N angles are close to 90° (88.45, 90.09, 91.16, and 91.29°). In this square-planar trans palladium (II) complex, the Pd-C distances which are consistent with Pd-C single bonds (2.037 Å) are shorter than the Pd-I distances (2.591 Å). The two imidazoylidene rings are close to coplanarity and are 120 tilted ~82° from the square panar central plane PdI 2 C 2 . This tilted conformation minimizes the steric interactions between the methyl groups and the iodines linked to the palladium (II) but also the steric interactions between the t Bu groups close to the palladium center.

125

To conclude, we have presented here a new synthetic procedure to obtain a porphyrin with an additional imidazole ring fused across a β,β'-pyrrolic position. We have shown that it is possible to generate an NHC at the periphery of a porphyrin and to use it as a coordination site to built multiporphyrin assemblies. We are 130 currently studying the tuning of the optical and redox properties of the NHC-porphyrin systems. The synthesis od bis(NHC)porphyrins are also under investigation.

Notes and references † Crystallographic data were recorded with an Xcalibur CCD camera 135 (Oxford Diffraction) using graphite monochromated Mo Ka radiation (λ = 0.71073 Å), 40 s per frame. The structure was solved using Patterson methods [START_REF] Beurskens | a Computer Program System for Crystallography Laboratory[END_REF] and refined using full-matrix least squares methods [START_REF] Betteridge | [END_REF] . Hydrogen atoms (except one belonging to a chloroform molecule) were located from the Fourier difference map and not refined. Crystal data for

3 Fig. 1 7 . 2 |

 3172 Fig. 1 Structures of the complexes 1-7.

diaminoporphyrin 7

 7 was obtained by the reduction of the NO 2 group of 6 with NaBH 4 in the presence of methanol and Pd/C.21 The porphyrin 7 was not isolated but used straightforward for the formation of the imidazole ring.The cyclization reaction with formic acid was more challenging and realized in two steps compared to the classical procedure described for 2,3-diaminobenzene derivatives (one quantitative step).22 First, the alcohol 8 was obtained by the complete condensation reaction of 7 with formic acid in refluxing toluene (1:1 mixture) in less than 10 minutes. Then, two competitive reactions occur in these conditions: the formation of the porphyrin-imidazole 1 by the elimination of a molecule of water and the formation of the ester 9 (Scheme 2). To prevent the formation of the undesirable ester, it was preferable to change the reaction conditions after the formation of the alcohol 8. The imidazole 1 was preferentially obtained by the slow addition of TFA to a refluxing solution of 8 in toluene. The overall yield from 6 to 1 was 48%. The 1 H NMR spectrum of 1 in CDCl 3 shows broad signals due to the slow imidazole tautomerism on the 1 H NMR timescale. The double N-alkylation of the imidazole 80 ring of 1 with iodomethane yields the corresponding imidazolium salt 2 in 76% yield. A sharp singlet at δ = 11.50 ppm corresponding to the iminium C(2')-H is observed in the 1 H NMR spectrum (C 6 D 6 ) of 2. This downfield chemical shift shows the highly electron-withdrawing nature of the metalloporphyrin 85 macrocycle.

Scheme 3 10 Fig. 2

 3102 Scheme 2

| [journal], [year], [vol], 00-00 This journal is © The Royal Society of Chemistry [year]