Younes Regragui
email: regragui.y@ucd.ac.ma

Najem Moussa
email: moussa.n@ucd.ac.ma

Laroseri

A Cellular Automata Model for Urban Traffic with Multiple Roundabouts

Keywords: cellular automaton, traffic flow, city, roundabout, gridlock

Urban transportation with multiple roundabouts is facing significant challenges such as traffic congestion, gridlock and traffic accidents. In order to understand these behaviors, we propose a two-dimensional cellular automata (CA) model, where all streets are two-way, with one lane in each direction. To allow the turning movement, a roundabout is designed for each intersection where four roads meet. The distance between each pair of roundabouts is configured with the parameter K while the turning behavior of drivers is modeled by a parameter γ. To study the impact of these different parameters on the urban traffic, several traffic metrics are considered such as traffic flow, average velocity, accident probability and waiting time at the entrance of roundabout. Our simulation results show that the urban traffic is in free flow state when the vehicle's density is low enough. However, when the density exceeds a critical density ρ c , the urban traffic will be in gridlock state whenever γ is nonzero. In the case where γ = 0, the urban traffic presents a phase transition between free flow and congested state. Furthermore, detailed analysis of the traffic metrics shows that the model parameters (γ, K) have a significant effects on urban traffic dynamics.

Introduction

Traffic congestion has attracted the attention of many scientists because they are becoming one of the biggest problems found in urban environments. In order to understand traffic congestion phenomenon, scientists have carried out many studies based on different models and methods. The cellular automaton (CA) model developed by Nagel and Schreckenberg (NaSch) [START_REF] Nagel | A cellular automaton model for freeway traffic[END_REF] is one of efficient models for traffic flow problems.

Traffic flow is governed by several factors, among them drivers' behavior (e.g., imperfect driving styles, slower cars and car accidents) which play an important role in the formation of traffic jams within the transportation system, especially when it is combined with the increase in car density (for a review, see [START_REF] Chowdhury | Statistical physics of vehicular traffic and some related systems[END_REF][START_REF] Hou | An extended car-following model based on visual angle and backward looking effect[END_REF]). Indeed, when the density of cars increases, a phase transition from free flow phase to congestion phase occurs. In free flow phase, cars move close to the speed limit, and an increase in density leads to an increase in traffic flow. However, the congested phase is characterized by a negative linear relationship between traffic flow and density. It has been shown that, in congested phase, the drivers' behavior has a major effect on the spatial distribution of vehicles relative to each other over the road [START_REF] Járai-Szabó | Earthquake model describes traffic jams caused by imperfect driving styles[END_REF][START_REF] Zamith | A new stochastic cellular automata model for traffic flow simulation with drivers behavior prediction[END_REF].

The modern roundabout is a type of intersection with no traffic lights. It is a circular intersection with design features that offer benefits in terms of circulation safety, delays and capacity. It was first developed in the United Kingdom and now is widely used in most countries. Drivers approaching a roundabout must reduce their speeds and look for potential conflicts with vehicles already in the circle. Many technical reports stated that the average accident risk at roundabouts have found important reductions in crashes compared to other conventional crossroads or T-junction, with or without traffic signals [START_REF] Persaud | Safety effect of roundabout conversions in the united states: Empirical bayes observational before-after study[END_REF][START_REF] Eisenman | Operational and safety performance of modern roundabouts and other intersection types[END_REF][START_REF] Rodegerdts | Roundabouts in the United States[END_REF]. However, car accidents inside roundabouts are one of the most frequent contributing factors to jam formation. Among the reasons for car accidents is the high velocity and the violation of some safety conditions related to priority rules. Despite the demonstrated safety benefits of roundabouts, some crashes still occur. An Institute study of crashes at 38 roundabouts in Maryland found that collisions occurred more frequently at entrances to roundabouts than within the circulatory roadway or at exits [START_REF] Mandavilli | Crash patterns and potential engineering countermeasures at Maryland roundabouts[END_REF]. The researchers concluded that unsafe speeds were an important crash factor, since drivers may not have seen the roundabout in time to slow down sufficiently.

Several models have been proposed to study the characteristics of vehicular traffic flow at a roundabout.

The authors in [START_REF] Fouladvand | Characteristics of vehicular traffic flow at a roundabout[END_REF] have investigated the characteristics of traffic at an isolated roundabout in the framework of cellular automata and car-following models. They show that overall delay is significantly affected by roundabout size. In [START_REF] Wang | Modelling traffic flow at multi-lane urban roundabout[END_REF] the authors proposes Multi-stream Minimum Acceptable Space (MMAS) Cellular Automata models to study unsignalised multi-lane (two-or three-lane) urban roundabouts. They found that traffic flow is influenced by the topology of the roundabout, turning rates and critical arrival rates. On the other hand, in [START_REF] Huang | Modeling gridlock at roundabout[END_REF], the author proposed a cellular automaton model to analyse traffic flow around a traffic roundabout. Based on the observation of different transitions, including the transition between free-flowing and gridlock and bottleneck and gridlock, the author has identified that the gridlock can be taken as an extreme limit of bottleneck.

Cellular automata models have been also used to study the probability of car accidents for various traffic scenarios [START_REF] Boccara | Car accidents and number of stopped cars due to road blockage on a one-lane highway[END_REF][START_REF] Moussa | Car accidents in cellular automata models for one-lane traffic flow[END_REF][START_REF] Echab | Simulation study of traffic car accidents at a single lane roundabout[END_REF]. The first CA model including dangerous situations (accident) have been proposed by Boccara et al [START_REF] Boccara | Car accidents and number of stopped cars due to road blockage on a one-lane highway[END_REF]. In [START_REF] Moussa | Car accidents in cellular automata models for one-lane traffic flow[END_REF], the author introduces the conditions for the occurrence of car accidents, based on the delayed reaction time of the successor car. The author discusses the effect of these conditions on the probability of traffic accidents. In [START_REF] Echab | Simulation study of traffic car accidents at a single lane roundabout[END_REF], the authors have studied the probability of entering/circulating car accidents to occur at single-lane roundabout when the incoming vehicles ignore the priority rules.

The urban traffic, where traffic lights are installed to regulate traffic flow at intersections, has been well studied. Here we can cite some basic references which show that the traffic undergoes a phase transition when the density of cars in the city is increased [START_REF] Cuesta | Phase transitions in two-dimensional traffic-flow models[END_REF][START_REF] Brunnet | Cellular automaton block model of traffic in a city[END_REF]. To the best of our knowledge, no study has provided a model for urban traffic with roundabouts. In this paper, we introduce a two-dimensional CA model based on discrete events capable of simulating the traffic in urban with roundabouts. Fig. 1 gives an illustration of our proposed structure of urban environment. Our objective is to provide a study of the impact of turning movement and some geometric factor on urban traffic capacity with multiple roundabouts.

The rest of the paper is organized in the following way. We first describe our proposed model in section 2. In Section 3, we present the simulation results and the paper is concluded in Section 4.

Model description

We consider a CA model described in the two-dimensional system with periodic boundary conditions.

The underlying structure is a L × L cell grid, where L is the system size. All streets are two-way, with one lane in each direction. The distance between each pair of roundabouts is configured with a parameter K (see Fig. 2).

Mobility model in urban streets

In accordance to the NaSch model, we modeled our urban streets as a set of cells where each cell can either be empty or occupied by exactly one vehicle (see Fig. 2). The length of a single cell is set to 7.5m.

The vehicles move within each route with periodic boundary conditions without changing lane. In each simulation setup, vehicles are either eastbound or westbound or southbound or northbound. The global density is defined by ρ = N/L 2 . Here the city size L is defined as L = 2 √ K * N r , where N r is the number of roundabouts in the city.

At each discrete time step t -→ t + 1, the system update is performed in parallel according to the following rules:

1. Acceleration outside roundabouts:

v n (t + 1) = min(v n (t) + 1, v max ) 2. Deceleration: v n (t + 1) = min(v n (t), d n (t))
3. Randomization, braking: v n (t + 1) = min(v n (t) -1, 0) with probability p. 4. Car motion: each vehicle will move according to its new velocity.

where v n (t) denotes the velocity of the vehicle. v max denotes the maximum velocity in urban streets. d n (t) denotes the gap (number of empty cells) between the vehicle n and its immediate predecessor or between the vehicle n and the last cell in the lane (cell that is right next to the roundabout).

Mobility model and car accident in roundabout

At each intersection between streets, we introduce a roundabout designed to allow drivers to change direction during their travel. Fig. 3 illustrates the type of roundabout considered in this paper. In addition, before entering the roundabout, each vehicle n is assigned a turning probability (p turn (n)), which allows driver to choose his preferred driving direction (see Fig. 4). Note that in real world, the turning probability of different drivers may be distinct. For the sake of simplicity, we assume that of all drivers have the same turning probability (p turn (n) = γ). The turning behavior of vehicles at roundabouts is implemented via algorithm (1). The majority of roundabouts were operated based on the offside priority rule, which implies that a vehicle V A approaching a roundabout (on the entry leg) is usually required to give way to the traffic already in the roundabout. Another priority rule contemplated here concerns another vehicle V A entering a roundabout and wishing to exit via the exit leg without using the circle of the roundabout. Let V B be a circulating vehicle in the roundabout that V A may encounter (see Fig. 5). Now, we define the set of gaps used to control the entering vehicle V A to roundabout based on offside priority rule. The gap gap 1 A (t) (resp. gap 1 B (t)) represents the number of empty cells in front of the vehicle V A (resp. V B ) in its travel path at time t. For example in Fig. 5a, if the vehicle V A turn right then gap 1 A = gap a else gap 1 A = gap a . Similarly, in Fig. 5b, if the vehicle

V B turn left then gap 1 B = gap d else gap 1 B = gap d . The gap gap 2 A (t) (resp. gap 2 B (t)
) represents the number of empty cells in front of the vehicle V A (resp. V B ) and the collision cell at time t. Remember that there are two different cells where a conflict may occur; the first is at the entry leg while the second is on the if ( thenγ > rand(0, 1))

3:
p=0.5 // to make a right turn or left turn with equal probability.

4:

if (p > rand(0, 1)) then end if 12: end if exit leg of the roundabout. In the situation where a conflict occurred at the entry leg (Fig. 5c), we have

gap 2
A = gap a and gap 2 B = gap b . However, at the exit leg (Fig. 5d), we have gap 2 A = gap e and gap 2 B = gap f . The offside priority rule is implemented via the algorithm (2). So, if the speed of V A is large enough then the algorithm must be executed (line 1). The condition in line 2 means that when V B is far away from the cell of collision, V A enters safely to the roundabout. If not, V A will move to just behind the cell of collision (line 6). In the other hand, it is believed that roundabouts are very important for the limitation of traffic jams, the reduction of accidents and contribute to slow down speeding cars [START_REF] Pratelli | Design of modern roundabouts in urban traffic systems[END_REF]. Nevertheless, roundabouts suffer from the occurrence of car accidents when entering vehicles violate the priority rules. The violation of safety conditions is mainly related to inability to accurately estimate the available gap, a lack of attention concerning the offside priority rule or the long reaction time τ of driver. The conditions of the occurrence of these accidents are defined as shown in algorithm 3.

Algorithm 2 : Offside priority rule

1: if (v A (t) >= gap 2 A (t)) then 2: if (gap 2 B (t) >= v maxrp ) then 3: v A (t + 1) = min(v A (t) + 1, gap 1 A (t), v maxrp ) 4: v B (t + 1) = min(v B (t) + 1, v maxrp ) 5: else 6: v A (t + 1) = gap 2 A (t) 7: v B (t + 1) = min(v A (t) + 1, gap 1 B (t), v maxrp ) 8:
end if 9: end if Algorithm 3 : Detecting car accidents

1: if (conflict between V A and V B occurs in the roundabout) then 2: v B (t + 1) = min(v B (t) + 1, gap 1 B (t), v maxrp ) 3: if (τ v A (t) > gap

Performance Metrics

Model performance metrics are developed to assess our urban traffic system behavior. We monitor the impact of cars's density ρ and turning probability γ on traffic flow, accident probability and average waiting time. Similarly, we will investigate the impact of the urban geometric characteristics by varying the distance between roundabouts K, while keeping fixed the number of roundabouts N r in the urban city.

• Average velocity: we define the average velocity of vehicles as the sum velocities of all vehicles during the simulation time divided by time interval. The average velocity is then given as follows:

Average velocity = N i=1 v i (t) N × T ( 1
)
where T is the time interval and N is the number of vehicles.

• Traffic flow: we define the traffic flow as the car density ρ multiplied to average velocity. The traffic flow in the city is then given as follows:

Traffic flow = ρ × N i=1 v i (t) N × T (2)
• Accident probability: we define the accident probability as the total number of accidents (n ac ) committed by vehicles within the roundabout during the simulation time divided by the number of vehicles and the simulation time. The accident probability is then given as follows:

Accident probability = n ac N × T s (3)
• Average waiting time: we define the waiting time as the time between the arrival time (t i arr ) of a vehicle i in the entry cell of a roundabout, and the moment of its departure (t i dep ) from this cell. Let N c be the number of vehicles that have left the entry cells. The waiting time is then given as follows:

Average waiting time = Nc i=1 (t i dep -t i arr ) N c (4)

Results and discussion

In this section, we present the simulation results for our indicators of system performance in order to investigate the relationship between the states of our transportation system and the model parameters. The model parameters which have been considered in this work are given in Table 1. In this paper, we are interested to the effect of the turning rate and the city structure on the capacity of urban traffic. The impact of the city size is provided by varying the distance K between roundabouts (Large cities correspond to high values of K).

First, we will analyze the different traffic states present in the transportation system. With increasing the density, we find that the traffic flow increases almost linearly and then begins to decrease beyond certain value of the density. This critical density ρ c represents a transition between free flow and congested state.

As Fig. 6 shows, this congested state is unstable and it depends greatly on the simulation time. A detailed study of this behavior leads to the discovery that congested states change over time to gridlock state when γ = 0. In this case, the model presents a state transition from free low to gridlock at a critical car density ρ c . Fig. 7 shows a snapshot illustration of the two states present in the model when γ = 0.30. In free-flow state (Fig. 7a) vehicles move freely while in gridlock state (Fig. 7b), vehicles pile up around some roundabouts, forming a single immobile cluster with zero mean velocity. However, on the other hand, for γ = 0, we observe from Fig. 8a,c that the average velocity is stable with time and decreases when the density is diminished, thus showing the existence of the congested state. However, if γ = 0, the average velocity is stable with time for low values of the density; but as soon as this density exceeds ρ c the average velocity decreases with time and vanishes at t = t grid ; showing that the system has reached the gridlock state (Fig. 8b,d).

On the basis of our simulations, we can see that the main cause of the gridlock is the conflict of circulation between vehicles who circulate in a roundabout and those who want to leave. In such situations, no one can move because everyone is in someone else's way (??). More precisely, when several exits of a roundabout present simultaneously conflicts of circulation, a local deadlock emerges. This situation allows other circulating vehicles to slow down and stop because there is not a free space in front of exiting vehicles.

This leads to the propagation of a traffic jam wave towards other roads linked to this roundabout, and thus causing a global gridlock.

In order to determine the critical density ρ c , several simulations were carried out by examining the time evolution of the average velocity for different car densities. Fig. 9 shows the obtained results for different values of γ and K. It is shown that the gridlock state can take longer time (t grid ) to occur as the car density decreases, and t grid will become infinity when approaching to critical density. Our experimental simulations show that the model parameters have no obvious impact on the values of ρ c . Moreover, since critical densities are found to be in the range of about 0.160 to 0.190, Based on a detailed analysis of the gridlock state, it appears that the gridlock occurs due to right-turning vehicles which may be trapped in loops when the car density exceeds a critical car ρ c . This means that a loop formation can occur when the car density becomes sufficient to form a loop of vehicles. This loop is governed by the rate of right-turning vehicles especially when they are located in the head of road segments and waiting to access the roundabout, but the destination lanes are not empty which leads to a local gridlock. This local gridlock can propagate toward other sides of the city causing a global gridlock. As the appearance of gridlock is mainly related to an increase in the rate of right-turning vehicles in the road segments (e.g., γ > 0) which lead to the formation the square loop.

However, when γ = 0, the gridlock can occur, but with a much lower probability as compared with the occurrence of the square loop formed by the right-turning vehicles, and therefore the transition between free flow and gridlock can take much long time. As the right-turning vehicles are absent, the gridlock can occur only due to an intersection between fully saturated road segments that lead to make obstacles in front of exiting vehicles from the circulating ring of roundabout. We limited our results to (γ = 0.3) because the detection of gridlock can take much long time (e.g., several days and months). But, when the density increases enough, it's passible to have a gridlock quickly as illustrated in (see Fig. 7c) for (ρ = 0.3). Indeed, we found that the critical car density can be given as follows:

ρ c = 4 × (K + R s ) 32 × K (5)
Moreover, since critical densities are found to be in the range of about 0.160 to 0.190, we limit our simulations and analysis up to the density 0.160.

We begin our investigation by examining the impact of the turning rate on our traffic system. Fig. 10 shows the characteristics of traffic flow, average velocity, car accident and waiting time as a function of the density for different values of the turning probability γ. As plotted on Fig. 10a, the traffic flow versus the density reproduces the free flow state observed in real traffic flow, regardless of the value of γ. In this state, the traffic flow increases almost linearly with ρ because almost all the vehicles move with their maximum speed v = v f ree , due to the availability of large headways occurring in the traffic stream.

Furthermore, it is shown that γ has no visible effect on the traffic flow and the average velocity for low car densities. As the car density increases (ρ > 0.1), turning movement starts to have an effect on the transportation system. It is shown that both traffic flow and average velocity increase with increasing γ, in accordance with the results of the model considered in [START_REF] Cuesta | Phase transitions in two-dimensional traffic-flow models[END_REF]. This can be explained by the fact that under high values of γ, the number of right turning movements is higher, and so several exit possibilities will be available for rotating vehicles. These exiting vehicles create opportunities for other entering vehicles, and therefore new gaps will be created inside roundabouts. Fig. 10c shows the car accident probability for different values of γ, as a function of car density. In this paper, we study the causes of car accidents at roundabouts, without taking into account their impacts on the traffic flow. This means that the car accident does not really happen, but only that we monitor the car accident probability without affecting the traffic flow. We observe that unlike accidents in highways, which usually do not occur until the cars density exceeds some critical value [START_REF] Moussa | Car accidents in cellular automata models for one-lane traffic flow[END_REF], accidents at roundabouts can exist even if the density is very low. Indeed, at low densities, vehicles access roundabouts at a maximal speed and the probability to collide with other circulating vehicles will be considerable. Moreover, with increasing the density, the car accident rate increases until it reaches a maximum, and then decreases with further density. It can be observed that, the higher the turning rate, the more frequent the accidents at roundabouts. Indeed, with higher values of γ, the traffic system creates more opportunities for entering vehicles and, as a result, these vehicles access the roundabouts with relatively high speeds, which increases the risk of collisions with rotating vehicles. On the other hand, for a given value γ, the waiting time increases as the density increases due to the excessive number of vehicles at roundabouts (see Fig. 10d). Moreover, at fixed density, the waiting time decreases with increasing γ. Once again, this is the result of the fluidity of traffic caused by the increase of γ.

In order to get a better understanding of the effect of urban network structure on the traffic dynamics, the plots of traffic flow, car accident probability, average velocity and waiting time against the density for varying values of K are shown in Fig. 11. Note that, when we vary K, the number of roundabouts present in the urban structure remains fixed. Fig. 11a,b show that, as the distance between roundabouts K decreases, the traffic flow and the average velocity decrease significantly. This can be explained by the fact that in the case of low values of K (small cities), vehicles are able to reach the roundabouts quickly and therefore they are forced to either slow down or stop to avoid collisions with other circulating vehicles. This affects significantly the traffic flow and imposes a speed reduction of the vehicles every time they want to access the roundabouts (see Fig. 11b). From the obtained curves of Fig. 11c, it is clear that, at fixed car density, the high rate of car accidents corresponds to low values of K. As mentioned before, the smaller the distance between two successive roundabouts, the more quickly vehicles reach the roundabouts. Therefore, during one simulation period, the frequency of violation of the safety conditions will become higher. Furthermore, for a given density, the waiting time increases with increasing K. In order to understand this phenomenon, it is necessary to remember that the number of roundabouts remains fixed when K is increased. Moreover, for a fixed density, the increase in K automatically leads to an increase in the number of vehicles (ρ = N/(4 * N r * K)). As a result, the traffic capacity of roundabouts is particularly limited if number of vehicles exceeds some limit. This will result in many stops in the entry legs and thus the average waiting time becomes more important.

Conclusion

Urban traffic with roundabouts has been studied based on a two dimensional CA model. Our results can be summarized as follows: 1. Urban traffic without turning behavior exhibits a transition from free flow to congested state as the density exceeds a critical density ρ c . 2. The principal cause to the appearance of gridlock is the turning movement of vehicles. 3. Flow, accidents and waiting time are influenced by the turning rate as well as by the geometry of the urban city: -A high turning rate can lead to an increase in the urban traffic capacity, but also it can be a factor that increases the risk of accident. -Urban traffic is significantly better in large cities than in small ones. On the other hand, we have shown that ρ c varies

Fig. 1 .

 1 Fig. 1. The illustration of proposed structure of urban environment.

Fig. 2 .

 2 Fig. 2. Urban streets : (a) Realistic environment (b) CA model.

Fig. 3 .

 3 Fig. 3. Illustration of our proposed models of roundabout based on CA concept.

Fig. 4 .

 4 Fig. 4. Illustration of allowed driving directions for drivers entering the roundabout.

Algorithm 1 :

 1 Turning rules for roundabouts 1: if the vehicle is on the entry leg then 2:

  the vehicle move strait, d 1 .11:

Fig. 5 .

 5 Fig.5. Illustration of different gaps used to manage priority between entering vehicles and circulating vehicles and to determine car accidents at entry and exit legs of roundabout.

Fig. 6 .

 6 Fig. 6. Fundamental diagrams for different values of simulation time with parameters K = 40 and γ = 0.3. Each point represents one simulation run result and for each density we plot 30 points. (a) Traffic flow diagram (b) Mean velocity diagram.

Fig. 7 .

 7 Fig. 7. Snapshot illustration of states with parameters K = 40 and vmax = 3. (a) ρ = 0.15 and γ = 0.3, (b) ρ = 0.2 and γ = 0.3, and (c) ρ = 0.3 and γ = 0.

Fig. 8 .

 8 Fig. 8. Evolution of the average velocity for different car densities and simulation times with parameters K = 40 and γ = 0.3. (a) and (c): γ = 0; (b) and (d): γ = 0.05.

ρ 0. 165 TimeFig. 9 . 1 ×10 - 3 Fig. 10 .

 16591310 Fig. 9. Illustration of the transition between free flow and gridlock for different values of γ and K. (a) and (b): γ = 0.3 and K = 40; (c) and (d): γ = 0.9 and K = 40; (e) and (f): γ = 0.3 and K = 60.

3 Fig. 11 .

 311 Fig. 11. Effect of increasing the distance between roundabouts K with γ = 0.3. The city size L 2 depends on the value of K: L 2 = 7200 for K = 50, L 2 = 5760 for K = 40, L 2 = 4320 for K = 30 and L 2 = 2880 for K = 20.

Table 1 .

 1 Mobility pattern parameters used in the simulation.

	Parameter

very little when we vary the model parameters (0.160 < ρ c < 0.190). Then, it would be very interesting to implement intelligent strategies to increase ρ c . This idea is under study and will be considered in a future work.


Guillaume Ducoffe

Alexandru Popa

A quasi linear-time b-Matching algorithm on distance-hereditary graphs and bounded split-width graphs *

Keywords: maximum matching, b-matching, FPT in P, split decomposition, distance-hereditary graphs

We present a quasi linear-time algorithm for Maximum Matching on distance-hereditary graphs and some of their generalizations. This improves on [Dragan, WG'97], who proposed such an algorithm for the subclass of (tent,hexahedron)-free distance-hereditary graphs. Furthermore, our result is derived from a more general one that is obtained for b-Matching. In the (unit cost) b-Matching problem, we are given a graph G = (V, E) together with a nonnegative integer capacity b v for every vertex v ∈ V . The objective is to assign nonnegative integer weights (x e ) e∈E so that: for every v ∈ V the sum of the weights of its incident edges does not exceed b v , and e∈E x e is maximized. We present the first algorithm for solving b-Matching on cographs, distance-hereditary graphs and some of their generalizations in quasi linear time.

For that, we use a decomposition algorithm that outputs for any graph G a collection of subgraphs of G with no edge-cutsets inducing a complete bipartite subgraph (a.k.a., splits). The latter collection is sometimes called a split decomposition of G. Furthermore, there exists a generic method in order to design graph algorithms based on split decomposition [Rao, DAM'08]. However, this technique only applies to "localized" problems: for which a "best" partial solution for any given subgraph in a split decomposition can be computed almost independently from the remaining of the graph. Such framework does not apply to matching problems since an augmenting path may cross the subgraphs arbitrarily.

We introduce a new technique that somehow captures all the partial solutions for a given union of subgraphs in a split decomposition, in a compact and amenable way for algorithms -assuming some piecewise linear assumption holds on the value of such solutions. The latter assumption is shown to hold for b-Matching. Doing so, we prove that solving b-Matching on any pair G, b can be reduced in quasi linear-time to solving this problem on a collection of smaller graphs: that are obtained from the subgraphs in any split decomposition of G by replacing every vertex with a constant-size module. In particular, if G has a split decomposition where all subgraphs have order at most a fixed k, then we can solve b-Matching for G, b in O((k log 2 k)•(m+n)•log ||b|| 1 )-time. This answers an open question of [Coudert et al., SODA'18].

Introduction

The Maximum Matching problem takes as input a graph G = (V, E) and it asks for a subset F of pairwise disjoint edges of maximum cardinality. This is a fundamental problem with a wide variety of applications [START_REF] Bunke | Graph matching: Theoretical foundations, algorithms, and applications[END_REF][START_REF] Dekel | A parallel matching algorithm for convex bipartite graphs and applications to scheduling[END_REF][START_REF] Lovász | Matching theory[END_REF][START_REF] Pulleyblank | Matchings and extensions[END_REF]. Hence, the computational complexity of Maximum Matching has been extensively studied in the literature. In particular, this was the first problem shown to be solvable in polynomial-time [START_REF] Edmonds | Paths, trees, and flowers[END_REF]. Currently, the best-known algorithms for Maximum Matching run in O(m √ n)-time on n-vertex m-edge graphs [START_REF] Micali | An O( √ V E) algorithm for finding maximum matching in general graphs[END_REF]. Such superlinear running times can be prohibitive for some applications. In order to overcome the superlinear barrier, we initiated in [START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF] the complexity study of Maximum Matching on bounded clique-width graph classes (the latter research direction being also motivated by the recent linear-time algorithm for Maximum Matching on bounded treewidth graphs, see [START_REF] Fomin | Fully polynomial-time parameterized computations for graphs and matrices of low treewidth[END_REF][START_REF] Iwata | On the power of tree-depth for fully polynomial FPT algorithms[END_REF]). As a new attempt in this direction, our initial motivation for this paper was to design a quasi linear-time algorithm for Maximum Matching on distance-hereditary graphs and some classes of graphs that are defined via the so-called splitdecomposition. We succeeded in our initial goal and, in fact, we prove a more general result. All graphs studied in what follows have bounded clique-width [START_REF] Rao | Solving some NP-complete problems using split decomposition[END_REF].

Related work

There is a long line of work whose aim is to find more efficiently solvable special cases for Maximum Matching (e.g., see [START_REF] Chang | Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs[END_REF][START_REF] Dahlhaus | Matching and multidimensional matching in chordal and strongly chordal graphs[END_REF][START_REF] Dragan | On greedy matching ordering and greedy matchable graphs[END_REF][START_REF] Fouquet | An O(n)-time algorithm for maximum matching in P 4 -tidy graphs[END_REF][START_REF] Fouquet | Bipartite graphs totally decomposable by canonical decomposition[END_REF][START_REF] Glover | Maximum matching in a convex bipartite graph[END_REF][START_REF] Hopcroft | An nˆ5/2 algorithm for maximum matchings in bipartite graphs[END_REF][START_REF] Liang | Finding a maximum matching in a circular-arc graph[END_REF][START_REF] Mertzios | Linear-time algorithm for maximum-cardinality matching on cocomparability graphs[END_REF][START_REF] Karp | Maximum matching in sparse random graphs[END_REF][START_REF] Yu | An O(n)-time algorithm for maximum matching on cographs[END_REF][START_REF] Yuster | Maximum matching in graphs with an excluded minor[END_REF][START_REF] Yuster | Maximum matching in regular and almost regular graphs[END_REF]). In particular, there exist linear-time algorithms for computing a maximum matching on trees, cographs [START_REF] Yu | An O(n)-time algorithm for maximum matching on cographs[END_REF] and subclasses of distance-hereditary graphs [START_REF] Dragan | On greedy matching ordering and greedy matchable graphs[END_REF] 1 . Furthermore, a natural follow-up of such investigations is to study whether the techniques used in every case can also be applied to larger classes of graphs. This has be done, especially, for the Split & Match technique introduced in [START_REF] Yu | An O(n)-time algorithm for maximum matching on cographs[END_REF] for cographs (e.g., see [START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF][START_REF] Fouquet | An O(n)-time algorithm for maximum matching in P 4 -tidy graphs[END_REF][START_REF] Fouquet | Bipartite graphs totally decomposable by canonical decomposition[END_REF] where the latter technique has been applied to other graph classes). We also consider this above aspect in our work, as we seek for a Maximum Matching algorithm on distance-hereditary graphs that can be easily generalized to larger classes of graphs that we define in what follows.

Fully Polynomial Parameterized Algorithms. More precisely, we seek for parameterized algorithms (FPT). Formally, given a graph invariant denoted π (e.g., maximum degree, treewidth, etc.), we address the question whether there exists a Maximum Matching algorithm running in time O(k c • (n + m) • log O (1) (n)), for some constant c, on every graph G such that π(G) ≤ k 2 . Note that such an algorithm runs in quasi linear time for any constant k, and that it is faster than the state-of-the art algorithm for Maximum Matching whenever k = O(n In general, the parameters that are considered in this type of study represent the closeness of a graph to some class where the problem at hands can be easily solved (distance from triviality). In particular, Maximum Matching can be solved in O(k 2 • n log n)-time on graphs with treewidth at most k [START_REF] Fomin | Fully polynomial-time parameterized computations for graphs and matrices of low treewidth[END_REF][START_REF] Iwata | On the power of tree-depth for fully polynomial FPT algorithms[END_REF], and in O(k 4 • n + m)-time on graphs with modular-width at most k [START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF]. The latter two parameters somewhat represent the closeness of a graph, respectively, to a tree or to a cograph. In this work, we study the parameter split-width, that is a measure of how close a graph is to a distance-hereditary graph [START_REF] Rao | Solving some NP-complete problems using split decomposition[END_REF]. Distance-hereditary graphs are a natural superclass of both cographs and trees and they have already been well studied in the literature [START_REF] Bandelt | Distance-hereditary graphs[END_REF][START_REF] Dragan | LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem[END_REF][START_REF] Gavoille | Distance labeling scheme and split decomposition[END_REF][START_REF] Gioan | Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs[END_REF][START_REF] Golumbic | On the clique-width of some perfect graph classes[END_REF]. Our work subsumes the one of [START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF] with modular-width -that is an upper-bound on split-width -but it is uncomparable with the work of [START_REF] Fomin | Fully polynomial-time parameterized computations for graphs and matrices of low treewidth[END_REF][START_REF] Iwata | On the power of tree-depth for fully polynomial FPT algorithms[END_REF] with treewidth.

Split Decomposition. Bounded split-width graphs can be defined in terms of split decomposition. A split is a join that is also an edge-cut. By using pairwise non crossing splits, termed "strong splits", we can decompose any graph into degenerate and prime subgraphs, that can be organized in a treelike manner. The latter is termed split decomposition [START_REF] Cunningham | Decomposition of directed graphs[END_REF], and it is our main algorithmic tool for this paper. The split-width of a graph is the largest order of a non degenerate subgraph in some canonical split decomposition. In particular, distance-hereditary graphs are exactly the graphs with split-width at most two [START_REF] Gioan | Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs[END_REF].

Many NP-hard problems can be solved in polynomial time on bounded split-width graphs (e.g., see [START_REF] Rao | Solving some NP-complete problems using split decomposition[END_REF]). In particular we have that clique-width is upper-bounded by split-width, and so, any FPT algorithm parameterized by clique-width can be transformed into a FPT algorithm parameterized by split-width (the converse is not true). Recently we designed FPT algorithms for polynomial problems when parameterized by split-width [START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF]. It turns out that many "hard" problems in P such as Diameter, for which a conditional superlinear lower-bound has been proved [START_REF] Roditty | Fast approximation algorithms for the diameter and radius of sparse graphs[END_REF], can be solved in O(k O (1) • n + m)-time on graphs with split-width at most k. However, we left this open for Maximum Matching. Indeed, as we detail next the standard design method for FPT algorithms based on split decomposition does not apply to matching problems. Our main contribution in [START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF] was a Maximum Matching algorithm based on the more restricted modular decomposition. As our main contribution in this paper, we present an algorithm that is based on split decomposition in order to solve some generalization of Maximum Matching -thereby answering positively to the open question from [START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF]. Our techniques are quite different than those used in [START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF].

Contributions

In order to discuss the difficulties we had to face on, we start giving an overview of the FPT algorithms that are based on split decomposition.

• We first need to define a weighted variant of the problem that needs to be solved for every component of the decomposition separately (possibly more than once). This is because there are additional vertices in a split component, i.e., not in the original graph, that substitute the other remaining components; intuitively, the weight of such additional vertex encodes a partial solution for the union of split components it has substituted.

• Then, we take advantage of the treelike structure of split decomposition in order to solve the weighted problem, for every split component sequentially, using dynamic programming. Roughly, this part of the algorithm is based on a "split decomposition tree" where the nodes are the split components and the edges represent the splits between them. Starting from the leaves of that tree (resp. from the root), we perform a tree traversal. For every split component, we can precompute its vertex-weights from the partial solutions we obtained for its children (resp., for its father) in the split decomposition tree.

Our approach. In our case, a natural weighted variant for Maximum Matching is the more general unit-cost b-Matching problem [START_REF] Edmonds | Matching: A well-solved class of integer linear programs[END_REF]. Roughly, b-Matching differs from Maximum Matching in that a vertex can be matched to more than one edge, and an edge can be put in the matching more than once. In more details, every vertex v is assigned some input capacity b v , and the goal is to compute edge-weights (x e ) e∈E so that: for every v ∈ V the sum of the weights of its incident edges does not exceed b v , and e∈E x e is maximized. The particular case of Maximum Matching is obtained by setting b v = 1 for every vertex v. Interestingly, b-Matching has already attracted attention on its own, e.g., in auction theory [START_REF] Penn | Constrained multi-object auctions and b-matching[END_REF][START_REF] Tennenholtz | Tractable combinatorial auctions and b-matching[END_REF]. However. we want to stress that solving b-Matching is a much more ambitious task than "just" solving Maximum Matching.

In particular, Maximum Flow on general graphs is computationally equivalent to b-Matching on bipartite graphs [START_REF] Madry | Navigating central path with electrical flows: From flows to matchings, and back[END_REF]. The corresponding reductions preserve the treewidth of the graphup to a constant-factor -and so, solving b-Matching in quasi linear-time on bounded-treewidth graphs would already be an impressive achievement on its own. On general graphs, the best-known algorithms for b-Matching run in O(nm log 2 n)-time [START_REF] Gabow | An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems[END_REF][START_REF] Gabow | Data structures for weighted matching and extensions to b-matching and f -factors[END_REF].

Our main technical difficulty is how to precompute efficiently, for every component of the decomposition, the specific instances of b-Matching that need to be solved . To see that, consider the bipartition (U, W ) that results from the removal of a split. In order to compute the b-Matching instances on side U , we should be able after processing the other side W to determine the number of edges of the split that are matched in a final solution. Guessing such number looks computationally challenging. We avoid doing so by storing a partial solution for every possible number of split edges that can be matched. However, this simple approach suffers from several limitations. For instance, we need a very compact encoding for partial solutions for otherwise we could not achieve a quasi linear-time complexity. Somehow, we also need to consider the partial solutions for all the splits that are incident to the same component all at once.

Results. We prove a simple combinatorial lemma that essentially states that the cardinality of a maximum b-matching in a graph grows as a piecewise linear function in the capacity b w of any fixed vertex w (we think of w as a vertex substituting a union of split components). Then, we derive from our combinatorial lemma a variant of some reduction rule for Maximum Matching that we first introduced in the more restricted case of modular decomposition [START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF]. Roughly, in any given split component C i , we consider all the vertices w substituting a union of other components. The latter vertices are in one-to-one correspondance with the strong splits that are incident to the component. We expand every such vertex w to a module that contains O(1) vertices for every straight-line section of the corresponding piecewise-linear function. Altogether combined, this allows us to reduce the solving of b-Matching on the original graph G to solving b-Matching on supergraphs of every its split components. Furthermore, we prove with the help of a dichotomic search that we only need to consider O(log ||b|| 1 ) supergraphs for every split component, where ||b|| 1 = v∈V b v , and the respective orders of these above supergraphs can only be three times more than the respective orders of the split components.

Overall, our main result is that b-Matching can be solved in O((k log 2 k) • (m + n) • log ||b|| 1 )-time on graphs with split-width at most k (Theorem 1). It implies that Maximum Matching can be solved in O((k log 2 k) • (m + n) • log n)-time on graphs with split-width at most k. Since distancehereditary graphs have split-width at most two, we so obtain the first known quasi linear-time algorithms for Maximum Matching and b-Matching on distance-hereditary graphs. Furthermore, since cographs are a subclass of distance-hereditary graphs, we also obtain the first known quasi linear-time algorithm for b-Matching on cographs. We expect our approach to be useful in a broader context, e.g. for other matching and flow problems.

We introduce the required terminology and basic results in Section 2. Then, Section 3 is devoted to a combinatorial lemma that is the key technical tool in our subsequent analysis. In Section 4, we present our algorithm for b-Matching on bounded split-width graphs. We conclude in Section 5 with some open questions.

Preliminaries

We use standard graph terminology from [START_REF] Bondy | Graph theory[END_REF][START_REF] Diestel | Graph Theory[END_REF]. Graphs in this study are finite, simple (hence without loops or multiple edges), and connected -unless stated otherwise. Furthermore we make the standard assumption that graphs are encoded as adjacency lists. Given a graph G = (V, E) and a vertex v ∈ V , we denote its neighbourhood by N G (v) = {u ∈ V | {u, v} ∈ E} and the set of its incident edges by

E v (G) = {{u, v} | u ∈ N G (v)}. When G is clear from the context we write N (v) and E v instead of N G (v) and E v (G).

Split-width

We mostly follow the presentation we gave in [START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF]. We start defining what a simple decomposition of a graph is. For that, let a split in a graph G = (V, E) be a partition V = U ∪ W such that: min{|U |, |W |} ≥ 2; and there is a complete join between the vertices of N G (U ) and N G (W ). A simple decomposition of G takes as input a split (U, W ), and it outputs the two subgraphs

G U = G[U ∪ {w}] and G W = G[W ∪ {u}] with u ∈ N G (W ), w ∈ N G (U ) being chosen arbitrarily.
The vertices u, w are termed split marker vertices. A split decomposition of G is obtained by applying recursively some sequence of simple decompositions (e.g., see Fig. 1). We name split components the subgraphs in a given split decomposition of G. It is often desirable to apply simple decompositions until all the subgraphs obtained cannot be further decomposed. In the literature there are two cases of "indecomposable" graphs. Degenerate graphs are such that every bipartition of their vertex-set is a split. They are exactly the complete graphs and the stars [START_REF] Cunningham | Decomposition of directed graphs[END_REF]. A graph is prime for split decomposition if it has no split. We can define the following two types of split decomposition:

• Canonical split decomposition. Every graph has a canonical split decomposition where all the subgraphs obtained are either degenerate or prime and the number of subgraphs is minimized. Furthermore, the canonical split decomposition of a given graph can be computed in linear-time [START_REF] Charbit | Linear time split decomposition revisited[END_REF].

• Minimal split decomposition. A split-decomposition is minimal if all the subgraphs obtained are prime. A minimal split-decomposition can be computed from the canonical split-decomposition in linear-time [START_REF] Cunningham | Decomposition of directed graphs[END_REF], that consists in performing simple decompositions on every split component that induces either a star or a complete graph of order at least four, until all such components have been replaced by a collection of triangles and paths of length three. Doing so, we avoid handling with the particular cases of stars and complete graphs in our algorithms. The set of prime graphs in any minimal split decomposition is unique up to isomorphism [START_REF] Cunningham | Decomposition of directed graphs[END_REF].

For instance, the split decomposition of Fig. 1 is both minimal and canonical.

Definition 1. The split-width of G, denoted by sw(G), is the minimum k ≥ 2 such that any prime subgraph in the canonical split decomposition of G has order at most k.

We refer to [START_REF] Rao | Solving some NP-complete problems using split decomposition[END_REF] for some algorithmic applications of split decomposition. In particular, graphs with split-width at most two are exactly the distance-hereditary graphs, a.k.a the graphs whose all connected induced subgraphs are distance-preserving [START_REF] Bandelt | Distance-hereditary graphs[END_REF][START_REF] Gioan | Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs[END_REF]. Distance-hereditary graphs contain many interesting subclasses of their own such as cographs (a.k.a., P 4 -free graphs) and 3-leaf powers, see [START_REF] Gioan | Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs[END_REF]. Furthermore, we can observe that every component in a minimal split decomposition of G has order at most max{3, sw(G)}.

Split decomposition tree.

A split decomposition tree of G is a tree T where the nodes are in bijective correspondance with the subgraphs of a given split decomposition of G, and the edges of T are in bijective correspondance with the simple decompositions used for their computation. More precisely:

• If the considered split decomposition is reduced to G then T is reduced to a single node;

• Otherwise, let (U, W ) be a split of G and let G U = (U ∪ {w}, E U ), G W = (W ∪ {u}, E W )
be the corresponding subgraphs of G. We construct the split decomposition trees T U , T W for G U and G W , respectively. Furthermore, the split marker vertices u and w are contained in a unique split component of G W and G U , respectively. We obtain T from T U and T W by adding an edge between the two nodes that correspond to these subgraphs.

The split decomposition tree of the canonical split decomposition, resp. of a minimal split decomposition, can be constructed in linear-time [START_REF] Rao | Solving some NP-complete problems using split decomposition[END_REF].

Matching problems

A matching in a graph is a set of edges with pairwise disjoint end vertices. We consider the problem of computing a matching of maximum cardinality.

Problem 1 (Maximum Matching).

Input: A graph G = (V, E).

Output: A matching of G with maximum cardinality.

The Maximum Matching problem can be solved in O(m √ n)-time (see [START_REF] Gabow | The weighted matching approach to maximum cardinality matching[END_REF] for a simplified presentation). We do not use this result directly in our paper. However, we do use in our analysis the notion of augmenting paths, that is a cornerstone of most matching algorithms. Formally, let G = (V, E) be a graph and F ⊆ E be a matching of G. A vertex is termed matched if it is incident to an edge of F , and exposed otherwise. An F -augmenting path is a path where the two ends are exposed, all edges {v 2i , v 2i+1 } are in F and all edges {v 2j-1 , v 2j } are not in F . We can observe that, given an F -augmenting path P = (v 1 , v 2 , . . . , v 2 ), the matching E(P )∆F (obtained by replacing the edges {v 2i , v 2i+1 } with the edges {v 2j-1 , v 2j }) has larger cardinality than F .

Lemma 1 (Berge, [4]). A matching F in G = (V, E) is maximum if and only if there is no F -augmenting path.
It is folklore that the proof of Berge's lemma also implies the existence of many vertex-disjoint augmenting paths for small matchings. We will use the following result in our analysis: In particular, we can solve b-Matching in O(nm log 2 n)-time.

Lemma 2 (Hopcroft-Karp, [31]). Let F 1 , F 2 be matchings in G = (V, E). If |F 1 | = r, |F 2 | =
There is a nonefficient (quasi polynomial) reduction from b-Matching to Maximum Matching that we will use in our analysis (e.g., see [START_REF] Tutte | A short proof of the factor theorem for finite graphs[END_REF]). More precisely, let G, b be any instance of b-Matching. The "expanded graph" G b is obtained from G and b as follows. For every v ∈ V , we add the nonadjacent vertices v 1 , v 2 , . . . , v bv in G b . Then, for every {u, v} ∈ E, we add the edges {u i , v j } in G b , for every 1 ≤ i ≤ b u and for every 1 ≤ j ≤ b v . It is easy to transform any b-matching of G into an ordinary matching of G b , and vice-versa.

Changing the capacity of one vertex

We first consider an auxiliary problem on b-matching that can be of independent interest. Let G = (V, E) be a graph, let w ∈ V and let b : V \ w → N be a partial assignment. We denote µ(t) the maximum cardinality of a b-matching of G provided we set to t the capacity of vertex w. Clearly, µ is nondecreasing in t. Our main result in this section is that the function µ is essentially piecewise linear (Proposition 1). We start introducing some useful lemmata.

Lemma 4. µ(t + 1) -µ(t) ≤ 1.
Proof. Consider the two expanded graphs G b,t and G b,t+1 that are obtained after setting the capacity of w to, respectively, t and t + 1. Let F t be any maximum matching of G b,t . By the hypothesis, |F t | = µ(t). Furthermore, since G b,t+1 can be obtained from G b,t by adding a new vertex w t+1 (that is a false twin of w 1 , w 2 , . . . , w t ), F t is also a matching of G b,t+1 . Suppose that F t is not maximum in G b,t+1 , i.e., µ(t + 1) = µ(t) + r, for some r ≥ 1. By Hopcroft-Karp lemma (Lemma 2) there are r F t -augmenting paths in G b,t+1 that are vertex-disjoint. Furthermore, since F t is maximum in G b,t , every such path must contain w t+1 , and so, r = 1.

Lemma 5. If µ(t + 2) = µ(t) then we have µ(t + i) = µ(t) for every i ≥ 0.

Proof. By contradiction, let i 0 be the least integer i ≥ 3 such that µ(t + i) > µ(t). By Lemma 4 we have µ(t + i 0 ) ≤ µ(t + i 0 -1) + 1 = µ(t) + 1, therefore µ(t + i 0 ) = µ(t) + 1. Consider the two expanded graphs G b,t and G b,t+i 0 that are obtained after setting the capacity of w to, respectively, t and t + i 0 . Let F t be any maximum matching of G b,t . By the hypothesis, |F t | = µ(t). Furthermore, since G b,t+i 0 can be obtained from G b,t by adding the new vertices w t+1 , . . . , w t+i 0 (that are false twins of w 1 , w 2 , . . . , w t ), F t is also a matching of G b,t+i 0 . However F t is not maximum in G b,t+i 0 since we have µ(t + i 0 ) = µ(t) + 1. By Berge lemma (Lemma 1) there exists an F t -augmenting path P in G b,t+i 0 . Furthermore, since F t is maximum in G b,t , P must contain a vertex amongst w t+1 , . . . , w t+i 0 . Note that the latter vertices are all exposed, and so, an F t -augmenting path can only contain at most two of them. Furthermore, since w t+1 , . . . , w t+i 0 are pairwise false twins, we can assume w.l.o.g. that P has w t+1 as an end. In the same way, in case P has its two ends amongst w t+1 , . . . , w t+i 0 then we can assume w.l.o.g. that the two ends of P are exactly w t+1 , w t+2 . It implies either µ(t) < µ(t+1) ≤ µ(t+2) or µ(t) = µ(t+1) < µ(t+2). In both cases, µ(t+2) > µ(t), that is a contradiction. Lemma 6. If µ(t + 1) = µ(t) then we have µ(t + 3) = µ(t + 2).

Proof. If µ(t + 2) = µ(t) then the result follows from Lemma 5 directly. Thus, we assume from now on that µ(t + 2) > µ(t). By Lemma 4 we have µ(t + 2) ≤ µ(t + 1) + 1 = µ(t) + 1, therefore µ(t + 2) = µ(t) + 1. Suppose by contradiction µ(t + 3) > µ(t + 2). Again by Lemma 4 we get µ(t + 3) = µ(t + 2) + 1, therefore µ(t + 3) = µ(t) + 2. Consider the two expanded graphs G b,t and G b,t+3 that are obtained after setting the capacity of w to, respectively, t and t + 3. Let F t be any maximum matching of G b,t . By the hypothesis, |F t | = µ(t). Furthermore, since G b,t+3 can be obtained from G b,t by adding the three new vertices w t+1 , w t+2 , w t+3 (that are false twins of w 1 , w 2 , . . . , w t ), F t is also a matching of G b,t+3 . However F t is not maximum in G b,t+3 since we have µ(t + 3) = µ(t) + 2. By Hopcroft-Karp lemma (Lemma 2) there exist 2 F t -augmenting paths in G b,t+3 that are vertex-disjoint. Furthermore, since F t is maximum in G b,t , every such path must contain a vertex amongst w t+1 , w t+2 , w t+3 . Note that the latter vertices are all exposed, and so, an F t -augmenting path can only contain at most two of them. In particular, there is at least one of these two F t -augmenting paths, denoted by P , that only contains a single vertex amongst w t+1 , w t+2 , w t+3 . W.l.o.g., since w t+1 , w t+2 , w t+3 are pairwise false twins, we can assume that w t+1 is an end of P . However, it implies that P is also an F t -augmenting path in G b,t+1 , and so, that µ(t + 1) > µ(t), that is a contradiction.

We are now ready to prove the main result of this section: Proposition 1. There exist integers c 1 , c 2 such that:

µ(t) =      µ(0) + t if t ≤ c 1 µ(c 1 ) + (t -c 1 )/2 = µ(0) + c 1 + (t -c 1 )/2 if c 1 < t ≤ c 1 + 2c 2 µ(c 1 + 2c 2 ) = µ(0) + c 1 + c 2 otherwise.
Furthermore, the triple (µ(0), c 1 , c 2 ) can be computed in O(nm log 2 n log ||b|| 1 )-time. Proof. Let c 1 be the maximum integer t such that µ(t) = µ(0) + t. This value is well-defined since, trivially, the function µ must stay constant whenever t ≥ v∈N G (w) b v . Furthermore, by Lemma 4 we have µ(t) = µ(0)+t for every 0 ≤ t ≤ c 1 . Then, let t max be the least integer t such that, for every i ≥ 0 we have µ(t max +i) = µ(t max ). Again, this value is well-defined since we have the trivial upperbound

t max ≤ v∈N G (w) b v . Furthermore, since µ is strictly increasing on [|0; c 1 |], we have t max ≥ c 1 . Let c 2 = t max -c 1 .
We claim that c 2 = 2c 2 is even. For that, we need to observe that µ(c 1 ) = µ(c 1 +1) by maximality of c 1 . By Lemma 6 we get µ(c 1 +2i) = µ(c 1 +2i+1) for every i ≥ 0, thereby proving the claim. Moreover, for every 0 ≤ i < c 2 we have by Lemma 5 µ(c 1 + 2i) < µ(c 1 + 2(i + 1)) (since otherwise t max ≤ c 1 +2i). By Lemma 6 we have µ(c 1 +2i) = µ(c 1 +2i+1). Finally, by Lemma 4 we get µ(c

1 + 2(i + 1)) ≤ µ(c 1 + 2i + 1) + 1 = µ(c 1 + 2i) + 1, therefore µ(c 1 + 2(i + 1)) = µ(c 1 + 2i) + 1.
Altogether combined, it implies that µ(c 1 + 2i) = µ(c 1 + 2i + 1) = µ(c 1 ) + i for every 0 ≤ i ≤ c 2 , that proves the first part of our result.

W for H W , b W such that ||x W || 1 ≥ ||x|| 1 + c U 2 -µ U (0).
Proof. See Fig. 4 for an illustration. Let us define b U w = e∈C×D x e . As an intermediate step, we can construct a b-matching x U of the pair G U , b U as follows. First we keep all the edge-weights x e = x U e , for every e ∈ E(U ). Then, for every v ∈ C we set x U {v,w} = v ∈D x {v,v } . We deduce from this transformation that:

||x U || 1 = e∈E(U )∪(C×D) x e ≤ µ U (b U w ).
In particular, let y U be a b-matching of G U , b U of optimal cardinality µ U (b U w ) and such that

d = deg y U (w) = e∈Ew(G U ) y U e is minimized. By Proposition 1, we have d ≤ c U 1 + 2c U 2 .
We obtain a b-matching x W for the pair H W , b W as follows:

x x U y U x W 2 2 4 4
Figure 4: The construction of x W . Vertices with capacity greater than 1 are labeled with their capacity. Thin and bold edges have respective weights 0 and 1.

• We keep all the edge-weights x e = x W e , for every e ∈ E(W ). Doing so, we get an initial b-matching of cardinality

||x|| 1 -||x U || 1 ≥ ||x|| 1 -µ U (b U w );
• Then, in order to define x W e , for every edge e that is incident to u 1 , we make a simple reduction to a flow problem. Namely, consider a star with leaves D and central node the split marker vertex u. The star is node-capacitated, with the capacity being set to: min{d, c U 1 } for u; and v∈C x {v,v } for every v ∈ D. By construction, the capacities on side D sum to b U w ≥ d. So, we can send exactly min{d, c U 1 } units of flow from D to u. Furthermore, we define x W {u 1 ,v } , for every v ∈ D, as the value of the flow passing through the arc (v , u). Doing so, we get a partial solution of cardinality

≥ ||x|| 1 -µ U (b U w ) + min{d, c U 1 }.
• We end up defining the weights of the edges that are incident to u 2 or u 3 . There are two cases:

-Case d ≤ c U 1 . By Proposition 1, µ U (b U w ) -d = µ U (0). We complete the b-matching by setting x W {u 2 ,u 3 } = c U 2 . -Case d > c U 1 .
By Proposition 1 and the minimality of d, we have that

d -c U 1 = 2d is even, d ≤ c U 2 and µ U (b U w ) -c U 1 = µ U (0) + d .
We make two other reductions to a flow problem, on the same star as before but with different node capacities. More precisely, we set the capacity of u to d , while for every v ∈ D, we decrease its original capacity by x W {u 1 ,v } . By construction, the capacities on side D now sum to b U w -c U 1 ≥ d -c U 1 ≥ 2d . So, we can send exactly d units of flow from D to u. Furthermore, we define x W {u 2 ,v } , for every v ∈ D, as the value of the flow passing through the arc (v , u). Then, we again decrease the node capacity for every v ∈ D, by exactly x W {u 2 ,v } . We send d more units of flow from D to u. For every v ∈ D, we define x W {u 3 ,v } as the additional amount of flow being sent through the arc (v , u). Note that, doing so, we get

that v ∈D x W {u 2 ,v } = v ∈D x W {u 3 ,v } = d . Finally, we set x W {u 2 ,u 3 } = c U 2 -d .
In total, the cardinality of the b-matching has so increased by 2d

+ (c U 2 -d ) = c U 2 + d .
Therefore in both cases, the resulting b-matching has cardinality at least

||x|| 1 + c U 2 -µ U (0).
In fact, the converse of Lemma 7 also holds: if x W is a b-matching for H W , b W then there exists a b-matching x for the pair G, b such that

||x|| 1 ≥ ||x W || 1 -c U 2 +µ U (0) (Proposition 2).
We postpone the proof of the converse inequality since, in order to prove it, we first need to prove intermediate lemmata that will be also used in the proof of Theorem 1.

b-matchings with additional properties

We consider an intermediate modification problem on the b-matchings of some "auxiliary graphs" that we define next. Let C i be a split component in a given split decomposition of G. The subgraph C i is obtained from a sequence of simple decompositions. For a given subsequence of the above simple decompositions (to be defined later) we apply the reduction rule of Definition 2. Doing so, we obtain a pair H i , b i with H i being a supergraph of C i obtained by replacing some split marker vertices u it , 1 ≤ t ≤ l, by the modules M it = {u 1 it , u 2 it , u 3 it }. We recall that u 2 it , u 3 it are adjacent and they have the same capacity.

We seek for a maximum-cardinality b-matching x i for the pair H i , b i such that the following properties hold for every 1 ≤ t ≤ l:

• (symmetry) deg x i (u 2 it ) = deg x i (u 3 it ). • (saturation) if deg x i (u 1 it ) < c 1 it then, deg x i (u 2 it ) = x i {u 2 i t ,u 3 i t } .
We prove next that for every fixed t, any x i can be processed in O(|E u i t (C i )|)-time so that both the saturation property and the symmetry property hold for M it . However, ensuring that these two above properties hold simultaneously for every t happens to be trickier.

Lemma 8. In O(|V (H i )| • |E(H i )| • log 2 |V (H i )|)-time,
we can compute a maximum-cardinality b-matching x i for the pair H i , b i such that both the saturation property and the symmetry property hold for every M it , 1 ≤ t ≤ l.

Proof. Let x i be some initial maximum-cardinality b-matching (to be defined later). While there exists a t such that the saturation property or the symmetry property does not hold for M it , we keep repeating the following rules until none of them can be applied:

• Rule 1. Suppose deg x i (u 1 it ) < c 1 it and there exists v ∈ N H i (M it ) such that x i {u 2 i t ,v } > 0 (resp., x i {u 3 i t ,v } > 0). Then, we increase x i {u 1 i t
,v } as much as we can, that is by exactly min{c

1 it -deg x i (u 1 it ), x i {u 2 i t ,v } } (resp., min{c 1 it -deg x i (u 1 it ), x i {u 3 i t
,v } }), and we decrease x i

{u 2 i t ,v } (resp., x i {u 3 i t
,v } ) by exactly the same amount. By repeating this step until it is no more possible to do so, we ensure that the saturation property holds for M it .

• Rule 2. Suppose deg x i (u 2 it ) > deg x i (u 3 it )+1 (the case deg x i (u 3 it ) > deg x i (u 2 it )+1 is symmetrical to this one). Let v ∈ N H i (M it ) such that x i {u 2 i t ,v } > x i {u 3 i t ,v } . We increase x i {u 3 i t
,v } as much as we can, that is by min

deg x i (u 2 i t )-deg x i (u 3 i t ) 2 , x i {u 3 i t ,v } , while we decrease x i {u 3 i t
,v } by exactly the same amount. By repeating this step until it is no more possible to do so, we ensure that

|deg x i (u 2 it ) -deg x i (u 3 it )| ≤ 1. • Rule 3. Suppose deg x i (u 2 it ) = deg x i (u 3 it )+1 (the case deg x i (u 3 it ) = deg x i (u 2 it )+1 is symmetrical to this one). Let v ∈ N H i (M it ) such that x i {u 2 i t ,v } > x i {u 3 i t ,v } . We decrease x i {u 2 i t
,v } by one unit; similarly, we increase x i

{u 2 i t ,u 3 i t
} by one unit. Doing so, we ensure that the symmetry property holds for M it .

Overall, we only need to scan O(1) times the set N H i (M it ), and so, we can ensure that both the saturation property and the symmetry property hold for M it in O(|N H i (M it )|)-time. However, doing so, we may break the saturation property or the symmetry property for some other t = t (e.g., see Fig. 5). Therefore, if we start from an arbitrary x i , the above procedure may take quasi polynomial time in order to converge. In order to overcome this above issue, we assign costs on the edges. All the edges of H i have unit cost, except the edges {u 2 it , u 3 it }, for every 1 ≤ t ≤ l, to which we assign cost 2. We compute a maximum-cardinality b-matching x i for the pair H i , b H i that is of maximum cost. By Lemma 3, this can be done in time

O(|V (H i )||E(H i )| log 2 |V (H i )|)
. Then, we apply the same procedure on x i as described above. We claim that there is at most one loop for every t. Indeed, let 1 ≤ t ≤ l be arbitrary. We observe that Rules 1 and 2 do not change the cost of the b-matching. Furthermore, for every v ∈ N H i (M it ), Rules 1 and 2 do not change the x i -degree of v . Hence, we can only break the saturation property or the symmetry property for some other t = t by applying Rule 3. However, Rule 3 increases the cost of x i , and so, since x i is supposed to be of maximum cost, this rule will never be applied. Therefore, the claim is proved. Overall, it implies that the postprocessing of

x i takes time O( l t=1 |N H i (M it )|), that is in O(|E(H i )|).

Merging the partial solutions together

Finally, before we can describe our main algorithm (Theorem 1) we need to consider the intermediate problem of merging two partial solutions (that have been obtained, respectively, for the two subgraphs outputted by a simple decomposition). For that, we introduce the following data structure for storing a b-matching:

Lemma 9. For every G = (V, E) there exists a data structure that can be initialized in O(m)-time, and such that the following properties hold:

• (Access) An edge-weight assignment (x e ) e∈E is stored. Initially, all the edge-weights are set to 0. For every e ∈ E, we can read and modify x e in constant-time.

• (Split) Furthermore, let (U, W ) be a split of G and let

G U = (U ∪ {w}, E U ), G W = (W ∪ {u}, E W ) be the corresponding subgraphs of G.
In O(1)-time, we can modify the data structure so that it can store separate edge-weight assignments for G U and G W (initially set to (x e ) e∈E U and (x e ) e∈E W ).

• (Merge) Conversely, let (U, W ) be a split of G and let

G U = (U ∪ {w}, E U ), G W = (W ∪ {u}, E W )
be the corresponding subgraphs of G. Suppose that two separate assignments (x U e ) e∈E U and (x W e ) e∈E W are stored in the data structure. In O(1)-time, we can modify the data structure so that it stores the following edge-weight assignment for G:

x e =            x U e if e ∈ E U \ E W x W e if e ∈ E W \ E U max{x U e , x W e } if e ∈ E U ∩ E W undefined otherwise.
Proof. Every edge e ∈ E has a pointer to its corresponding weight x e (initially set to 0). Now, consider any split (U, W ) of G and let G U = (U ∪{w}, E U ), G W = (W ∪{u}, E W ) be the corresponding subgraphs of G. Observe that E U , E W intersect in exactly one edge e U,W = {u, w}. So, in order to perform a split of the data structure, it suffices to split the pointer of e U,W in two new pointers, that are initially pointing to two distinct copies of the value x e . Note that for every pointer newly introduced, we need to keep track of the corresponding split (U, W ) and of the corresponding side (i.e., U or W ). Conversely, in order to merge the respective data structures obtained for G U and G W , it suffices to extract the values x U e U,W and x W e U,W (on which the two new pointers introduced after the split are pointing to) and to set the original value x e U,W to max{x U e U,W , x W e U,W }.

Let (U, W ) be a split of G and let G U = (U ∪ {w}, E U ), G W = (W ∪ {u}, E W ) be the corresponding subgraphs of G. Consider some partial solutions x U and x W obtained, respectively, for the pairs G U , b U and G W , b W (for some capacity functions b U , b W to be defined later in the description of our main algorithm). We reduce the merging stage to a flow problem on a complete bipartite subgraph (induced by the split) with node-capacities. We detail this next. Proof. There are two cases. First, suppose C = N G (W ) = {u} (the case D = N G (U ) = {w} is symmetrical to this one). The split marker vertex w is pendant in G U , with its unique neighbour being u (so, in particular, x U {u,w} = d). In order to compute x, we set x U {u,w} to 0 and then we merge x U , x W . By Lemma 9 this takes constant-time. Furthermore, since

|E| -|E U | -|E W | = |C||D| -|C| -|D| = -1, and sc(G) = sc(G U ) + sc(G W ), we get ϕ(G) -ϕ(G U ) -ϕ(G W ) = 3 > 0.
Therefore, from now on we assume that |C| ≥ 2 and |D| ≥ 2. For every v ∈ C we assign a capacity c v = x U {v,w} and then we set x U {v,w} to 0. In the same way, for every v ∈ D we assign a capacity c v = x W {v ,u} and then we set x W {v ,u} to 0. It takes O(|C| + |D|)-time. Then, let us merge x U , x W in order to initialize x. By Lemma 9 this takes constant-time. While there exist a v ∈ C and a v ∈ D such that c v > 0, c v > 0 we pick one such pair v, v and we set:

x {v,v } = min{c v , c v }; c v = c v -x {v,v } ; c v = c v -x {v,v } .
Since for every loop, the capacity of at least one vertex drops to 0, it takes total time O(|C|+|D|). Furthermore, since |C| ≥ 2 and |D| ≥ 2 we have

|E| -|E U | -|E W | = |C||D| -(|C| + |D|) ≥ 2(|C| + |D|) -4 -(|C| + |D|) ≥ |C| + |D| -4. As a result, ϕ(G) -ϕ(G U ) -ϕ(G W ) ≥ |C| + |D| -4 + 4 ≥ Ω(|C| + |D|).
Overall, since there are at most n -2 components in any minimal split decomposition of G [START_REF] Rao | Solving some NP-complete problems using split decomposition[END_REF], the merging stages take total time O(ϕ(G)) = O(n + m).

Main result

Our main result can be seen as an algorithmic proof of the following equality: Proposition 2. Let G = (V, E), b, let (U, W ) be a split of G and let H W , b W be as defined in Definition 2. Given a maximum-cardinality b-matching x for the pair G, b and a maximum-cardinality b-matching x W for the pair H W , b W we have:

||x|| 1 = ||x W || 1 + µ U (0) -c U 2 Proof. We have ||x W || 1 ≥ ||x|| 1 -µ U (0)+c U
2 by Lemma 7. In order to prove the converse inequality, we can assume w.l.o.g. that x W satisfies both the saturation property and the symmetry property w.r.t. the module M u (otherwise, by Lemma 8, we can process x W so that it is the case). We partition ||x W || 1 as follows:

µ W = e∈E(W ) x W e , c 1 = deg x W (u 1 ) ≤ c U 1 and c 2 = deg x W (u 2 ) - x W {u 2 ,u 3 } = deg x W (u 3 ) -x W {u 2 ,u 3 } ≤ c U 2 .
Since we assume that x W satisfies both the saturation property and the symmetry property w.r.t. M u , we have c 2 > 0 only if c 1 = c U 1 . Furthermore, we observe that u 2 and u 3 must be saturated (otherwise, we could increase the cardinality of the b-matching by setting x W {u 2 ,u 3 } = c U 2 -c 2 ). Therefore, we get:

||x W || 1 = µ W + c 1 + 2c 2 + (c U 2 -c 2 ) = µ W + c 1 + c 2 + c U 2 .
x W We define b W u = b U w = c 1 + 2c 2 . Then, we proceed as follows (see Fig. 6 for an illustration).

• We transform x W into a b-matching for the pair G W , b W by setting x W {u,v } = x W {u 1 ,v } + x W {u 2 ,v } + x W {u 3 ,v } for every v ∈ N G W (u) = D. Note that we have deg x W (u) = b W u = c 1 + 2c 2 . Furthermore, the cardinality of the b-matching has decreased by x W {u 2 ,u 3 } = c U 2 -c 2 . • Let x U be a b-matching for the pair G U , b U of maximum cardinality µ U (c 1 + 2c 2 ). Since c 1 ≤ c U 1 , c 2 > 0 only if c 1 = c U 1
, and c 2 ≤ c U 2 , the following can be deduced from Proposition 1:

||x U || 1 = µ U (c 1 + 2c 2 ) = µ U (0) + c 1 + c 2 ; and the split marker vertex w is saturated in x U , i.e., deg x U (w) = b U w = c 1 + 2c 2 .
Finally, since we have

deg x W (u) = deg x U (w) = c 1 + 2c 2 ,
≥ ||x || 1 = ||x U || 1 + ||x W || 1 -(c U 2 -c 2 ) - (c 1 + 2c 2 ) = µ U (0) + c 1 + c 2 + ||x W || 1 -(c U 2 + c 1 + c 2 ) = ||x W || 1 + µ U (0) -c U 2 .
Finally, we now prove the main result in this paper. Proof. Let C 1 , C 2 , . . . , C s , s = sc(G) be the split components in any minimal split decomposition of G. Furthermore, let T be the corresponding split decomposition tree. It can be computed in linear-time [START_REF] Rao | Solving some NP-complete problems using split decomposition[END_REF]. We root T in C 1 .

For every 1 ≤ i ≤ s, let T i be the subtree of T that is rooted in C i . If i > 1 then let C p(i) be its parent in T . By construction of T , the edge {C p

(i) , C i } ∈ E(T ) corresponds to a split (U i , W i ) of G, where V (C i ) ∩ V ⊆ U i . Let G U i = (U i ∪ {w i }, E U i ), G W i = (W i ∪ {u i }, E W i ) be the corresponding subgraphs of G. As we observed in [9], T i is a split decomposition tree of G U i , T \ T i is a split decomposition tree of G W i .
Our algorithm proceeds in two main steps, with each step corresponding to a different traversal of the tree T . First, let G 1 = G and let G i = G U i for every i > 1. Let b 1 = b and, for every i > 1 let b i be the restriction of b to U i . We note that for any i > 1, b i does not assign any capacity to the split marker vertex w i . Up to adding a dummy isolated vertex w 1 to G 1 , we assume that this above property holds for any i. Then, for any i, we compute the triple (µ i (0), c i 1 , c i 2 ) w.r.t. G i , b i and w i (as defined in Proposition 1).

In order to do so, we proceed by dynamic programming on the tree T , as follows. Let

C i 1 , C i 2 , . . . , C i l be the children of C i in T . Every edge {C i , C it } ∈ E(T ), 1 ≤ t ≤ l corresponds to a split (U it , W it ) of G i , where V (C it ) ∩ V (G i ) ⊆ U it . We name w it ∈ V (C it ), u it ∈ V (C i )
the vertices added after the simple decomposition. Furthermore, let (µ it (0), c it 1 , c it 2 ) be the triple corresponding to G it , b it and w it (obtained by dynamic programming). We apply the reduction rule of Definition 2 -i.e., we replace the split marker vertex u it by the module M it = {u 1 it , u 2 it , u Finally, by applying Proposition 2 for every split (U it , W it ) we have:

µ i (0) = µ H i (0) + l t=1 (µ it (0) -c it 2 ).
Overall, this step takes total time O((k log Second, we compute a b-matching for the pair G, b that is of maximum cardinality µ 1 (0), by reverse dynamic programming on T . More precisely, for any i let b i w i be a fixed capacity for the split marker vertex w i (if i = 1 then we set b 1 w 1 = 0; otherwise, for i > 1, b i w i is obtained by reverse dynamic programming). In what follows, we compute a maximum-cardinality b-matching for the pair G i , b i . For that we set b H i w i = b i w i .

• We compute a maximum-cardinality x i for the pair H i , b H i such that both the saturation property and the symmetry property hold for every • For every 1 ≤ t ≤ l, let us define b i

u i t = deg x i (u 1 it ) + 2 • deg x i (u 2 it )
. We merge M it into the original split marker vertex u it . Furthermore, we assign the capacity b i u i t to u it , and we update the b-matching x i such that, for every v ∈ N H i (M it ), we have x i {v,u i t } = x i {v,u

1 i t } + x i {v,u 2 i t } + x i {v,u 3 i t
} . Doing so, we transform x i into a b-matching for C i , b i where all vertices u i 1 , u i 2 , . . . , u i l are saturated. This transformation has decreased the cardinality of the solution by:

l t=1 x i {u 2 i t ,u 3 i t } ≤ l t=1 c it 2 .
• For every 1 ≤ t ≤ l we set b it

w i t = b i u i t
and then we compute a maximum-cardinality b-matching x it for the pair G it , b it . Since the symmetry and saturation properties hold, we can deduce from Proposition 1 that w it is saturated.

• By applying the routine of Lemma 10 for every incident split (U it , W it ) we merge x i with all the x it 's until we obtain a b-matching for G i , b i . It takes time O(ϕ(G i ) -l t=1 ϕ(G it )).

Open questions

We presented an algorithm for solving b-Matching on distance-hereditary graphs, and more generally on any graph with bounded split-width. It would be interesting to extend our technique in order to solve the more general Maximum-Cost b-Matching problem. In particular, this would imply a quasi linear-time algorithm for Maximum-Weight Matching on bounded split-width graphs. Our main difficulty for handling with this more general case is that edges in a different split can now have pairwise different costs. We do not know how to encode this additional information within our gadgets in a compact manner.

Finally, we stress that, as a byproduct of our main result, we obtained an O((n + m) log n)time Maximum Matching algorithm on graphs with bounded split-width. We ask whether there exists a linear-time algorithm for this problem. In a companion paper [START_REF] Ducoffe | The use of a pruned modular decomposition for maximum matching algorithms on some graph classes[END_REF], we prove with a completely different approach that Maximum Matching can be solved in O(n + m)-time on distance-hereditary graphs. However, it is not clear to us whether similar techniques can be used for bounded split-width graphs in general.

Figure 1 :

 1 Figure 1: A graph and its split decomposition.

  s and s > r, then there exist at least s -r vertex-disjoint F 1 -augmenting paths. b-Matching. More generally given a graph G = (V, E), let b : V → N assign a nonnegative integer capacity b v for every vertex v ∈ V . A b-matching is an assignment of nonnegative integer edge-weights (x e ) e∈E such that, for every v ∈ V , we have e∈Ev x e ≤ b v . We define the x-degree of vertex v as deg x (v) = e∈Ev x e . Furthermore, the cardinality of a b-matching is defined as ||x|| 1 = e∈E x e . We will consider the following graph problem: Problem 2 (b-Matching). Input: A graph G = (V, E); an assignment function b : V → N. Output: A b-matching of G with maximum cardinality. For technical reasons, we will also need to consider at some point the following variant of b-Matching. Let c : E → N assign a cost to every edge. The cost of a given b-matching x is defined as c • x = e∈E c e x e . Problem 3 (Maximum-Cost b-Matching). Input: A graph G = (V, E); assignment functions b : V → N and c : E → N. Output: A maximum-cardinality b-matching of G where the cost is maximized. Lemma 3 ( [23, 24]). For every G = (V, E) and b : V → N, c : E → N, we can solve Maximum-Cost b-Matching in O(nm log 2 n)-time.

Figure 2 :

 2 Figure 2: An example with (µ(0), c 1 , c 2 ) = (1, 1, 1). Vertices are labeled with their capacity. Thin and bold edges have respective weights 0 and 1.

Lemma 7 .

 7 Let x be a b-matching for G, b. There exists a b-matching x

Figure 5 :

 5 Figure 5: An example where the naive processing stage requires O(||b|| 1 )-time.

Lemma 10 .

 10 Suppose that b U (resp., b W ) satisfies b U v ≤ b v for every v ∈ U (resp., b W v ≤ b v for every v ∈ W ). Let x U , x W a b-matching for, respectively, the pairs G U , b U and G W , b W such that deg x U (w) = deg x W (u) = d.Furthermore, for any graph H let ϕ(H) = |E(H)| + 4 • (sc(H) -1), with sc(H) being the number of split components in any minimal split decomposition of H 3 . Then, in at most O(ϕ(G) -ϕ(G U ) -ϕ(G W ))-time, we can obtain a valid b-matching x for the pair G, b such that ||x|| 1 = ||x U || 1 + ||x W || 1 -d.

Figure 6 :

 6 Figure 6: The construction of x . Vertices with capacity greater than 1 are labeled with their capacity. Thin and bold edges have respective weights 0 and 1.

  we can define a b-matching x for the pair G, b by applying Lemma 10. Doing so, we get ||x|| 1

Theorem 1 .

 1 For every pair G = (V, E), b with sw(G) ≤ k, we can solve b-Matching in O((k log 2 k)• (m + n) • log ||b|| 1 )-time.

  2 k) • i (|E(C i )| + |V (C i )|) • log ||b|| 1 ) = O((k log 2 k) • (n + m) • log ||b|| 1 ). Furthermore, since G 1 = G, we have computed the maximum cardinality µ 1 (0) of any b-matching of G.

Finally, the aboveCorollary 2 .

 2 b-matching is of maximum cardinality, that follows from Proposition 2 (applied for every incident split).Overall, this second step of the algorithm takes total time O(ϕ(G))+ O((k log 2 k) • i (|E(C i )| + |V (C i )|)) = O((k log 2 k) • (n + m)). For every graph G = (V, E) with sw(G) ≤ k, we can solve Maximum Matching in O((k log 2 k) • (m + n) • log n)-time.

  3 it } where u1 it has capacity c it 1 and the two adjacent vertices u 2 it , u 3 it have equal capacity c it 2 . Doing so for every 1 ≤ t ≤ l, we obtain a pairH i , b H i where H i is a supergraph of C i such that: |V (H i )| ≤ 3|V (C i )| ≤ max{3k, 9} and |E(H i )| ≤ 9|E(C i )|+|V (C i )|. Let us compute the triple (µ H i (0), c i 1 , c i 2 ) corresponding to H i , b H i and w i . By Proposition 1 it can be done in time O(|V (H i )||E(H i )| log 2 |V (H i )| log ||b|| 1 ), that is in O((k log 2 k) • (|E(C i )| + |V (C i )|) log ||b|| 1 ).

2c -ε ), for some ε > 0. This kind of FPT algorithms for polynomial problems have attracted recent attention[START_REF] Abboud | Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs[END_REF][START_REF] Bentert | Parameterized aspects of triangle enumeration[END_REF][START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF][START_REF] Fluschnik | When can graph hyperbolicity be computed in linear time?[END_REF][START_REF] Fomin | Fully polynomial-time parameterized computations for graphs and matrices of low treewidth[END_REF][START_REF] Giannopoulou | Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs[END_REF][START_REF] Husfeldt | Computing graph distances parameterized by treewidth and diameter[END_REF][START_REF] Iwata | On the power of tree-depth for fully polynomial FPT algorithms[END_REF][START_REF] Mertzios | The power of linear-time data reduction for maximum matching[END_REF] -although some examples can be found earlier in the literature[START_REF] Yuster | Maximum matching in graphs with an excluded minor[END_REF][START_REF] Yuster | Maximum matching in regular and almost regular graphs[END_REF]. We stress that Maximum Matching has been proposed in[START_REF] Mertzios | The power of linear-time data reduction for maximum matching[END_REF] as the "drosophila" of the study of these FPT algorithms in P. We continue advancing in this research direction.[START_REF] Abboud | Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs[END_REF] We stress that the work in[START_REF] Dragan | On greedy matching ordering and greedy matchable graphs[END_REF] is focused on a generic method in order to compute maximum matchings. In particular, the complexity of Maximum Matching on general distance-hereditary graphs is not considered.[START_REF] Bandelt | Distance-hereditary graphs[END_REF] The polynomial dependency in k is overlooked by some authors[START_REF] Mertzios | The power of linear-time data reduction for maximum matching[END_REF], who accept any functional dependency in the parameter. Since Maximum Matching is already known to be polynomial-time solvable, we find it more natural to consider this restricted setting.

We recall that the set of prime graphs in any minimal split decomposition is unique up to isomorphism[START_REF] Rao | Solving some NP-complete problems using split decomposition[END_REF].

* 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.

We can compute µ(0) with any b-Matching algorithm after we set the capacity of w to 0. Furthermore, the value of c 1 can be computed within O(log c 1 ) calls to a b-Matching algorithm, as follows. Starting from c 1 = 1, at every step we multiply the current value of c 1 by 2 until we reach a value c 1 > c 1 such that µ(c 1 ) < µ(0) + c 1 . Then, we perform a dichotomic search between 0 and c 1 in order to find the largest value c 1 such that µ(c 1 ) = µ(0) + c 1 . Once c 1 is known, we can use a similar approach in order to compute c 2 . Overall, since

The algorithm

We present in this section a quasi linear-time algorithm for computing a maximum-cardinality bmatching on any bounded split-width graph (Theorem 1). Given a graph G, our algorithm takes as input the split decomposition tree T of any minimal split decomposition of G. We root T in an arbitrary component C 1 . Then, starting from the leaves, we compute by dynamic programming on T the cardinality of an optimal solution. This first part of the algorithm is involved, and it uses the results of Section 3. It is based on a new reduction rule that we introduce in Definition 2. Finally, starting from the root component C 1 , we compute a maximum-cardinality b-matching of G, b by reverse dynamic programming on T . This second part of the algorithm is simpler than the first one, but we need to carefully upper-bound its time complexity. In particular, we also need to ensure that some additional property holds for the b-matchings we compute at every component. • The auxiliary graph H W is obtained from G W by replacing the split marker vertex u by a module

Reduction rule

we also add an edge between u 2 , u 3 (cf. Fig. 3). For every v ∈ W we set b

We will show throughout this section that our gadget somewhat encodes all the partial solutions for side U . For that, we start proving the following lemma: