Elena Raponi

Nathanaël Carraz Rakotonirina

Jérémy Rapin

Carola Doerr

Olivier Teytaud

Optimizing with Low Budgets: a Comparison on the Black-box Optimization Benchmarking Suite and OpenAI Gym

Keywords: Benchmarking, Black-box optimization, BBOB, OpenAI Gym, Bayesian Optimization, Reinforcement Learning

The growing ubiquity of machine learning (ML) has led it to enter various areas of computer science, including black-box optimization (BBO). Recent research is particularly concerned with Bayesian optimization (BO). BO-based algorithms are popular in the ML community, as they are used for hyperparameter optimization and more generally for algorithm configuration. However, their efficiency decreases as the dimensionality of the problem and the budget of evaluations increase. Meanwhile, derivative-free optimization methods have evolved independently in the optimization community. Therefore, we urge to understand whether cross-fertilization is possible between the two communities, ML and BBO, i.e., whether algorithms that are heavily used in ML also work well in BBO and vice versa. Comparative experiments often involve rather small benchmarks and show visible problems in the experimental setup, such as poor initialization of baselines, overfitting due to problem-specific setting of hyperparameters, and low statistical significance.

With this paper, we update and extend a comparative study presented by Hutter et al. in 2013. We compare BBO tools for ML with more classical heuristics, first on the well-known BBOB benchmark suite from the COCO environment and then on Direct Policy Search for OpenAI Gym, a reinforcement learning benchmark. Our results confirm that BO-based optimizers perform well on both benchmarks when budgets are limited, albeit with a higher computational cost, while they are often outperformed by algorithms from other families when the evaluation budget becomes larger. We also show that some algorithms from the BBO community perform surprisingly well on ML tasks.

I. INTRODUCTION

Black-Box Optimization (BBO) is an affirmed and rapidly growing field of optimization and a topic of critical importance in many application areas including complex systems engineering, energy and environment, materials design, drug discovery, chemical process synthesis, and computational biology [START_REF] Bajaj | Black-Box Optimization: Methods and Applications[END_REF]. As in other classical optimization contexts, BBO assumes that we are facing an objective function f for which we aim to provide a solution x with f (x) as good as possible E. Raponi (the corresponding author) is with LIACS, Leiden University, Leiden, The Netherlands (e-mail: e.raponi@liacs.leidenuniv.nl). At the time of writing this article, she was initially affiliated with Meta AI Research in Paris, France, and later with the Technical University of Munich in Munich, Germany, and LIP6, CNRS, Sorbonne Université in Paris, France. N. C. Rakotonirina is with Universitat Pompeu Fabra, Barcelona, Spain (email: nathanael.rakotonirina@upf.edu). At the time of writing this article, he was affiliated with LIMA, Université d'Antananarivo, Madagascar. J. Rapin and O. Teytaud are with Meta AI Research, Paris, France (e-mail: jrapin, oteytaud@fb.com). C. Doerr is with LIP6, CNRS, Sorbonne Université, Paris, France (e-mail: carola.doerr@lip6.fr).

using as little computational effort as possible. The key distinguishing property of BBO is that the algorithms learn about the problem instance f only by querying the quality f (x) of possible solution candidates x. This may be because we indeed lack an explicit representation of f (e.g., if simulations or experiments are required for assessing the quality of a possible solution) or when we lack efficient approaches to make use of the instance information (e.g., many real-world scheduling and routing problems are solved with heuristic approaches). Simplifying the complexity measurement, in BBO we typically only account for the number of function evaluations, and hence aim for identifying high-quality solutions x using as few function evaluations as possible.

Because of its high practical relevance, people with many different backgrounds are drawn into BBO, leading to a multitude of approaches in the area, ranging from simple heuristics such as local search to local/global modeling approaches. To understand the strengths and weaknesses of these different methods, fair performance comparisons are needed. Several platforms and benchmark suites (i.e., collections of benchmark problems) address this empirical comparison. Some examples are the Black-Box Optimization Benchmarking (BBOB) collection of the COCO environment [START_REF] Hansen | COCO: A platform for comparing continuous optimizers in a blackbox setting[END_REF], Large-Scale Global Optimization (LSGO) [START_REF] Tang | Benchmark Functions for the CEC'2010 Special Session and Competition on Large-Scale Global Optimization[END_REF], Nevergrad [START_REF] Rapin | Nevergrad -A gradient-free optimization platform[END_REF], Pseudo-Boolean Optimization (PBO) [START_REF] Doerr | IOHprofiler: A Benchmarking and Profiling Tool for Iterative Optimization Heuristics[END_REF], and Machine Learning and Data Analysis (MLDA) [START_REF] Rapin | Exploring the MLDA benchmark on the nevergrad platform[END_REF]. Apart from these more general benchmarking suites, there are also problem collections for evaluating and comparing algorithms for specific BBO tasks such as algorithm configuration and selection [START_REF] Bischl | ASlib: A benchmark library for algorithm selection[END_REF], [START_REF] Hutter | AClib: A benchmark library for algorithm configuration[END_REF], neural architecture search [START_REF] Mehta | NAS-benchsuite: NAS evaluation is (now) surprisingly easy[END_REF], [START_REF] Zela | NAS-Bench-1Shot1: Benchmarking and Dissecting One-shot Neural Architecture Search[END_REF], and expensive global optimization [START_REF] Bliek | Expobench: Benchmarking surrogate-based optimisation algorithms on expensive black-box functions[END_REF]; see [START_REF] Bartz-Beielstein | Benchmarking in optimization: Best practice and open issues[END_REF]Section 3] for a more exhaustive summary.

An approach commonly used for expensive optimization problems (for which the available number of function evaluations can be very small) uses surrogates to approximate the problem instance f , with the idea that the approximation f can be used to locate interesting solution candidates without requiring evaluations of the true problem f . Recently, Machine Learning (ML) has gone down this road and proposed several tools for BBO along these lines. In particular, a large field of research is Bayesian Optimization (BO), which is based on the Efficient Global Optimization (EGO) algorithm [START_REF] Jones | Efficient Global Optimization of Expensive Black-Box Functions[END_REF]. Despite its success, BO is stated to be limited to less than 15 parameters [START_REF] Nayebi | A Framework for Bayesian Optimization in Embedded Subspaces[END_REF], [START_REF] Wang | Bayesian Optimization in a Billion Dimensions via Random Embeddings[END_REF] and a few thousand evaluations [START_REF] Wang | Batched Large-scale Bayesian Optimization in High-dimensional Spaces[END_REF] according to the literature. To overcome this issue, recent research started to explore space partitioning and local modeling. In fact, learning a classifier that locates the samples on a promising subregion of the domain with high probability might be more effective than learning a regressor on the whole domain. Among other partitioning strategies, the Latent Action Monte Carlo Tree Search (LA-MCTS) [START_REF] Wang | Learning search space partition for black-box optimization using monte carlo tree search[END_REF] recursively learns space partition in a hierarchical manner using Monte Carlo Tree Search (MCTS) [START_REF] Coulom | Efficient selectivity and backup operators in Monte-Carlo tree search[END_REF]. Therefore, in addition to BO, MCTS has also been adapted from control and games to BBO [START_REF] Wang | Learning search space partition for black-box optimization using monte carlo tree search[END_REF], [START_REF] Munos | Optimistic optimization of a deterministic function without the knowledge of its smoothness[END_REF]. However, both the BO and MCTS tools for BBO have rarely been compared to existing BBO methods in a systematic and satisfactory manner. For example, the comparisons in the LA-MCTS paper [START_REF] Wang | Learning search space partition for black-box optimization using monte carlo tree search[END_REF] depend heavily on poor initialization of competitors, and the baselines used in the paper are not made available in the provided code, while the comparisons in [START_REF] Turner | Bayesian optimization is superior to random search for machine learning hyperparameter tuning: Analysis of the black-box optimization challenge 2020[END_REF] consider only the simple (1 + 1) sampling method and not the more sophisticated (and often better performing) BBO methods provided by the Nevergrad platform, although they refer to the comparison as 'Nevergrad'. However, we note some efforts to make neutral and comprehensive comparisons. Extensive comparisons in Nevergrad [START_REF] Rapin | Nevergrad -A gradient-free optimization platform[END_REF] tend to favor more classical methods such as tools from mathematical programming like Cobyla [START_REF] Powell | A Direct Search Optimization Method That Models the Objective and Constraint Functions by Linear Interpolation[END_REF] and others [START_REF] Cartis | Improving the flexibility and robustness of model-based derivative-free optimization solvers[END_REF], [START_REF] Powell | An efficient method for finding the minimum of a function of several variables without calculating derivatives[END_REF] or evolution strategies [START_REF] Beyer | The Theory of Evolution Strategies, ser. Natural Computing Series[END_REF] like CMA-ES [START_REF] Hansen | Completely derandomized selfadaptation in evolution strategies[END_REF], possibly equipped with surrogate models [START_REF] Auger | Local and global order 3/2 convergence of a surrogate evolutionary algorithm[END_REF]- [START_REF] Luksic | Meta-model framework for surrogate-based parameter estimation in dynamical systems[END_REF]. Hutter et al. [START_REF] Hutter | An evaluation of sequential model-based optimization for expensive blackbox functions[END_REF] ran SMAC-BBOB, a wellknown BO framework, on the BBOB benchmark suite and got positive results for BO when the budget of admissible function evaluations is fairly small. However, their investigation on expensive black-box functions only assesses SMAC against CMA-ES, yielding a rather limited benchmarking study.

Overall, there is widespread utilization of black-box optimization algorithms in the ML field, yet there exists a deficiency in conducting comprehensive comparisons between the algorithms favored in ML domains and those favored by evolutionary computation researchers. Recent papers [START_REF] Markov | The false dawn: Reevaluating Google's reinforcement learning for chip macro placement[END_REF] raised doubts on the reproducibility of some results in the ML community. In this work, we update and extend the comparison made in [START_REF] Hutter | An evaluation of sequential model-based optimization for expensive blackbox functions[END_REF] by adding several state-of-the-art solvers and by comparing not only on the BBOB benchmark suite but alsoas it is closer to ML -on direct policy search for OpenAI Gym problems [START_REF] Brockman | OpenAI Gym[END_REF]. We evaluate the performance of various BBO algorithms, considering solvers commonly associated with the ML community as well as more classical heuristics, and testing over a range of budgets that allow us to draw fair and unbiased conclusions.

II. BLACK-BOX OPTIMIZATION ALGORITHMS

We briefly summarize the algorithms included in our comparison, along with a brief description of two main classes of interest, BO and LA-MCTS.

A. Bayesian Optimization

BO [START_REF] Jones | Efficient Global Optimization of Expensive Black-Box Functions[END_REF], [START_REF] Mockus | Bayesian Approach to Global Optimization: Theory and Applications[END_REF] is a sequential design strategy targeting global optimization of black-box functions that do not assume any functional forms. It is particularly advantageous for problems where the objective function is difficult to evaluate, is a black box with some known structure, relies upon less than 20 dimensions, and where no information about sensitivity and derivatives is available. Since the objective function does not have an explicit mathematical formulation, BO treats it as a random function and places a prior over it. A Kriging model, also known as Gaussian Process Regression (GPR), can be used as a prior probability distribution over functions in BO.

BO starts with sampling an initial Design of Experiments (DoE) of size n 0 : X = [x (1) , x (2) , . . . , x (n0) ] ⊤ , where the sample i is denoted as

x (i) = (x (i) 1 , ..., x (i) D ) ∈ X ⊂ R D [33].
The corresponding objective function values are denoted as y = (f (x (1) ), f (x (2) ), . . . , f (x (n0) )) ⊤ . Conventionally, a centered Gaussian process prior is assumed on the objective function: f ∼ gp(0, K(•, •)), where K : X × X → R is a positive definite function -also known as kernel functionwhich computes the autocovariance of the process.

Often, a Gaussian likelihood is taken, leading to a conjugate posterior process [START_REF] Rasmussen | Gaussian Processes for Machine Learning, ser. Adaptive Computation and Machine Learning[END_REF], i.e., f | y ∼ gp( f (•), K ′ (•, •)), where f and K ′ are the posterior mean and covariance function, respectively.

On an unknown point x, f (x) yields the maximum a posteriori estimate of f (x) whereas ŝ2 (x) := K ′ (x, x) quantifies the uncertainty of this estimation. The posterior process is, again, a GPR. Based on the posterior process, promising points are identified via the so-called infill-criterion, i.e., by optimizing an acquisition function that balances f with ŝ2 (exploitation vs. exploration). A variety of infillcriteria has been proposed in the literature, e.g., Probability of Improvement [START_REF] Mockus | Bayesian Approach to Global Optimization: Theory and Applications[END_REF], [START_REF] Forrester | Engineering Design via Surrogate Modelling -A Practical Guide[END_REF], Expected Improvement [START_REF] Forrester | Engineering Design via Surrogate Modelling -A Practical Guide[END_REF], and the Upper Confidence Bound [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF], [START_REF] Srinivas | Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design[END_REF]. When a new candidate point is selected by the infill criterion, it is evaluated and added to the BO data set, which is used to update the GPR posterior. This process is repeated until a stopping condition is met, i.e., a good enough result is located or the computational budget is exhausted.

B. Monte Carlo Tree Search

Monte Carlo Tree Search (MCTS) [START_REF] Coulom | Efficient selectivity and backup operators in Monte-Carlo tree search[END_REF] is a solver that migrated from trees of bandits for games and control, including alpha-zero [START_REF] Silver | Mastering the game of Go with deep neural networks and tree search[END_REF], [START_REF] Silver | Mastering chess and shogi by self-play with a general reinforcement learning algorithm[END_REF], to applications in BBO [START_REF] Wang | Learning search space partition for black-box optimization using monte carlo tree search[END_REF], [START_REF] Munos | From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning[END_REF]. Its evolved version, LA-MCTS [START_REF] Wang | Learning search space partition for black-box optimization using monte carlo tree search[END_REF], progressively learns and generalizes promising regions in the problem space by recursively partitioning so that solvers like BO can access these regions to improve their performance. At any iteration t of the algorithm, a training dataset D t = (X, Y) of all the points evaluated so far is available. A tree node A represents a subregion of the search space Ω A . Therefore, D t ∩ Ω A is the set of all the samples falling in the subregion Ω A . MCTS uses the Monte Carlo simulation to accumulate value estimates that lead to highly rewarding trajectories in the search tree. In other words, MCTS pays more attention to promising nodes (i.e., subregions of the search space), in order to avoid the need to brute force all possibilities. This is done by using an Upper Confidence Bound (UCB) policy. More specifically, each node has an associated UCB value and, during selection, the child node with the highest UCB value is considered. The statistics used to compute the UCB are (1) n A , which is the number of samples in D t ∩ Ω A , and (2) the node value

v A := ( xi∈Dt ∩Ω A f (x i ))/n A .
Therefore, in LA-MCTS, which is the MCTS-based optimizer that we include in the comparisons of this study, promising regions are found by recursively partitioning the search space based on latent actions. In one iteration, LA-MCTS starts building the tree by partitioning and then selects a region based on UCB. Finally, sampling is performed in the selected region using BO. In this way, BO avoids overexploring the search space, and its performance improves, especially for high-dimensional problems.

C. Selection of BO-based Algorithms

From the large collection of existing BO-based solvers, we have selected the following ones for our empirical comparison:

• BO: the Bayesian Optimization algorithm [START_REF] Snoek | Practical Bayesian optimization of machine learning algorithms[END_REF] implemented in Nevergrad. The python class is a wrapper over the bayes opt package [START_REF] Nogueira | Bayesian Optimization: Open source constrained global optimization tool for Python[END_REF].

• LA-MCTS [START_REF] Wang | Learning search space partition for black-box optimization using monte carlo tree search[END_REF]: as described above, LA-MTCS is an MCTS-based derivative-free meta-solver that recursively learns space partition in a hierarchical manner. Sampling is then performed in the selected region using BO.

• Turbo [START_REF] Eriksson | Scalable global optimization via local Bayesian optimization[END_REF]: a trust-region-inspired algorithm using Thompson sampling rather than the optimization of an acquisition function to find new candidate solutions in each subregion. Turbo20 denotes the multi-trust-regions counterpart of Turbo.

• AX [START_REF] Facebookresearch | Ax -adaptive experimentation[END_REF]: a modular BO framework that uses BoTorch primitives for optimization over continuous spaces. It automates the selection of optimization routines, reducing the amount of fine-tuning required.

• SMAC [START_REF] Hutter | Sequential modelbased optimization for general algorithm configuration[END_REF]: a sequential model-based algorithm for algorithm configuration to optimize the parameters of arbitrary algorithms. It scales well to high dimensions and is particularly suitable for hyperparameter optimization of ML algorithms. The main core consists of BO. SMAC2 refers to SMAC-HPO, i.e., SMAC with hyperparameter optimization.

• HyperOpt [START_REF] Bergstra | Hyperopt: a python library for model selection and hyperparameter optimization[END_REF]: library for serial and parallel hyperparameter optimization, designed to accommodate BO algorithms based on Gaussian processes and regression trees. We use the version based on Parzen estimates. • Optuna [START_REF] Akiba | Optuna: A nextgeneration hyperparameter optimization framework[END_REF]: automatic hyperparameter optimization software framework which uses state-of-the-art algorithms for sampling hyperparameters and pruning unpromising trials. By default, Optuna implements a BO algorithm (Tree-structured Parzen Estimator).

D. Classical Black-box Optimization Algorithms

As baselines commonly used in the broader BBO context we consider CMA, which stands for CMA-ES, a well-known evolution strategy [START_REF] Hansen | Completely derandomized selfadaptation in evolution strategies[END_REF], Cobyla, a tool from mathematical programming [START_REF] Powell | A Direct Search Optimization Method That Models the Objective and Constraint Functions by Linear Interpolation[END_REF], particle swarm optimization (PSO [START_REF] Kennedy | Particle Swarm Optimization[END_REF]), and NGOpt from Nevergrad [START_REF] Rapin | Nevergrad -A gradient-free optimization platform[END_REF], a wizard that combines many classical algorithms in various ways [START_REF] Meunier | Black-box optimization revisited: Improving algorithm selection wizards through massive benchmarking[END_REF]. In the use cases considered in this work (sequential, low-dimensional, noisefree problems), NGOpt mainly uses CMA, Cobyla, and (1+1)type sampling equipped with metamodels.

We also include DefaultCMA [START_REF] Hansen | Completely derandomized selfadaptation in evolution strategies[END_REF], a version of CMA without the BBOB-specific initialization used for the experiments of CMA on BBOB [START_REF] Hansen | Real-parameter black-box optimization benchmarking 2009: Experimental setup[END_REF]. We do this to show that ad hoc initialization of CMA-ES does not lead to significant improvement over DefaultCMA.

III. BENCHMARK PROBLEMS

Extensive comparisons have already been proposed in Nevergrad [START_REF] Meunier | Black-box optimization revisited: Improving algorithm selection wizards through massive benchmarking[END_REF], focusing on reproducibility, real-world, and different problem sizes. We propose here additional experiments in the well-known BBOB framework [START_REF] Hansen | Real-parameter black-box optimization benchmarking 2009: Experimental setup[END_REF], chosen for its simplicity/canonicity, and for OpenAI Gym1 , commonly used in the reinforcement learning (RL) environment [START_REF] Thoma | RL-agents[END_REF]- [START_REF] Rezazadeh | Continuous multi-objective zero-touch network slicing via twin delayed ddpg and openai gym[END_REF].

BBOB: The BBOB collection contains 24 functions, with known difficulty (e.g., non-separability, ill-conditioning, different levels of multimodality, adequate or weak global structure, etc.). Although all functions are defined and can be evaluated over R D , the default search domain is [-5, 5] D ; that is, in contrast to Nevergrad's experiments in [START_REF] Rapin | Nevergrad -A gradient-free optimization platform[END_REF], [START_REF] Rapin | Dashboard of results for Nevergrad platform[END_REF], the BBOB suite has a focus on bounded domains.

BBOB offers a possibility to randomize both the position of the optimal solution (that is, test functions are randomly shifted in the domain) and the function value of the optimum (test functions are randomly shifted in the co-domain). To reduce bias with respect to problem encoding, we run the algorithms on 15 randomly chosen instances per test function and dimension. We consider six different dimensions (2, 3, 5, 10, 20, and 40).

As suggested in [START_REF] Hutter | An evaluation of sequential model-based optimization for expensive blackbox functions[END_REF], we focus on a relatively small budget of 10D or 100D function evaluations (the default setting for BBOB experiments is 1000D). When a method crashes, we rerun it with the remaining budget.

For the BBOB experiments, our key performance measure is the empirical cumulative distribution function (ECDF) of the runtimes needed to reach the optimal objective value with a given precision ∆t, i.e., the runtime depends on a given target function value (f t = f opt + ∆t) and is computed across all runs of an optimizer on a function, as the total number of function evaluations before reaching f t divided by the number of trials that actually reached f t . Informally, the ECDF shows the proportion of problems solved within a given budget, with the budget indicated on the x-axis.

OpenAI Gym with Direct Policy Search: Firstly, we work on a multi-deterministic Open AI Gym with tiny neural nets. Indeed, we analyze a small version (small number of neurons, low budget) to fit the low-budget context of the present work. Multi-deterministic here means that for a given algorithm, a different seed is drawn at random for each repetition, and this list of seeds is used for all algorithms. There are different seeds so that we avoid overfitting, and the list of seeds is the same over the different algorithms so that we have statistical pairing. This means that parameters are not tuned based on specific landscapes (e.g., bounded/unbounded domains, prescribed optimal regions, and multimodality of the objective function). This is somewhat analogous to random perturbation of the optimum in classical BBO benchmarks in the sense that the objective function is deterministic but drawn randomly.

Within the gym library, we select a few environments to compare algorithms based on (1) average loss (i.e. average negated reward) and ( 2 We chose these problems with D < 50 because they are sufficiently challenging and are not too hard in our context of tiny networks and minimal budget, i.e., not all algorithms perform equally. Here we use a neural factor (i.e., the scaling coefficient used in the benchmarking suite to choose the size of neural networks) of 1. The dimension, i.e., the total number of weights, is a consequence of the number of neurons, which in turn is based on the scaling factor (the number of neurons per hidden layer is the neural factor multiplied by the input dimension).

In a second set of experiments we include problems with dimensions D ≤ 264 for larger networks defined by setting the neural factor to 3, which parameterizes the size of the hidden layer. This bound on the dimension and the different neural factor lead to a different subset of OpenAI Gym problems: LunarLanderContinuous-v2, Blackjack-v0, Pendulum-v0, HotterColder-v0, MountainCarContinuous-v0, CartPole-v0, Acrobot-v1, NChain-v0, GuessingGame-v0, CartPole-v1.

Winning percentage rates are evaluated at fixed budgets of 25, 50, 100, 200, and 400 function evaluations for both settings (neural factor 1 and 3), while bigger budgets are also considered for the bigger networks (see Sections IV and V in the Supplementary Material).

IV. RESULTS OF THE EMPIRICAL COMPARISON

Results for BBOB: Figs. 1 and2 present results with budget equal to 10D and 100D, respectively, in dimension D. The xaxis is the budget divided by the dimension, in logarithmic scale, while the y-axis shows the frequency of problems solved, i.e., the higher, the better. The plots are built by using the COCO/BBOB post-processing tool. It aggregates problems with different target precision values and displays the runtime distributions with simulated restarts [START_REF] Hansen | COCO: A platform for comparing continuous optimizers in a blackbox setting[END_REF], [START_REF] Hansen | Anytime performance assessment in blackbox optimization benchmarking[END_REF]. The default target precision values are 51 evenly log-spaced values between 10 2 and 10 -8 . The complete data set is archived on Zenodo [START_REF] Raponi | Comparison of Low-budget Black-box Optimization Algorithms on BBOB[END_REF] and allows further comparison with other BBOB data sets through the original COCO platform [START_REF] Hansen | COCO: A platform for comparing continuous optimizers in a blackbox setting[END_REF] or the IOHanalyzer web-interface [START_REF] Wang | IOHanalyzer: Detailed Performance Analyses for Iterative Optimization Heuristics[END_REF].

Our experiments for a budget of 10D reproduce the results in [START_REF] Hutter | An evaluation of sequential model-based optimization for expensive blackbox functions[END_REF], where SMAC outperforms CMA. However, SMAC performance decreases with increasing dimension. Similar to all BO-based algorithms, its computational complexity increases significantly with increasing dimension and with increasing budget.

Although we tested fewer optimizers for the D = 20 and D = 40 cases due to the high computational cost, it is interesting to note that Cobyla, which is simply based on linear interpolation, often performs better than all other solvers. Although there is no tuning for our present results from Cobyla on BBOB, it outperformed all BO-based algorithms. Cobyla is also the algorithm selected by the NGOpt wizard for the test cases considered, which explains their similar performance. Fig. 2 shows that both versions of CMA -defaultcma and cmafmin2 (and NGOpt16, which uses CMA as a component) -perform better than all other solvers when a larger budget of function evaluations is available.

We conclude by remarking that, in the BBOB benchmark with our specific setting using a low budget, there are elements that have a significant impact on the overall result:

• The LinearSlope function, which has optima in the corners, is difficult for methods that assume that the optimum is supposed to be inside. • The precision parameter, ranging from 1e -8 to 100 by default, has a significant impact on results. Since our budget is much smaller than the default setting, the percentage of the problems that are successfully solved is smaller than the typically reported ones. In an additional set of experiments, we verified that removing LinearSlope or changing the precision parameter does not change the overall picture of our results.

Table I and Table II list the total execution time in seconds for 15 runs on the 24 BBOB functions for budget 10D and 100D, respectively. Note that NGOpt sometimes, in particular when the budget is sufficiently large compared to the dimension, spends a significant time learning a metamodel and checking in cross-validation whether this metamodel could be applied. NGOpt can hence be unexpectedly more expensive in lower dimensions, which in our experiments leads to the non-monotonic behavior of the running time with respect to the dimension. DefaultCMA, Turbo20, and SMAC2 have comparable execution times to CMAFmin2, Turbo, and SMAC, respectively. AX, BO, LAMCTS, and SMAC showed a total time of more than 20 000 seconds in dimension 10. As their computational cost became unmanageable for dimension 20, we stopped the runs after 3-day wall-clock time. We therefore do not report results for these algorithms for the 20-and 40-dimensional BBOB functions with 10D budget. The same algorithms, with the exception of SMAC, plus Optuna, are excluded from the experiments with a higher total evaluation budget (100D) due to their excessive computational cost for that budget.

Results for the Direct Policy Search on OpenAI Gym: In Fig. 3, we provide an independent comparison of blackbox solvers applied to the Ng-Full-Gym benchmark, which is Nevergrad's direct policy search applied to OpenAI Gym. More precisely, is the optimization of a neural network as a controller for OpenAI Gym problems. We plot the unscaled loss, defined as the opposite of the reward the agent accumulates over time. Here, the lower the curve, the better the performance. The non-monotonic trend of the curves with respect to the elapsed budget is due to the fact that, for a given problem and algorithm, we perform new runs each time the total budget of the evaluations is updated. As a consequence, the algorithm may choose a different parametrization depending on the total budget or the ratio between the budget and the dimension of the specific benchmark, leading to a statistically significant difference in performance. In addition, since we perform independent runs for different budgets and average over the repetitions, some variability in performance is to be expected.

We add the following algorithms to our comparison: QO-RandomSearch [START_REF] Rahnamayan | Quasioppositional differential evolution[END_REF], MetaTuneRecentering [START_REF] Meunier | Variance reduction for better sampling in continuous domains[END_REF], and MetaRecentering [START_REF] Cauwet | Fully parallel hyperparameter search: Reshaped space-filling[END_REF] are variants of random search that are fully parallel and reduce redundancies compared to random search. We also add NGOpt16RL and SpecialRL from Nevergrad: NGOpt16RL is Nevergrad's wizard NGOpt optimized specifically for RL problems; SpecialRL runs the base NGOpt16RL for half of the budget and then uses test-based population size adaptation (TBPSA) [START_REF] Khalidov | Consistent population control: generate plenty of points, but with a bit of resampling[END_REF] in the second half. Moreover, since the OpenAI Gym suite contains problems that are unbounded with optima at a small scale, we add algorithms that can adjust the scale of the search. GeneticDE and RotatedTwoPointsDE, for example, are designed to extrapolate the scale from some variables to others and find the right scale before running the classic DE [START_REF] Storn | Differential Evolution -A Simple and Efficient Heuristic for global Optimization over Continuous Spaces[END_REF] algorithm. MetaTuneRecentering performs a DoE entirely designed to choose the right scale depending on the relationship between budget and dimension. MultiCMA is a tentative robustification of CMA that runs three copies of CMA. We also consider a (1+1) evolutionary algorithm [START_REF] Schumer | Adaptive Step Size Random Search[END_REF], which is a simple and fast state-of-the-art heuristic for adjusting the scale, Diagonal CMA [START_REF] Hansen | Completely derandomized selfadaptation in evolution strategies[END_REF], which uses a diagonal covariance matrix, and its scaled version, Scaled Diagonal CMA [START_REF] Rapin | Nevergrad -A gradient-free optimization platform[END_REF]. Finally, we add to our portfolio Lamcts-Turbo [START_REF] Wang | Learning search space partition for black-box optimization using monte carlo tree search[END_REF], an improved version of vanilla LA-MCTS coupled with Turbo to draw new samples in the selected node of the Monte Carlo search tree at each iteration. For a complete list of all algorithms compared, see Section VI in the Supplementary Material.

Although we cannot derive comprehensive recommendations from Fig. 3 because of the high variability of results across different benchmarks and dimensions, some conclusions can be drawn from the observation of similar patterns. First, we note that Fig. 3b,3c, and 3d corresponding to problems of intermediate dimension (D = 15 and D = 24) show no significant differences in solver performance. On the contrary, for the low-dimensional test cases in Fig. 3a and 3g, we observe a very clear superiority of the BObased solvers (BO and AX), HyperOpt, PSO, and the wizard NgOpt16RL, all consistently belonging to the 5-best group. On the other hand, Fig. 3e, 3f, and3h show that the quality of the performance of the 5-best group deteriorates as the dimension of the problem increases. Indeed, we observe the lowest loss values at the end of the total evaluation budget for population-based algorithms like DE and CMA, which are known to be powerful heuristics to address difficult black-box problems when a large number of function evaluations are available. However, for lower budgets of up to 100 function evaluations, the best-performing algorithms are still BO, AX, HyperOpt, PSO, and NgOpt16RL. On the contrary, Lamcts-Turbo consistently performs poorly on OpenAI Gym benchmarks, regardless of problem budget and dimension, in sharp contrast to the results shown in [START_REF] Wang | Learning search space partition for black-box optimization using monte carlo tree search[END_REF], where LA-MCTS was reported to perform well on some OpenAI Gym problems. We suspect that this discrepancy is caused by a poor initialization of the competitors in [START_REF] Wang | Learning search space partition for black-box optimization using monte carlo tree search[END_REF].

For an in-depth comparison, we also present aggregate plots based on average winning rates (e.g., Fig. 4), where we observe good results for the BO-based methods: BO is the most powerful solver for the lowest budget, while AX, NGOpt16RL and PSO turn out to be the best algorithms (within the confidence intervals) when aggregating results across all budgets (Fig. 4f). This means that vanilla BO is actually good for fast low-precision approximations on difficult problems, whereas AX, NGOpt16RL and PSO can be recommended when optimizing low-dimensional problems with low to medium budgets. Furthermore, Fig. 4 confirms, on the one hand, the good performance of NGOpt16RL, PSO, and HyperOpt for benchmarks with tiny neural networks, and, on the other hand, the poor search capabilities of Lamcts-Turbo, regardless of the available budget. For higher dimensions, Fig. 5 shows that BO-based solvers become less competitive, although they still perform among the best for the smallest budgets (25 and 50 evaluations). For larger budgets, we see that CMA and DE start becoming more competitive, which is in line with [START_REF] Meunier | Black-box optimization revisited: Improving algorithm selection wizards through massive benchmarking[END_REF]. However, Fig. 5f shows a supremacy of HyperOpt, which is designed for large-scale optimization for models with hundreds of parameters, and PSO, which performs surprisingly well considering that it is a classical heuristic originating from the BBO field and rarely used in ML applications. It can also be noted that Cobyla does not perform as well as for BBOB, while PSO performs constantly well for intermediate budgets from 50 to 400 total evaluations. Fig. 1 in the Supplementary Material extends the present

(a) (b) (c) (d) (e) (f) (g) (h)
Fig. 3. Multi-deterministic Open AI Gym with tiny neural net: a random seed is randomly drawn for each optimization run so that overfitting is more difficult. See Fig. 4 for an aggregated view. The legend lists all the compared algorithms with two numbers in parentheses: These are the performance values for the last and second-to-last budgets on the x-axis, respectively. The first number is also used to sort the algorithms by performance.

results to budgets 800, 1600, and 3200 for both tiny and big neural nets. Here, as the total budget increases, a smaller set of algorithms are compared: AX is affordable for runs on tiny neural nets up to a budget of 800 evaluations, and BO and Lamcts-Turbo become too expensive when exceeding a total budget of 1600 evaluations for big neural nets. The RL-specific algorithms, SpecialRL, and NGOpt16RL achieve the best performance for the largest budgets, followed by the various CMA and DE versions, leaving PSO and HyperOpt behind.

All in all, our results on OpenAI Gym show the competitiveness of BO-based methods for small dimensions and evaluation budgets (up to 100 evaluations), comparably to other solvers, while solvers from other families perform better as the budget increases. We note that this is different behavior from the BBOB benchmarks, where BO-based methods never rank first and show only average performance.

V. CONCLUSION

Our results provide insight into the comparison between different state-of-the-art BO methods, commonly used in ML, and more classical BBO heuristics. We compared the solvers on the BBOB benchmark suite from the COCO environment, which is well-known in the BBO community, and on OpenAI Gym problems, which are from the RL domain. On the BBOB comparison, we noted that Cobyla and the Nevergrad wizard perform best for any tested dimensionality from 2D to 40D with a total budget of 10D. They were consistently better than SMAC and Turbo, which was highlighted as a strong BO method in [START_REF] Turner | Bayesian optimization is superior to random search for machine learning hyperparameter tuning: Analysis of the black-box optimization challenge 2020[END_REF]. It is worth noting that Turbo and HyperOpt have the advantage of being computationally cheaper than other BO methods. Moreover, HyperOpt performed among the best on OpenAI Gym, with the exception of the largest considered budget for big neural nets. Good performance was also observed for PSO, which is commonly considered a classical heuristic and hardly ever used for ML tasks. For the larger budget of 100D, CMA or the Nevergrad wizard perform best regardless of the considered dimension of the problem.

In general, we found that the OpenAI Gym benchmark is very sensitive to variable scaling. While BBOB focuses on translations of optima and might therefore favor algorithms tuned for this setting, direct policy search for OpenAI Gym has an unbounded domain and depends differently on the initialization scaling and the ability of the algorithm to change scaling as needed. We optimized the scaling to Bayesian Optimization methods for obtaining results in Fig. 4, and then we ran the experiments to get the (possibly more neutral) results in Fig. 5 . Same results as reported in Fig. 3, but aggregated comparison as provided by Nevergrad [START_REF] Rapin | Nevergrad -A gradient-free optimization platform[END_REF]. Row A column B shows the frequency at which method A outperformed method B for the given budget. 9 distinct problems per budget. We include only problems for which the dimension is D < 50. Methods are ranked per average winning rate; best methods are listed first. Note that winning rates are all very close to each other: only PSO is significantly better. Fig. 5 presents similar experiments but with bigger neural nets. Fig. 1 in the Supplementary Material extends the present results to budgets 800, 1600, and 3200. equivalently to mathematical programming or evolutionary techniques. In future work, we plan to compare BO and other methods in discrete settings as well. Our results also indicate a high relevance of initializing the solvers with the right scaling.

Identifying suitable methods for a dynamic control policy is therefore another topic that we aim to investigate in future works. Of course, it remains interesting to periodically update our comparisons with new state-of-the-art solvers. Since all our experiments are performed with Nevergrad, such an ongoing benchmarking is largely facilitated: users can simply add their favorite method and compare their results to the ones reported above.

  ) average winning rates (i.e., the frequencies at which one method outperforms another): MountainCar-v0 (D = 12), Pendulum-v0 (D = 15), GuessingGame-v0 (D = 24), HotterColer-v0 (D = 24), CartPole-v0 (D = 28). CartPole-v1 (D = 28), NChain-v0 (D = 40), and MountainCarContinuous-v0 (D = 8).

Fig. 1 .

 1 Fig. 1. Illustration of the ECDF of runtimes on the BBOB functions f1-f24, using 51 targets uniformly spaced on a log scale between 1e -8 and 100. Plots are shown for dimension D equal to (a) 2, (b) 3, (c) 5, (d) 10, (e) 20, and (f) 40 and budget 10D. X-axis: budget/dimension in log-scale. Y-axis: frequency of solving at the requested precision. Overall, Cobyla and NGOpt16 (which heavily relies on Cobyla) perform best in these examples.

Fig. 2 .

 2 Fig. 2. As Fig. 1 but with a 100D budget and only for dimensions (a) 2, (b) 3, (c) 5, and (d) 10. Some methods, which are too slow, are removed from the analysis. Overall, CMA algorithms and NGOpt16 perform best here.

  without any change. Overall, tools based on heavy use of machine learning are computationally more expensive and perform roughly (a) Budget 25 (b) Budget 50 (c) Budget 100 (d) Budget 200 (e) Budget 400 (f) All budgets

Fig. 4

 4 Fig.4. Same results as reported in Fig.3, but aggregated comparison as provided by Nevergrad[START_REF] Rapin | Nevergrad -A gradient-free optimization platform[END_REF]. Row A column B shows the frequency at which method A outperformed method B for the given budget. 9 distinct problems per budget. We include only problems for which the dimension is D < 50. Methods are ranked per average winning rate; best methods are listed first. Note that winning rates are all very close to each other: only PSO is significantly better. Fig.5presents similar experiments but with bigger neural nets. Fig.1in the Supplementary Material extends the present results to budgets 800, 1600, and 3200.

Fig. 5 .

 5 Fig.5. Same as Fig.4, but with bigger nets (neural factor 3 in Nevergrad's benchmark scaling). 11 distinct problems per budget. We truncated at dimension ≤ 264. Dimension ranges from 24 to 264 instead of 8 to 40 in Fig.4. Due to the computational cost, it was not possible to finish the runs for SMAC. Fig.1in the Supplementary Material extends the present results to budgets 800, 1600, and 3200.

https://www.gymlibrary.dev/

ACKNOWLEDGMENTS

Our work is supported by ANR, project ANR-22-ERCS-0003-01, by the CNRS INS2I emergence project RandSearch, and by the PRIME programme of the German Academic Exchange Service (DAAD) with funds from the German Federal Ministry of Education and Research (BMBF).


Julien Bensmail

Closure Results for Arbitrarily Partitionable Graphs

Keywords: connected partition, arbitrarily partitionable graph, closure, traceability

A well-known result of Bondy and Chvátal establishes that a graph with order n is Hamiltonian if and only if its n-closure (obtained through repeatedly adding an edge joining any two non-adjacent vertices with degree sum at least n) also is. In this work, we investigate such closure results for arbitrarily partitionable graphs, a weakening of Hamiltonian graphs being those graphs that can be partitioned into arbitrarily many connected graphs with arbitrary orders. Among other results, we establish closure results for arbitrary partitions into connected graphs with order at most 3, for arbitrary partitions into connected graphs with order exactly any λ, and for the property of being arbitrarily partitionable in full.

Introduction

Let n ≥ 1 be a positive integer. An n-graph G is a graph with order n, while an npartition π = (λ 1 , . . . , λ p ) is a partition of n (i.e., λ 1 + ⋅ ⋅ ⋅ + λ p = n). A partition (S 1 , . . . , S p ) of the vertex set V (G) of G is called a realisation of π in G if each part S i is connected and has cardinality λ i , that is, if, for every i ∈ {1, . . . , p}, graph G[S i ] is a connected graph with order λ i . We now say G is arbitrarily partitionable (AP) if every n-partition is realisable in G, or, in other words, if G can be partitioned into arbitrarily many connected graphs with arbitrary orders. All these notions have been introduced and considered independently by Barth, Baudon, and Puech in [START_REF] Barth | Decomposable trees: a polynomial algorithm for tripodes[END_REF], and by Horňák and Woźniak in [START_REF] Horňák | On arbitrarily vertex decomposable trees[END_REF], in connection, in particular, with a practical network sharing problem. Since then, quite some interesting aspects of AP graphs have been introduced and investigated in literature, see e.g. the latest references [START_REF] Bensmail | A σ 3 condition for arbitrarily partitionable graphs[END_REF][START_REF] Bensmail | On three polynomial kernels of sequences for arbitrarily partitionable graphs[END_REF][START_REF] Bensmail | Toughness Properties of Arbitrarily Partitionable Graphs[END_REF][START_REF] Bensmail | More Aspects of Arbitrarily Partitionable Graphs[END_REF][START_REF] Broersma | Fully decomposable split graphs[END_REF][START_REF] Buchanan | Toughness of recursively partitionable graphs[END_REF][START_REF] Liu | Arbitrarily partitionable {2K 2 , C 4 }-free graphs[END_REF] on the topic for further information.

One of the main sources of motivation behind the investigations in the current work, is the fact that APness can be perceived both as a strengthening of perfect matchings (sets of ⌊n/2⌋ pairwise disjoint edges 1 ) and a weakening of Hamiltonian paths (paths going through all n vertices exactly once). Indeed, note that an AP n-graph, depending on the parity of n, admits realisations of (1, 2, . . . , 2) or (2, . . . , 2), which form perfect matchings; and that every path is obviously AP, from which we get that any traceable graph, i.e., any graph admitting a Hamiltonian path, is AP. From this, interesting questions on AP graphs arise when wondering how classical results on perfect matchings and Hamiltonian paths adapt to AP graphs. This line of research was initiated by Marczyk, who, in [START_REF] Marczyk | A note on arbitrarily vertex decomposable graphs[END_REF], proved: Theorem 1.1 (Marczyk [START_REF] Marczyk | A note on arbitrarily vertex decomposable graphs[END_REF]). Let G be a connected n-graph in which the degree sum of any two non-adjacent vertices is at least n -2. Then G is AP if and only if G admits perfect matchings.

Clearly, Theorem 1.1 stands as a weakening, to APness, of the well-known sufficient condition by Ore for graphs to admit Hamiltonian paths or cycles (stating that any connected n-graph in which the degree sum parameter is at least n or n-1 admits Hamiltonian cycles or paths, respectively [START_REF] Ore | Note on hamilton circuits[END_REF]). A remarkable fact also, is that the statement of Theorem 1.1 involves the two notions (perfect matchings and Hamiltonian paths) between which APness is comprised; although these two notions are rather distant in general, this shows there are stronger connections between the two in the context of AP graphs.

Marczyk's Theorem 1.1 opened the way to an interesting line of research on AP graphs, being to investigate how well-known sufficient conditions for Hamiltonicity or traceability weaken to APness. In the very line of Theorem 1.1, better results involving the degree sum of pairs of non-adjacent vertices were established in [START_REF] Horňák | Dense arbitrarily vertex decomposable graphs[END_REF][START_REF] Marczyk | An Ore-type condition for arbitrarily vertex decomposable graphs[END_REF], and such results for triples of pairwise non-adjacent vertices were considered in [START_REF] Bensmail | A σ 3 condition for arbitrarily partitionable graphs[END_REF]. In [START_REF] Kalinowski | Dense arbitrarily partitionable graphs[END_REF], sufficient conditions in terms of number of edges have also been established, while toughness properties of AP graphs have been studied in [START_REF] Bensmail | Toughness Properties of Arbitrarily Partitionable Graphs[END_REF]. Last, in [START_REF] Bensmail | More Aspects of Arbitrarily Partitionable Graphs[END_REF], the authors considered several other classical concepts and results for Hamiltonicity and traceability, such as forbidden induced patterns and the square operation, and proved that some adapt to APness while some others do not.

In the current work, we pursue this line of research by considering yet another classical aspect borrowed from the study of Hamiltonian and traceable graphs, being that of graph closures. Recall that, for a graph G and some x ≥ 1, the x-closure clos(G, x) of G is obtained upon repeatedly adding an edge uv between two non-adjacent vertices u and v satisfying d(u) + d(v) ≥ x. Equivalently, note that the x-closure clos(G, x) of G is obtained through an x-closing sequence G 0 , . . . , G m , being a sequence of n-graphs where G 0 = G and G m = clos(G, x), and, for every i ∈ {1, . . . , m}, graph G i is obtained from G i-1 by adding a single edge uv such that

d G i-1 (u) + d G i-1 (v) ≥ x.
Graph closures emerged in a seminal work [START_REF] Bondy | A method in graph theory[END_REF] of Bondy and Chvátal, in which they provided the celebrated Bondy-Chvátal sufficient condition for Hamiltonicity and traceability: Theorem 1.2 (Bondy, Chvátal [START_REF] Bondy | A method in graph theory[END_REF]). An n-graph is Hamiltonian if and only if its n-closure is Hamiltonian. Likewise, an n-graph is traceable if and only if its (n-1)-closure is traceable Among other remarkable aspects of interest, Bondy and Chvátal's Theorem 1.2 is important in that it implies several other classical sufficient conditions for Hamiltonicity and traceability, such as Dirac's conditions [START_REF] Dirac | Some theorems on abstract graphs[END_REF] and Ore's conditions [START_REF] Ore | Note on hamilton circuits[END_REF]. It is also worth mentioning that the concept of graph closure does not restrict to Hamiltonian cycles and paths only, and can also be employed to express sufficient conditions for graphs to admit other types of objects. For more details on this point, and more generally on anything related to graph closures, we refer the interested reader to the survey [START_REF] Broersma | Closure Concepts: A Survey[END_REF].

Our main intent in the current work is to initiate the study of graph closures in the very context of AP graphs. In particular, as explained earlier when introducing Marczyk's Theorem 1.1, given any sufficient condition for Hamiltonicity and traceability, it is natural to wonder whether it weakens to APness. Bondy and Chvátal's Theorem 1.2 being one of the most influential results on graph closures, it is thus legitimate to wonder how it adapts (or not) to APness. As a first step, we consider (n -2)-closures in Section 2, showing that, for APness, we cannot just weaken Theorem 1.2 to (n -2)-closures. Our arguments lead us to considering arbitrary partitions into connected graphs with order at most 3 in Section 3, for which we prove the tight result that it is necessary and sufficient to consider (n-1)-closures. Then, in Section 4, we consider weaker closures, and establish more general results for partitions into connected graphs with order any fixed λ, and for the AP property in full. We finish off in Section 5 with discussions for further work on the topic.

On the APness of (n -2)-closures

Given how sufficient conditions on degree sums of pairs of non-adjacent vertices essentially weaken from n for Hamiltonicity to n -1 for traceability (Ore's Theorem) and to n -2 for APness (Marczyk's Theorem 1.1), a first, legitimate question is whether Bondy and Chvátal's Theorem 1.2 weakens the same way to APness, or, in other words, whether n-graphs are AP if and only if their (n -2)-closure is. Likewise, just like how Bondy and Chvátal's Theorem 1.2 implies Ore's Theorem, one can also wonder whether there is some result on APness and (n -2)-closures that would imply Marczyk's Theorem 1.1.

Previous studies on AP graphs have highlighted that, when realising an n-partition π in an n-graph, an important parameter to take into account is the spectrum sp(π) of π, which is the set of all values appearing in π (thus, sp(π) is essentially π with all duplicates removed). Perhaps one of the most significant results on partition spectra is one by Ravaux stating that, in graphs with large diameter, the AP property relies solely on the realisability of partitions with small spectrum [START_REF] Ravaux | Decomposing trees with large diameter[END_REF]. More generally speaking, as described in [START_REF] Bensmail | Toughness Properties of Arbitrarily Partitionable Graphs[END_REF], something we learn from previous works on AP graphs is that, 1) the smaller the spectrum of a partition π is, and 2) the smaller the values of π are, the less chances there are that π is realisable in a given graph. In other words, to establish that some graphs with particular properties are not necessarily AP, very generally speaking one should consider the realisability of partitions with small values and low variety of values.

From these thoughts, regarding the hopes we have exposed for (n -2)-closures earlier, we get to the matter of establishing whether, in general, n-partitions with small spectrum are realisable if and only if they are in the (n -2)-closure. As a starting point, it thus makes sense to wonder about perfect matchings2 , or, in other words, about realisations of partitions with spectrum {2}. Below, we prove that, indeed, already for this particular type of partitions we cannot weaken Bondy and Chvátal's Theorem 1.2 to value n -2 as is. For transparency, let us mention that upcoming Theorem 2.3 is actually a particular case of a previous result of Plummer and Saito [START_REF] Plummer | Closure and factor-critical graphs[END_REF]; still, we provide a straight, thorough proof, as our arguments stand as a good introduction to the ones to be used later on.

To begin with, let us remind Tutte's condition for the existence of perfect matchings.

Theorem 2.1 (Tutte [START_REF] Tutte | The factorization of locally finite graphs[END_REF]). A graph G with even order has a perfect matching if and only if for every S ⊆ V (G) the graph G-S has at most |S| connected components with odd order.

We now proceed with our first result, Theorem 2.3. Before that, we just need to introduce an auxiliary result that will show Theorem 2.3 is indeed the best we can hope for. Recall that for any two positive integers p, q ≥ 1, we denote by K p,q the complete bipartite graph with partition classes of cardinality p and q. Lemma 2.2. For any p ≥ 1, clos(K p,p+2 , n -2) has perfect matchings while K p,p+2 has not.

Proof. Set G = K p,p+2 for some p ≥ 1, and denote by U the partition class of G with cardinality p, and by V that with cardinality p + 2. Note that all vertices of U have degree

|V | = p + 2, while all vertices of V have degree |U | = p. Set n = |V (G)| = 2p + 2.
First off, note that G -U consists of p + 2 connected components, all of which have odd order, 1. Meanwhile, |U | = p. Thus, by Tutte's Theorem, G admits no perfect matchings. Now consider G ′ = clos(G, n -2). Note that, in G, any two non-adjacent vertices u and v either both belong to U , or both belong to

V . Also, if u, v ∈ U , then d G (u) + d G (v) = 2(p+2) = 2p+4 = n+2; while, if u, v ∈ V , then d G (u)+d G (v) = 2p = n-2.
Thus, for any two non-adjacent vertices u and v of G, we have d G (u) + d G (v) ≥ n -2, which implies that u and v are adjacent in G ′ . Thus G ′ is complete, and hence it admits perfect matchings.

Theorem 2.3. Every graph G with even order n ≥ 2 admits perfect matchings if and only if clos(G, n -1) does. Besides, value n -1 in the previous statement is best possible.

Proof. Set G ′ = clos(G, n -1). Clearly, if G admits perfect matchings, then so does G ′ . Thus, it remains to prove that if G ′ admits perfect matchings, then so does G. Consider an (n -1)-closing sequence G 0 , . . . , G m where G 0 = G and G m = G ′ . It suffices to prove that, for any i ∈ {1, . . . , m}, from any perfect matching of G i we can deduce one of G i-1 . Set thus H = G i-1 and H ′ = G i , and let M be a perfect matching of H ′ .

If M is a perfect matching of H, then we are done. Otherwise, it means M contains uv, the unique edge of

H ′ not in H. Then, by definition, d H (u) + d H (v) ≥ n -1. Now, for every neighbour w ≠ v of u in H, note that if ww ′ ∈ M for some w ′ /
∈ {u, v, w}, and we have

vw ′ ∈ E(H), then M ∖ {uv, ww ′ } ∪ {uw, vw ′ } is a perfect matching of H. If there is no such configuration in H, then it means that, for every edge uw ∈ E(H) such that ww ′ ∈ M , we cannot have vw ′ ∈ E(H). From this, we deduce that d H (v) ≤ n -2 -d H (u), and thus that d H (u) + d H (v) ≤ n -2,
contradicting that uv is an edge of H ′ . Thus we can always derive a perfect matching of H from M , and we are done.

The last part of the statement follows e.g. from Lemma 2.2.

Due to Theorem 2.3, it is not true that any n-graph is AP if and only if its (n -2)closure is AP, which would have stood as a smooth and natural weakening of Bondy and Chvátal's Theorem 1.2 to APness. The fact that perfect matchings are an obstruction to such a result is actually not that surprising either, as, recall, Marczyk's Theorem 1.1, to weaken Ore's Theorem from n -1 to n -2, already had to exclude such partitions from the equation. In the present case, however, things are a bit different, as we can actually adapt Theorem 2.3 to partitions with spectrum {3}, see upcoming Theorem 2.5.

As earlier, we start off by introducing some construction that will show the next result is best possible. In the present case, the construction actually holds for any size value λ ≥ 2, although upcoming Theorem 2.5 deals only with the particular case where λ = 3. For any three positive integers p, q, r ≥ 1, we denote by T (p, q, r) the graph obtained from the disjoint union of three cliques K p , K q , and K r on p, q, and r vertices, respectively, by adding a universal vertex v. Note that v is a cut-vertex of T (p, q, r), whose removal results in exactly three connected components, being K p , K q , and K r .

Theorem 2.4. For every λ ≥ 2 and p ≥ 1 with p ≡ 0 mod λ -1, clos(T (1, p, p), n -2) has realisations of (λ, . . . , λ) with T (1, p, p) has not.

Proof. For any λ ≥ 2 and p ≥ 1

with p ≡ 0 mod λ -1, set G = T (1, p, p) and n = |V (G)| = 2p + 2.
Since G has a cut-vertex v whose removal results in three connected components, K, K ′ , and K ′′ , having order 1, p, and p, respectively, and p ≡ 0 mod λ -1, it should be clear that, in any realisation R of (λ, . . . , λ) in G, there must be one part containing v and λ -1 vertices of K ′ , and similarly one part containing v and λ -1 vertices of K ′′ , which is impossible. Thus R cannot exist, and G does not admit any realisation of (λ, . . . , λ).

Let us now consider G ′ = clos(G, n -2). Note that, in G, all vertices of K ′ and K ′′ have degree p = n-2 2 , vertex v has degree n -1, and the unique vertex of K has degree 1. Thus, in G ′ , any two vertices of K ′ and K ′′ are adjacent. This implies G ′ is traceable, from which we get that G ′ is AP, and thus admits realisations of (λ, . . . , λ), as claimed.

Theorem 2.5. Every graph G with order n ≡ 0 mod 3 at least 3 admits realisations of (3, . . . , 3) if and only if clos(G, n -1) does. Besides, value n -1 in the previous statement is best possible.

Proof. Set G ′ = clos(G, n -1). As in the proof of Theorem 2.3, we focus on an (n -1)closing sequence G 0 , . . . , G m where G 0 = G and G m = G ′ , our goal being to prove that, for any i ∈ {1, . . . , m}, any realisation R of (3, . . . , 3) in some H ′ = G i can be turned into one of H = G i-1 . Assume thus R does not hold as is in H; thus, there is a part S = {u, v, w} of R that contains the unique edge vw of H ′ not in H, thereby making H[S] not connected. Then we can assume H[S] contains uv, while w is isolated in H[S].

Let n 3 , n 2 , and n 1 be the number of parts of R different from S in which, in H, vertex v has exactly three, two, or one neighbour, respectively. Then d H (v) = 1 + 3n 3 + 2n 2 + n 1 . We now analyse the number of possible edges incident to w going to some part S ′ = {x, y, z} of R different from S in which v also has neighbours (all these adjacencies being in H).

• If v is adjacent to all of x, y, and z, then we claim a realisation of (3, . . . , 3) in H can be deduced if w, in H, is also adjacent to any vertex of S ′ . Indeed, assume, w.l.o.g., that wx is an edge of H. Since H[S ′ ] is connected, H ′ (and thus H) necessarily contains one of xy or xz. In the former case, replacing S and S ′ in R with {u, v, z} and {w, x, y} results in a realisation of (3, . . . , 3) in H. In the latter case, we can instead replace parts S and S ′ with {u, v, y} and {w, x, z}.

• If v is adjacent only to, say, x and y in S ′ , then we claim a realisation of (3, . . . , 3) in H can be deduced if w, in H, is also adjacent to any two vertices in S ′ . First off, note that, for similar arguments as in the previous case, we would be done if these at least two neighbours of w in S ′ include z. So suppose w is only adjacent to x and y. Since H ′ [S ′ ] is connected, we have that xz or yz lies in H ′ (and thus in H). In the former case, replace, in R, parts S and S ′ with {u, v, y} and {w, x, z} to get a realisation in H. In the latter case, replace S and S ′ with {u, v, x} and {w, y, z}.

• If v is adjacent only to, say, x in S ′ , then, for similar reasons as earlier, we claim a realisation of (3, . . . , 3) in H can be obtained from R if w is adjacent, in H, to all three vertices of S ′ . This is because, in that case, replacing, in R, parts S and S ′ with {u, v, x} and {w, y, z} yields a desired realisation. Now, if none of the situations above occurs, then we deduce that

d H (w) ≤ n -3 -3n 3 -2n 2 -n 1 = n -2 -(1 + 3n 3 + 2n 2 + n 1 ) = n -2 -d H (v),
and hence d H (w) ≤ n -2 -d H (v), and d H (v) + d H (w) ≤ n -2, a contradiction.
To conclude the proof, remark that e.g. Theorem 2.5 shows the second part of the statement also holds true.

Although the first part of the statement of Theorem 2.5 holds only for partitions containing value λ = 3 only, Theorem 2.4 implies that if the first part of Theorem 2.5 also held for any λ ≥ 4, then value n -1 would be best possible. Anyhow, Theorem 2.5 shows that Bondy and Chvátal's Theorem 1.2 does not weaken to APness by just considering threshold n -2, and this is not due to perfect matchings only, as Theorem 2.3 could indicate.

Connected partitions into parts of size at most 3

In previous Theorems 2.3 and 2.5, we were only concerned with connected partitions into parts all having the same size, λ, for very small values of λ, namely 2 and 3. To get a flavour of what it would take, with the same approach, to generalise our arguments to any partition, in the next result we consider a generalisation of Theorems 2.3 and 2.5 to partitions with spectrum included in {1, 2, 3}, or, in other words, to connected partitions into parts of size at most 3. As will be recalled right after the proof, such a result is not interesting only for generalisation purposes, but also because such partitions, in previous works on APness, have been proved to be of prime interest for certain graph classes.

Theorem 3.1. For every n ≥ 2 and every n-partition π with spectrum included in {1, 2, 3}, every graph G with order n admits realisations of π if and only if clos(G, n -1) does. Besides, value n -1 in the previous statement is best possible.

Proof. The proof goes similarly as the proofs of Theorems 2.3 and 2.5. Since one of the two directions is obvious, we focus on proving the less straight direction. Set G ′ = clos(G, n-1), and let π be an n-partition with spectrum included in {1, 2, 3}. We consider an (n -1)closing sequence G 0 , . . . , G m where G 0 = G and G m = G ′ . Again, it suffices to prove that, for any i ∈ {1, . . . , m}, any realisation of π in G i yields one of G i-1 . So, we consider H = G i-1 and H ′ = G i , and let R be a realisation of π in H ′ . If R does not hold directly in H, then it is because of a part S containing the unique edge of H ′ that does not belong to

H (that is, H[S] is not connected while H ′ [S] is). Then, |S| ∈ {2, 3}.
To begin with, we assume S has cardinality 2, and set S = {u, v}. Then, uv ∈ E(H ′ ) and uv / ∈ E(H). As in the proofs of Theorems 2.3 and 2.5, we analyse the possible neighbours of v in H w.r.t. those of u.

• If u has, in H, a neighbour in a part S ′ of cardinality 2 of R different from S, and v is adjacent to the other vertex of S ′ , then, through the exact same arguments as in the proof of Theorem 2.3, we can deduce, from R, a realisation of π in H.

• If u is adjacent, in H, to a vertex w such that S ′ = {w} is a part of R, then note that, from R, replacing S and S ′ with {u, w} and {v} results in a realisation in H.

• Assume last that u has, in H, neighbours in a part S ′ = {w, x, y} of cardinality 3.

-If u is adjacent to all of w, x, and y, and v is also adjacent to some vertex of S ′ , then a realisation of π in H can be obtained from R as follows. Assuming, w.l.o.g., that v is adjacent to w, then just replace parts S and S ′ with {u, x, y} and {v, w}. This indeed results in a desired realisation.

-If u is adjacent, in H, to exactly two vertices in S ′ , say w and x w.l.o.g., then we claim a realisation of π in H can be deduced from R in case v is also adjacent to two vertices of S ′ in H. We distinguish two cases. * Assume first that v is adjacent to y. In that case, it suffices to replace parts S and S ′ of R with {u, w, x} and {v, y}. * Assume second that v is adjacent to w and x (and not to y). Since H ′ [S ′ ] (and thus H[S ′ ]) is connected, then one of w and x is adjacent to y in H ′ (and H). Assuming w.l.o.g. that xy is an edge of H, we can here replace parts S and S ′ of R with {u, w} and {v, x, y} to be done.

-If u is adjacent, in H, to only one vertex of S ′ , say w w.l.o.g., and v is adjacent, in H, to all of w, x, and y, then we can obtain a desired realisation by replacing parts S and S ′ of R with {u, w} and {v, x, y}. Now denote by m 1 and m 2 the number of parts of size 2 of R in which u has (in H) exactly one or two neighbours, respectively, and by n 1 , n 2 , and n 3 the number of parts of size 3 in which u has (in H) exactly one, two, or three neighbours. Then

d H (u) = m 1 + 2m 2 + n 1 + 2n 2 + 3n 3 .
Also, since none of the cases above apply, we have

d H (v) ≤ n -2 -m 1 -2m 2 -n 1 -2n 2 -3n 3 = n -2 -d H (u),
and thus d H (u) + d H (v) ≤ n -2, a contradiction.
Now suppose S = {u, v, w}, where H[S] contains the edge uv while w is isolated (because H ′ contains the edge vw while H does not contain it). For the same reasons as in the proof of Theorem 2.5, we can assume that, in R, there is no S ′ ≠ S of size 3 in which:

• v has three neighbours and w has one neighbour;

• v has two neighbours and w has two neighbours;

• v has one neighbour and w has three neighbours.

We now lead a similar analysis regarding the possible neighbours of v in H in parts S ′ ≠ S of R of cardinality 1 or 2.

• Assume first that v has, in H, a neighbour x in a part S ′ = {x} of size 1. Then a realisation of π in H is obtained upon replacing S and S ′ with {u, v, x} and {w}.

• Assume second that v has, in H, neighbours in a part S ′ = {x, y} of cardinality 2.

Recall that xy is an edge of both H ′ and H.

-Assume first v is adjacent to both x and y in H. If w is adjacent to any of x and y in H, then a realisation of π in H is obtained from R upon replacing parts S and S ′ with either {u, v, x} and {w, y}, or {u, v, y} and {w, x}.

-Assume second v is adjacent only to x in G. If w is adjacent to x and y, then a realisation is obtained when replacing parts S and S ′ with {u, v, x} and {w, y}.

Now set m 1 and m 2 the number of parts of cardinality 2 of R in which v has (in H) exactly one or two neighbours, respectively, and n 1 , n 2 , and n 3 the number of parts of cardinality 3 in which v has (in H) exactly one, two, or three neighbours. Then

d H (v) = 1 + m 1 + 2m 2 + n 1 + 2n 2 + 3n 3 .
Meanwhile, by the arguments above, we have

d H (w) ≤ n -3 -m 1 -2m 2 -n 1 -2n 2 -3n 3 = n -2 -d H (v), from which we deduce d H (v) + d H (w) ≤ n -2, a final contradiction.
The very last part of the statement follows e.g. from Lemma 2.2 and Theorem 2.4.

Theorem 3.1 makes more particular sense in the context of graph classes for which the AP property is known to rely only on the realisability of partitions with spectrum included in {1, 2, 3}. Such matters relate to questions raised first by Barth and Fournier in [START_REF] Barth | A degree bound on decomposable trees[END_REF] on the complexity of determining whether a graph is AP. Note that it is not clear whether this problem lies in NP or co-NP, since the APness of an n-graph relies on the realisability of an exponential number of n-partitions, while the non-APness of an n-graph implies an exponential number of partitions of the vertex set do not stand as realisations of particular n-partitions. Still, following the terminology from [START_REF] Bensmail | On three polynomial kernels of sequences for arbitrarily partitionable graphs[END_REF], it is believed that, perhaps, every n-graph G admits a polynomial kernel of partitions, i.e., a set K of a polynomial number (function of n) of n-partitions such that G is AP if and only if all partitions of K are realisable in G. If this was true, then this would imply deciding APness lies in NP.

Polynomial kernels of partitions have been proved to exist for a few graph classes, such as subdivided stars [START_REF] Barth | Decomposable trees: a polynomial algorithm for tripodes[END_REF][START_REF] Barth | A degree bound on decomposable trees[END_REF], graphs with large diameter [START_REF] Ravaux | Decomposing trees with large diameter[END_REF], superclasses of split graphs [START_REF] Bensmail | More Aspects of Arbitrarily Partitionable Graphs[END_REF][START_REF] Broersma | Fully decomposable split graphs[END_REF][START_REF] Liu | Arbitrarily partitionable {2K 2 , C 4 }-free graphs[END_REF], and others [START_REF] Bensmail | On three polynomial kernels of sequences for arbitrarily partitionable graphs[END_REF][START_REF] Bensmail | More Aspects of Arbitrarily Partitionable Graphs[END_REF]. In particular, the polynomial kernel from [START_REF] Broersma | Fully decomposable split graphs[END_REF] for split graphs contains partitions with spectrum included in {1, 2, 3} only, which kernel also holds for superclasses of split graphs [START_REF] Liu | Arbitrarily partitionable {2K 2 , C 4 }-free graphs[END_REF], in particular for {2K 2 , C 4 }-free graphs. Thus, a direct, general consequence of Theorem 3.1 and of these thoughts, is the following:

Corollary 3.2.
If G is a class of graphs with order n ≥ 2 admitting n-partitions with spectrum included in {1, 2, 3} as a polynomial kernel, then every G ∈ G is AP if and only if clos(G, n -1) is.

Note that Corollary 3.2 would extend the same way to any n-graph class for which n-partitions with spectrum included in {1, 2, 3} stand as a polynomial kernel. Recall also that building graph closures can be done in polynomial time (see e.g. [START_REF] Broersma | Closure Concepts: A Survey[END_REF]).

More general results for weaker closures

In this section, we investigate how the proof arguments from the proofs of previous Theorems 2.3, 2.5, and 3.1 could be generalised to other partitions with spectrum of size 1 (Subsection 4.1) and even to APness (Subsection 4.2), provided we consider weaker closures.

Connected partitions into parts of size λ

Before proceeding with our main result here, let us establish the following useful lemma. Proof. Since u and v are not adjacent, we have N (u) ∪ N (v) ⊆ V (G) ∖ {u, v}, which set has cardinality n -2. Now, if u and v had at most c + 1 common neighbours only, then we would have

d(u) + d(v) ≤ 2(c + 1) + (n -2) -(c + 1) = n + c -1, a contradiction.
The last part is because having d(u) + d(v) ≥ 2n -3 would imply u and v have at least n -1 common neighbours, which is impossible in loopless graphs.

We now essentially adapt the first part of the statement of Theorem 2.5 to partitions with spectrum {λ} for any λ ≥ 4. Recall that Theorem 2.4 is precisely about such partitions, and thus indicates that, even in this context, we must at least consider (n -1)-closures.

= G i-1 . If R does not hold as is in H, then it is because a part S of R is not connected in H (while it is in H ′ ). That is, H ′ [S] contains the only edge uv that is present in H ′ but not in H.
Since H[S] is not connected, and H[S] = H ′ [S] -uv, vertices u and v cannot have any common neighbour in S. We claim there is necessarily a part S ′ ≠ S of R in which u and v have at least λ -1 common neighbours. Indeed, note first that the value of λ ensures that n ≥ 2λ, as, for n = λ, we have α = λ -1, while H in the present case is not connected and thus d H (u) + d H (v) ≤ n -2 = λ -2, a contradiction. Thus, |R| ≥ 2, and if u and v had at most λ -2 common neighbours in all of the n λ -1 ≥ 1 parts of R different from S, then u and v would have at most

( n λ -1) (λ -2) = n -( 2n λ + λ -2)
common neighbours, while, by Lemma 4.1, vertices u and v have at least n -( 2n λ + λ -3) common neighbours in H, a contradiction.

Thus, let S ′ ≠ S be any part of R in which u and v have at least λ-1 common neighbours. Let also S u and S v be the vertex sets of the exactly two connected components of H[S], where S u contains u while S v contains v. In case u and v have exactly λ -1 common neighbours in S ′ , then let also w be the unique vertex of S ′ not adjacent to both u and v; otherwise, if u and v are both adjacent to all vertices of S ′ , then let w be any vertex of S ′ . In both cases, let w ′ be any neighbour of w in

H[S ′ ]. Since λ ≥ 4, we must have λ -|S u | ≥ 2 or λ -|S v | ≥ 2.
Assume w.l.o.g. the former inequality holds. Now replace S and S ′ in R with both

S u ∪ {w, w ′ } ∪ X and S v ∪ Y , where X is any set of λ -(|S u | + 2) ≥ 0 vertices of S ′ ∖ {w, w ′ }, and Y = S ′ ∖ {w, w ′ } ∖ X.
Since ww ′ is an edge of H, and u and v are adjacent to all vertices in S ′ ∖ {w}, it can be observed that this results in a realisation of (λ, . . . , λ) in H.

Note that 2n -( 2n

λ + λ -1) is a non-decreasing function of λ, so the most interesting case, yielding the stronger closure, is for λ = 4, for which case Theorem 4.2 deals with ( 3 2 n -3)-closures. Recall that, regardless of the actual value of λ, in any case we cannot hope to establish results involving closures stronger than (n -1)-closures.

APness

We here consider the AP property in full, that is, we wonder about generalisations of Bondy and Chvátal's Theorem 1.2 to AP graphs. By the last part of Lemma 4.1, recall that we must consider degree sum thresholds at most 2n-4. In what follows, we prove that an n-graph G is indeed AP if and only if its (2n -4)-closure is. This result being surely far from optimal, we then improve it down to (2n -5)-closures and even to (2n -6)-closures, for the sake mainly of showcasing why it might be tedious to go even lower. Proof. Set G ′ = clos(G, 2n -4). Again, it suffices to prove that if the (2n -4)-closure clos(G, 2n-4) is AP, then G is also AP. Actually, we can consider a (2n-4)-closing sequence G 0 , . . . , G m where G 0 = G and G m = G ′ , and prove that, for H ′ = G i and H = G i-1 for some i ∈ {1, . . . , m}, any realisation R of any n-partition π in H ′ yields one of H. If R holds as is in H, then we are done. Otherwise, some part S of R contains the only edge uv of H ′ not in H, and we have that H[S] is not connected.

Let us denote by S u and S v the subsets of vertices of S such that S u contains the vertices of H[S] belonging to the same connected component as u, and S v contains those belonging to the same connected component as v. Then, S = S u ∪ S v , and we have u ∈ S u and v ∈ S v . By Lemma 4.1, vertices u and v have at least n -2 common neighbours in H, and, actually, since u and v are not adjacent in H, we have N H (u) = N H (v) = V (H)∖{u, v}. In particular, since H[S] is not connected, it must be that |S u | = |S v | = 1, as otherwise u and v would have, in H, a common neighbour in either S u or S v , making H[S] connected. Thus, |S| = 2, and since n -2 ≥ 1 we have |π| ≥ 2. Now, consider S ′ ≠ S another part of R. Then, as mentioned above, in H, vertices u and v are adjacent to all vertices of S ′ . It then suffices, to obtain a realisation of π in H, to start from R, and, denoting by w any vertex of S ′ , to replace parts S and S ′ with, say, {u, w} and {v} ∪ S ′ ∖ {w}. Proof. The proof goes similarly as that of Theorem 4.3 (from a (2n -5)-closing sequence). This time, in H vertices u and v have at least n -3 common neighbours. Since H[S] is not connected, vertices u and v have no common neighbours in S, which implies 2 ≤ |S| ≤ 3.

If |S| = 3, then we can assume, w.l.o.g., that S u = {u} and S v = {v, w}. Thus vw is an edge of H, and u and v admit all vertices of V (H) ∖ {u, v, w} as common neighbours. Then, again, we can just consider any part S ′ ≠ S of R (such exists since 2n -5 ≥ 3), and, denoting by x any vertex of S ′ , a realisation of π in H is obtained when starting from R, and replacing parts S and S ′ with {v, w, x} and {u} ∪ S ′ ∖ {x}, respectively. Now assume |S| = 2, i.e., S contains u and v only. This concludes the proof. • If there is a part S ′ ≠ S with |S ′ | = 3, then, setting S ′ = {w, x, y}, it here suffices to replace S and S ′ with, say, S u ∪ {w, x} and S v ∪ {y}.

If N H (u) = N H (v) = V (H) ∖ {u,
• If there is a part S ′ ≠ S with |S ′ | = 2, then, setting S ′ = {w, x}, it here suffices to replace S and S ′ with, say, S u and S v ∪ {w, x}.

• If there is a part S ′ ≠ S with |S ′ | = 1, then, setting S ′ = {w}, it here suffices to replace S and S ′ with, say, S u ∖ {u} and S v ∪ {w, u}.

Thus, when |S| = 4, a realisation of π in H can be deduced in all cases.

If |S| = 3, then set S = {u, v, w}, where S u = {u} and S v = {v, w} (thus vw is an edge of H). If u and v are, in H, both adjacent to all vertices of V (H) ∖ S (there are such, since 2n -6 ≥ 4), then a realisation of π in H can be obtained similarly as in the proof of Theorem 4.4. Thus, we can assume there is some x ∈ V (H) ∖ S such that all vertices of V (H) ∖ S ∖ {x} are common neighbours of u and v. Actually, again, if there is some part S ′ ≠ S of R not containing x, then a realisation can be obtained. So we get to assuming that |π| = 2, and that, besides S, the only part S ′ of R contains x.

• If |S ′ | = 1, then n = 4, a case not covered by the statement.

• If |S ′ | ≥ 2, then S ′ contains a vertex y adjacent to x being a common neighbour of u and v. Furthermore, u and v are both adjacent to all vertices of S ′ ∖ {x}. Then the two parts {u, x, y} and {v, w} ∪ S ′ ∖ {x, y} form a realisation of π in H.

It now remains to consider when |S| = 2, that is, when S = {u, v}. In this case, there are at most two vertices of V (H)∖{u, v} that are not common neighbours of u and v in H. We can actually suppose that there exist exactly two such vertices w and x of V (H) ∖ {u, v} that are not common neighbours, as, if there is none or only one such vertex, then we can proceed similarly as in the proof of Theorem 4.4. Likewise, if there is a part S ′ ≠ S of R that contains only common neighbours of u and v in H, then a realisation can also be deduced. So, besides S, we can last assume either there is only one part S ′ (that is, |π| = 2, and S ′ contains both w and x), or there are exactly two parts S w and S x (that is, |π| = 3, and S w contains w while S x contains x).

• Assume first |π| = 2. Thus, R contains a unique part S ′ ≠ S, that contains both w and x. If there is a spanning tree of H[S ′ ] that contains a leaf y different from w and x, then recall that that leaf is adjacent to both u and v in H, and the two parts {u, y} and {v} ∪ S ′ ∖ {y} then form a realisation of π in H (unless S ′ = {w, x, y}, in which case necessarily wx is an edge, and we could instead consider the two parts {u, v, y} and {w, x}). So we can now assume that any vertex of S ′ ∖ {w, x} is a cut-vertex of any spanning tree of H[S ′ ], which implies any spanning tree T of H[S ′ ] must be a path with end-vertices w and x. In that case, a realisation of π in H is obtained upon considering parts {w, w ′ } and {u, v} ∪ S ′ ∖ {w, w ′ }, where w ′ is the unique neighbour of w in T . Note indeed that if this was not the case, then we would have w ′ = x, thus |S ′ | = 2 and n = 4, which peculiar case is not covered by the statement. We are thus done in all cases.

Conclusions

In this work, inspired by Bondy and Chvátal's influential Theorem 1.2, we have investigated closure results for connected partitions of graphs, in particular in the context of the AP property which has been regarded as a weakening of Hamiltonicity. Looking at Theorem 1.2, a natural first question (in view of Marczyk's Theorem 1.1) was whether (n -2)-closures are necessary and sufficient for the AP property. In Section 2, we proved that this is not true, because of several particular types of n-partitions. For such partitions, we proved, in particular throughout Section 3, that it is sufficient and necessary to consider (n -1)-closures. In last Section 4, we then considered other n-partitions, including the whole set of n-partitions (and thus the AP property), and proved that it is here sufficient to consider weaker closures (namely (2n -c)-closures for some c).

Let us mention that the fact that (n-2)-closures do not suffice for APness (Theorems 2.3 and 2.5) is not too surprising, given that Marczyk's Theorem 1.1 already had to exclude perfect matchings from the equation. Given all connections between the results involved, the fact that perfect matchings form an obstruction to APness and (n -2)-closures can thus be regarded as a counterpart. What is more surprising is that perfect matchings, in our case, are not the only obstruction, recall Theorem 2.5.

Given the results we came up with, we thus have no obvious objection again the fact that, perhaps, in general (n -1)-closures are necessary and sufficient. Question 5.1. Is is true that any graph is AP if and only if its (n -1)-closure is?

If true, a notable consequence of Question 5.1 is that it would imply Marczyk's Theorem 1.1, just like how Bondy and Chvátal's Theorem 1.2 implies Ore's Theorem. A way to progress towards Question 5.1 could be to first generalise Theorems 4.3 to 4.5 to (2n -c)closures for any fixed c ≥ 4. However, as highlighted by the proofs of Theorems 4.3 to 4.5, proceeding this way is not quite obvious. In particular, in our arguments, it is important that we keep control over the structure of H[S], which is less and less obvious as c increases, but easy to do when c is very small (as in the cases we considered). Also, the fact that uv is an edge of H ′ but not of H is a very local property, which becomes less and less easy to exploit as the diameter of H[S] increases (which might be the case when c is large). Altogether, an annoying point is that |S| being large implies u and v have lots of common neighbours in V (H) ∖ S but the structure of H[S] might get hard to handle, while |S| being small implies the structure of H[S] is easier to deal with but u and v have less common neighbours in V (H) ∖ S, which is a crucial point.

To summarise, while some of our arguments in the proofs of Theorems 4.3 to 4.5 could obviously be generalised to larger values of c, some others do not; thus, to go further, it would be crucial to come up with other arguments. For instance, it might be useful to exploit that if, for some c, the closure clos(G, 2n -c) is AP but H[S] has a very faulty structure, then we could deduce other n-partitions showing that clos(G, 2n -c) is not AP.

One has to take into account also that if c is too large w.r.t. n, then we might fall into pathological cases, as better highlighted by Theorem 4.5. Note indeed that if we consider as G the disjoint union of two edges, then n = 4 and 2n -6 = 2, while, for any two non-adjacent vertices u and v of G we have d G (u) + d G (v) = 2. Thus in that case clos(G, 2n-6) is complete and thus AP, while G is obviously not AP (consider partitioning it following (1, 3)). So the statement of Theorem 4.5 is actually best possible (w.r.t. n), and, as considering larger values of c, we must make sure to focus on large enough values of n only, or add additional constraints (such as focusing at least on connected graphs only).

Other directions of interest include other results of the type of Theorem 3.1, to establish other results of the sort of Corollary 3.2, for other polynomial kernels of partitions. As a more general perspective, we wonder whether it could be worth studying the APness of graphs w.r.t. the traceability or the Hamiltonicity of some of their closures, and vice versa.

Lemma 4 . 1 .

 41 If G is an n-graph with two non-adjacent vertex u and v such that d(u) + d(v) ≥ n + c, then u and v have at least c + 2 common neighbours. In particular, c ≤ n -4.

Theorem 4 . 2 .

 42 For every λ ≥ 4, every graph G with order n ≡ 0 mod λ at least λ admits realisations of (λ, . . . , λ) if and only if clos(G, 2n -( 2n λ + λ -1)) does.Proof. Set α = 2n -( 2n λ + λ -1), and G ′ = clos(G, α). Consider an α-closing sequence G 0 , . . . , G m where G 0 = G and G m = G ′ . It again suffices to prove that any realisation R of (λ, . . . , λ) of H ′ = G i for any i ∈ {1, . . . , m} yields one of H

Theorem 4 . 3 .

 43 Every graph G with order n ≥ 3 is AP if and only if clos(G, 2n -4) is.

Theorem 4 . 4 .

 44 Every graph G with order n ≥ 4 is AP if and only if clos(G, 2n -5) is.

  v}, then a realisation of π in H can be obtained similarly as in the proof of Theorem 4.3. Hence, we can last assume u and v have only n -3 common neighbours in H. Let us thus denote by w the only vertex of V (H) ∖ {u, v} not adjacent to both u and v in H. Again, since 2n -5 ≥ 3, we must have |π| ≥ 2. If R contains a part S ′ ≠ S not containing w, then we can again reach our conclusion similarly as in the proof of Theorem 4.3. Otherwise, |π| = 2, and R thus contains only two parts, S and S ′ , where w ∈ S ′ . By arguments above, u and v are adjacent to all vertices of S ′ ∖ {w}. • If |S ′ | = 1, then n = 3, a case not covered by the statement. • If |S ′ | = 2, then S ′ = {w, x} where x is a common neighbour of u and v in H. In that case, n = 4, and since d H (u) + d H (v) ≥ 2n -5 = 3, for uv to be an edge of H ′ it must be that uw is an edge of H, w.l.o.g. Then a realisation of π in H is obtained upon considering parts {u, w} and {v, x}. • If |S ′ | ≥ 3, then consider any vertex x of S ′ ∖ {w} such that H[S ′ ∖ {x}] is connected. Such an x can be obtained e.g. by considering a leaf different from w of a spanning tree of H[S ′ ]. Since |S ′ | ≥ 3, recall that H[S ′ ∖ {x}] contains a vertex adjacent to both u and v. Then a realisation of π in H is obtained from R when considering parts {u, x} and {v} ∪ S ′ ∖ {x}.

Theorem 4 . 5 .

 45 Every n-graph G with n ≥ 5 is AP if and only if clos(G, 2n -6) is.Proof. We follow the lines of the proofs of Theorems 4.3 and 4.4 (but this time considering a (2n -6)-closing sequence). Here, in H, vertices u and v have at least n -4 common neighbours. Because H[S] is not connected, vertices u and v have no common neighbours in S, from which we deduce 2 ≤ |S| ≤ 4. Also, keep in mind throughout that n ≥ 5.Similarly as in the proof of Theorem 4.4, if |S| = 4, then u and v are adjacent to all vertices of V (H) ∖ S. If, say, |S u | = 1 and |S v | = 3, then, again, it suffices to consider any part S ′ ≠ S of R (it can be checked that such exists, as n ≥ 5 which implies 2n -6 ≥ 4), and, denoting by w any vertex of S ′ (being a common neighbour of u and v in H), a realisation of π in H is obtained when replacing parts S and S ′ of R with S v ∪ {w} and S ′ ∪ {u} ∖ {w}. Otherwise, |S u | = |S v | = 2; we consider a few cases.• If there is a part S ′ ≠ S of R with |S ′ | ≥ 4, then a realisation of π in H is obtained upon replacing S and S ′ with S u ∪ {w, x} (where w and x are any two vertices of S ′ ) and S v ∪ S ′ ∖ {w, x}.

•

  Assume now |π| = 3. Thus, R contains exactly two parts S w and S x different from S, where S w and S x contain w and x, respectively. Also, in H vertices u and v are both adjacent to all vertices of S w ∖ {w} and S x ∖ {x}. Here, assume, say, that H[S w ] contains a spanning tree with a leaf y different from w. Then, a realisation of π in H is obtained upon replacing, in R, parts S and S w with {u, y} and {v} ∪ S w ∖ {y}. Now, if none of H[S w ] and H[S x ] admits such a spanning tree, then |S w | = |S x | = 1 and n = 4, which peculiar case is not covered by the statement.

For convenience, unless stated otherwise, the order of any graph is denoted by n throughout.

From here on, perfect matchings are only considered for graphs with even order.