Guillaume Ducoffe
email: guillaume.ducoffe@ici.ro

Alexandru Popa
email: alexandru.popa@fmi.unibuc.ro

The use of a pruned modular decomposition for Maximum Matching algorithms on some graph classes

Keywords: 2012 ACM Subject Classification Graph theory, Design and analysis of algorithms maximum matching, FPT in P, modular decomposition, pruned graphs, one-vertex extensions, P 4 -structure Digital Object Identifier 10.4230/LIPIcs.ISAAC.2018

We address the following general question: given a graph class C on which we can solve Maximum Matching in (quasi) linear time, does the same hold true for the class of graphs that can be modularly decomposed into C ? As a way to answer this question for distance-hereditary graphs and some other superclasses of cographs, we study the combined effect of modular decomposition with a pruning process over the quotient subgraphs. We remove sequentially from all such subgraphs their so-called one-vertex extensions (i.e., pendant, anti-pendant, twin, universal and isolated vertices). Doing so, we obtain a "pruned modular decomposition", that can be computed in quasi linear time. Our main result is that if all the pruned quotient subgraphs have bounded order then a maximum matching can be computed in linear time. The latter result strictly extends a recent framework in (Coudert et al., SODA'18). Our work is the first to explain why the existence of some nice ordering over the modules of a graph, instead of just over its vertices, can help to speed up the computation of maximum matchings on some graph classes.

Introduction

Can we compute a maximum matching in a graph in linear-time? -i.e., computing a maximum set of pairwise disjoint edges in a graph. -Despite considerable years of research and the design of elegant combinatorial and linear programming techniques, the best-known algorithms for this fundamental problem have stayed blocked to an O(m √ n)-time complexity on n-vertex m-edge graphs [START_REF] Micali | An O( √ V E) algorithm for finding maximum matching in general graphs[END_REF]. Nevertheless, we can use some well-structured graph classes in order to overcome this superlinear barrier for particular cases of graphs. Our work combines two successful approaches for this problem, namely, the use of a vertex-ordering

Related work

A cornerstone of most Maximum Matching algorithms is the notion of augmenting paths [2,[START_REF] Edmonds | Paths, trees, and flowers[END_REF]. However, although we can compute a set of augmenting paths in linear-time [START_REF] Gabow | A linear-time algorithm for a special case of disjoint set union[END_REF], this is a tedious task that involves the technical notion of blossoms and this may need to be repeated Ω( √ n) times before a maximum matching can be computed [START_REF] Hopcroft | An nˆ5/2 algorithm for maximum matchings in bipartite graphs[END_REF]. A well-known greedy approach consists in, given some total ordering (v 1 , v 2 , . . . , v n ) over the vertices in the graph, to consider the exposed vertices v i by increasing order, then to try to match them with some exposed neighbour v j that appears later in the ordering [START_REF] Dragan | On greedy matching ordering and greedy matchable graphs[END_REF]. The vertex v j can be chosen either arbitrarily or according to some specific rules depending on the graph class we consider. Our initial goal was to extend similar reduction rules to module-orderings.

Modular decomposition.

A module in a graph G = (V, E) is any vertex-subset X such that every vertex of V \X is either adjacent to every of X or nonadjacent to every of X. The modular decomposition of G is a recursive decomposition of G according to its modules [START_REF] Habib | A survey of the algorithmic aspects of modular decomposition[END_REF].

We postpone its formal definition until Section 2. For now, we only want to stress that the vertices in the "quotient subgraphs" that are outputted by this decomposition represent modules of G (e.g., see Fig. 1 for an insightful illustration). Our main motivation for considering modular decomposition in this note is its recent use in the field of parameterized complexity for polynomial problems. More precisely, let us call modular-width of a graph G the minimum k ≥ 2 such that every quotient subgraph in the modular decomposition of G is either "degenerate" (i.e., complete or edgeless) or of order at most k. With Coudert, we proved in [START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF] that many "hard" graph problems in P -for which no linear-time algorithm is likely to exist -can be solved in k O (1) (n + m)-time on graphs with modular-width at most k. In particular, we proposed an O(k 4 n + m)-time algorithm for Maximum Matching.

One appealing aspect of our approach in [START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF] was that, for most problems studied, we obtained a linear-time reduction from the input graph G to some (smaller) quotient subgraph G in its modular decomposition. -We say that the problem is preserved by quotient. -This paved the way to the design of efficient algorithms for these problems on graph classes with unbounded modular-width, assuming their quotient subgraphs are simple enough w.r.t. the problem at hands. We illustrated this possibility through the case of (q, q -3)-graphs (i.e., graphs where no set of at most q vertices, q ≥ 7, can induce more than q -3 paths of length four). However, this approach completely fell down for Maximum Matching. Indeed, our Maximum Matching algorithm in [START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF] works on supergraphs of the quotient graphs that need to be repeatedly updated every time a new augmenting path is computed. Such approach did not help much in exploiting the structure of quotient graphs. We managed to do so for (q, q -3)-graphs only through the help of a deeper structural theorem on the nontrivial modules in this class of graphs. Nevertheless, to take a shameful example, it was not even known before this work whether Maximum Matching could be solved faster than with the state-of-the art algorithms on graphs that can be modularly decomposed into paths!

Our contributions

We propose pruning rules on the modules in a graph (some of them new and some others revisited) that can be used in order to compute Maximum Matching in linear-time on several new graph classes. More precisely, given a module M in a graph G = (V, E), recall that M is corresponding to some vertex v M in a quotient graph G of the modular decomposition of G. Assuming v M is a so-called one-vertex extension in G (i.e., it is pendant, anti-pendant, universal, isolated or it has a twin), we show that a maximum matching for G can be computed from a maximum matching of G[M ] and a maximum matching of G \ M efficiently (see Section 4). Our rules are purely structural, in the sense that they only rely on the structural properties of v M in G and not on any additional assumption on the nontrivial modules. Some of these rules (e.g., for isolated or universal modules) were first introduced in [9] -although with slightly different correctness proofs.

Our main technical contributions in this work are the pruning rules for, respectively, pendant and anti-pendant modules (see Sections 4.2 and 4.3). The latter two cases are surprisingly the most intricate. In particular, they require amongst other techniques: the computation of specified augmenting paths of length up to 7, the addition of some "virtual edges" in other modules, and a careful swapping between some matched and unmatched edges.

Then, we are left with pruning every quotient subgraph in the modular decomposition by sequentially removing the one-vertex extensions. We prove that the resulting "pruned quotient subgraphs" are unique (independent from the removal orderings) and that they can be computed in quasi linear-time using a trie data-structure (Section 3). Furthermore, as a case-study we prove that several superclasses of cographs are totally decomposable w.r.t.

this new "pruned modular decomposition". These classes are further discussed in Section 5.

Note that for some of them, such as distance-hereditary graphs, we so obtain the first known linear-time algorithm for Maximum Matching -thereby extending previous partial results obtained for bipartite and chordal distance-hereditary graphs [START_REF] Dahlhaus | Matching and multidimensional matching in chordal and strongly chordal graphs[END_REF]. Our approach actually has similarities with a general greedy scheme applied to distance-hereditary graphs [START_REF] Cogis | Computing maximum stable sets for distance-hereditary graphs[END_REF].

With slightly more work, we can extend our approach to every graph that can be modularly decomposed into cycles. The case of graphs of bounded modular treewidth [23] is left as an interesting open question.

Definitions and our first results are presented in Section 2. We introduce the pruned modular decomposition in Section 3, where we show that it can be computed in quasi linear-time. Then, the core of the paper is Section 4 where the pruning rules are presented along with their correctness proofs. In particular, we state our main result in Section 4.4.

Applications of our approach to some graph classes are discussed in Section 5. Finally, we conclude in Section 6 with some open questions. Due to lack of space, several proofs are omitted. Full proofs can be found in our technical report [START_REF] Ducoffe | The use of a pruned modular decomposition for maximum matching algorithms on some graph classes[END_REF].

Preliminaries

For the standard graph terminology, see [START_REF] Bondy | Graph theory[END_REF]. We only consider graphs that are finite, simple and unweighted. For any graph

G = (V, E) let n = |V | and m = |E|. Given a vertex v ∈ V , we denote its (open) neighbourhood by N G (v) = {u ∈ V | {u, v} ∈ E} and its closed neighbourhood by N G [v] = N G (v) ∪ {v}. Similarly, we define the neighbourhood of any vertex-subset S ⊆ V as N G (S) = v∈S N G (v) \ S.
In what follows, we introduce our main algorithmic tool for the paper as well as the graph problems we study. Pruned modular decomposition and Maximum Matching notation, we will sometimes identify a module M i with the induced subgraph

Modular decomposition

A module in a graph G = (V, E) is any subset M ⊆ V (G) such that for any u, v ∈ M we have N G (v) \ M = N G (u) \ M .
H i = G[M i ],
i.e., we will write P = {H 1 , H 2 , . . . H p }. The quotient subgraph G/P has vertex-set P, and there is an edge between every two modules M i , M j ∈ P such that M i ×M j ⊆ E. Conversely, let G = (V , E ) be a graph and let P = {H 1 , H 2 , . . . H p }. be a collection of subgraphs.

The substitution graph G (P) is obtained from G by replacing every vertex v i ∈ V with a module inducing H i . In particular, for G = def G/P we have that G (P) = G.

We say that G is prime if its only modules are trivial (i.e., ∅, V, and the singletons {v}).

We call a module M strong if it does not overlap any other module, i.e., for any module M of G, either one of M or M is contained in the other or M and M do not intersect.

Let M(G) be the family of all inclusion wise maximal strong modules of G that are proper subsets of V . The family M(G) is a modular partition of G [START_REF] Habib | A survey of the algorithmic aspects of modular decomposition[END_REF], and so, we can define

G = G/M(G).
The following structure theorem is due to Gallai.

Theorem 1 ( [17]

). For an arbitrary graph G exactly one of the following conditions is satisfied.

G is disconnected;

2. its complement G is disconnected;

or its quotient graph G = G/M(G) is prime for modular decomposition.

We now formally define the modular decomposition of G -introduced earlier in Section 1.

We output the quotient graph G = G/M(G) and, for any strong module

M ∈ M(G) that is nontrivial (possibly none if G = G ),

we also output the modular decomposition of G[M ]. By

Theorem 1 the subgraphs from the modular decomposition are either edgeless, complete, or prime for modular decomposition. See Fig. 1 for an example. The modular decomposition of a given graph G = (V, E) can be computed in linear-time [START_REF] Tedder | Simpler linear-time modular decomposition via recursive factorizing permutations[END_REF]. There are many graph classes that can be characterized using the modular decomposition.In particular, G is a cograph if and only if every quotient subgraph in its modular decomposition is either complete or disconnected [START_REF] Corneil | A linear recognition algorithm for cographs[END_REF].

Maximum Matching

A matching in a graph is defined as a set of edges with pairwise disjoint end vertices. The maximum cardinality of a matching in a given graph G = (V, E) is denoted by µ(G).

Problem 1 (Maximum Matching). Input: A graph G = (V, E).

Output: A matching of G with maximum cardinality.

We remind the reader that Maximum Matching can be solved in O(m √ n)-time on general graphs [START_REF] Micali | An O( √ V E) algorithm for finding maximum matching in general graphs[END_REF] -although we do not use this result directly in our paper. Furthermore, let G = (V, E) be a graph and let F ⊆ E be a matching of G. We call a vertex matched if it is incident to an edge of F , and exposed otherwise. Then, we define an F -augmenting path as a path where the two ends are exposed, and the edges belong alternatively to F and not to F . It is well-known and easy to check that, given an F -augmenting path P , the matching E(P )∆F (obtained by symmetric difference on the edges) has larger cardinality than F .

Lemma 2 (Berge, [2]). A matching F in G = (V, E) is maximum if and only if there is no F -augmenting path.

In this paper, we will consider an intermediate matching problem, first introduced in [START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF].

Problem 2 (Module Matching). Input: A graph G = (V , E ) with the following additional information; a collection of subgraphs

P = {H 1 , H 2 , . . . , H p }; a collection F = {F 1 , F 2 , . . . , F p },
with F i being a maximum matching of H i for every i. Output: A matching of G = G (P) with maximum cardinality.

A natural choice for Module Matching would be to take P = M(G). However, we will allow P to take different values for our reduction rules.

Additional notations. Let G , P, F be any instance of Module Matching. The order of G , equivalently the cardinality of P, is denoted by p. For every 1 ≤ i ≤ p let

M i = V (H i ) and let n i = |M i | be the order of H i . We denote δ i = |E(M i , M i )| the size of the cut E(M i , M i )
with all the edges between M i and N G (M i ). In particular, we have

δ i = vj ∈N G (vi) n i n j . Let us define ∆m(G ) = p i=1 δ i . We will omit the dependency in G if it is clear from the context. Finally, let ∆µ = µ(G) - p i=1 µ(H i ).
Our framework is based on the following lemma (inspired from [START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF]). An important observation for our subsequent analysis is that, given any module M of a graph G, the internal structure of G[M ] has no more relevance after we computed a maximum matching F M for this subgraph. More precisely, we will use the following lemma:

Lemma 4 ( [9]). Let M be a module of G = (V, E), let G[M ] = (M, E M ) and let F M ⊆ E M be a maximum matching of G[M ]. Then, every maximum matching of G M = (V, (E \ E M ) ∪ F M ) is a maximum matching of G.
By Lemma 4 we can modify our algorithmic framework as follows. For every instance G , P, F for Module Matching, we can assume that H i = (M i , F i ) for every 1 ≤ i ≤ p. Data structures. Finally, let G , P, F be any instance for Module Matching. A canonical ordering of H i (w.r.t. F i ) is a total ordering over V (H i ) such that the exposed vertices appear first, and every two vertices that are matched together are consecutive. In what follows, we will assume that we have access to a canonical ordering for every i. Such 1 We stress that every polynomial function is subadditive. Furthermore, let F be a (not necessarily maximum) matching for the subdivision G = G (P). We will make the standard assumption that, for every v ∈ V (G), we can decide in constant-time whether v is matched by F , and if so, we can also access in constant-time to the vertex matched with v.

I S A

A pruned modular decomposition

In this section, we introduce a pruning process over the quotient subgraphs, that we use in order to refine the modular decomposition.

Definition 5. Let G = (V, E) be a graph. We call v ∈ V a one-vertex extension if it falls in one of the following cases:

N G [v] = V (universal) or N G (v) = ∅ (isolated); N G [v] = V \ u (anti-pendant) or N G (v) = {u} (pendant), for some u ∈ V \ v; N G [v] = N G [u] (true twin) or N G (v) = N G (u) (false twin), for some u ∈ V \ v.
A pruned subgraph of G is obtained from G by sequentially removing one-vertex extensions (in the current subgraph) until it can no more be done. This terminology was introduced in [START_REF] Lanlignel | Pruning graphs with digital search trees. application to distance hereditary graphs[END_REF], where they only considered the removals of twin and pendant vertices.

Also, the clique-width of graphs that are totally decomposed by the above pruning process (i.e., with their pruned subgraph being a singleton) was studied in [START_REF] Rao | Clique-width of graphs defined by one-vertex extensions[END_REF] 2 . Our contribution in this part is twofold. First, we show that the gotten subgraph is "almost" independent of the removal ordering, i.e., there is a unique pruned subgraph of G (up to isomorphism).

The latter can be derived from the following (easy) lemma: For many graph classes a pruning sequence can be computed in linear-time. We observe that the same can be done for any graph (up to a logarithmic factor).

Proposition 1. For every graph G = (V, E), we can compute a pruned subgraph in O(n + m log n)-time.

Proof. By Corollary 7, we are left with greedily searching for, then eliminating, the onevertex extensions. We can compute the ordered degree sequence of G in O(n + m)-time.

Furthermore, after any vertex v is eliminated, we can update this sequence in O(|N (v)|)time. Hence, up to a total update time in O(n + m), at any step we can detect and remove in constant-time any vertex that is either universal, isolated, pendant or anti-pendant. Finally, in [START_REF] Lanlignel | Pruning graphs with digital search trees. application to distance hereditary graphs[END_REF] they proposed a trie data-structure supporting the following two operations: suppression of a vertex; and detection of true or false twins (if any). The total time for all the operations on this data-structure is in O(n + m log n) [START_REF] Lanlignel | Pruning graphs with digital search trees. application to distance hereditary graphs[END_REF].

  There are trivial examples of modules such as ∅, V, and {v} for every v ∈ V . Let P = {M 1 , M 2 , . . . , M p } be a partition of the vertex-set V . If for every 1 ≤ i ≤ p, M i is a module of G, then we call P a modular partition of G. By abuse of

Figure 1 A

 1 Figure 1 A graph and its modular decomposition.

Lemma 3 .

 3 Let G = (V, E) be a graph. Suppose that for every H in the modular decomposition of G we can solve Module Matching on any instance H , P, F in time T (p, ∆m, ∆µ), where T is a subadditive function 1 . Then, we can solve Maximum Matching on G in time O(T (O(n), m, n)).

  and Maximum Matching orderings can be computed in time O( i |M i | + |F i |) by scanning all the modules and the matchings in F, that is an O(∆m) provided G has no isolated vertex.

Lemma 6 .Corollary 7 .

 67 Let G = (V, E) be a graph and let v, v ∈ V be one-vertex extensions of G. If v, v are not pairwise twins then v is a one-vertex extension of G \ v. Every graph G = (V, E) has a unique pruned subgraph up to isomorphism.

Anti-twins are also defined as one-vertex extensions in[START_REF] Rao | Clique-width of graphs defined by one-vertex extensions[END_REF]. Their integration to this framework remains to be done.

This work was supported by the Institutional research programme PN 1819 "Advanced IT resources to support digital transformation processes in the economy and society -RESINFO-TD" (2018), project PN 1819-01-01 "Modeling, simulation, optimization of complex systems and decision support in new areas of IT&C research", funded by the Ministry of Research and Innovation, Romania.

144:7

We will term "pruned modular decomposition" of a graph G the collection of the pruned subgraphs for all the quotient subgraphs in the modular decomposition of G. Note that there is a unique pruned modular decomposition of G (up to isomorphism) and that it can be computed in O(n + m log n)-time by Proposition 1 (applied to every quotient subgraph in the modular decomposition separately). Furthermore, we remark that most cases of onevertex extensions imply the existence of non trivial modules, and so, they cannot exist in the prime quotient subgraphs of the modular decomposition. Nevertheless, such vertices may appear after removal of pendant or anti-pendant vertices (e.g., in the bull graph).

Reduction rules

Let G , P, F be any instance of Module Matching. Suppose that v 1 , the vertex corresponding to M 1 in G , is a one-vertex extension. Under this assumption, we present reduction rules to a smaller instance G * , P * , F * where |P * | < |P|. Each rule can be implemented to run in O(∆m(G ) -∆m(G * ))-time. Due to lack of space, we skip the complexity analysis.

In Section 4.1 we recall the rules introduced in [START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF] for universal and isolated modules (explicitly) and for false or true twin modules (implicitly). Our main technical contributions are the reduction rules for pendant and anti-pendant modules (in Sections 4.2 and 4.3, respectively), which are surprisingly the most intricate. Finally, we end this section stating our main result (Theorem 14).

Simple cases

We introduce two local operations on a matching, first used in [START_REF] Yu | An O(n)-time algorithm for maximum matching on cographs[END_REF] for cographs. Let F ⊆ E be a matching and let M ⊆ V be a module.

Operation 1 (MATCH). While there are x ∈ M, y ∈ N (M ) exposed, add {x, y} to F .

Operation 2 (SPLIT). While there are x, x ∈ M, y, y ∈ N (M ) such that x and x are exposed, and {y, y } ∈ F , replace {y, y } in F by {x, y}, {x , y }.

Let G = H 1 ⊕H 2 be the join of the two graphs H 1 , H 2 and let F 1 , F 2 be maximum matchings for H 1 , H 2 , respectively. The "MATCH and SPLIT" technique consists in applying Operations 1 then 2 to M = V (H 1 ) and F = F 1 ∪ F 2 , thereby obtaining a new matching F , then to M = V (H 2 ) and F = F . Based on this technique, we design the following rules:

Reduction rule 1 (see also [START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF]). Suppose

Reduction rule 2 (see also [START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF]). Suppose

. We apply the "MATCH and SPLIT" technique to

Reduction rule 4. Suppose v 1 , v 2 are true twins in G . Let F * 2 be the matching of H 1 ⊕H 2 obtained from the "MATCH and SPLIT" technique applied to

Anti-pendant

Suppose v 1 is anti-pendant in G . W.l.o.g., v 2 is the unique vertex that is nonadjacent to v 1 in G . By Lemma 4, we can also assume w.l.o.g. that E(H i ) = F i for every i. In this situation, we start applying Reduction rule 1, i.e., we set

Then, we obtain a maximum matching F * of G \ M 1 (i.e., by applying our reduction rules to this new instance). Finally, from F 1 and F * , we compute a maximum matching F of G, using an intricate procedure. We detail this procedure next.

First phase: pre-processing. Our correctness proofs in what follows will assume that some additional properties hold on the matched vertices in F * . So, we start correcting the initial matching F * so that it is the case. For that, we introduce two "swapping" operations.

Recall that v 2 is the unique vertex that is nonadjacent to v 1 in G .

Operation 3 (REPAIR). While there exist x 2 , y 2 ∈ M 2 such that {x 2 , y 2 } ∈ F 2 and y 2 is exposed in F * , we replace any edge {x 2 , w} ∈ F * by {x 2 , y 2 }.

Operation 4 (ATTRACT). While there exist x 2 ∈ M 2 exposed and {u, w}

Let

Summarizing, we get: Definition 8. A matching F of G is good if it satisfies the following two properties:

Main phase: a modified Match and Split. We now apply the following three operations sequentially:

1. Match(M 1 , F (0) ) (Operation 1). Doing so, we obtain a larger good matching F (1) .

2. Split(M 1 , F (1) ) (Operation 2). Doing so, we obtain a larger good matching F (2) . Operation 5 (Unbreak). While there exist

the operation

and there also exist

, we replace any two edges {y 2 , u}, {z 2 , w} ∈ F (2) by the three edges {x 2 , u}, {y 2 , z 2 } and {w, x 1 }.

We stress that the two edges {y 2 , u}, {z 2 , w} ∈ F (2) always exist since F (2) is a good matching of G. Furthermore doing so, we obtain a larger matching F (3) .

The resulting matching F (3) is not necessarily maximum. However, this matching satisfies the following crucial property:

No vertex of M 1 can be an end in an F (3) -augmenting path.

G. Ducoffe and A. Popa 144:9

Finalization phase: breaking some edges in F 1 . Intuitively, the matching F (3) may not be maximum because we sometimes need to borrow some edges of F 1 in augmenting paths. So, we complete our procedure by performing the following two operations: Let U 1 contain all the exposed vertices in

The set U 1 is a module of this subgraph. We apply Split(U 1 , F (3)

Doing so, we obtain a larger good matching F (4) . Then, we apply LocalAug, defined next (see also Fig. 3 for an illustration): Operation 6 (LocalAug). While there exist x 2 ∈ M 2 and c ∈ N (M 1 ) exposed, and there also exist {x 1 , y 1 } ∈ F 1 ∩ F (4) and {y 2 , z 2 } ∈ F 2 \ F (4) , we do the following:

we remove {x 1 , y 1 } and any edge {a, y 2 }, {b, z 2 } from F (4) ; we add {x 2 , a}, {y 2 , z 2 }, {b, x 1 } and {y 1 , c} in F (4) .

We stress that the two edges {y 2 , a}, {z 2 , b} ∈ F (4) always exist since F (4) is a good matching of G. Furthermore doing so, we obtain a larger matching F (5) .

Lemma 10. F (5) is a maximum-cardinality matching of G.

Pendant

Suppose v 1 is pendant in G . W.l.o.g., v 2 is the unique vertex that is adjacent to v 1 in G . This last case is arguably more complex than the others since it requires both a preprocessing and a post-processing treatment on the matching.

First phase: greedy matching. We apply the "Match and Split" technique to M 1 .

Doing so, we obtain a set F 1,2 of matched edges between M 1 and M 2 . We remove V (F 1,2 ), the set of vertices incident to an edge of F 1,2 , from G. Then, there are three cases.

are nonempty. In particular, suppose there remains an exposed vertex

Our first result in this section is that there always exists an optimal solution that contains F 1,2 . This justifies a posteriori the removal of V (F 1,2 ) from G.

Lemma 11. There is a maximum matching of G that contains all edges in F 1,2 .

We stress that during this phase, all the operations except maybe the last one increase the cardinality of the matching. Furthermore, the only possible operation that does not increase the cardinality of the matching is the replacement of an edge in F 2 by an edge in F 1,2 . Doing so, either we fall in one of the two pathological cases We will assume Property 1 to be true for the remaining of this section.

Second phase: virtual split edges. We complete the previous phase by performing a Split between M 2 , M 1 (Operation 2). That is, while there exist two exposed vertices

x 2 , y 2 ∈ M 2 and a matched edge {x 1 , y 1 } ∈ F 1 we replace {x 1 , y 1 } by {x 1 , x 2 }, {y 1 , y 2 } in the current matching. However, we encode the Split operation using virtual edges in H 2 .

Formally, we add a virtual edge {x 2 , y 2 } in H 2 that is labeled by the corresponding edge

Let H * 2 and F * 2 be obtained from H 2 and F 2 by adding all the virtual edges.

We set

Intuitively, virtual edges are used in order to shorten the augmenting paths crossing M 1 .

Third phase: post-processing. Let F * be a maximum-cardinality matching of the subdivision G * (P * ) (i.e., obtained by applying our reduction rules to the new instance).

We construct a matching F for G as follows. We add in F all the non virtual edges in F * .

For every virtual edge {x 2 , y 2 }, let {x 1 , y 1 } ∈ F 1 be its label. If {x 2 , y 2 } ∈ F * then we add {x 1 , y 2 }, {x 2 , y 1 } in F , otherwise we add {x 1 , y 1 } in F . In the first case, we say that we confirm the Split operation, whereas in the second case we say that we cancel it. Finally, we complete F with all the edges of F 1 that do not label any virtual edge (i.e., unused during the second phase).

Lemma 12. F is a maximum-cardinality matching of G.

The above result is proved by contrapositive. More precisely, we prove intricate properties on the intersection of shortest augmenting paths with pendant modules. Using these properties and the virtual edges, we could transform any shortest F -augmenting path into an F * -augmenting path, a contradiction.

Main result

Our framework consists in applying any reduction rule presented in this section until it can no more be done. Then, we rely on the following result:

Theorem 13 ( [9]). We can solve Module Matching for G , P, F in O(∆µ • p 4 )-time.

We are now ready to state our main result in this paper (the proof of which directly follows from all the previous results in this section).

Theorem 14. Let G = (V, E) be a graph. Suppose that, for every prime subgraph H in the modular decomposition of G, its pruned subgraph has order at most k. Then, we can solve Maximum Matching for G in O(k 4 • n + m log n)-time.

Applications

We conclude this paper presenting applications and refinements of our main result to some graph classes. Recall that cographs are exactly the graphs that are totally decomposable by modular decomposition [START_REF] Corneil | A linear recognition algorithm for cographs[END_REF]. We start showing that several distinct generalizations of cographs in the literature are totally decomposable by the pruned modular decomposition.

Distance-hereditary graphs.

A graph G = (V, E) is distance-hereditary if it can be reduced to a singleton by pruning sequentially the pendant vertices and twin vertices [START_REF] Bandelt | Distance-hereditary graphs[END_REF].

Conversely, G is co-distance hereditary if it is the complement of a distance-hereditary graph, i.e., it can be reduced to a singleton by pruning sequentially the anti-pendant vertices and twin vertices. In both cases, the corresponding pruning sequence can be computed in lineartime [START_REF] Damiand | A simple paradigm for graph recognition: application to cographs and distance hereditary graphs[END_REF][START_REF] Dubois | On co-distance hereditary graphs[END_REF]. Therefore, we can derive the following result from our framework:

G. Our proof is based on a deep structural characterization of tree-perfect graphs [START_REF] Brandstädt | Tree-and forest-perfect graphs[END_REF].

The case of unicycles. We end up this section with a refinement of our framework for the special case of unicyclic quotient graphs (a.k.a., graphs with exactly one cycle).

Proposition 4. We can solve Maximum Matching in linear-time on the graphs that can be modularly decomposed into unicycles.

For that, we reduce the case of unicycles to the case of cycles (removing pendant modules). Then, we test for all possible numbers of matched edges between two adjacent modules.

Doing so, we reduce the case of cycles to the case of paths.

Open problems

The pruned modular decomposition happens to be an interesting add up in the study of Maximum Matching algorithms. An exhaustive study of its other algorithmic applications remains to be done. Moreover, another interesting question is to characterize the graphs that are totally decomposable by this new decomposition. We note that our pruning process can be seen as a repeated update of the modular decomposition of a graph after some specified modules (pendant, anti-pendant) are removed. However, we can only detect a restricted family of these new modules (i.e., universal, isolated, twins). A fully dynamic modular decomposition algorithm could be helpful in order to further refine our framework.


C S Unnikrishnan

Reconstructing Quantum Mechanics Without Foundational Problems

I present a reconstruction of quantum mechanics with a new interpretation of the wavefunction and the Schroedinger equation that eliminates all its foundational problems. The key …nding is that the wavefunction is a hybrid entity involving the ensemble average of particle dynamics, without superposition, while the phase-waves pertaining to the single quantum events reproduce all interference e¤ects. The reconstructed quantum mechanics without 'matter waves' eliminates the cardinal problem known as the collapse of the wavefunction and with that, the vexing issue of quantum measurement. Another signi…cant advance is the correct decoding of quantum entanglement and purging of inseparability and nonlocality in quantum correlations. The resulting picture is in complete agreement with all empirical requirements and in harmony with credible physical ontology. The reconstruction and interpretation dissolve the quantum-classical divide.

Introduction

Quantum mechanics is believed to be a universal theory of physical phenomena, with a simple mathematical structure that is well established. Its empirical success and reach are unprecedented. Yet, there is no consensus on a satisfactory interpretation and understanding of quantum mechanics [START_REF] Feynman | The Character of Physical Law -Probability and Uncertainty: The Quantum Mechanical View of Nature[END_REF][START_REF] Laloë | Do We Really Understand Quantum Mechanics[END_REF][START_REF] Weinberg | The Trouble with Quantum Mechanics[END_REF].

I present a reconstruction of quantum mechanics (QM) and the Schroedinger equation, with new physical input and interpretation of the wavefunction. The reconstruction is based on two distinct physical entities -the material particle, which is the carrier of dynamical quantities like energy and momentum, and the associated 'action-waves' (or 'phase-waves') that are the carriers of 'action', with no energy or momentum. The particle's dynamics is linked to the phase and its fundamental uncertainty, of the phase-waves in a wave-particle connection. Material particle does not behave as waves or superpose; there are no matter waves. I will show that the wavefunction of the Schroedinger dynamics is really a hybrid entity involving the ensemble averaged probability density for the material particle, without superposition, and phase-waves of quantum possibilities that can superpose and interfere, event by event. Thus, the probabilistic particle dynamics and the vital quantum interference are intact. There is a radical change in the physical basis and interpretation, while the mathematical super-structure and operations remain intact because the quantum mechanical calculations pertains to the averages over the (virtual) ensemble. This purges QM of all its foundational problems.

The conventional formalism of QM leads to several vexing problems, debated as its 'birth defects' [START_REF] Laloë | Do We Really Understand Quantum Mechanics[END_REF]4,[START_REF] Norsen | Foundations of Quantum Mechanics[END_REF]. Foremost is the core issue known as the collapse of the wavefunction during an observation. The quantum physical state is represented by a state vector in Hilbert space, ji. This can be linear superposition of component states ji = P   j  i, with P j  j 2 = 1. When a measurement is made, only one of the possible results  =  materializes, stochastically. The quantum state is said to collapse uniquely to j  i, with other components disappearing instantaneously.

The problem of collapse gets di¢cult for multi-particle systems. For a two-particle two-state system, with possibilities j+i and j¡i, the joint state may be a linear superposition  1 j+ 1 ij¡ 2 i +  2 j¡ 1 ij+ 2 i, called an entangled state. Then, the state is not separable into single particle states and there is no individual quantum state for either particle. Measurement on one particle returns a de…nite value of the observable, and endows a quantum state, say j¡ 1 i. Then, instantaneously, the other particle, which could be spatially widely separated, acquires a correlated state j+ 2 i, without any interaction. This nonlocal collapse is the basis of the Einstein-Podolsky-Rosen [START_REF] Einstein | Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?[END_REF] discussion.

The ensuing quantum measurement problem [START_REF] Norsen | Foundations of Quantum Mechanics[END_REF][START_REF] Leggett | The Quantum Measurement Problem[END_REF] is closely linked to the collapse of the wavefunction. If two physical states of a system are represented as j1i  and j2i  the physical system can also be in the state  j1i  +  j2i  with jj 2 + jj 2 = 1 During a measurement, another physical system acting as the ideal measurement 'apparatus' with pointer states j1i  and j2i  interacts with the system and forms the correlated and entangled state

 j1i  j1i  +  j2i  j2i  (1)
Then, neither the microscopic system nor the macroscopic apparatus has any independent physical state. This is the same as the much discussed problem of the Schroedinger's cat, where the 'apparatus system' is macroscopic and possibly living. The …nal (conscious) experience about the measurement is however, either the state j1i  j1i  or the state j2i  j2i   and not a superposition. The process by which this 'state reduction' and the appearance of a unique pointer state happens is a mystery. Finally, despite many proposals, there is no satisfactory understanding of the emergence of the classical macroscopic world from what is believed to be the more fundamental quantum world. The answer would lie in solving the measurement problem.

The Reconstructed Quantum Mechanics (RQM) eliminates all these foundational problems in one stroke.

Reconstruction of QM

In RQM, I carefully distinguish the three di¤erent notions -the material entity or particle, its physical state, and the representation of the state in the theory. Empirically we know that the 'particle' is indivisible. However, we also know from quantum interference of multiple paths in space that there seems some physical entity that responds to the multiple possibilities, event by event [START_REF] Unnikrishnan | Origin of quantum-mechanical complementarity without momentum back action in atom-interferometry experiments[END_REF].

In the reconstruction, the particle exists as a real undivided entity at all times, without superposition. The physical state of the particle, with its fundamental charges like electric charge, mass, spin etc., is characterized by a set of dynamical variables   (energy, momentum, angular momentum etc.) and associated coordinates   at all times. Associated with the particle is the distinct 'phase-wave', which is the physical entity that splits into multiple possibilities, recombine, and interfere, event by event. There is no matter wave; there are only the action-waves associated with matter. The phasewaves carry 'action' and they do not have energy or momentum. These are complex quadrature waves (sine and cosine) in general. They are 'waves' in the sense of a periodicity in phase, related to the quantum of action . Only the combinations of the dynamic variables and generalized coordinates in the form of a action-phase R     appear in the time evolution of the phase-wave. Then, dynamics is completely characterized by the coordinate derivatives of the phase function. The fundamental uncertainty in the action is the Plank quantum . Therefore, exact values cannot be assigned to the dynamical variables and associated coordinates simultaneously. It is the phase of the phase-wave that is directly linked to indeterminism and scatter in the observables of the particle. The quantum uncertainty is a scatter relation over the ensemble of events for the particle.

QM is then really the fusion of two fundamental features; stochastic particle dynamics and event by event quantum interference of phase-waves. The particle is in a de…nite physical state at every instant and does not partake in superposition. The ensemble average of the set of all possibilities of particle dynamics match the phase-wave superposition, as I will show. A hybrid function represents the physical state, which has a positive real part related to the ensemble average of the statistical behaviour of the particle and another part that is a pure phase-wave. Both the particle and its phase-waves exist in real space and time and the hybrid wavefunction is in the Hilbert space of QM. Thus, Schroedinger equation is a hybrid evolution equation. I stress that the phase-waves do not carry or exchange energy or momentum. The particle, on the other hand, has the usual dynamics, involving forces and exchange of energy and momentum. The fundamental trait of quantum dynamics is the relation between the two, where the value of the relative phase determines the probability for the particle to take di¤erent values of the dynamical variables from multiple possibilities. RQM based on this structure resolves all foundational problems. Before presenting the details, an example of a matter interferometer in RQM is depicted in …gure 1, as illustration.

The relation between the action function ( ) and dynamics is rooted in Hamilton's dynamics [START_REF] Hamilton | Second Essay on a General Method in Dynamics[END_REF], evolved from his 'general method of expressing the paths of light and of the planets', which guided Schroedinger as well [START_REF] Schrödinger | An undulatory theory of the mechanics of atoms and molecules[END_REF]. The fundamental relation is

( )  = ¡ ( 2
)
where  is the Hamiltonian. The characteristic aspects of quantum dynamics is the existence of a minimum 'quantum of action', , and the phenomenon of quantum interference. Hamilton's fundamental relation can be incorporated in the dynamics of an entity capable of interference by writing the evolution equation for the complex action-wave (phase wave),  = exp(~). The phase  in the function exp() is R     where  stands for dynamical variables like momentum, energy, spin etc. and  are the associated coordi-nates.  is an elementary quantum of action, and …xed as ~from empirical data. Energy is the time derivative of the phase and the momentum is the gradient of the phase. With  = ( 2 2) +  and  = r, dynamics can be described in terms of the action-waves as

~   µ = ¡   ¶ = ¡ ~2 2 ¡ r 2 +  ¢  = ¡2  r 2  + 1 2 (r) 2 (3)
Now, there is a pure imaginary 'quantum action' term, nonzero only when r¢ = r 2  is nonzero. The very existence of a scale for the action, necessary in the action-wave, manifests when a spatial distribution of momenta of the particles are present; this implies a multi-particle situation or a statistical ensemble of single particle dynamics. We will see the relevance of this term in the next step in the reconstruction. This term is not signi…cant for the dynamics of macroscopic objects with   ~. The probability density  of the intrinsically stochastic particle dynamics obeys a continuity (conservation) equation,

( )  = ¡r ¢ () (4)
 is the ensemble averaged real quantity. If the positive real

( ) =  2 ( ), we get   = ¡  2 r ¢  ¡  ¢ r = ¡  2 r 2  ¡ 1  r ¢ r (5)
We can recast this equation of constraint as a 'wave equation' by de…ning the pseudo-wave ( ) =  12 ® exp() ´ exp(). The time evolution  is represented in the real part of the evolution . The mathematical independence of  from the dummy phase is ensured with  =  2 = j ¤ j 12 . This is the exact Born's rule.

It is striking that the ensemble of particle dynamics and the continuity of its probability density can be combined if we elevate the dummy quantity  to the action ( ) in a hybrid function ( ) = ¹ ( ) exp(( )~). Here, ¹  ´ is an ensemble averaged quantity and ( )~is phase of the phase-wave of single particle dynamics. Thus, the wavefunction is not the matter-wave. Nor is it a probability wave.

Then,

~   = ¡   + ~    (6)
What is really remarkable is that the di¤erential terms required for   as well as for   are obtained from the single quantity r 2 .

¡ ~2 2 r 2  =  2 (r) 2 + ~ 2    r 2  ¡ ~ 2 r 2  ¡    r ¢ r (7)
The last three terms are related to the ensemble averaged time evolution and they are not active in the single particle dynamics, because the quantity  is an ensemble average of all events. For a given single event, the particle state is well de…ned and there is no  and its derivatives. The characteristic feature of quantum dynamics is the Heisenberg uncertainty, encoded as the uncertainty in the phase ~as  ' ~. This manifests in the scatter in  and  in the statistical ensemble of particle events as ¢¢ ' ~. This is the source of the additional di¤usive and dissipationless ensemble uncertainty term (~2) r 2  in  that a¤ects the time evolution of the hybrid . It is entirely independent of  or its derivatives, and not relevant for single events, since  and its derivatives exist only as ensemble averages (we stress this vital di¤erence with the de Broglie-Bohm formulation where such a term is associated with a potential acting on single particle dynamics, resulting in nonlocal e¤ects). Combining all the terms we arrive at the hybrid equation for the ensemble averaged time evolution of the hybrid quantity ,

~   = ¡ ~2 2 r 2  +   (8)
which generalizes to ~_  = , which is the Schroedinger equation, but with a radically new inner structure and interpretation. In this bottom up construction, we have discovered that the Schroedinger equation is an ensemble equation as well as a single particle equation. It is not an equation for matter waves or probability waves.

The particle is always in a unique physical state, as a single whole. In contrast, the phase-waves associated with the states j  i are present with every realization of the evolution in the ensemble, responsible for superposition and interference. They are necessarily in quadrature combination with uniform magnitude, or cos  +  sin  = exp(), because  =  ¤ is without real oscillations in space, in general. The hybrid wavefunction ji = hi 12 ji exp(~) is the entire representation of the physical state.

As an example, in a 70:30 beam splitter, or two slits with width ratio 07 : 03, the phase-wave splits in the ratio   :   = p 07 : p 03, in each event, with each particle, irrespective of whether the particle takes path 1 or 2, with probability (over the virtual ensemble) 07 : 03. Both the measurement results and e¤ect of quantum interference are then correctly reproduced for each particle.

The reconstructed quantum mechanics (RQM) solves all the foundational problems of conventional quantum mechanics in one stroke.

RQM without foundational problems Particle dynamics and interference

In RQM, as the material particle encounters a fork of possibilities   , it takes exactly one  =  with the probability determined by the experimental set up (beam splitters, slits etc.) and the initial phase of the quantum state at that instant. The material particle is in one unique path (state) at any instant, in a given event. The phase-wave splits and propagates in all paths (…g. 1). The interference of phase-waves determine the subsequent probability of partition into other states. When a measurement is done in eigen-basis, the result is the factual state of the particle. When a measurement of position is done, the particle is found where it actually is. Born's rule is reproduced exactly by the ensemble average. There is no collapse of the wavefunction, because the phase-waves do not collapse and the amplitude of the hybrid wavefunction is an ensemble average. The phase-waves, which do not carry energy or momentum, continue their propagation, but it is irrelevant for further detail of the dynamics of the particle. The interactions of the phasewaves involve exchange of only phase. This is the essence of wave-particle connection in RQM. No conservation law is a¤ected. The superposition like  1 j 1 i +  2 j 2 i is only applicable to the phase-waves. For the particle,  1 and  2 refers to an ensemble with probability  2  =   in the state j  i. If particle is allowed to propagate without interruption by detection to the point where the phase-waves are recombined, the phase di¤erence after interference determines the subsequent probabilities.

Consider a generic symmetric interferometer for neutrons, …gure 2, with the …eld  and its gradient  0 in the z-direction. At the point of entry in the apparatus, the random initial phase of x-polarized neutrons results in the random choice of j+i or j¡i state and path a particular neutron actually takes. The particle propagates exactly in one of the paths and unique state (j+i or j¡i) in each event, with no superposition. Measurement before path closure results in the factual state of the particle state; there is no collapse. The phase-waves corresponding to both states are present in every event, accumulating the dynamical phase R , and the phase from the interaction  ()~=  ¢ ~. If there are spin ‡ippers in the paths, the actual spin ‡ip with the energy exchange ¢ = 2   happens only for the particle, where it is actually propagating. The phase-wave changes its phase by 2 as they pass the spin ‡ipper, but there is no energy exchange.

The initial phase-waves corresponding to the possibilities of the particle states are

j+i = 1 p 2 j+i + 1 p 2 j¡i j¡i = 1 p 2 j+i ¡ 1 p 2 j¡i (9)
This is very similar to a Mach-Zehnder interferometer with a polarizing beamsplitter and two orthogonal input states. The time evolved phase-waves superpose at the exit as

j 0 +i = 1 p 2 j+i  +  + 1 p 2 j¡i  ¡  (10)
The quantity  § ´ §  ~. Note that the probability for the particles to be in the j+i and j¡i does not change due to the phase evolution. Now the probability for getting the particle in the state j¡i can be calculated,

j h ¡ j 0 +i j 2 = ¯1 2 ¡   +  ¡   ¡  ¢ ¯2 = 1 2 µ 1 ¡ cos 2   ~ ¶ (11)
We have reproduced the most important feature of quantum interference, while avoiding the collapse of the wavefunction. When the particle emerges out, the resultant phase of the phase-waves from both the paths determine the subsequent probability to be found in states j §i j §i etc.

As other examples, a massive neutrino of one ‡avour is in one of the three mass states and never in superposition of the three. The phase-waves corresponding to the mass states superpose and interfere, resulting in oscillations in the probabilities for di¤erent ‡avour states. Similarly, an atom is never in a superposition of two positions or energy states; the phase-waves are, which carry no energy. The reconstruction generalizes to the Dirac equation ~_  =  , with the same Hamilton's relation as the basis for relativistic particle dynamics as well. This resolves the foundational issue of 'zitterbewegung', identifying it as the ensemble average [START_REF] Unnikrishnan | Reconstructed Quantum Mechanics: Causal, Local, Universal, and Without the Collapse of the Wavefunction[END_REF].

A multi-particle 'entangled' system in RQM is equally simple. The superposition represented as  1 j+i 1 j¡i 2 +  2 j¡i 1 j+i 2 are applicable only to the associated phase-waves. The joint physical state of the two particles is always a unique unentangled state, like j+i 1 j¡i 2 or j¡i 1 j+i 2 . The probabilities for measurement results in a general basis are determined by the relative phase of the superposed phase-waves, now with the correlated pairs of phase-waves (see later). Hence there is no collapse of the state. Ensemble average gives j 1 j and j 2 j and determine the hybrid wavefunction; 'entanglement' is apparent and an ensemble statement. RQM deconstructs the enigma of quantum entanglement, restoring the physicality and separability of the particle states. I will show that the phase-waves interfere locally to give all correlations correctly, after addressing the vital quantum measurement problem.

Quantum measurement problem

A quantum system that can be in the superposition P   j  i, after interaction with an apparatus with pointer states j  i, is conventionally in the correlated entangled state

ji  = P   j  i j  i (12)
However, in RQM, only the phase-waves superpose, and the matter states are unique and distinct at every event. Entanglement is an ensemble apparition. In each trial, a unique state of the system, determined by the local interference of the phase-waves, results in a unique correlated pointer state after the interaction. We already saw how the deterministic Schroedinger equation is related to (virtual) ensemble average of the indeterministic particle dynamics. Since there is no collapse of the state of either the system or the apparatus, the quantum measurement problem is solved completely. The joint state after interaction at any measurement event is exactly one of the possible j  i j  i. The ensemble average of such multiple measurements has the relative probability j  j 2 . The macroscopic apparatus is characterized by the stable phase of its state, because the quantum uncertainty in the phase amounting to a few ~is insigni…cant compared to the gross action of the large physical system. Otherwise, there is no di¤erence between macroscopic and microscopic matter, in RQM.

As we have already solved the problem of quantum measurement, there is no quantum-classical divide or transition in RQM. Neither is any involvement of 'consciousness', beyond what is obvious and familiar. The phase-waves of the macroscopic systems interfere over tiny spatio-temporal intervals, much smaller than atomic scales, and thus quantum interference is not e¤ective in determining their dynamics.

Entanglement and Correlations

We conclude with the solution of the hard problem of the correlation of the two-particle entangled system in which the enigma of quantum mechanics appears in the most pronounced way. Consider a two-particle state that is correlated in momentum, but restricted to two possible values § (two paths) in an interference experiment, as shown in Fig. 2A. The particles are always in some de…nite correlated physical state, either j+i 1 j¡i 2 or j¡i 1 j+i 2 , in a given pair-event. There is no superposition of two-particle states. Two pairs of phase-waves, (+ 1  ¡ 1 ) and (+ 2  ¡ 2 ), associated with the two particles are present in each event. Phase-waves are correlated at the source (or interaction point) through the conservation laws [START_REF] Unnikrishnan | Correlation functions, Bell's inequalities and the fundamental conservation laws[END_REF][START_REF] Unnikrishnan | The incompatibility between local hidden variable theories and the fundamental conservation laws[END_REF][START_REF] Unnikrishnan | Is the quantum mechanical description of physical reality complete? Proposed resolution of the EPR puzzle[END_REF]. When the dynamical quantity   is conserved, it re ‡ects in the phase exp(    ), with

  =  1 +  2 .
The sum of the initial phases are …xed by the conservation constraint, but the individual phases are random. I will now derive the two-particle correlation from entirely local interference of phase-waves, retaining the independent physical states of the particles, eliminating nonseparability and nonlocality, and answering the EPR query.

Referring to Fig. 3A, the source emits the particles with opposite momenta ( ¥1   ¡2 ) or ( ¡1   +2 ). The source size has to be larger than  for getting correlated particles, where  signi…es the degree of the lack of correlation. Thus, the point of origin   of the particles varies by more than ¢ § event to event, stochastically. Two pairs of correlated phase-waves from   are present in each event;  ¥1 and  ¡1 associated with particle #1 and  +2 and  +2 with particle #2. They interfere locally at the detector D1 at  1 and at the detector D2 at  2 .

j1  1 i = 1 p 2   +1 ( 1 ¡  )~+ 1 p 2   ¡1 ( 1 ¡  )j 2  2 i = 1 p 2   ¡2 ( 2 ¡)~+ 1 p 2   +2 ( 2 ¡)~( 13)
The phase-waves  +1 wave is always coupled with the  ¡2 wave and the  ¡1 wave with  +2 wave; there are no ( +1   +2 ) or ( ¡1   ¡2 ) combinations. Because of the conservation constraint, the  +1   ¡2 phase-waves are like single coherent phase wave; so are  ¡1   +2 . Also,  + = ¡ ¡ . The detected intensity at detector #1 of area  is jj1

 1 ij 2 . jj1  1 ij 2 = 1 + 1 2   +1 ( 1 ¡)~¡ ¡1 ( 1 ¡)~+ 1 2   ¡1 ( 1 ¡)~¡ +1 ( 1 ¡)= 1 + 1 2  ( + ¡ ¡ )( 1 ¡)~+ 1 2  ¡( + ¡ ¡ )( 1 ¡)~= 1 + cos (¢ ( 1 ¡   )) (14)
We have written ~= . For particle #2, we get a similar expression jj2  2 ij 2 = 1 + cos (¢ ( 2 +   )). Though these are the familiar cosine forms of interference, there is no single particle interference because the source point   is a stochastic quantity in the extended source, and   ¢ ¸2.

Thus, jj1  1 ij 2 ® = jj2  2 ij 2 ® = 1
, a uniform intensity. However, for the two-particle coincidence detection in the two detectors involves simultaneous, but independent, local interference of the phase-waves at location 1 and 2,

j1  1 i j2  2 i = µ 1 p 2   +1 ( 1 ¡) + 1 p 2   ¡1 ( 1 ¡) ¶ 1 µ 1 p 2   ¡2 ( 2 ¡) + 1 p 2   +2 ( 2 ¡) ¶ 2 (15) Keeping in mind that there is no ( +1   +2 ) or ( ¡1   ¡2 ) combinations, j1  1 i j2  2 i = 1 p 2   +1 ( 1 ¡) 1 p 2   ¡2 ( 2 ¡) + 1 p 2   ¡1 ( 1 ¡) 1 p 2   +2 ( 2 ¡)
(16) The detected intensity-intensity correlation is

jj1  1 i j2  2 ij 2 = 1 2 + 1 4  ( ¡ ¡ + )( 1 ¡)  ¡( ¡ ¡ + )( 2 ¡) + 1 4  ¡( ¡ ¡ + )( 1 ¡)  ( ¡ ¡ + )( 2 ¡) = 1 2 + 1 4  ¢( 1 ¡ 2 ) + 1 4  ¡¢( 1 ¡ 2 ) = 1 2 (1 + cos (¢  ( 1 ¡  2 ))) (17)
This is an interference pattern with 100% visibility, visible by …xing one detector and scanning the other. There is no wavefunction collapse and there is no nonlocality. Any mixture or lack of correlation in phase-waves results in the reduction of visibility, eventually dropping to 50% for the thermal state, as in the Hanburry Brown-Twiss correlation.

The correlation of the entangled spin singlet that epitomizes all the quantum mysteries is treated similarly in RQM. When the pair of particles emerge from the source with total spin zero, they are randomly but entirely in only one of the two possible joint states j § i = j+i 1 j¡i 2 or ¯0 ¨® = j¡i 1 j+i 2 , with no superposition. The phase-waves corresponding to both states are present in every event. The ensemble averaged hybrid wavefunction is hj = 0ii = (j+i 1 j¡i 2 ¡ j¡i 1 j+i 2 )  p 2 in any basis. This entanglement is not a statement on each pair, but over the ensemble.

For the case of spins, the initial random angular orientation  in …g. 3B is like the random origin   in …g. 3A. The spin analyzer orientation   corresponds to a stable phase, exactly as the detector position in the example of the interference. Phase-waves associated with each particle superpose and interfere, locally at analyzer 1 and 2 as

j1i = 1 p 2 j+i 1   +  1  ¡ +  + 1 p 2 j¡i 1   ¡  1  ¡ ¡  j2i = 1 p 2 j+i 2   +  2  ¡ +  + 1 p 2 j¡i 2   ¡  2  ¡ ¡  (18)
For independent detection, say particle #1 in the state j+i, with spin analyzer oriented at  1 the situation is analogous to interferometer in …g. 2, but now with a random phase included. We get the probability

 (1+  1 ) = jh1+j j1ij 2 = ¯1 2   +  1  ¡ +  + 1 2   ¡  1  ¡ ¡  ¯2 = 1 2 + 1 2 cos (¢ ( 1 ¡ )) (19)
Since  is stochastic in the interval (0 2), the average of cos ¢ ( ¡  1 ) is zero and there is uniform probability 12 for detecting +1 and ¡1 for the spin projections, for any setting of the apparatus.

The joint detection is with the constraint that j+i 1 phase-wave is correlated with the j¡i 2 wave and the j¡i 1 phase-wave is with the j+i 2 wave. This is analogous to a double-interferometer, as in …g. 3A. There are no j+i 1 j+i 2 wave or j¡i 1 j¡i 2 combinations.

j1 2i = 1 2 j+i 1   +  1  ¡ +  j¡i 2   ¡  2  ¡ ¡  + 1 2 j¡i 1   ¡  1  ¡ ¡  j+i 2   +  2  ¡ +  (
20) The probability for joint measurement of (+ ¡) or (¡ +) for the spin projections with their product ¡1 is

 +¡¡+ = jj1 + 2 ¡  1 ¡ 2 + ij 2 = 1 2 + 1 4  ¡( + ¡ ¡ )( 1 ¡ 2 ) + 1 4  ( + ¡ ¡ )( 1 ¡ 2 ) = 1 2 (1 + cos(¢ ( 1 ¡  2 ))) = cos 2 ( 1 ¡  2 ) 2 (21)
Then the probability to get (+ +) or (¡ ¡) for the spin projections with their product +1 is

 ++¡¡ = jj1 + 2 +  1 ¡ 2 ¡ ij 2 i = 1 ¡ cos 2 ( 1 ¡  2 ) 2 = sin 2 ( 1 ¡  2 ) 2 (22)
The …nal spin correlation is

( 1 ¡  2 ) = ¡1 £  +¡¡+ + 1 £  ++¡¡ = ¡ cos ( 1 ¡  2 ) (23)
I have derived the singlet correlation in the RQM without the wavefunction collapse or nonlocality, from local interference of the phase-waves. When ( 1 ¡  2 ) = 0, we get perfect anti-correlation event by event for every pair of particles, irrespective of the individual setting of the analyzers or the distance between the particles. Resolution of this problem, considered the greatest quantum mystery, shows the correctness and scope of the RQM. All familiar results involving bipartite correlations, like teleportation, are possible through the phase-wave correlation, while particle states remain separable and unentangled.

Concluding remarks

I have reconstructed quantum mechanics solving all its vexing foundational and conceptual problems. The key …nding is that the wavefunction of the Schroedinger equation is a hybrid quantity encoding the ensemble averaged stochastic dynamics of particles with real physical states and the phasewaves that accumulate the dynamical phases in all possibilities, event by event. This new wave-particle connection, rather than duality, in RQM eliminates the collapse of the wavefunction, the measurement problem, and the quantum-classical divide. It restores separable independent particle states in quantum entanglement and eliminates nonlocality. The reconstruction extends to relativistic QM, quantum optics, and the Dirac equation, enabling the resolution some foundational issues [START_REF] Unnikrishnan | Reconstructed Quantum Mechanics: Causal, Local, Universal, and Without the Collapse of the Wavefunction[END_REF]. With the waves as phase carriers, the divergent energy that is usually associated with the quantum vacuum modes is no more troublesome. It is hoped that RQM will result in the de…nite closure of the philosophical debates anchored on the conceptual issues of QM [START_REF] Wayne | Philosophical Issues in Quantum Theory, The Stanford Encyclopedia of Philosophy[END_REF]. RQM makes it clear that matter states and their long-range …elds do not superpose. The entity in superposition, the phase-waves, do not have energy-momentum. Also, there is no physical sense in the superposition of states when there is only single realization of a material system. Therefore, RQM will rechart the conceptual trajectory in the …elds of quantum gravity and quantum cosmology.

Figure 1 :

 1 Figure 1: Matter dynamics and phase-wave interference in RQM, correctly reproducing statistical results of measurements as well as quantum interference, without collapse and other foundational issues. Particle dynamics has two distict possibilities inside the interferometer that do not superpose, and two at exit (B) Particle probabilities at exit are determined by the relative phase of the two interfering phase-waves (broken arrows), which are present in every event.

Figure 2 :

 2 Figure 2: The making of the hybrid wavefunction. A and B are two realizations of the spin-1/2 particle dynamics in a Stern-Gerlach device. The particle enters in a de…nite spin state and its dynamics continues in one of the two possibilities, Up or Down, in each run. There is no superposition of particle states. The ensemble average over all realizations gives the real positive part of the hybrid wavefunction. The phase-waves corresponding to both the possibilities (dashed arrows) are present in both A and B. Their relative phase at the end, where paths are recombined, determines to probabilities of subsequent spin projections.

Figure 3 :

 3 Figure 3: Quantum correlations of entangled systems in RQM derived from the local and independent interference of the phase waves at the detectors. (The de…nite physical states of the particles are not shown). The uncertainty in the initial phase washes out interference at individual detectors, but their correlation is a de…nite function with 100% 'visibility'. For identical settings, we get perfect correlation without any nonlocality.


Carole Chevalier

Jean-Charles Walter

John Palmeri

Andrea Parmeggiani

Frederic Geniet

Jerome Dorignac

Nils-Ole Walliser

Eric Rivals

Damien Paulet

Alexandre David

Frédéric Geniet

Jérôme Dorignac

Modelling Spatio-temporal Dynamic of Ribosome During Translation

Keywords: Monte Carlo, TASEP, lattice gas, mean field theory, translation, deep sequencing

come   L'archive ouverte pluridisciplinaire

MAIN RESULTS

Extended model

Calculate Speed of Ribosomes

How are these preferred codons selected ? By their speed ?

S. cerevisiae htg (C1)

A similar graph for the low translated genes of S. cerevisiae → Preferred codons of C1 and C2 are therefore not selected by speed

Gene expression

: a future protein

Ribo-Seq

Bioinformatic treatment

Ribosome-profiling strategy based on the deep sequencing of ribosome-protected mRNA fragments (RPF).

  [*] D. Paulet, A. David and E. Rival. Ribo-seq enlightens codon usage bias. DNA Research 2017, 24(3), 303-310 No correlation 61 codons and 20 amino acids →The genetic code has redundancy. Severals codons specify the same amino acid. Example : 1 codon →1 amino acid 1 site ↔ 1 codon 1 ribosome covers 9 codons... ...and moves codon by codon... by the bioinformaticians and biologists of the GEM consortium show that there is a preferred codon for each amino acid [*]. relative speed (to cancel 𝜶) for each codon c :

  n a : number of synonymous codons for amino acid a x a,c : number of codons c Relative Synonymous Codon Usage estimation of preferred codons

  speed analysis with other species (simple and evolved) • The design of Ribo-seq experiments with a finite number of ribosomes may allow one to determine alpha • Impact of boundary layer on density variation with the length of mRNA PERSPECTIVES :

phase : Codon Usage Bias (CUB)

	UUA
	UUG
	CUU
	CUC
	CUA
	CUG
	1 codon → 1 amino acid but not
	necessarily different

Measured physiological rates :

Translation is in low density phase Mean field approximation : close neighbors correlations are neglected. We can write the speed as jump rates in low density