Luc Lesoil

Mathieu Acher

Arnaud Blouin

Jean-Marc Jézéquel

Beware of the Interactions of Variability Layers When Reasoning about Evolution of MongoDB

With commits and releases, hundreds of tests are run on varying conditions (e.g., over different hardware and workloads) that can help to understand evolution and ensure non-regression of software performance. We hypothesize that performance is not only sensitive to evolution of software, but also to different variability layers of its execution environment, spanning the hardware, the operating system, the build, or the workload processed by the software. Leveraging the MongoDB dataset, our results show that changes in hardware and workload can drastically impact performance evolution and thus should be taken into account when reasoning about evolution. An open problem resulting from this study is how to manage the variability layers in order to efficiently test the performance evolution of a software.

INTRODUCTION

Non-regression testing is supposed to ensure that performance does not decrease drastically when adding new features, but the reality is more complex and needs to be seen from different perspectives; the impact of a commit can change according to the executing environment and the benchmark fed to the software system 1 . So, in a situation where the performance changes brought by a code modification are beneficial for half of users but decrease the quality of service for the other half, should we push this code? Modify it? Ask for more benchmarking 2 ? Praise or blame?

Most of the time, a commit will optimize performance properties for a vast majority of users. But software performance is sometimes sensitive to different variability layers of its execution environment, such as the hardware, the operating system or the workload processed by the software. We rely on the concept of deep variability: existing interactions between different variability layers can modify or disturb our understanding of software variability and thus changing its underlying performance [START_REF] Lesoil | Deep Software Variability: Towards Handling Cross-Layer Configuration[END_REF][START_REF] Sayagh | On Cross-Stack Configuration Errors[END_REF]. Since the performance decreases in a heterogeneous way across all tests, tasks and projects 3 , it sometimes complexifies the developer life when reviewing code or pull requests. 1 See https://github.com/mongodb/mongo/pull/1068#discussion_r56706401 or https: //github.com/mongodb/mongo/pull/1118#discussion_r88797998 2 See https://github.com/mongodb/mongo/pull/472#issuecomment-22801074 3 See also https://github.com/mongodb/mongo/pull/23 Previous work has shown that thanks to testing infrastructures like Evergreen [START_REF] Daly | Creating a Virtuous Cycle in Performance Testing at MongoDB[END_REF], it is yet possible to identify change points [START_REF] Daly | The Use of Change Point Detection to Identify Software Performance Regressions in a Continuous Integration System[END_REF] i.e., changes made by developers that significantly alter software performance and measure their impact on the daily usage of the software. We are also interested in studying the impact of these change points, but in relation to the executing environments of MongoDB and the possible impact of variability layers. In short: is MongoDB performance evolution sensitive to deep variability?

Figure 1 typifies the problem we are addressing 5 . On the top graph, we display the change points detected by the test infrastructure over time, as well as their effect and impact on the performance (y-axis, percentage change). Bubble sizes represent the Z-scores [START_REF] Abdi | Z-scores[END_REF] related to the change points. On the bottom, we show the evolution of performances i.e., Time Series (TS) for six different executing environments but considering the same project, task, variant of hardware and test for each. Like that, we are able to observe the effect of a change point on the different Time Series, each TS having its own evolution. The interesting part starts in the middle of May and ends in June 2021 ; around the 15 𝑡ℎ of may, the performance property suddenly drops for TS #1, TS #4 and TS #5 while it increases for TS #2, TS #3 and TS #6. This suggests that two groups of TS react differently to the same commit. This result can be explained by looking at the thread level set when executing MongoDB. With the thread level fixed at 1, the performance property 6 increases. With a thread level of 512, the performance drops. Is it a performance bug though? Based on their thread level value when configuring the software, users will either agree or disagree. In this case, this is an example showing how an external factor (like the thread level here) threatens the work of MongoDB developers. This issue was fixed in the end of May. After this addition -or deletion, the performance matches its former value for all time series.

In this paper, we aim at identifying different variability layers impacting the evolution of performance of MongoDB. We first study the difference of performance evolution according to hardware in Section 2 and then the impact of workloads in Section 3.

Technical details. This paper is part of the ICPE 2022 Data Challenge 7 . We rely on the dataset they provided for all our experiments 8 . For Sections 2 and 3, we use the Legacy Performance Dataset [START_REF] Daly | The Use of Change Point Detection to Identify Software Performance Regressions in a Continuous Integration System[END_REF]. Code and results are publicly available9 .

IMPACT OF HARDWARE

According to the hardware platform of the final user, the performance of MongoDB may evolve differently. In this section, we quantify and study these differences of evolution, by answering the following research question: RQ1 -What is the impact of hardware variability on the evolution of MongoDB?

Protocol

Metric. We first need a measure to quantify the similarities between time series. We rely on Dynamic Time Warping [START_REF] Müller | Dynamic time warping[END_REF] (DTW). Unlike Euclidian distance -a point by point comparison, it is able to detect a pattern common to two time series even if this pattern does not appear at the same time for both series.

Time series pre-processing. We remove all the time series having less than two measurements. Since two time series do not necessarily have the same time stamps (e.g., TS #3 and TS #6 in Figure 1), we only compare them during their common period of definition. For instance, to compare TS #3 and TS #6, we would remove the values of TS #3 before the starting time of TS #6 and after the last value of TS #6. When there exists a point in one time series that does not have a corresponding point in the other one, we interpolate the value with a linear function based on the two values closest to the missing one. To avoid biasing the results with different scales, we standardise [START_REF] Shirley | Statistics for research[END_REF] the performance values.

Implementation. For each project, each test and each workload, we compute the DTW between the time series related to different hardware platforms. Then, we average the DTW values for each pair of variants of hardware. We consider the resulting value as a measure of similarity between the time series of two different hardware platforms. In Figure 2a, each column and each line represents a variant of hardware, on which MongoDB is executed; the intersection of a line and a column shows this resulting DTW value between the variant of the line and the variant of the column. If there is no time series with common project, test and workload between two variants, we leave it blank. Due to space issue, names of variants are cut down to 20 characters 10 .

Interpretation. When two times series have exactly the same evolution, their DTW is equal to zero. Then, the greater the differences between time series, the greater the DTW value. We show four pairs of time series with their measure of DTW values in Figures 2b to 2e to help interpret Figure 2a 11 .

Results

The first result is a good news w.r.t. stability: 25 % of couples of hardware have a very low average DTW value i.e., inferior to 1.70 and half of them have a low DTW value i.e., inferior to 4.48. This is represented by clusters of dark red cells in Figure 2a. Knowing the evolution of MongoDB for one of these hardware platforms is enough to predict or estimate the evolution for all the other hardware platforms, as shown in Figure 2b or Figure 2c. In other words, we can reduce the benchmarking cost for all these variants of hardware, because they have similar performance evolutions. As a MongoDB developer, it shows consistency between these hardware platforms, which is reassuring; optimizations made to MongoDB over time will generalize to most users' executing environments.

Then, we highlight of set of hardware platforms for which the evolution of performance differs over time. In Figure 2a, they are mostly located on the top-left corner. A good example that shows how their evolution differ is depicted in Figure 2d. It seems that there is no common pattern of evolution between the different variants of hardware. As a result, the hardware layer deserves to be carefully benchmarked in such a way we understand how they react to code changes.

Finally, we isolate few hardware platforms with higher DTW values. They are blue cells in Figure 2a and their differences of evolution are typified by Figure 2e. High DTW values can be explained by the presence of outliers in their performance distributions. We suspect two potential factors at the origin of these outliers: i) either we incidentally create outliers when standardising the performance or ii) this is a problem related to the performance infrastructure. Further experiments are needed to conclude about the root cause.

IMPACT OF WORKLOAD

We now study the stability of performance evolution for different workloads fed to MongoDB. How many percents do we gain or lose between each commit? Does this value vary with the workloads? Do the workloads processed by MongoDB change its performance evolution? To address this, we answer the following research question: RQ2 -What is the impact of workload variability on the evolution of MongoDB?

Protocol

Metric. We define the Daily Relative Percentage Change (DRPC), a metric designed to measure the relative difference of performance (in percentage) per day :

𝐷𝑅𝑃𝐶 (𝑡) = 100 𝑑 (𝑡,𝑡 +1) * 𝑝 (𝑡 +1)-𝑝 (𝑡 ) 𝑝 (𝑡 )
where 𝑝 (𝑡) is the performance value at the time 𝑡 and 𝑑 (𝑡, 𝑡 +1) is the number of days between 𝑡 and 𝑡 + 1. We divide by the number of days between 𝑡 and 𝑡 + 1 to avoid artificially increasing the results when there are few measurements separated by long time periods. We then average the results in absolute value for each date of measurement 𝑡, which provides the average DRPC related to a time series.

Time series pre-processing. We remove all the time series having less than two measurements, because the metric is impossible to compute in this case.

Implementation. We consider the 22 workloads of the dataset; for each, we gather the time series including performance measurement on this workload and compute the average DRPC. In Figure 3a, we display the boxplots of DRPC distributions per workload. We also display some examples of evolution for two workloads with the detail of percentage change values in Figures 3b and 3c 12 .

Interpretation. The DRPC measures the stability of the evolution of MongoDB performance and quantifies the daily average percent change between two measurements. For a constant performance distribution, the DRPC is equal to zero. The greater the DRPC, the greater (and the more unstable) the evolution.

Results

Figure 3a illustrates how the variability of workloads affects the evolution of MongoDB. The daily percentage change of performance fluctuates with workloads; it can be very low or really high e.g., median at 0.15 % for the "genny_canary" workload or at 26.9 % for the "UserAcq-ActorFin" workload. In Figures 3b and3c, we plot the detail of percentage changes for these two workloads to show the difference of scale between their evolution of performance -up to a factor of 10 between their percentage changes.

Beyond the median values of the percentage changes, the results also show a difference in stability in the evolution of workload performance; while few stable workloads have a low InterQuartile Range e.g., "Genny-Setup" (IQR = 0.14 %), others can have various ranges of percentage changes e.g., "shell/benchurn" (IQR = 4.97 %) or "UserAcq-ActorFin" (IQR = 8.87 %). These stable workloads are reliable. For them, it is quite easy to detect an outlier, since their performance value rarely exceeds a given threshold. We guess they can be used as reference to detect a regression in the code. If such workloads observe a big decrease of performance, it is the sign that an error occurred in one of the last code modifications.

DISCUSSION

In this paper, we have considered two variability layers, namely hardware and workload, and studied their impacts on software evolution. Other variability layers can well be considered in the future, for example i) operating system: the Linux kernel is highly configurable and may have an impact on performance evolution of MongoDB; ii) compile-time options and flags: the way Mon-goDB has been built 13 can change the performance distributions. For instance, Lesoil et al. [START_REF] Lesoil | The Interplay of Compile-time and Run-time Options for Performance Prediction[END_REF] report on preliminary evidence of complex interactions between run-time options (e.g., command line parameters) and compile-time options (e.g., using ./configure) with different effects of non-functional properties of software. In the case of MongoDB we can wonder whether and to what extent these layers impact software evolution, e.g., does using a different Linux variant (distribution and kernel) change the conclusions and insights about evolution? Answering these questions requires varying different layers and gather specific measurements' data. It is left as future work.

Another limitation of our work is that we have not studied the interactions between variability layers. That is, we have focused on individual effects of each variability layer on evolution. As future work, we could investigate whether hardware together with workload changes the performance of a software system. A hypothesis is that specific combinations of hardware and workload cause a shift in performance. The identifying of such interactions typically requires controlled measurements of pairs of workload-hardware and is arguably costly to instrument at scale.

THREATS TO VALIDITY

Our results may vary with other choices of metrics. For instance, the DRPC used in Section 3 may amplify the noise of measurements by construction, thus slightly overestimating the real percentage of performance change. 13 See https://github.com/mongodb/mongo/blob/master/docs/building.md When standardising the performance in Section 2, there exists a risk to artificially create outliers if the standard deviation of the performance is too low. It could partly explain Section 2.2 results. Yet it appears to be the only solution to efficiently compare DTW related to distributions having different scales.

RELATED WORK

Software evolution and performance. There exist research works studying the impact of software evolution on performance [START_REF] Pablo | Tracking down Performance Variation against Source Code Evolution[END_REF][START_REF] Canali | Performance Evolution of Mobile Web-Based Services[END_REF][START_REF] Daly | The Use of Change Point Detection to Identify Software Performance Regressions in a Continuous Integration System[END_REF][START_REF] Martin | Transfer Learning Across Variants and Versions: The Case of Linux Kernel Size[END_REF][START_REF] Mens | Challenges in software evolution[END_REF][START_REF] Mühlbauer | Identifying Software Performance Changes Across Variants and Versions[END_REF][START_REF] Pablo | Performance evolution blueprint: Understanding the impact of software evolution on performance[END_REF]. Martin et al. [START_REF] Martin | Transfer Learning Across Variants and Versions: The Case of Linux Kernel Size[END_REF] presents a solution, based on transfer learning, to deal with the evolution of the Linux kernel when predicting kernel sizes of configurations. Mühlbauer et al. [START_REF] Mühlbauer | Identifying Software Performance Changes Across Variants and Versions[END_REF] investigated the history of software performances to isolate when a performance shift happens over time and variants (software configurations). Our study pursues a similar objective, but pays attention to the impact of hardware and workload on software evolution. Our results show that hardware and workload variability cannot be ignored when reasoning about performance history.

Hardware variability. Resarch work has been investigating the effect of hardware on software performance [START_REF] Brink | On Hardware Variability and the Relation to Software Variability[END_REF][START_REF] Dougherty | Automating Hardware and Software Evolution Analysis[END_REF][START_REF] Elkeelany | Performance Evaluation of Different Hardware Models of RC5 Algorithm[END_REF][START_REF] Jamshidi | Transfer Learning for Performance Modeling of Configurable Systems: An Exploratory Analysis[END_REF][START_REF] Valov | Transferring Pareto Frontiers across Heterogeneous Hardware Environments[END_REF][START_REF] Valov | Transferring Performance Prediction Models Across Different Hardware Platforms[END_REF]. In particular, Valov et al. [START_REF] Valov | Transferring Pareto Frontiers across Heterogeneous Hardware Environments[END_REF][START_REF] Valov | Transferring Performance Prediction Models Across Different Hardware Platforms[END_REF] suggest that changing the hardware has reasonable impacts on software configurations since linear functions are highly accurate when reusing prediction models. Unlike our work, the evolution of software is not taken into account in their studies and dataset, nor are changes in workloads.

Workload performance analysis. There are numerous works addressing the performance analysis of software systems [START_REF] Pereira | Sampling Effect on Performance Prediction of Configurable Systems: A Case Study[END_REF][START_REF] Coppa | Estimating the Empirical Cost Function of Routines with Dynamic Workloads[END_REF][START_REF] Fathyatlam | Comparative Study on CBIR based on Color Feature[END_REF][START_REF] Simon | Measuring Empirical Computational Complexity[END_REF][START_REF] Leitner | Patterns in the Chaos-A Study of Performance Variation and Predictability in Public IaaS Clouds[END_REF][START_REF] Lesoil | The Interaction between Inputs and Configurations fed to Software Systems: an Empirical Study[END_REF][START_REF] Lesoil | The Interaction between Inputs and Configurations fed to Software Systems: an Empirical Study[END_REF][START_REF] Pongnumkul | Performance Analysis of Private Blockchain Platforms in Varying Workloads[END_REF][START_REF] Sinha | Using a Genetic Algorithm to Optimize Configurations in a Data-Driven Application[END_REF] depending on different input data (also called workloads or benchmarks). In this paper, we specifically study the impact of workloads on software evolution.

Jamshidi et al. [START_REF] Jamshidi | Transfer Learning for Performance Modeling of Configurable Systems: An Exploratory Analysis[END_REF] conducted an empirical study on four configurable systems, varying software configurations and environmental conditions, namely hardware, workload, and software versions. Results show transferring performance can be difficult depending on environment changes. An important feature of the study, and therefore of their dataset, is that all three variability factors are modified together, for example, both version, hardware and workload are modified and compared to a baseline. Without isolating the individual effect of each variability layer, it is challenging to understand whether a performance shift is due to the evolution of software or other factors (hardware and workload). In contrast, our study leverages the dataset to investigate i) the impact between hardware and evolution ii) the impact between workload and evolution.

CONCLUSION

In this paper, we investigated to what extent two variability layers impact performance of MongoDB evolution, namely the hardware platforms on which MongoDB are executed and the workloads fed to MongoDB. Our analysis over the MongoDB dataset showed that these two variability layers cannot be ignored when reasoning about the performance evolution of MongoDB. We also provided some insights to efficiently benchmark executing environments of users w.r.t. these two variability layers.

Figure 1 :

 1 Figure 1: Joint evolution of mongoDB change points (top) and performance values (bottom) -Different thread levels change the evolution of performance values In this short paper, we consider MongoDB, a well-known Data Base Management System 4 , and ask the following questions: How do the different factors of the executing environment affect Mon-goDB performance distribution? Do these interactions have an impact on the performance of the software over time? Is it possible to reason about performance evolution independently of e.g., workloads and hardware variability used for measuring MongoDB?Previous work has shown that thanks to testing infrastructures like Evergreen[START_REF] Daly | Creating a Virtuous Cycle in Performance Testing at MongoDB[END_REF], it is yet possible to identify change points[START_REF] Daly | The Use of Change Point Detection to Identify Software Performance Regressions in a Continuous Integration System[END_REF] i.e., changes made by developers that significantly alter software performance and measure their impact on the daily usage of the software. We are also interested in studying the impact of these change points, but in relation to the executing environments of MongoDB and the possible impact of variability layers. In short: is MongoDB performance evolution sensitive to deep variability?Figure1typifies the problem we are addressing5 . On the top graph, we display the change points detected by the test infrastructure over time, as well as their effect and impact on the performance (y-axis, percentage change). Bubble sizes represent the Z-scores[START_REF] Abdi | Z-scores[END_REF] related to the change points. On the bottom, we show the evolution of performances i.e., Time Series (TS) for six different executing environments but considering the same project, task, variant of hardware and test for each. Like that, we are able to observe the effect of a change point on the different Time Series, each TS having its own evolution.

  (a) Heatmap of average DTW between times series related to different variants of hardware (b) DTW = 0.38 (c) DTW = 3.23 (d) DTW = 5.39 (e) DTW = 15.31

Figure 2 :

 2 Figure 2: Performance evolution of MongoDB according to hardware platforms

  (a) DRPC distributions per workload (b) DRPC = 1.61 %, "genny_canaries" workload (c) DRPC = 25.07 %, "UserAcq-ActorFin" workload

Figure 3 :

 3 Figure 3: Performance evolution of MongoDB according to different workloads.

See https://www.mongodb.com/

Dataset: Expanded Metrics, Project: sys-perf, Task: industry benchmark wmajority, Hardware: Linux 3 node replSet, Test: csb 50 read 50 update w majority

Here, the performance property is the 99 𝑡ℎ percentile of allocated memory in Megabytes

See https://icpe2022.spec.org/tracks-and-submissions/data-challenge-track/ and https://www.daviddaly.me/2021/10/questions-on-icpe-2022-data-challenge.html for additional explanations

Download the dataset at https://zenodo.org/record/5138516

Companion repository : https://github.com/llesoil/icpe2022

Details about the environments used in Figures3b and 3ccan be consulted at https://github.com/llesoil/icpe2022/blob/main/Data%20Challenge.ipynb

Acknowledgments. This research was funded by the ANR-17-CE25-0010-01 VaryVary project.


Laurent Bulteau

Guillaume Fertin

Vincent Jugé

Stéphane Vialette

Cheb Plzeň

Permutation Pattern Matching for Doubly Partially Ordered Patterns

Keywords: 2012 ACM Subject Classification Theory of computation Partial orders, Permutations, Pattern Matching, Algorithmic Complexity, Parameterized Complexity

We study in this paper the Doubly Partially Ordered Pattern Matching (or DPOP Matching) problem, a natural extension of the Permutation Pattern Matching problem.

Permutation Pattern Matching takes as input two permutations σ and π, and asks whether there exists an occurrence of σ in π; whereas DPOP Matching takes two partial orders Pv and Pp defined on the same set X and a permutation π, and asks whether there exist |X| elements in π whose values (resp., positions) are in accordance with Pv (resp., Pp). Posets Pv and Pp aim at relaxing the conditions formerly imposed by the permutation σ, since σ yields a total order on both positions and values. Our problem being NP-hard in general (as Permutation Pattern Matching is), we consider restrictions on several parameters/properties of the input, e.g., bounding the size of the pattern, assuming symmetry of the posets (i.e., Pv and Pp are identical), assuming that one partial order is a total (resp., weak) order, bounding the length of the longest chain/anti-chain in the posets, or forbidding specific patterns in π. For each such restriction, we provide results which together give a(n almost) complete landscape for the algorithmic complexity of the problem.

Preamble

Let us play the following little puzzle game. Among the selection of fifteen cities of the Czech Republic depicted in Figure 1 It is assumed that no two cities have the same longitude or latitude. Notice that the game does not provide complete information as, for example, no information is provided about the relative positioning of A and C (and silence is tantamount to consent). We may assume that We show that this puzzle game can be modeled as a permutation pattern matching problem for doubly partially ordered patterns. Let us first associate a permutation π ∈ S [START_REF] Fox | Stanley-wilf limits are typically exponential[END_REF] with the problem (see Figure 2). We sort the fifteen cities of the Czech Republic depicted in Figure 1 both by increasing longitude (E) and by increasing latitude (N), so that π(i) = j if Introduction

We say that a permutation σ occurs in another permutation π (or that π contains σ) if there exists a subsequence of elements of π that has the same relative order as σ. Otherwise, we say that π avoids σ. For example, π contains the permutation σ = 123 (resp., σ = 321) if it has an increasing (resp., a decreasing) subsequence of size 3. Similarly, σ = 4312 occurs in π = 6152347, as shown in 6 1 5 2 3 4 7, but the same π = 6152347 avoids σ ′ = 2341.

Deciding whether a permutation σ ∈ S(k) occurs in some permutation π ∈ S(n)

is NP-complete [START_REF] Bose | Pattern matching for permutations[END_REF], but is fixed-parameter tractable for the parameter k [START_REF] Fox | Stanley-wilf limits are typically exponential[END_REF][START_REF] Guillemot | Finding small patterns in permutations in linear time[END_REF]. Two exponential-time algorithms have been recently proposed [START_REF] Aram Berendsohn | Finding and counting permutations via csps[END_REF], improving upon [START_REF] Ahal | On complexity of the subpattern problem[END_REF][START_REF] Bruner | A fast algorithm for permutation pattern matching based on alternating runs[END_REF]. A vast literature is devoted to the case where both the pattern σ and the target π are restricted to a proper permutation class, e.g., 321-avoiding permutations [START_REF] Guillemot | Pattern matching for 321-avoiding permutations[END_REF][START_REF] Michael | The complexity of pattern matching for 321-avoiding and skew-merged permutations[END_REF][START_REF] Jelínek | Hardness of permutation pattern matching[END_REF], (213, 231)-avoiding permutations [START_REF] Both | Permutation pattern matching in (213, 231)-avoiding permutations[END_REF], (2413, 3142)-avoiding (a.k.a. separable) permutations [START_REF] Ibarra | Finding pattern matchings for permutations[END_REF][START_REF] Both | Pattern matching for separable permutations[END_REF], and (k . . . 1)avoiding permutations [START_REF] Bulteau | Pattern matching for k-track permutations[END_REF]. For more background on permutation patterns and pattern avoidance, we refer to [START_REF] Bóna | Combinatorics of Permutations[END_REF] and [START_REF] Kitaev | Patterns in Permutations and Words[END_REF].

In the last years, the notion of pattern has been generalized in several ways. A vincular pattern is a permutation in which some entries must occur consecutively [START_REF] Babson | Generalized permutation patterns and a classification of the mahonian statistics[END_REF]. Consecutive patterns are a special case of vincular patterns in which all entries need to be adjacent [START_REF] Elizalde | Consecutive patterns in permutations[END_REF].

Bivincular patterns generalize classical patterns even further than vincular patterns by requiring that not only positions but also values of elements involved in a matching may

Increasing longitudes

Increasing latitudes be forced to be adjacent [START_REF] Bousquet-Mélou | 2+2)-free posets, ascent sequences and pattern avoiding permutations[END_REF]. Mesh patterns (a further generalization of bivincular patterns) 72 impose further restrictions on the relative positions of the entries in an occurrence of a 73 pattern [START_REF] Brändén | Mesh patterns and the expansion of permutation statistics as sums of permutation patterns[END_REF] and boxed mesh patterns are special cases of mesh patterns [START_REF] Sergey | Avoidance of boxed mesh patterns on permutations[END_REF]. Strongly related 74 to our approach are partially ordered patterns that are vincular patterns in which the relative 75 order of some elements is not fixed [START_REF] Kitaev | Introduction to partially ordered patterns[END_REF]. The best general reference is [START_REF] Kitaev | Patterns in Permutations and Words[END_REF].

76

In this paper, we consider a new generalization of classical patterns in which both the relative order and the relative positioning of some elements are not fixed. The idea is to allow the possibility for some elements to be incomparable in value (i.e., their relative order is unknown) and to go one step further by allowing the possibility for some elements to be incomparable in position (i.e., their relative positioning in the occurrence is unknown). Since the problem is clearly NP-hard (as it contains Permutation Pattern Matching as a sub-problem), our goal is to identify tractable cases when restrictions apply to the pattern and/or to the permutation.

The restrictions we consider here apply to the following parameters of the problem: size of the pattern; symmetry (i.e., same partial order in positions and values); one partial order is a total (resp., weak) order; size of the longest chain (resp., anti-chain) in the partial orders (height and width); forbidden patterns in π. On the positive side, we show that the FPT algorithm for Permutation Pattern Matching can be generalized to our setting (with the pattern size as parameter). We further give polynomial-time algorithms when the pattern is a symmetric disjoint union of a constant number of weak orders. Finally, we also provide polynomial-time algorithms when the pattern is symmetric and the permutation belongs to some restricted classes, such as (123, 132)-avoiding permutations. We complement these positive results with NPor W [START_REF] Ahal | On complexity of the subpattern problem[END_REF]-hardness proofs in most of the remaining cases.

Definitions

Permutations and Patterns

A permutation σ is said to be contained in (or is a sub-permutation of) another permutation π, which we denote by σ ⪯ π, if π has a (not necessarily contiguous) subsequence whose terms are order-isomorphic to σ. We also say that π admits an occurrence of the pattern σ. If no such subsequence exists, we say that π avoids σ (or is σ-avoiding). A permutation is separable if it avoids both 2413 and 3142. Permutation Pattern Matching is the problem of deciding whether a permutation is contained into another permutation.

For any non-negative integer n, we denote by [n] the set {1, 2, . . . , n}. When n ⩾ 1, we also note ip(n) = 1 2 . . . n the increasing permutation of length n and dp(n) = n (n -1) . . . 1 the decreasing permutation of length n. Let π ∈ S(n). The reverse (resp., complement) of π is the

permutation π r = π(n)π(n-1) . . . π(1) (resp., π c = (n-π(1)+1)(n-π(2)+1) . . . (n-π(n)+1)).
The inverse of π is the permutation π -1 ∈ S(n) defined by π -1 (j) = i if and only if π(i) = j.

Given a permutation π of size m and a permutation σ of size n, the skew sum of π and σ is the permutation of size m + n defined by

(π ⊖ σ)(i) = π(i) + n for 1 ⩽ i ⩽ m, σ(i -m) for m + 1 ⩽ i ⩽ m + n,
and the direct sum of π and σ is the permutation of size m + n defined by

(π ⊕ σ)(i) = π(i) for 1 ⩽ i ⩽ m, σ(i -m) + m for m + 1 ⩽ i ⩽ m + n.

Orders

A relation ⩽ is a partial order on a set X if it has:

reflexivity: for all x ∈ X, x ⩽ x (i.e., every element is related to itself); transitivity: for all x, x ′ , x ′′ ∈ X, if x ⩽ x ′ and x ′ ⩽ x ′′ , then x ⩽ x ′′ ;

antisymmetry: for all x, x ′ ∈ X, if x ⩽ x ′ and x ′ ⩽ x, then x = x ′ (i.e., no two distinct elements precede each other).

If ⩽ has the following additional property, we say that it is a weak order on X: transitivity of incomparability: for all x, x ′ , x ′′ ∈ X, if x is incomparable with x ′ (i.e., neither x ⩽ x ′ nor x ′ ⩽ x is true) and if x ′ is incomparable with x ′′ , then x is incomparable with x ′′ .

Two subsets X 1 , X 2 are independent if there is no

x 1 ∈ X 1 , x 2 ∈ X 2 such that x 1 ⩽ x 2 or x 2 ⩽ x 1 .
We say that a partial order is k-weak if there exists a partition of X into k pairwise independent sets X 1 , . . . , X k such that, for each i, the restriction of ⩽ to X i is a weak order (in other words, ⩽ is the disjoint union of k weak partial orders).

Let P = (X, ⩽) be a finite partially ordered set. A chain in P is a set of pairwise comparable elements (i.e., a totally ordered subset) and an antichain in P is a set of pairwise incomparable elements. The partial order height of P, denoted by height(P), is defined as the maximum cardinality of a chain in P, and the partial order width of P, denoted by width(P), is defined as the maximum cardinality of an antichain in P. By Dilworth Theorem, width(P) is also the minimum number of chains in any partition of P into chains. The dual of P is the partial order P ∂ = (X, ⩽ ∂ ) defined by letting ⩽ ∂ be the converse relation of ⩽, i.e., x ⩽ ∂ x ′ if and only if x ′ ⩽ x. The dual of a partial order is a partial order and the dual of the dual of a relation is the original relation. A total order is a partial order in which any two elements are comparable, and a set equipped with a total order is a totally ordered set.

A linear extension of a partial order is a total order that is compatible with the partial order.

It will be convenient to represent a linear extension of a poset P = (X, ⩽) as the mapping

τ P : X → [ |X| ] such that τ P (i) < τ P (j) if i < j in the linear extension.
A doubly partially ordered pattern (dpop) P is a pair, denoted by P = (P v , P p ), of posets

P v = (X, ⩽ v
) and P p = (X, ⩽ p ) defined over the same set X. We call P v and P p the value poset and the position poset, respectively. A dpop P = (P v , P p ) is symmetric if P v = P p , dual if P v = P p ∂ , and semi-total if one of P p or P v is a total order. We let height(P ) and width(P ) stand for max{height(P v ), height(P p )} and max{width(P v ), width(P p )}, respectively. Finally, the size of P is defined as the cardinality |X| and is denoted by |P |.

▶ Definition 1 (DPOP Matching). Given a permutation π ∈ S(n) and a dpop P = (P v , P p ), an occurrence (or mapping) of P in π is an injective function φ : X → [n] such that:

π • φ is ⩽ v -non-decreasing, i.e., for all x, y ∈ X, if x ⩽ v y then π(φ(x)) ⩽ π(φ(y)),
and

φ is ⩽ p -non-decreasing, i.e., for all x, y ∈ X, if x ⩽ p y then φ(x) ⩽ φ(y).
The DPOP Matching problem consists in deciding whether P occurs in π.

First Observations

▶ Observation 2. Permutation Pattern Matching is the special case of DPOP Matching where both ⩽ v and ⩽ p are total orders.

We note that applying a vertical and/or horizontal symmetry on both pattern and permutation does not alter the existence of an occurrence.

▶ Observation 3. Let P = (P v , P p ) be a dpop and π be a permutation. The following statements are equivalent:

1. (P v , P p ) occurs in π; 2. (P v , (P p ) ∂ ) occurs in π r ; 3. ((P v ) ∂ , P p ) occurs in π c ; 4. ((P v ) ∂ , (P p ) ∂ ) occurs in π c r ; 5. (P p , P v ) occurs in π -1 .
The following reformulation will prove useful.

▶ Observation 4. Let P = (P v , P p ) be a dpop with

P v = (X, ⩽ v ), P p = (X, ⩽ p ) and k = |X|,
and let π ∈ S(n) be a permutation. The following statements are equivalent:

P occurs in π.
There exists a linear extension τ v : X → [k] of P v and a linear extension

τ p : X → [k]
of P p such that the permutation σ ∈ S(k) defined by

σ(i) = τ v (τ -1 p (i)) for 1 ⩽ i ⩽ k is contained in π.
The rationale for the reformulation introduced in Observation 4 stems from the following corollary that sets the general context.

▶ Corollary 5 ([16]). DPOP Matching is FPT for the parameter |P |.

Indeed, it is enough to guess two linear extensions

τ v : X → [k] of P v and τ p : X → [k]
of P p , and to check if the permutation σ ∈ S(k) defined by

σ(i) = τ v (τ -1 p (i)) for 1 ⩽ i ⩽ k is contained in π. There are O(k! 2
) pairs of such extensions and, for each of them, one can check whether σ occurs in π in n 2 O(k 2 log k) time [START_REF] Guillemot | Finding small patterns in permutations in linear time[END_REF].

Semi-Total Patterns

In this section we focus on semi-total patterns, i.e., without loss of generality, on the case where P p is a total order (up to symmetry by Observation 3). This case still contains Permutation Pattern Matching as a special case, and is thus NP-hard. We focus on small-height value partial orders, i.e., on dpops with constant height(P v ), and give an XP algorithm for weak orders (Proposition 6) and paraNP-hardness in general (Proposition 7).

▶ Proposition 6. DPOP Matching is solvable in O n height(P v ) time if P v is a weak order and P p is a total order.

Proof. Let π ∈ S(n) be a permutation and P = (P v , P p ) be a dpop on some ground set X,

where P v is a weak order and P p is a total order. Without loss of generality, we assume that X is the set [k] and that P p is the usual order on integers. For every x ∈ X, we abusively denote by height(x) the maximum cardinality of a chain with maximum element x in P v .

Finally, set ℓ = height(P v ).

For any two distinct variables x, y ∈ X, we have x < v y if and only if height(x) < height(y).

Thus, P occurs in π if and only there exists a sequence 0 = a 0 < a 1 < a 2 < . . . < a ℓ = n such that w σ is a subsequence of w π , where

w π ∈ [ℓ] n and w σ ∈ [ℓ] k are the two words defined by w π [i] = min{j : a j-1 < π(i) ⩽ a j } and w σ [i] = height(i).
As for the running time, there exist n-1 ℓ-1 distinct sequences (a i ) 0⩽i⩽ℓ and deciding whether w σ occurs in w π as a subsequence is a linear-time procedure. ◀ ▶ Proposition 7. DPOP Matching is NP-complete even if height(P v ) = 2, P p is a total order and π avoids 1234.

Proof. We perform a reduction from Vertex Cover, which is known to be NP-complete [START_REF] Karp | Reducibility among Combinatorial Problems[END_REF].

Let G = (V, E) be a graph and let k be a positive integer. We identify V with the set [n].

We construct a dpop P = (P v , P p ), where P v = (X, ⩽ v ) is a height-2 partial order and P p = (X, ⩽ p ) a total order, as follows. We set

X = {a 1 , b 1 , c 1 , a 2 , b 2 , c 2 , . . . , a n , b n , c n }, so that |X| = 3n. Then, we set a 1 ⩽ p b 1 ⩽ p c 1 ⩽ p a 2 ⩽ p b 2 ⩽ p c 2 ⩽ p . . . ⩽ p a n ⩽ p b n ⩽ p c n ,
which defines the total order ⩽ p . Finally, for each edge {i, j} in E with i < j, we set a i ⩽ v b j ; all other elements of X are pairwise incomparable by ⩽ v . This defines a partial order ⩽ v such that height(⩽ v ) = 2.

Write now N = 3n + 3 and m = (k + 1)N -2, and define a permutation π ∈ S(m) as follows:

π(iN + j) = (m + 1) -(iN + j + k) whenever 0 ⩽ i ⩽ k and 1 ⩽ j ⩽ N -2; π(iN -1) = (k + 1) -i and π(iN ) = (m + 1) -i whenever 1 ⩽ i ⩽ k.
It is straightforward to check that π is 1234-avoiding. It is also easy to see how the construction, illustrated in Figure 4, can be accomplished in polynomial-time.

Let us see under which conditions an injective ⩽ p -non-decreasing function φ : X → [m] maps P into π. We say that a vertex i belongs to the j-th gadget if one of the integers φ(a i )

or φ(b i ) is equal to jN -1 or to jN , i.e., if {φ(a i ), φ(b i )} ∩ {jN -1, jN } ̸ = ∅. When two
elements in the range of φ are consecutive, either they are integers φ(a i ) and φ(b i ) for a

given i, or one of them is an integer φ(c i ) for some i. Therefore, no two distinct vertices i and i ′ can belong to the same j-th gadget. Consequently, and since there are k gadgets, the set V ′ of vertices i that belong to some gadget is of size at most k.

Then, we define a notion of height as follows: for each element x of X, we set height

(x) = 0 if N divides φ(x) + 1, height(x) = 2 if N divides φ(x)
, and height(x) = 1 otherwise. By construction, for all x, y ∈ X such that x ⩽ p y, we have π(φ(x)) ⩽ π(φ(y)) if and only if x is of smaller height than y. Therefore, if φ maps P into π, and for each relation

a i ⩽ v b j ,
either a i has height 0 or b j has height 2. In particular, either i or j must belong to V ′ , and therefore V ′ is a vertex cover of size at most k.

Conversely, provided that there exist vertices v(1) < v(2) < . . . < v(k) that form a vertex cover V ′ , we construct an occurrence of P in π as follows. First, we abusively set v(0) = 0.

Then, for all i ∈ [k], we set f (i) = jN + 3(i -v(j)), where j is the largest integer such that v(j) ⩽ i. We set φ(a j ) = f (j) -1, φ(b j ) = f (j) and φ(c j ) = f (j) + 1.

By construction, we have f (i) + 3 ⩽ f (i + 1) for all i, and therefore φ is an injective ⩽ p -non-decreasing function. Moreover, for every i ∈ [n], the elements a i and b i have heights 0 and 2 if i ∈ V ′ , and they have height

1 if i / ∈ V ′ . It follows that π(φ(a i )) ⩽ π(φ(b j )) whenever a i ⩽ v b j , i.e.
, that φ is an occurrence of P in π. ◀

Symmetric Patterns

This section is devoted to studying complexity issues of pattern matching for symmetric dpop (i.e., those dpops P = (P, P), whose value and position posets coincide). We further focus on two special cases, first when P has a bounded width, then when π is restricted to constrained pattern-avoiding classes of permutations.

Symmetric Pattern with Bounded Width

We first observe that the problem is polynomial for width 1 (Observation 8). We further prove W[1]-hardness for the parameter k when P is a disjoint union of k chains (Proposition 10).

We complement this result with an XP algorithm for the slightly more general case where P is a disjoint union of weak orders (Proposition 11). Note that the existence of an XP algorithm for the width parameter remains open, and we conjecture that the problem is NP-hard even for constant width.

▶ Observation 8. DPOP Matching is solvable in O(n log log |P |) time for a symmetric dpop P of width 1 (i.e., a total symmetric dpop P ).

Proof. If P has width 1, then P = (P, P) for some total order P = (X, ≼). In particular, we can write X = {x 1 , . . . , x |X| } with x i ≺ x j for i < j, and in any mapping ϕ : X → Proof. We perform a reduction from Unary Bin Packing parameterized by the number of bins, which is known to be W[1]-hard [START_REF] Jansen | Bin packing with fixed number of bins revisited[END_REF]. In this version of Bin Packing, we are given a list of integers s 1 , s 2 , . . . , s n encoded in unary, and two integers B and k. These integers are interpreted as item sizes, and the task is to decide whether the items can be partitioned into k susbets, each of total size B. We show that there is a reduction from Unary Bin Packing, parameterized by the number of bins, to Balanced k-Increasing Coloring, parameterized by the number of colors. Each pattern ip(s i + 1) ⊖ dp(k -1) is called the i-th block of π. See Figure 5 for an illustration.

s 1 + 1 k -1 s 2 + 1 k -1 s 6 + 1 k -1 s 3 + 1 k -1 s 4 + 1 k -1 s 5 + 1 k -1 s 7 + 1 k -1 s 8 + 1 k -1 π ( avoids
It is straightforward to check that π is 312-avoiding.

We claim that the n items s 1 , s 2 , . . . , s n can be partitioned into k susbets, each of total size B, if and only if there exists a k-coloring of π such that each color induces an increasing pattern of length B + n.

Suppose first that the n items s 1 , s 2 , . . . , s n can be partitioned into k susbets, each of

total size B. Write S = S 1 ∪ S 2 ∪ • • • ∪ S k such a partition. Define a k-coloring of π as follows.
Consider the i-th block ip(s i + 1) ⊖ dp(k -1) of π, and suppose that s i ∈ S j . Color the whole ascending pattern ip(s i + 1) with color c j and arbitrarily color the elements of the descending pattern dp(k -1) with the remaining k -1 colors (each element of dp(k -1) is assigned to a distinct color). We claim that every color c j induces an increasing pattern of length B + n in π. First, it is clear that the above k-coloring induces increasing patterns only.

As for the length of each induced increasing pattern, focus on any color c j . We note that, in every block ip(s i + 1) ⊖ dp(k -1) of π, either the whole subpattern ip(s i + 1) is colored with color c j (if s i ∈ S j ) or exactly one element of the subpattern dp(k -1) is colored with color c j (if s i / ∈ S j ). It follows that the increasing pattern induced by color c j in π has length

si∈Sj (s i + 1) + n -|S i | = si∈Sj s i + |S i | + n -|S i | = B + n.
For the reverse direction, suppose now that there exists a k-coloring of π such that each color induces an increasing pattern of length B + n. Every block ip(s i + 1) ⊖ dp(k -1)

requires at least k colors, as it contains a decreasing subpattern of length k. Therefore, the whole subpattern ip(s i + 1) is colored with the same color. For every j ⩽ k, let S j be the set of all s i such that, in the i-th block ip(s i + 1) ⊖ dp(k -1), the subpattern ip(s i + 1) is colored with color c j . We have Proof. We perform a reduction from Balanced k-Increasing Coloring, which is W[1]hard for the parameter k. Let π ∈ S(kn) for some positive integers k and n. We construct a symmetric dpop P = (P, P), where P = (X, ≼), as follows:

B + n = si∈Sj (s i + 1) + n -|S j | = si∈Sj s i + |S j | + n -|S j |,
X = [k] × [n] and (i, j) ≼ (i ′ , j ′ )
if and only if i = i ′ and j ⩽ j ′ . We claim that P occurs in π if and only π admits a k-coloring for which every color induces an increasing pattern of length n.

If π admits such a k-coloring into colors c 1 , c 2 , . . . , c k , the function φ : X → [kn] that maps each pair (i, j) to the j-th smallest position with color c i is an occurrence of P in π.

Conversely, suppose that some injective function φ : X → [kn] is an occurrence of P in π.

For each i ⩽ k, the set {i}×[n] forms a chain of ≼, and therefore it is mapped to an increasing pattern of size n. Coloring this pattern in color c i produces the desired k-coloring. ◀

We show now that the problem where P consists of k independent chains is XP for the parameter k. In fact, we generalize this result to k-weak partial orders (i.e., if P consists of k independent weak orders). Before going further, we denote by 1 i the k-tuple with one element 1 (in position i) and k -1 elements 0. We also denote by < i the partial order on tuples I of intervals, where

▶
I < i I ′ if I j = I ′ j whenever j ̸ = i and x < x ′ whenever x ∈ I i and x ′ ∈ I ′ i .
When a i = |P i | for all i, such a partial matching exists for all permutations π, tuples of intervals I and integers ℓ. When a i = 0 for all i and ℓ = 1, and once π is fixed, such partial matchings coincide with (standard) matchings, and thus we are interested in checking whether a partial matching exists. Finally, for all tuples I and a and for all ℓ ⩽ n, a partial matching φ for (π, I, a, ℓ) exists precisely when one of the following cases occur:

1. φ is a partial matching for (π, I, a, ℓ + 1), i.e., ℓ / ∈ φ(P a );

2. there exists an integer i ⩽ k for which the ≼ i -least element of P min i,a , say x, is such that φ(x) = ℓ and π(ℓ) ∈ I i , and either

x is not the only element of P min i,a , and φ is a partial matching for (π, I, a + 1 i , ℓ + 1), or

x is the only element of P min i,a and there exists a tuple I ′ > i I such that φ is a partial matching for (π, I ′ , a + 1 i , ℓ + 1).

Consequently, we can compute by dynamic programming the list of triples (I, a, ℓ) such that there exists a partial matching for (π, I, a, ℓ): deciding whether adding a triple (I, a, ℓ) to the list simply requires to check which triples of the form (I ′ , a ′ , ℓ + 1) already belong to the list. Since there are less than n 3k+1 triples, this provides us with a Õ(n 6k+2 ) algorithm. ◀

Symmetric Pattern and Pattern-Avoiding π

In this final section, we consider restrictions on the shape of π, via pattern-avoiding restrictions.

Our goal here is to identify tractable cases among classes of permutations avoiding one or more size-3 patterns. We give an almost complete dichotomy of polynomial/NP-hard cases, as shown in Proof. In each of the cases presented below, we define a symmetric dpop P = (P, P) for some partially ordered set P = (X, ≼). Each time, we identify P with the partial order ≼.

Case 1: π is 123-avoiding and separable. We use a reduction from 3-Partition, as illustrated in Figure 6 with permutation π 1 . Let (A, B) be an instance of 1 Polynomial (green/light) and NP-hard (red/dark) cases for DPOP Matching with symmetric dpop and pattern-avoiding permutation π, for combinations of size-3 avoided patterns. For each case, see the referenced proposition and case for more details. Diagonal cases follow from any other hard case in the same row or column. For hard cases, the problem used for reduction is indicated as follows: bic: Biclique, 3P: 3-Partition, bin: Unary Bin Packing, bis: Bisection. For all p ⩽ n, we define a bin gadget b p as the permutation dp(3) ⊕ dp(B -3): we see this gadget as consisting of two parts. Our permutation π is now defined by π = ⊖ n p=1 b p .

Then, our partial order ≼ is defined on a set X of nB elements, noted x i , y i,2 , . . . , y i,ai for each i ⩽ 3n, so that x i ≼ y i,j for all i and j.

If P has an occurrence φ : X → [nB] in π, this occurrence is bijective. Moreover, each element x i is sent to the bottom-left of y i,2 , and thus it must is mapped to the left part of some gadget, say b f (i) . Each element y i,j must then be mapped to the right part of the same gadget. Now, for each p ⩽ n, the set S p = {i : Case 2: π is (132, 213)-avoiding. We use a reduction from Unary Bin Packing, as illustrated in Figure 6 with permutation π 2 . Given an instance (A, B, k) of Unary Bin Packing, where A is a list of integers a 1 , a 2 , . . . , a n larger than 1, we use the same dpop as in Case 1: our partial order ≼ is defined on a set X of nB elements, noted x i , y i,2 , . . . , y i,ai

f (i) = p} is of size 3,
for each i ⩽ n, so that x i ≼ y i,j for all i and j. However, this time, our gadget b p is the permutation ip(B), and our permutation π is again defined by π = ⊖ n p=1 b p .

If P has an occurrence φ : X → [nB] in π, this occurrence is bijective. Each element x i is sent to some gadget, say b f (i) , and the elements y i,j must then be mapped to the same gadget. Now, for each p ⩽ k, let S p = {i : f (i) = p}. Exactly B elements of X are mapped to the gadget b p , which means that i∈Sp a i = B. This means that (S, B, k) is a positive instance of the Unary Bin Packing problem.

Conversely, given a partition S 1 ∪ . . . ∪ S k of [n] such that i∈Sp a i = B for each i, we build an occurrence of P in π by mapping the B elements x i and y i,j (for i ∈ S p ) to b p .

Case 3: π is (132, 321)-avoiding. We use a reduction from Bisection, as illustrated in elements: 2nW elements, noted x v,i for each v ∈ V and i ⩽ W , and m elements, noted y e for each e ∈ E. This order contains the relations x v,i ≼ y e for which v is an endpoint of e.

Assume that there exists a mapping of P into π. For each v ∈ V , and since C has size k < W , at least one of the elements x v,i is mapped to A, in which case we say that v has type A, or to B, in which case v has type B. Then, each vertex has at least one type, and possibly both. We partition V into three sets V A , V B , V AB containing the vertices of type A, B and both A and B, respectively. Moreover, for each v ∈ V A , each element x v,i must be mapped either to A or to C: these two parts together contain L + k elements, so |V A | ⩽ (L + k)/W = n + 1 -1/W , and

|V A | ⩽ n. Similarly, |V B | ⩽ n.
We build a set V 1 as the union of V A with n -|V A | vertices of V AB , and

V 2 as V \ V 1 , so that |V 1 | = |V 2 | = n. Moreover, for every v ∈ V 1 (resp., v ∈ V 2 ), some element x v,i , say x v,1 ,
is mapped to A (resp., to B). Then, each edge e = (u, v) that is split by (V 1 , V 2 ) must be mapped to a point above some point of A and to the right of some point of B. This means that y e is mapped to C, and that (V 1 , V 2 ) splits at most k edges, i.e., is a valid bisection.

Conversely, given a bisection (V 1 , V 2 ) splitting at most k edges, we map P into π as follows: map elements x v,i for v ∈ V 1 (resp., V 2 ) to the first nW elements of A (resp., B), map elements y e for which e is induced by V 1 (resp., V 2 ) to the following elements of A (resp. B), and finally map all elements y e such that e is split by (V 1 , V 2 ) into C. This mapping is an occurrence of P in π.

Case 4: π is (231, 312)-avoiding. We use a reduction from Biclique, as illustrated in Case 5: π is (132, 312)-avoiding. We also use a reduction from Biclique, as illustrated in Figure 6 with permutation π 2 . Our partial order ≼ is the same as in Case 4, and our permutation π is defined by π Proof. In each of the cases presented below, we are given a permutation π and a symmetric dpop P = (P, P) for some partially ordered set P = (X, ≼). Each time, we identify P with the partial order ≼. Finally, the elements of singleton sets S i can be mapped to the remaining places in π.

= ((dp(n -k) ⊕ ip(k)) ⊖ dp(k)) ⊕ ip(n -k).
Case 3: π is (123, 321)-avoiding. Erdős-Szekeres theorem [START_REF] Erdös | A combinatorial problem in geometry[END_REF] proves that n ⩽ 4.

Concluding Remarks

Some open complexity questions remain among the parameters we identified for DPOP Matching. For semi-total dpops, the complexity is open for constant width, and for most classes of pattern-avoiding permutations (although, according to Propositions 7 and 10, the problem is NP-hard when π avoids 1234 or 312, respectively). For symmetric dpops, it would be interesting to settle the complexity status of deciding whether a dpop occurs in a (231, 321)-avoiding or (312, 321)-avoiding permutation. In particular, for these cases, we conjecture that the problem becomes polynomial when height(P ) is constant.

Regarding the original puzzle formulation of the problem, an interesting question is to generate instances that yield a unique solution, i.e., given a permutation π, find a dpop with a unique occurrence in π. This can be done by using a semi-total dpop (e.g., take X with |X| = |π|, let P p be a total order and P v be an empty order), but one could try to minimize |X| or the number of pairs of comparable elements in P (i.e., the number of clues) in order to have a unique solution.

  together with their geographic coordinates, find (if they exist) five cities, say A, B, C, D and E, such that: A and C are west of D and north of B, E is east of B and south of A, D is west of B and north of A and C.

  the information is minimal: requiring C is west of B is unnecessary since C is west of D and D is west of B. One solution is A = Praha, B = Brno, C = Plzeň, D = Liberec and E = Olomouc. Note that the solution is not unique, as A = Plzeň, B = Jindřichův Hradec, C = Cheb, D = Ústí nad Labem and E = Brno is another solution.

9 H r a d e c K r ál o v é 10 B r n o 11 O l o m o u c 12 Z lí n 13 O p a v a 14 O s t r a v a 15 KFigure 2 8 .

 910111213141528 Figure 2 Permutation π = 11 6 14 12 1 2 15 10 13 3 5 4 9 7 8 corresponding to the map from Figure 1. The solution of our puzzle, depicted Figure 1, is also represented.

Figure 3 A

 3 Figure3A dpop P = (Pv, Pp) representing the pattern for our puzzle, together with three distinct occurrences. Note that partial orders are represented by Hasse diagrams, i.e., a bottom-up path in Pv (resp., Pp) implies a bottom-up (resp., left-right) relation in the occurrence of P in π.

5 a 3 c 3 b 4 b 3 a 4 c 4 Figure 4

 544 Figure 4 Top left: vertex cover (in red) in a 5-vertex graph G. Bottom left: partially ordered set Pv constructed from G. Right: an occurrence of P in π obtained from our size-3 vertex cover.

▶ Proposition 9 .

 9 [n], the elements π ϕ(x1) , . . . , π ϕ(x |X| ) must form an increasing subsequence of π. Conversely, any size-|X| increasing subsequence of π can be used as an image for ϕ, so in this setting DPOP Matching corresponds to the longest increasing subsequence problem, which can be solved in O(n log log |X|) time[START_REF] Crochemore | Fast computation of a longest increasing subsequence and application[END_REF]. ◀To simplify the exposition of our next result, we introduce a new problem that may be of independent interest. Given a positive integer k and a permutation π ∈ S(kn), Balanced k-Increasing Coloring is the problem of deciding whether there exists a balanced kcoloring of π (i.e., a partition of [kn] into k subsets of size exactly n) such that each color induces an increasing subsequence of π. Balanced k-Increasing Coloring for 312-avoiding permutations is W[START_REF] Ahal | On complexity of the subpattern problem[END_REF]-hard for the parameter k.

Figure 5

 5 Figure 5 Reduction from Unary Bin Packing to Balanced k-Increasing Coloring for the list 6, 4, 3, 3, 3, 2, 2, 1, which admits the partition ({6}, {4, 2}, {3, 3}, {3, 2, 1}), and the integers B = 6, k = 4. Left: dpop P that consists of k chains, each of length n + B. Right: 312-avoiding permutation π that consists of n blocks. Each color/shape induces an increasing subsequence of π.

6 a 3 = 4 a 5 = 4 a 7 = 3 a 9 = 3 a 2 = 4 a 4 = 3 a 6 = 2 a 8 = 4 PFigure 6

 634547393244362846 Figure 6 Reductions from 3-Partition and Unary Bin Packing to DPOP Matching on 123avoiding and (132, 213)-avoiding permutations. Left: the height-2 dpop P used in both reductions. Right: the 123-avoiding and (132, 213)-avoiding permutations used in each reduction. The mapping of three subsets of P corresponding to a first bin gadget is highlighted in each figure.

  and exactly B elements of X are mapped to the gadget b p , which means that i∈Sp a i = B. Moreover, S 1 ∪ . . . ∪ S p forms a partition of [3n], hence it yields a 3-partition of A. Conversely, given a partition S 1 ∪ . . . ∪ S n of [3n] such that |S p | = 3 and i∈Sp a i = B for each p, we build an occurrence of P in π by mapping the three elements x i (for i ∈ S p ) to the left part of b p , and the B -3 elements y i,j (for i ∈ X p ) to the right part of b p .

Figure 7 .Figure 7

 77 Figure 7. Given a graph G = (V, E) and an integer k, the Bisection problem consists in deciding whether V admits a partition V 1 ∪ V 2 such that |V 1 | = |V 2 | and that splits at most k edges (i.e., at most k edges have one endpoint in V 1 and one endpoint in V 2 ). Our reduction is as follows. Let n = |V |/2, m = |E|, W = m + k + 1, and L = nW + m.Our partition π is defined by π = (ip(L) ⊖ ip(L)) ⊕ ip(k). These three parts of π are noted A, B and C, from left to right. Then, our partial order ≼ is defined on a set X of 2nW + m

Figure 8 with permutation π 1 .Figure 8

 18 Figure 8 with permutation π 1 . Given a bipartite graph G = (V, E) and an integer k, the Biclique problem consists in deciding whether V admits a complete bipartite subgraph K k,k . If V = A ∪ B is a partition of V into two independent sets, adding independent vertices if needed allows us to assume that A and B have the same size n, and that no vertex in either side is fully connected to the other side. Our permutation π is defined by π = dp(n -k) ⊕ dp(2k) ⊕ dp(n -k). These three parts of π are noted b 1 , b 2 and b 3 . Our partial order ≼ is the order on V such that x ≼ y whenever x ∈ A, y ∈ B and {x, y} / ∈ E. Consider a mapping of P into π. For each element x ∈ A, there exists y ∈ B such that x ≼ y, and therefore x cannot be mapped into b 3 . Symmetrically, no element y ∈ B may be mapped into b 1 . Overall, since |π| = |V | = 2n, b 1 contains n -k elements from A, b 3

Cases 6 - 9 :Case 7 :Case 8 :Case 9 :▶ 13 .

 6978913 These three parts of π are noted b 1 , b 2 , b 3 and b 4 . Consider a mapping of P into π. For each element y ∈ B, there exists x ∈ A such that x ≼ y, and therefore y cannot be mapped into b 1 or b 3 . Thus, and since |B| = n, the elements of B are mapped to b 2 or b 4 , and the elements of A are mapped to b 1 or b 3 . Hence, b 2 contains a size-k subset B ′ of B and b 3 contains a size-k subset A ′ of A. No element of b 2 is comparable to any element of b 3 , and therefore (A ′ , B ′ ) is a biclique. Conversely, if G has a biclique (A ′ , B ′ ), we map all elements of A \ A ′ into b 1 , all elements of A ′ into b 3 , all elements of B ′ into b 2 and all elements of B \ B ′ into b 4 . This mapping satisfies all relations x ≼ y with x ∈ A and y ∈ B, except for x ∈ A ′ and y ∈ B ′ , but indeed there is no such relation since (A ′ , B ′ ) is a biclique. These cases are symmetric to Cases 3, 5, 5 and 7, respectively. Indeed, if (P, π) is an instance of DPOP Matching with P a height-2 symmetric dpop, (P ∂ , π c r ) and (P, π -1 ) are equivalent instances of DPOP Matching with height-2 symmetric dpops, and Case 6: if π avoids 132 and 321 (Case 3), π c r avoids 132 c r = 213 and 321 c r = 321; if π avoids 132 and 312 (Case 5), π c r avoids 132 c r = 213 and 312 c r = 312; if π avoids 132 and 312 (Case 5), π -1 avoids 132 -1 = 132 and 312 -1 = 231; if π avoids 213 and 312 (Case 7), π -1 avoids 213 -1 = 213 and 312 -1 = 231.◀ Proposition DPOP Matching is in P for symmetric dpop P if one of the following restrictions on π occurs:

Case 1 :

 1 π is (123, 231)-avoiding. There exist integers k, ℓ and m, with sum n, such that π = dp(k) ⊖ (dp(ℓ) ⊕ dp(m)). These three parts of π are noted b 1 , b 2 and b 3 . Then, for every pair (u, v) such that u ≺ v, we must map u into b 2 and v into b 3 . Such values can be mapped greedily, since elements in b 2 are pairwise incompatible, as well as those in b 3 . Thus

Cases 4 - 5 :Case 4 :Case 5 :

 4545 These cases are symmetric to Cases 1 and 2, respectively. Indeed, if (P, π) is an instance of DPOP Matching with P a height-2 symmetric dpop, (P ∂ , π c r ) and (P, π -1 ) are equivalent instances of DPOP Matching with height-2 symmetric dpops, and if π avoids 123 and 231 (Case 1), π -1 avoids 123 -1 = 123 and 231 -1 = 312; if π avoids 123 and 132 (Case 2), π c r avoids 123 c r = 123 and 132 c r = 213. ◀

  and hence si∈Sj s i = B. Therefore, the n items s 1 , s 2 , . . . , s n can be packed into k bins, each

	of capacity B.	◀
	Most of the interest in Proposition 9 stems from the following proposition.
	▶ Proposition 10. DPOP Matching for symmetric dpop and 312-avoiding permutations is
	W[1]-hard for the parameter width(P ).

Table 1 .

 1 Hardness results are proven in Proposition 12, and also apply to height-2 dpops. Polynomial cases are proven in Proposition 13 and apply to dpops of any height.

▶ Proposition 12. DPOP Matching for height-2 symmetric dpop P and permutation π is NP-hard even if π is separable (it avoids 2413 and 3142) and one of the following restrictions occurs: 1. π is 123-avoiding; 2. π is (132, 213)-avoiding; 3. π is (132, 321)-avoiding; 4. π is (231, 312)-avoiding; 5. π is (132, 312)-avoiding; 6. π is (213, 321)-avoiding; 7. π is (213, 312)-avoiding; 8. π is (132, 231)-avoiding; 9. π is (213, 231)-avoiding.

  , P can be mapped into π if and only if it has height at most 2, there are at most a elements that are lower bounds, and at most b elements that are upper bounds. Note that, if P is not symmetric, the problem becomes NP-hard, since reversing the horizontal order of P p and π transforms π into the (132, 321)-avoiding permutation of the NP-hard Case 3 in Proposition 12. Case 2: π is (123, 132)-avoiding. The permutation π is a skew sum π = ⊖ k p=1 d p of patterns of the form d p = dp(a p ) ⊕ dp(1) for some integer a p ⩾ 0. Then, no two elements in X can share a strict lower bound, i.e., if u ≺ v and u ≺ w then v = w. Thus, P is of height at most 2, and there exists a partition S 1 ∪ . . . ∪ S ℓ of X in which each set S i contains a distinguished element s i , such that x ≼ s i if and only if x ∈ S i . Up to reordering the patterns d p and the sets S i , which are pairwise incomparable, we assume that a 1 ⩾ a 2 ⩾ . . . ⩾ a k and that |S 1 | ⩾ |S 2 | ⩾ . . . ⩾ |S ℓ |. Let also m be the number of sets S i with size at least 2.

Each set S i must be mapped into a single pattern, say d p(i) , and if i ⩽ m, i.e., if

|S i | ⩾ 2,

the element s i must be mapped to the unique top-right element of d p(i) . Such a mapping exists if and only if k ⩾ m and a i ⩾ |S i | -1 for all i ⩽ m: we shall choose p(i) = i and map greedily the elements of S i \ {s i } to the bottom-left part of d i .