Xuechen Liu

Md Sahidullah

Tomi Kinnunen

PARAMETERIZED CHANNEL NORMALIZATION FOR FAR-FIELD DEEP SPEAKER VERIFICATION

Keywords: acoustic feature extractor, channel normalization, spectrogram, far-field speaker verification

We address far-field speaker verification with deep neural network (DNN) based speaker embedding extractor, where mismatch between enrollment and test data often comes from convolutive effects (e.g. room reverberation) and noise. To mitigate these effects, we focus on two parametric normalization methods: per-channel energy normalization (PCEN) and parameterized cepstral mean normalization (PCMN). Both methods contain differentiable parameters and thus can be conveniently integrated to, and jointly optimized with the DNN using automatic differentiation methods. We consider both fixed and trainable (data-driven) variants of each method. We evaluate the performance on Hi-MIA, a recent large-scale far-field speech corpus, with varied microphone and positional settings. Our methods outperform conventional mel filterbank features, with maximum of 33.5% and 39.5% relative improvement on equal error rate under matched microphone and mismatched microphone conditions, respectively.

INTRODUCTION

Automatic speaker verification (ASV) [START_REF] Hansen | Speaker recognition by machines and humans: A tutorial review[END_REF] systems aim at verifying the speaker from input speech. ASV systems consist of three main components: acoustic feature extractor, speaker embedding extractor, and backend classifier. Thanks to advances in speaker embedding extraction based on deep neural networks (DNNs), ASV systems have improved substantially from conventional models such as i-vectors [START_REF] Dehak | Front-end factor analysis for speaker verification[END_REF]. This parallels advances in other speech tasks, such as automatic speech recognition (ASR) [START_REF] Hinton | Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups[END_REF] and keyword spotting (KWS) [START_REF] Chen | Small-footprint keyword spotting using deep neural networks[END_REF].

While achieving promising performance under controlled conditions, ASV performance remains substantially low in far-field scenarios, where the user must be authenticated from a distance [START_REF] Richey | Voices obscured in complex environmental settings (VOICES) corpus[END_REF]. Far-field ASV is needed in multiple applications, from virtual assistants to teleconferencing. Given its evolving research value, dedicated datasets and benchmarks have been released. One example is Voices Obsecured in Complex Environmental Settings (VOiCES) [START_REF] Richey | Voices obscured in complex environmental settings (VOICES) corpus[END_REF], which formulates a multi-channel simulated distant ASV scenario. An- other recent example is Hi-MIA [START_REF] Qin | HI-MIA: A far-field textdependent speaker verification database and the baselines[END_REF], a bilingual corpus (English and Mandarin) focused on smart home scenario with precise definition of microphone types and positions.

Far-field ASV is much more challenging compared to conventional ASV. The factors that impact recognition accuracy can be classified into two main categories: 1) Environmental variations, which includes natural room reverberation and additive noises. Common ways to tackle these include masking and de-reverberation techniques [START_REF] Taherian | Deep learning based multi-channel speaker recognition in noisy and reverberant environments[END_REF][START_REF] Qin | Far-field end-to-end textdependent speaker verification based on mixed training data with transfer learning and enrollment data augmentation[END_REF], along with other speech enhancement techniques; 2) Intrinsic variations introduced by microphone array and speakers themselves. Earlier studies have addressed model-wise multichannel training [START_REF] Cai | Multi-Channel Training for End-to-End Speaker Recognition Under Reverberant and Noisy Environment[END_REF] and adding beamforming front-end [START_REF] Mošner | Utilizing VOiCES dataset for multichannel speaker verification with beamforming[END_REF].

In this work, we thus focus on improving acoustic feature extractor without increasing computational complexity substantially. Such efforts lead to decent progress in other speech processing tasks. One successful example is powernormalized cepstral coefficients (PNCCs) [START_REF] Kim | Power-normalized cepstral coefficients (PNCC) for robust speech recognition[END_REF], whose efficacy has been demonstrated in speech recognition under various noisy conditions. Multi-taper MFCCs [START_REF] Kinnunen | Low-variance multitaper MFCC features: A case study in robust speaker verification[END_REF] and linear pre-Fig. 2: Recording condition of Hi-MIA, adopted from [START_REF] Qin | HI-MIA: A far-field textdependent speaker verification database and the baselines[END_REF], excluding sources that are not included in our protocol. The distance between noise source and speaker is 4m.

dictive features target robust ASV, but the advantages demonstrated with conventional models [START_REF] Jing | Speaker recognition based on principal component analysis of LPCC and MFCC[END_REF] do not necessarily generalize to DNN-based ASV [START_REF] Liu | A comparative re-assessment of feature extractors for deep speaker embeddings[END_REF].

In this work, we extend upon earlier research by adopting two parametric methods that operate on time-frequency spectrogram to enhance feature robustness. The first method, per-channel energy normalization (PCEN) [START_REF] Wang | Trainable frontend for robust and far-field keyword spotting[END_REF][START_REF] Lostanlen | Per-Channel Energy Normalization: Why and how[END_REF], replaces the commonly-used logarithmic compression. The second method, parameterized cepstral mean normalization (PCMN) [START_REF] Kalinli | Parametric cepstral mean normalization for robust speech recognition[END_REF], generalizes the widely-used parameter-free cepstral mean normalization (CMN) by the inclusion of learnable normalization parameters. Even if PCEN and PCMN were addressed in other tasks, to the best of the authors' knowledge, they have not been extensively addressed in DNN-based ASV for far-field applications. Thus, the primary contribution of this work is integration (and joint training of) these compensation methods with modern DNN-based ASV systems. Finally, we also propose a novel channel normalization method that combines the two methods in cascaded fashion. Our experiments are conducted on the recent Hi-MIA corpus [START_REF] Qin | HI-MIA: A far-field textdependent speaker verification database and the baselines[END_REF] with certain advantages elaborated below.

HI-MIA DATASET FOR FAR-FIELD SPEAKER VERIFICATION

The work of this paper is conducted on Hi-MIA. It is a dataset which contains 1561 hours of audio from 340 speakers [START_REF] Qin | HI-MIA: A far-field textdependent speaker verification database and the baselines[END_REF] recorded both under clean and smart home conditions in Mandarin and English. It consists of two subsets: AISHELLwakeup and AISHELL-2019B-eval, which complement one another in terms of recording conditions. Speech was collected with both close-talking (clean) high-fidelity microphone and 16 types of distributed microphone arrays under real rooms, corresponding to smart home environments. This is one of the advantages of Hi-MIA compared to VOiCES [START_REF] Richey | Voices obscured in complex environmental settings (VOICES) corpus[END_REF], where the source audios are replayed versions of prerecorded audio. The positional information of different types of devices and noise resources is illustrated in Fig. 2. The publicly available part of the data contains recordings for the close-talking microphone (position 7) and the microphone arrays at positions 2, 5 and 6. For more details about gender and age distribution, refer to [START_REF] Qin | HI-MIA: A far-field textdependent speaker verification database and the baselines[END_REF]. Hi-MIA shares similar recording conditions and contains overlapped speech with the evaluation data of the recent Far-Field Speaker Verification Challenge 2020 [START_REF] Qin | The INTERSPEECH 2020 far-field speaker verification challenge[END_REF].

PARAMETERIZED CHANNEL NORMALIZATION

Per-channel Energy Normalization

As a dynamic compression technique, PCEN [START_REF] Wang | Trainable frontend for robust and far-field keyword spotting[END_REF] addresses the singularity problem of logarithmic compression at zero, which is non-trivial and not robust to environmental and loudness variations from speakers. With t and f being time and frequency indices, PCEN is formulated as:

PCEN[t, f ] = E[t, f ] (M [t, f ] + ) α + δ r -δ r (1)
Here, E[t, f ] notes the input spectrogram energies. The PCEN operation in eq. 1 consists of two parts: automatic gain control (AGC) and dynamic range compression (DRC). AGC is represented by the term

G[t, f ] = E[t, f ]/(M [t, f ] + ) α , where M [t, f ] = (1-s)M [t-1, f ]+sE[t, f ]
denotes temporally integrated energies, computed using a first-order infinite impulse response (IIR) filter with pre-set smoothing coefficient s. For all experiments in this paper, s is the reciprocal to number of mel filters (40), following [START_REF] Wang | Trainable frontend for robust and far-field keyword spotting[END_REF]. The main control parameter is α ∈ (0, 1], which models the degree of compression. is a small number to avoid division by zero. Note that computation of G[t, f ] can be re-formulated to subtraction at logarithmic domain, followed by an exponential operation.

After obtaining the AGC-controlled energies, PCEN spectrogram is obtained by DRC, which is expressed as (G[t, f ] + δ) r -δ r , where the positive bias term δ > 1 and the exponent r ∈ (0, 1] are the main control parameters. They are designed to compress the loudness variations in the signal, reflecting earlier work on speech restoration [START_REF] Porter | Optimal estimators for spectral restoration of noisy speech[END_REF].

Fig. 3a and 3b compare the baseline and PCEN normalized mel spectrograms on a speech utterance. PCEN performs extensive compression of the dynamic range in specific parts of the signal while keeping part of the pattern. On the other hand, it has enhancement effect on speech onsets, which may be helpful in improving robustness. More work on analyzing compression characteristics of PCEN can be found in [START_REF] Lostanlen | Per-Channel Energy Normalization: Why and how[END_REF].

Parametric Cepstral Mean Normalization

Conventional CMN is a parameter-free and blind estimator which does not have interaction with other speech modules. It is expressed as below:

Xt [i] = X t [i] -µ t [i] (2)
where t and i are the time frame and feature indices, respectively.

µ t [i] = t m=t-N X m [i]/N stores
cepstral mean values with a sliding window of length N + 1. As a replacement, PCMN [START_REF] Kalinli | Parametric cepstral mean normalization for robust speech recognition[END_REF] is formulated as:

Xt [i] = β[i]X t [i] -(α[i]µ t [i] + µ 0 [i]) (3)
where β, α and µ 0 are the additional parameters. Compared to conventional CMN, this parameterized version allows the interaction between the normalizer and other learnable modules such as DNN speaker embedding extractor. It decides whether performing cepstral mean subtraction or not by varying the gain parameters α

[i] ∈ [0, 1].
Similar to PCEN, PCMN can also be effective on handling speech characteristics [START_REF] Kalinli | Parametric cepstral mean normalization for robust speech recognition[END_REF]. However, it may treat such information in a different way. Fig. 3c shows the PCMN-processed mel spectrogram. Interestingly, the lowfrequency speech components are generally preserved while high-frequency energies are subtracted to a lower level by PCMN. The compressed part becomes not as flat as observed from PCEN. This might be beneficial in preserving speech patterns as PCEN while creating more distinction and may also smear useful speech information. We take such a potential advantage and hypothesize that directly temporal modeling via PCMN can also lead to better ASV performance.

Trainable channel normalization

While related parameters can be primarily set in hand-crafted fashion, both PCEN and PCMN have data-driven variants in their original works [START_REF] Wang | Trainable frontend for robust and far-field keyword spotting[END_REF][START_REF] Kalinli | Parametric cepstral mean normalization for robust speech recognition[END_REF], making joint optimization via back propagation possible along with the DNN speaker embedding extractor.

For PCEN, as seen from eq. 1, the parameters α, δ, r are designed to be differentiable. Therefore, they can be generalized as frequency-dependent or even time-frequency dependent. Following [START_REF] Wang | Trainable frontend for robust and far-field keyword spotting[END_REF], we generalize them to be frequencydependent and perform the joint optimization: α = α(f ), δ = δ(f ), and r = r(f ), where f denotes frequency bin index.

For PCMN, from [START_REF] Kalinli | Parametric cepstral mean normalization for robust speech recognition[END_REF] the temporal dependency the method integrates can be leveraged by using a linear projection layer W •Y t +b, where Y t = [X t-10 , ..., X, ..., X t+10 ] are spliced cepstral input, W ∼ (α, β) and b are corresponding weights and bias. The weights contain the frequencydependent learnable values of α[i] and β[i] and the bias can be regarded as a frequency-dependent variant of µ 0 [i].

In the optimization of above trainable front-ends, we employ kernelized initialization, where the parameters are not selected from a specific distribution such as normal one [START_REF] Glorot | Understanding the difficulty of training deep feedforward neural networks[END_REF], but are migrated from common practical knowledge such as the workable hand-crafted counterparts. It has been applied and demonstrated to be effective for data-driven MFCCs [START_REF] Liu | Learnable MFCCs for speaker verification[END_REF]. Kernel initialization sets a starting point for further learning and adaptation via back-propagation. The exact values of related parameters are addressed in the next section.

EXPERIMENTS

Data

We conducted all experiments on the Hi-MIA dataset. Training of the speaker embedding extractor was conducted using AISHELL-2 [START_REF] Du | AISHELL-2: transforming mandarin ASR research into industrial scale[END_REF], following the original Hi-MIA protocol [START_REF] Qin | HI-MIA: A far-field textdependent speaker verification database and the baselines[END_REF]. The training data contains 1991 speakers recorded using an iOS device. The data was further augmented using room impulse response (RIR) [START_REF] Ko | A study on data augmentation of reverberant speech for robust speech recognition[END_REF] and noise sources from the MUSAN dataset [START_REF] Snyder | MUSAN: A music, speech, and noise corpus[END_REF].

Evaluation was conducted on the test partition of Hi-MIA. Our protocol defines two trial sets and six trial lists in total, based on recording conditions illustrated in Fig. 2: • Matched microphone, where the type of microphone between each enrollment and test utterances for each trial pair are the same. Enrollment data are recorded at position 2 while test utterances can originate from either 2, 5 or 6. This results in Ma-2, Ma-5, Ma-6 in Table 2.

• Mismatched microphone, where the enrollment utterances are recorded using the close-talk microphone at position 7 while the test utterances are from the microphone arrays at position 2, 5 and 6. This results in Mis-2, Mis-5, Mis-6 in table 2.

The protocol of full trial lists are available as an open-sourced Kaldi 1 recipe.

1 https://github.com/kaldi-asr/kaldi/tree/master/egs/hi mia/v1 Module Values PCEN α = 0.98, δ = 2.0, r = 0.5 [START_REF] Wang | Trainable frontend for robust and far-field keyword spotting[END_REF] PCMN β = 1.0, α = 0.5, µ 0 = 0.0

System Configuration

Front-ends. For all ASV systems considered the number of mel filters was set to 40, which is same as the input feature dimension for speaker embedding network. We consider mel filterbank with logarithmic compression and CMN post processor as our baseline, as illustrated in Fig. 1. Additionally, we combine PCEN and PCMN, where PCEN replaces the logarithmic non-linearity. We refer to front-ends with fixed and trainable (adaptive) components, respectively, as fixed front-ends and adaptive front-ends. Details of exact parameter values for fixed front-ends and kernel initialization is shown in Table 1. For kernel initialization, the values of vector-wise parameters are set as constant across all elements. Speaker embedding extractor. Extended x-vector based on time-delayed neural network (E-TDNN) [START_REF] Snyder | Speaker recognition for multi-speaker conversations using X-vectors[END_REF] is used as speaker embedding extractor. It is one of the descendants from x-vector which have reached promising performance using mel cepstral features. We introduce two modifications from original configuration: 1) For pooling layer, we acquired attentive statistics pooling [START_REF] Okabe | Attentive statistics pooling for deep speaker embedding[END_REF]; 2) For loss function we make use of additive margin softmax [START_REF] Wang | Additive margin softmax for face verification[END_REF]. For inference, we extract 512-dimensional embedding vector for each utterance from the first fully-connected layer after the pooling layer.

Backend. For all the experiments, we train corresponding probabilistic linear discriminant classifiers (PLDA) using the speaker embeddings from the train partition provided by Hi-MIA open-sourced protocol. Embeddings are processed via mean subtraction, length normalization, and centering using a 200-dimensional linear discriminant analyzer (LDA) before being fed to the PLDA.

Evaluation. Results are reported in terms of equal error rate (EER %). We also provide detection error trade-off (DET) curves of fixed front-ends for analysis.

RESULTS

The results on fixed and adaptive front-ends are presented in Table 3 and 4, respectively. Prefix 'a' added to the beginning of component indicates the adaptive variants. Recall that the mismatched microphone scenario contains additional mismatch between high-fidelity close talking microphone and the microphone array. The enrollment utterances are always recorded with microphone distance of 25cm from the speaker. Therefore, it is expected that for test utterances at same position, corresponding EERs are generally higher. This is what we indeed observe in both scenarios. In the following, we discuss results for matched and mismatched scenarios one by one.

Matched Microphone

Fixed front-ends. All the proposed variants outperform the baseline when there is a large distance between the enrollment and test recordings (Ma-5, Ma-6). Lowest EERs come from log+PCMN, where the maximum relative improvement of 33.5% over baseline comes from the furthest microphone position. Meanwhile, when the sources come from the same position, systems with PCEN do not outperform the baseline. Nonetheless, they do reach slightly lower EERs when the testing microphone moves from position 5 to 6. This indicates the potential of PCEN in normalizing room acoustic differences. Combining PCEN and PCMN gives slightly worse numbers than PCEN for all three trials. The comparative difference between PCEN and PCMN may be attributed to suboptimal parameter values: for computational reasons, we chose the values based on earlier recommendations from [START_REF] Lostanlen | Per-Channel Energy Normalization: Why and how[END_REF] and [START_REF] Kalinli | Parametric cepstral mean normalization for robust speech recognition[END_REF].

Adaptive front-ends. Somewhat disappointingly, results for the adaptive front-ends indicates generally worse performance compare to their fixed counterparts. The only system that returns satisfying performance for certain conditions is adaptive PCEN, which outperforms fixed PCEN by relatively 2.5% in Ma-2. This indicates sensitivity of data-driven methods, especially there is mismatch between training and test data. There are meanwhile numbers of points can be improved related to engineering issues and domain adaptation on those parameter values, left as a future work. As a starting point, we see that kernelized initialization of the parameters gives slight relative improvement for most cases. Maximum improvement made by kernelized initialization is from aPCMN in Ma-5, by relatively 16%. Such finding furthers the potential importance of hand-crafted knowledge to robust acoustic features.

Mismatched Microphone

Fixed front-ends. The improvement brought by fixed frontends agree with ones in the matched microphone scenario. PCMN the Mis-2 condition. At the same time, for the two PCEN variants, better verification performance compared to the baseline on all cases is observed. Different from matched microphone condition, here the combination of PCEN and PCMN outperforms PCEN-only front-end, especially at the furthest microphone condition (Mis-6, relatively 4.8%).

Adaptive front-ends. For Mis-2 condition with 75cm distance between the close talking microphone and the arrays, most adaptive front-ends outperform the baseline. Lowest EER is obtained by aPCEN with kernel initialization in Mis-2, outperforming baseline by relatively 28.3%. Nonetheless, for the other two cases, no adaptive front-end feature extractor gives lower EER than baseline and the performance gap between adaptive and fixed systems is noticeable. Also, while still giving relatively lower EER in Mis-5 by a maximum of 16.5% (aPCMN), kernel initialization degrades the performance for all adaptive systems in Mis-6 condition.

Analysis with DET plots

DET curves of fixed front-ends for PCEN and PCMN on Ma-2 and Mis-2 are illustrated in Fig. 4. The DET curves reiterate what has been reflected in the EERs. Interestingly, however, when the false alarm rate gets high, performances of different front-ends approach to each other. Especially for the combination of logarithmic compression and PCMN: in fact, under Ma-2 it is outperformed by the baseline as can be noticed from the figure. Therefore, it may not be a good option for systems that are less strict on false alarms.

Analysis with Adaptive Components

Ablation study on PCEN. As noted earlier, PCEN consists of two main components: AGC and DRC. As our last experiment, we address their effect by removing one of them from the adaptive pipeline. The results are shown at the last two rows of of Table 4. By removing DRC the filterbank energies are divided by its filtered variant without further compression. Compared to full adaptive PCEN, the results become worse. Meanwhile, by removing AGC, the energies are directly compressed without the division. In this case, performance of aP-CEN is substantially improved and outperforms baseline in all conditions, except for Ma-2 with least mismatch between enrollment and test utterances. Results on Mis-6 indicates re- Learnt values of PCMN. Finally, we show the weights and bias values of the best-performed system with adaptive PCMN involved in Fig. 5, where we combine logarithmic compression, adaptive PCMN and kernel initialization. As is evident, the learnt normalizers are different for each channel (unlike in the conventional non-parametric CMN). Further interpretation of the learnt normalization operations, and particularly their dependency on the training data, is deferred to a future work.

CONCLUSION

We addressed far-field speaker verification problem with mismatch conditions introduced by room reverberation and acoustic noise. We proposed new feature extractors to alleviate the negative impact due to these mismatches on verification performance by introducing two parameterized techniques on channel normalization: PCEN and PCMN. Our results on the recent Hi-MIA dataset confirm the efficacy of the introduced methods, especially for fixed PCMN. Our ablation study indicated the potential of DRC from PCEN.

In future research, we plan continue to explore both methods and their ingredients, especially compression parts such as DRC as a non-linearity itself and better integration on PCEN and PCMN with factorization, in order to compensate the high mismatch created by microphone and the factors.

Fig. 1 :

 1 Fig. 1: Proposed feature extractor with channel normalization on mel filterbank, DFT: discrete Fourier transform, PCEN: per-channel energy normalization, CMN: cepstral mean normalization, PCMN: parametric cepstral mean normalization.

Fig. 3 :

 3 Fig. 3: Different spectrogram representations on a speech utterance from Hi-MIA.

Fig. 4 :

 4 Fig. 4: DET curves for fixed front-ends.

Fig. 5 :

 5 Fig. 5: Values of learnt weights α, β and bias b for system with log and aPCMN (with kernel initializaion). Number of channel indices is i = 40 for all of them.

Table 1 :

 1 Setting of parameter values for related modules for fixed front-ends. They are also used for kernel initialization if applicable.

	Trial ID	#Enroll	#Test	#Target #Nontarget
	Ma-2	Arr, Pos. 2 Arr, Pos. 2	35910	35250
	Ma-5	Arr, Pos. 2 Arr, Pos. 5	34920	35175
	Ma-6	Arr, Pos. 2 Arr, Pos. 6	34575	35175
	Mis-2	Mic, Pos. 7 Arr, Pos. 2	34845	35010
	Mis-5	Mic, Pos. 7 Arr, Pos. 5	35625	34920
	Mis-6	Mic, Pos. 7 Arr, Pos. 6	34860	35655

Table 2 :

 2 Statistics for Hi-MIA sub-trials. Arr: Microphone array, Mic: close-talking microphone. Pos: position IDs where audios are recorded, referred from Fig. 2.

Table 3 :

 3 with logarithmic nonlinearity retains the lowest EERs overall, with a maximum relative improvement of 46.6% in Hi-MIA matched mic Hi-MIA mismatched mic Non-linearity Post norm. Ma-2 Ma-5 Ma-6 Mis-2 Mis-5 Mis-6 EER (%) results on Hi-MIA for fixed front-ends.

	log	CMN	3.65	7.43	8.51	8.16	11.01	12.84
	PCEN	-	4.05	6.93	6.87	6.45	10.7	12.34
	log	PCMN	3.27	5.56	5.66	4.35	6.66	9.23
	PCEN	PCMN	4.32	7.23	7.61	6.18	9.87	11.74
				Hi-MIA matched mic Hi-MIA mismatched mic
	Non-linearity	Post norm. Kernel init. Ma-2 Ma-5 Ma-6 Mis-2 Mis-5 Mis-6
	aPCEN	-	no	4.35	8.25	9.28	7.44	12.64	15.4
	aPCEN	-	yes	3.94	8.05	9.11	5.85	12.47	15.67
	log	aPCMN	no	4.45	8.85	9.14	8.94	13.24	14.58
	log	aPCMN	yes	4.31	7.43	8.9	6.17	11.59	16.09
	aPCEN	aPCMN	no	4.35	8.25	9.29	7.44	13.64	16.4
	aPCEN	aPCMN	yes	4.26	8.65	9.65	7.37	13.52	16.25
	aPCEN(no DRC)	-	yes	4.17	8.55	8.97	7.07	13.02	16.08
	aPCEN(no AGC)	-	yes	4.60	6.66	7.48	6.34	9.90	10.95

Table 4 :

 4 EER (%) results on Hi-MIA for adaptive front-ends, including ablation study for adaptive PCEN.

ACKNOWLEDGEMENTS

This work was partially supported by Academy of Finland (project 309629) and Inria Nancy Grand Est.


Guillaume Ducoffe

Alexandru Popa

The b-Matching problem in distance-hereditary graphs and beyond 1

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

We make progress on the fine-grained complexity of Maximum-Cardinality Matching within graphs of bounded clique-width. Quasi linear-time algorithms for this problem have been proposed for the important subclasses of bounded-treewidth graphs (Fomin et al., SODA'17) and graphs of bounded modular-width (Coudert et al., SODA'18). We present such algorithm for bounded split-width graphs -a broad generalization of graphs of bounded modular-width, of which an interesting subclass are the distance-hereditary graphs. Specifically, we solve Maximum-Cardinality Matching in O((k log 2 k) • (m + n) • log n)-time on graphs with split-width at most k. We stress that the existence of such algorithm was not even known for distance-hereditary graphs until our work. Doing so, we answer an open question of (Coudert et al., SODA'18). Our work brings more insights on the relationships between matchings and splits, a.k.a., join operations between two vertex-subsets in different connected components. Furthermore, our analysis can be extended to the more general (unit cost) b-Matching problem. On the way, we introduce new tools for b-Matching and dynamic programming over split decompositions, that can be of independent interest.

Introduction

The Maximum-Cardinality Matching problem takes as input a graph G = (V, E) and it asks for a subset F of pairwise non incident 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-Cardinality Matching has been extensively studied in the literature. In [START_REF] Edmonds | Paths, trees, and flowers[END_REF], Edmonds presented the first polynomial-time algorithm for this problem. It was also the first time that the complexity class P was formalized. Currently, the best-known algorithms for this problem 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. Intriguingly, Maximum-Cardinality Matching is one of the few remaining fundamental graph problems for which we neither have proved the existence of a quasi linear-time algorithm, nor a superlinear time complexity (conditional) lower-bound. This fact has renewed interest in understanding what kind of graph structure makes this problem difficult. Our present work is at the crossroad of two successful approaches to answer this above question, namely, the quest for improved graph algorithms on special graph classes and the much more recent π(G) ≤ k2 . 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-Cardinality Matching whenever k = O(n 1 2c -ε ), for some ε > 0. This kind of FPT algorithms for polynomial problems have attracted recent attention [START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF][START_REF] Dong | A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path[END_REF][START_REF] Giannopoulou | Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs[END_REF][START_REF] Iwata | On the power of tree-depth for fully polynomial FPT algorithms[END_REF][START_REF] Kratsch | Efficient and adaptive parameterized algorithms on modular decompositions[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-Cardinality 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.

Note that another far-reaching generalization of distance-hereditary graphs are the graphs of bounded clique-width [START_REF] Golumbic | On the clique-width of some perfect graph classes[END_REF]. In [START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF], we initiated the complexity study of Maximum-Cardinality Matching -and other graph problems in P -on bounded clique-width graph classes. The latter research direction was also motivated by the recent O(k 2 • n log n)-time algorithm for Maximum-Cardinality Matching on graphs of treewidth at most k, 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]. Turning our attention on denser graph classes of bounded clique-width, we proved in [START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF] that Maximum-Cardinality Matching can be solved in O(k 4 • n + m)-time on graphs with modular-width at most k. We stress that distance-hereditary graphs have unbounded treewidth and unbounded modular-width. Furthermore, clique-width is upper-bounded by split-width [START_REF] Rao | Solving some NP-complete problems using split decomposition[END_REF], whereas split-width is upper-bounded by modular-width [START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF]. As our main contribution in this paper, we present a quasi linear-time algorithm in order to solve some generalization of Maximum-Cardinality Matching on bounded split-width graphs -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], while improving the state-of-the-art. Our result shows interesting relationships between graph matchings and splits, the latter being an important particular case of the join operation that is used in order to define clique-width. The fine-grained complexity of Maximum-Cardinality Matching parameterized by clique-width, however, remains open.

Our contributions

We consider a vertex-weighted generalization for Maximum-Cardinality Matching that is known as the unit-cost b-Matching problem [START_REF] Edmonds | Matching: A well-solved class of integer linear programs[END_REF]. Roughly, every vertex v is assigned some input capacity b v , and the goal is to compute integer 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. We prove a simple combinatorial lemma that essentially states that the cardinality of a maximum b-matching in a graph grows as the floor of at most three linear pieces in the capacity b w of any fixed vertex w. This nice result (apparently never noticed before) holds for any graph. As such, we think that it could provide a nice tool for the further investigations on b-Matching. Then, we derive from our combinatorial lemma a variant of some reduction rule for Maximum-Cardinality 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]. 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. We expect our approach to be useful in other matching and flow problems.

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-Cardinality Matching can be solved in O((k log 2 k) • (m + n) • log n)-time on graphs with split-width at most k. Since distance-hereditary graphs have split-width at most two, we so obtain the first known quasi linear-time algorithms for Maximum-Cardinality Matching and b-Matching on distance-hereditary graphs.

We introduce the required terminology and basic results in Section 2, where we also sketch the main ideas behind our algorithm (Section 2.3). 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. Results of this paper were partially presented at the ISAAC'18 conference [START_REF] Ducoffe | The b-Matching Problem in Distance-Hereditary Graphs and Beyond[END_REF].

Preliminaries

We use standard graph terminology from [START_REF] Bondy | 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 neighborhood 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)
. Similarly, we define the neighborhood of any vertex-subset

S ⊆ V as N G (S) = v∈S N G (v) \ S.

Split-width

A complete join is a subset of edges A × B where A and B are disjoint vertex-subsets (equivalently, the edges of a complete join induce a complete bipartite graph with respective partite sets A and B). Let a split in a graph G = (V, E) be a partition V = U ∪ W such that there is a complete join between the vertices of N G (U ) and N G (W ). Note that any ordered bipartition (U, W ) where min{|U |, |W |} ≤ 1 is always a split, sometimes called a trivial split. It is desirable to restrict ourselves to non trivial splits, for which we have the additional requirement min{|U |, |W |} ≥ 2. A simple decomposition of G takes as input a non trivial split (U, W ), and it outputs two subgraphs

G U = G[U ∪ {w}] and G W = G[W ∪ {u}] where u, w / ∈ V are fresh new vertices such that N G U (w) = N G (W ) and N G W (u) = N G (U ).
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. First, a graph is prime for split decomposition if it only has trivial splits. Throughout the remainder of this paper, a prime subgraph of a graph G refers to any induced subgraph of G that is prime for split decomposition. We can now define the following first type of split decomposition:

• Minimal split decomposition. A split-decomposition is minimal if all the subgraphs obtained are prime.

The set of prime graphs in any minimal split decomposition is unique up to isomorphism [START_REF] Cunningham | Decomposition of directed graphs[END_REF]. However, a minimal split decomposition is in general not unique. To see that, consider a star with center x 0 and leaves x 1 , x 2 , x 3 . For every 1 ≤ i ≤ 3, we can define a split (U i , W i ) where

U i = {x 0 , x i } and W i = {x 1 , x 2 , x 3 } \ {x i }.
The simple decomposition associated to each split leads to the creation of two stars, each having exactly two leaves. However, the outputs of each simple decomposition are pairwise different. It leads us to our second case of "indecomposable" graphs. Specifically, 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]. We can now define another type 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].

Interestingly, the canonical split decomposition of a graph is unique [START_REF] Cunningham | Decomposition of directed graphs[END_REF]. The classic algorithms for computing a split decomposition, e.g. [START_REF] Charbit | Linear time split decomposition revisited[END_REF], compute this canonical split decomposition. Nevertheless, a minimal split decomposition can be computed from the canonical split decomposition in linear-time [START_REF] Cunningham | Decomposition of directed graphs[END_REF]. If the unicity of the decomposition is not required (that is the case for the algorithmic problems considered in this paper), then it is more convenient to work with a minimal split decomposition than with the canonical one. Indeed, doing so, we avoid handling with the particular cases of stars and complete graphs in our algorithms. For instance, the split decomposition of Fig. 1 is both minimal and canonical for the graph G to its left. Let us replace the edge {a, b} by a clique of size four, denoted by K, whose all vertices are adjacent to c. Doing so, we get a new graph G . In the split decomposition of Fig. 1, there is a unique complete subgraph, whose vertices are a, b and some split marker vertex w. In order to construct the canonical split decomposition of G , it suffices to replace this complete subgraph by a complete subgraph on K ∪ {w}. Since, the canonical split decomposition of G contains a subgraph with five vertices, it is not minimal. To construct a minimal split decomposition of G , we need to further decompose this subgraph into 3 triangles. 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]. Distance-hereditary graphs contain many interesting subclasses of their own such as cographs (a.k.a., P 4 -free graphs) and 3-leaf powers. Furthermore, since every degenerate graph has a split decomposition where all the components are either triangles or paths of length three, 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.

Problem 1 (Maximum-Cardinality Matching).

Input: A graph G = (V, E).
Output: A matching of G with maximum cardinality.

The Maximum-Cardinality Matching problem can be solved in O(m √ n)-time [START_REF] Micali | An O( √ V E) algorithm for finding maximum matching in general graphs[END_REF]. 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. Namely, 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, [START_REF] Berge | Two theorems in graph theory[END_REF]). 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. More precisely:

Lemma 2 (Hopcroft-Karp, [START_REF] Hopcroft | An nˆ5/2 algorithm for maximum matchings in bipartite graphs[END_REF]). Let F 1 , F 2 be matchings in G = (V, E). If |F 1 | = r, |F 2 | = 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 use 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 ( [21,[START_REF] Gabow | Data Structures for Weighted Matching and Extensions to b-matching and ffactors[END_REF]). 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.
In particular, we can solve b-Matching in O(nm log 2 n)-time.

There is a nonefficient (quasi polynomial) reduction from b-Matching to Maximum-Cardinality 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.

High-level presentation of the algorithm

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 vertex-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 split marker vertices in every component that substitute the other remaining components; intuitively, the weight of such a 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. 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 vertex-weighted generalization for Maximum-Cardinality Matching is the unit-cost b-Matching problem [START_REF] Edmonds | Matching: A well-solved class of integer linear programs[END_REF]. 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]. We observe that independently from this work3 , the authors in [START_REF] Kratsch | Efficient and adaptive parameterized algorithms on modular decompositions[END_REF] proposed a new Maximum-Cardinality Matching algorithm on graphs of bounded modular-width that is also based on a reduction to b-Matching. Unlike this work, the algorithm of [START_REF] Kratsch | Efficient and adaptive parameterized algorithms on modular decompositions[END_REF] cannot be applied to the more general case of bounded split-width graphs. Indeed, the main technical difficulty for the latter graphs -not addressed in [START_REF] Kratsch | Efficient and adaptive parameterized algorithms on modular decompositions[END_REF] -is how to precompute efficiently, for every component of their split 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 -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. This is where we use a result from Section 3, namely, that for every fixed vertex w in a graph, the maximum-cardinality of a b-matching is a piecewise-linear function, with at most three linear pieces, in the capacity b w of this vertex. 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 correspondence 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. We want to stress that to the best of our knowledge, the combination of dynamic programming over split decomposition with the recursive computation of some piecewiselinear functions is an all new algorithmic technique4 .

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, w ∈ V and 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, with only constantly many pieces (Proposition 1).

We start by introducing some useful lemmata. They are obtained by studying vertex-disjoint augmenting paths in some "expanded graphs" G b,t (cf. Lemmata 1 and 2). 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+1 be a maximum matching of G b,t+1 . Since G b,t+1 can be obtained from G b,t by adding a new vertex w t+1 , we can transform F t+1 into a (not necessarily maximum) matching of G b,t by removing at most one edge. In particular, µ(t) ≥ µ(t + 1) -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's 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 (since they are not in G b,t ), 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 in 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 µ must stay constant whenever t ≥ v∈N G (w) b v (saturation of all the neighbors). 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 upper-bound t max ≤ v∈N G (w) b v . Furthermore, since µ is strictly increasing between 0 and c 1 , 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 . Using Lemma 6, we prove by induction µ(c 1 + 2i) = µ(c 1 + 2i + 1) for every i ≥ 0. The latter proves, as claimed, c 2 = 2c 2 is even by minimality of c 2 . 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. We can compute µ(0) with any b-Matching algorithm after we set the capacity of w to 0. 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, 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 binary 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

c 1 + 2c 2 = t max ≤ v∈N G (w) b v = O(

The algorithm

We present in this section a quasi linear-time algorithm for computing a maximum-cardinality b-matching 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 top-to-bottom 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.

Reduction rule

Recall that an edge between a rooted subtree and its parent in T corresponds to a split (U, W ) of G. After we processed the side U (corresponding to this subtree) we account for all the partial solutions found for G U by transforming the split marker vertex u into a module5 , as follows: • The auxiliary graph H W is obtained from G W by replacing the split marker vertex u by a module

Definition 2. For any instance G = (V, E), b and any split (U, W ) of G let C = N G (W ) ⊆ U, D = N G (U ) ⊆ W . Let G U = (U ∪ {w}, E U ), G W = (W ∪ {u}, E W )
M u = {u 1 , u 2 , u 3 }, N H W (M u ) = N G W (u) = D;
we also add an edge between u 2 , u 3 .

For

every v ∈ W we set b W v = b v ; we set b W u 1 = c U 1 , b W u 2 = b W u 3 = c U 2 .
See Fig. 3 for an illustration. We will show throughout this section that our gadget somewhat encodes all the partial solutions for side U . Formally, the following relationship holds between solutions for G, b and solutions for H W , b W : Proposition 2. Given a graph G = (V, E) and a capacity function b, let (U, W ) be a split of G and let H W , b W be as in Definition 2. If x and x W are maximum-cardinality b-matchings for the pairs G, b and H W , b W , respectively, then we have:

||x|| 1 = ||x W || 1 + µ U (0) -c U 2
In what follows, we prove the first direction of Proposition 2 using classical flow techniques. We postpone the proof of the other direction since, for that one, we need to prove intermediate lemmata that will be also used in the proof of Theorem 1.

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:

• 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 edges incident to u 2 , u 3 . There are two cases:

-Case d < c U 1 . By Proposition 1, b U w = d and µ 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 .
In both cases, the resulting b-matching has cardinality at least

||x|| 1 + c U 2 -µ U (0).
The following Sections 4.2 and 4.3 detail the intermediate results that we will use in order to prove the other direction of Proposition 2 (as well as 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. -The necessary notations and terminology introduced here for understanding this intermediate problem are repeated in the proof of Theorem 1. -First, let us fix a given split decomposition of G, and let T be the associated split decomposition tree. We root T arbitrarily. Let C i be an arbitrary split component. We have that C i is obtained from a sequence of simple decompositions. Specifically:

• Let C p(i) be the parent node of C i (if it exists). The edge {C i , C p(i) } ∈ E(T ) corresponds to some split (U i , W i ) of G, where V (C i ) ∩ V ⊆ U i .
Recall that after we applied the simple decomposition associated to this split (see Sec. 2), we created the two split marker vertices u i , w i . In particular w i ∈ V (C i ).

• In the same way, if {C i , C it } is an edge of T between C i and a child node C it , then it corresponds to some split (U it , W it ) of G, where V (C i ) ∩ V ⊆ W it . After we applied the simple decomposition associated to this split (see Sec. 2), we created the two split marker vertices u it , w it . In particular u it ∈ V (C i ).

In order to create an auxiliary graph, we consider a split component C i and the subsequence of all the simple decompositions that are corresponding to the edges between C i and its children C it in T (i.e., we only exclude the edge between C i and its parent node in T if it exists). We apply the reduction rule of Definition 2 to each simple decomposition of this subsequence. Doing so, we obtain a pair H i , b H i with H i being a supergraph of C i obtained by replacing the split marker vertices u it , 1 ≤ t ≤ , by the modules

M it = {u 1 it , u 2 it , u 3 it }.
By construction the capacity of vertex u 1 it equals c it 1 ; furthermore, u 2 it , u 3 it are adjacent and they have the same capacity c it 2 . Let w i ∈ V (C i ) be the split marker vertex associated to the edge between C i and its parent node in T (if it exists). We observe that our above construction does not say anything about the capacity of w i in H i . Actually, several different capacities need to be assigned to w i in our final algorithm (i.e., see the proof of Theorem 1). However, this has no incidence on the discussion below, and so, for the remainder of this section, we may assume the capacity of w i to be arbitrary. We seek for a maximum-cardinality b-matching x i for the pair H i , b H i such that the following properties hold for every 1 ≤ t ≤ :

• (symmetry) deg x i (u 2 it ) = deg x i (u 3 it ). • (saturation) if deg x i (u 1 it ) < c it 1 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. We manage to do so by reducing to Maximum-Cost b-Matching (i.e., internal edges in the modules are assigned a larger cost than the other edges).

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 H i such that both the saturation property and the symmetry property hold for every M it , 1 ≤ t ≤ .

Proof. We start presenting an iterative solution that works on a standard (unit-cost) b-matching.

We show why this solution may not work when there are > 1 modules. Then, we explain how to fix this solution by assigning edge-costs. 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 it 1 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

13 min{c it 1 -deg x i (u 1 it ), x i {u 2 i t ,v } } (resp., min{c it 1 -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 2 i t ,v } , while we decrease x i {u 2 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. a a a a 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 ≤ , 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 ≤ be arbitrary. We observe that Rules 1 and 2 cannot modify the weight of an edge inside a module M i j . As a result, 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( 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. 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 b U , b W to be defined later). Assuming an appropriate data-structure for b-matchings (Lemma 9), this merging stage of x U with x W can be solved with a greedy algorithm (Lemma 10).

First we introduce the following data structure for storing a b-matching. To make things easier in our presentation, we shall assume (only for Lemmata 9 and 10 below) the split marker vertices u and w, for any split (U, W ), to be vertices of the original graph G. Specifically, we assume that we have u ∈ N G (W ) and w ∈ N G (U ). Note that in this situation, E U ∪ E W ⊆ E(G), and in fact E U ∩ E W is reduced to a single edge e = {u, w}. 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 }. Then, in at most K • (ϕ(G) -ϕ(G U ) -ϕ(G W ))-time, for some universal constant K, we can obtain a valid b-matching x for the pair G, b such that

||x|| 1 = ||x U || 1 + ||x W || 1 -d.
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 neighbor 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. Overall, v∈C c v = v ∈D c v = d.
Then, let us merge x U , x W in order to initialize x (note that by construction, x {u,w} = 0, and

||x|| 1 = ||x U || 1 + ||x W || 1 -2d)
. 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

The following algorithmic proof of Proposition 2 is the cornerstone of our main result.

Proof of Proposition 2. 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 .
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 .
x W • 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 .
Since we have deg

x W (u) = deg x U (w) = c 1 + 2c
≥ ||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 .
We finally prove (in a similar way as above) the main result in this paper.

Theorem 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.
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 lineartime [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. We can observe that T i is a split decomposition tree of G U i , while 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 .

Step 1: Computing the cardinality of the solution. 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 be the children of C i in T . Every edge {C i , C it } ∈ E(T ), 1 ≤ t ≤ also 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

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 ).
Finally, by applying Proposition 2 for every split (U it , W it ) we have:

µ i (0) = µ H i (0) + t=1 (µ it (0) -c it 2 ).
Overall, this step takes total time O((k

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

Step 2: Computing an optimal solution. We compute a b-matching for the pair G, b that is of maximum cardinality µ 1 (0), in two passes: the first one uses a top-to-bottom dynamic programming on T , and the second one uses a bottom-to-top dynamic programming on T . The output of Step 2 is more general than what we did in Step 1, thus seemingly subsuming this previous step. However, Step 1 is needed in order to properly initialize the capacities of all the subgraphs considered during Step 2. Indeed, we consider the same pairs H i , b H i as for Step 1. Each subgraph H i contains some triples of vertices u 1 it , u 2 it , u 3 it , that are in one-to-one correspondence with the edges {C i , C it } of the split decomposition tree. Their respective capacities were computed during Step 1 by bottom-to-top dynamic programming. Unlike for Step 1, the capacity of vertex w i is also fixed (computed by top-to-bottom dynamic programming).

Specifically, 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 top-to-bottom 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 b-matching x i for the pair H i , b H i such that both the saturation property and the symmetry property hold for every ). 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 . Recall that since the symmetry property holds, we have deg x i (u 2 it ) = deg x i (u 3 it ). In particular, we have after the transformation that:

v∈N H i (M i t ) x i {v,u i t } = deg x i (u 1 it ) + (deg x i (u 2 it ) -x i {u 2 i t ,u 3 i t } ) + (deg x i (u 3 it ) -x i {u 2 i t ,u 3 i t } ) = deg x i (u 1 it ) + 2 • (deg x i (u 2 it ) -x i {u 2 i t ,u 3 i t } ) = b i u i t .
As a result, in x i , all vertices u i 1 , u i 2 , . . . , u i are saturated. ) would result in a decrease of the maximum-cardinality of a b-matching for the pair G it , b it . As a result, in x it , the split marker vertex 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 (bottom-to-top dynamic programming). It takes time at most K • (ϕ(G i ) -l t=1 ϕ(G it )), for some universal constant K. Finally, the above b-matching is of maximum cardinality, that follows from Proposition 2 (applied for every incident split). Overall, this second step of the algorithm

Open questions

We presented an algorithm for solving b-Matching on distance-hereditary graphs, and more generally on any graph with bounded split-width. In contrast to our result, we stress that as already noticed in [START_REF] Kratsch | Efficient and adaptive parameterized algorithms on modular decompositions[END_REF], Maximum-Weight Matching cannot be solved faster on complete graphs, and so, on distance-hereditary graphs, than on general graphs. An interesting open question would be to know whether b-Matching can be solved in linear time on bounded split-width graphs. 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-Cardinality 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. Split marker vertices that correspond to a same simple decomposition are identified by two rectangles with the same color.

Lemma 4 .

 4 µ(t + 1) -µ(t) ≤ 1.

Figure 2 :

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

  ||b|| 1 ), we are left with O(log ||b|| 1 ) calls to any b-Matching algorithm. Therefore, by Lemma 3, we can compute the triple (µ(0), c 1 , c 2 ) in O(nm log 2 n log ||b|| 1 )-time.

  be the corresponding subgraphs of G. We define the pairs G U , b U and H W , b W as follows:• For every v ∈ U we set b U v = b v ; the capacity of the split marker vertex w is left unspecified. Let (µ U (0), c U 1 , cU2 ) be as defined in Proposition 1 w.r.t. G U , b U and w.

Figure 3 :

 3 Figure 3: The reduction of Definition 2.

Lemma 7 .

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

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

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 be b-matchings for, respectively, the pairs G U , b U and G W , b W such that we have 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 6 .

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.

•i u i t ≤ c it 1 or b i u i t = c it 1 + 2 •} ≤ c it 2 .

 122 For every 1 ≤ t ≤ we set b it w i t = b i u i t and then we compute a maximum-cardinality bmatching x it for the pair G it , b it . Note that since the saturation property holds, we have either b d it where d it = deg x i (u 2 it ) Then, we can deduce from Proposition 1 that any decrease of b it w i t (= b i u i t

  takes total time O(ϕ(G)) + O((k log 2 k) • i (|E(C i )| + |V (C i )|)) = O((k log 2 k) • (n + m)).Setting b v = 1 for every v ∈ V , we obtain the following implication of Theorem 1:Corollary 1. For every graph G = (V, E) with sw(G) ≤ k, we can solve Maximum-Cardinality Matching in O((k log 2 k) • (m + n) • log n)-time.

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

  3 it } where u 1 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 ≤ , we obtain a pair H 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

  1 ≤ t ≤ . By Lemma 8, it can be done in time O(|V(H i )||E(H i )| log 2 |V (H i )|), that is in O((k log 2 k) • (|E(C i )| + |V (C i )|)).

	{u 2 i t	,u 3 i t	}

• For every 1 ≤ t ≤ , let us define b i

u i t = deg x i (u 1 it ) + 2 • (deg x i (u 2 it ) -x i

The polynomial dependency in k is ignored 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-Cardinality Matching is already known to be polynomial-time solvable, we find it more natural to consider this restricted setting.

Our preliminary version of this paper was released on arXiv one day before theirs.

Earlier examples of dynamic programming which recursively computes a piece-wise linear function can be found in the literature, e.g., see[START_REF] Tseng | On computing the nested sums and infimal convolutions of convex piecewise-linear functions[END_REF].

Recall that M is a module if for every x, y ∈ M we have N (x) \ M = N (y) \ M .

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