Andreas Kosmala
email: kosmala@fb9-ti.uni-duisburg.derigoll@fb9-ti.uni-duisburg.de

Gerhard Rigoll

Stéphane Lavirotte
email: stephane.lavirotte@sophia.inria.fr

Loïc Pottier
email: loic.pottier@sophia.inria.fr

On-Line Handwritten Formula Recognition using Hidden Markov Models and Context Dependent Graph Grammars

This paper presents an approach for the recognition of on-line handwritten mathematical expressions. The Hidden Markov Model (HMM) based system makes use of simultaneous segmentation and recognition capabilities, avoiding a crucial segmentation during pre-processing. With the segmentation and recognition results, obtained from the HMMrecognizer, it is possible to analyze and interpret the spatial two-dimensional arrangement of the symbols. We use a graph grammar approach for the structure recognition, also used in off-line recognition process, resulting in a general tree-structure of the underlying input-expression. The resulting constructed tree can be translated to any desired syntax (for example: Lisp, L A T E X, OpenMath . . . ).

Introduction

Currently, most people who need to enter mathematical expressions for a computational treatment need to type formulae in an ASCII form or use an editor. But regarding today's word processors or mathematical software tools, the input interface still offers poor convenience for editing expressions. Obviously, handwritting could serve as a superior man machine interface for the input of formulae from lots of different domains, like physics, mathematics, chemistry. . . . Beside the mentioned desk-top applications, such a recognition engine could also be used as an interface for the upcoming keyboard-less "personal digital assistants" (PDA), in order to integrate complex calculator facilities. According to [START_REF] Blostein | Recognition of Mathematical Notation[END_REF], the solution for the mathematical expressions recognition can be sub-divided into two main problems: segmentation and recognition, analysis and interpretation of the symbol's spatial-arrangement.

System overview

The system proposed here is capable of recognizing mathematical expressions with a set of 100 different characters or symbols in a writer dependent mode.

Beside small and capital letters, and digits, the system contains several mathematical symbols (+ -• : / ˆ√ , =<>≤≥→↔≈!∞), as well as some of the most frequently used Greek letters (α, β, γ, λ, μ, Δ, π, ω, , τ, φ) and some parentheses ((, ), [, ], {, }). To model the spaces between the symbols, an additional 'space' model is introduced. For initialization, each of these symbols is written several times well separated on a sheet. For an embedded training, 100 common mathematical or physical formulae are collected as training set and an additional set of 30 formulae is used as test set, represented by 150000 feature vectors and 45000 feature vectors, respectively. Figure 1 gives an overview of the entire system. The processing levels as they are shown, will be described in the following sections.

On-line character recognition

With the presented approach, it is not necessary to enter each single symbol well separated, neither spatially nor temporally. This continuous formula recognition can be considered as a kind of sentence recognition without previous word segmentation. The segmentation of the distinct words is realized within the HMM framework, applying a special 'space' HMM for the detection of word boundaries. Instead of attempting to identify each symbol separately, the efficient HMM-based decoding techniques allow a complete identification of the entire formula string. Another advantage of the HMM approach for this application is the possibility to incorporate high level syntactic constraints (e.g. grammars) directly into the low level recognition process.

Pre-processing and low-level feature extraction

The raw data is captured with a constant sample rate of 200 Hz, resulting in a temporal vector sequence of the Cartesian coordinates of the pen position. The preprocessing step is a re-sampling of the captured pen trajectory with vectors of constant length [START_REF] Rigoll | A Comparison between Continuous and Discrete Density Hidden Markov Models for Cursive Handwriting Recognition[END_REF]. Beside the data reduction effects of 1:2 up to 1:3, a further advantage of the re-sampling is, that the implicitly given writing speed, resulting from different distances between two samples and the constant sample rate, is eliminated. Writing speed is especially in the context of formula recognition supposed as a highly inconsistent feature, because obviously identical handwriting images can be produced with completely different writing speeds. For instance, this could happen if the writer holds on to think about his currently written formula. It should be stressed, that the re-sampling preserves the spatial information, i.e. the Cartesian pen coordinates.

On the recognition level, several features are extracted from the re-sampled vector sequence. The first type of features are the online features [START_REF] Rigoll | A Comparison between Continuous and Discrete Density Hidden Markov Models for Cursive Handwriting Recognition[END_REF], which is the orientation α of the re-sampling vectors coded in sine and cosine as well as the sine and cosine of the differential angle Δα of two successive re-sampling vectors. The third online feature is the pen pressure, which is extracted as a binary feature and indicates if the pen is set down or lifted. The pen pressure is helpful to model word or symbol boundaries within an expression. The second type of feature is an off-line feature [START_REF] Kosmala | An Investigation of the Use of Trigraphs for Large Vocabulary Cursive Handwriting Recognition[END_REF][START_REF] Manke | Combining Bitmaps with Dynamic Writing Information for On-Line Handwriting Recognition[END_REF], which is a sub-sampled bitmap, sliding along the pen-trajectory after re-sampling. In a subsequent step, each of these feature streams, except the binary pressure, is quantized with a vector quantizer (VQ). As vector quantizer, usually a k-means VQ is used or a MMI neural net (NN) VQ [START_REF] Rigoll | An Investigation of Context-Dependent and Hybrid Modeling Techniques for Very Large Vocabulary On-Line Cursive Handwriting Recognition[END_REF] with different codebook sizes for each feature, respectively. Subsequently, the resulting discrete multi-stream is presented to the HMMs.

HMM training and recognition

For the modeling of the symbols, discrete left to right HMMs without skips and with different numbers of states are used. With the features described above, discrete, i.e. hybrid NN-HMMs have shown to be superior compared to continuous HMMs [START_REF] Rigoll | An Investigation of Context-Dependent and Hybrid Modeling Techniques for Very Large Vocabulary On-Line Cursive Handwriting Recognition[END_REF]. One reason for this is the discrete nature of the pen-pressure (pen up or pen down). Furthermore, the α and Δα-features are due to the constant resampling vector length distributed on the unit circle, which enables an efficient vector quantization, while Gaussian pdfs as they are commonly used in continuous HMM systems can not be sufficiently mapped to this kind of distribution. HMMs with 12 states are used for capital letters and larger mathematical operators, like sum or product. Small letters and smaller operators are modeled with HMMs with 8 states, while very short symbols (.,) are modeled with 3 state HMMs.

For recognition purposes, a synchronous Viterbi decoding is used [START_REF] Rabiner | A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition[END_REF]. By means of the Viterbi algorithm, it is possible to determine the most likely state sequence q of a set of HMMs λ for a given sequence of frames O.

P (O, q |λ) = max q P (O, q|λ) (1)
This can be very effectively exploited for formula recognition by analyzing the resulting alignment of each feature frame to its best matching HMM state, with the result, that the indexes of start-and end-frames of the recognized symbols within an expression can be taken directly from the decoding or recognition process. The achieved recognition with the simultaneous segmentation of the symbols is an important information for further extraction of geometrical features for the structure analysis. The initialization of the HMMs is realized with the Viterbi training using the separate collected, isolated samples of the symbols. HMM parameter optimization is carried out by an iterative application of the Viterbi algorithm in order to find an optimal state sequence, and a reestimation path of the pdfs.

For the embedded training of the complete formulae, the Forward Backward algorithm is used. Again, in an iterative way, optimized HMM parameters λ can be found by a maximization of the Kullback-Leibler distance Q(λ, λ):

max λ Q(λ, λ) = max λ q P (q|O, λ) log P (O, q| λ) (2)
The re-estimation formulae for the HMM parameter set can be derived directly from Q(λ, λ) [START_REF] Rabiner | A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition[END_REF].

Structure analysis

As described before, the result from the Viterbi decoder is not only the transcription (the sequence of recognized words and symbols) but also the start-and end-frames of each symbol. The following sub-sections describe, how this information can be used for further processing.

Spatial alignment

The temporal alignment of frames together with the resampled vector-data allows the extraction of geometrical features of the symbols or a spatial alignment. These geometrical features are the center of a recognized symbol and the size and position of its bounding box. As shown in Fig. 2, the bounding box of a word is extracted by stepping through the re-sampled vector sequence starting at the start-frame number of the current word until the stop-frame number is reached, and searching for minima and maxima in x-and y-direction in the determined part of the sequence of Cartesian vectors. The spatial alignment for each symbol is characterized by the parameters of the bounding box up, lo, le, ri and denotes the upper, lower, left and right boundary of the symbol. The centers of the bounding boxes mx and my of each symbol are shown in the last two columns in figure 1 and figure 2.

Before starting analysis of spatial alignment, we introduce other computed information which will be attributes of recognized symbols. The introduction of this data will help to recognize formula's structure.

Deduction of criterions

Next step is to deduce an approximative baseline depending on the recognized symbol and to compute a relative size for each recognized character in order to make some groups of symbols. This last process is not just depending on the bounding box size but is also relative to the recognized symbol. For example, if we compare "e" and "g" just considering the size of the bounding box, it will lead to the conclusion that "e" is smaller than "g". So we ponder each symbol by a relative size depending on the manner to write the character. This can be done while collecting symbols during the training set. All this information will be used to determine the symbol potentially in a subscript or a superscript position.

Lexical analysis

Before starting the syntax recognition we give a lexical type to each recognized symbol. This method helps us to locate operators and avoid some parsing mistakes. It was first mentioned in [START_REF] Lee | Design of a mathematical expression recogntion system[END_REF] as an approach to help subscript and superscript recognition. Thus, recognition is based on spatial coordinates as well as local context depending on the lexical type. This system prevents misrecognition of relationship between two symbols. For example, it's a good way to avoid the detection of "." as a subscript of x in the example "x.y", because a dot is not supposed to be a subscript for a letter. For a well formed printed document recognition, this problem of spatial arrangement is not as important as in a hand printed recognition because the writer does not follow the writing baseline exactly. This technic is helpful for subscript and superscript recognition but also to determinate other spatial relationship and especialy to avoid some of them depending on lexical rules.

Two dimensional parsing

The goal is now to generate a tree with recognized symbols as it is shown in figure 1.

Graph construction

With all these elements (symbols, lexical type, bounding box, approximative baseline and size) we have a lot of graphical information that we must translate in a more structured format to be usable and parsable. So, we introduce graph which provides a good formalism to describe structural manipulations of multi-dimensional data.

The graph building process is very important because too many links lead to ambiguities and with too few links one looses important data. This mechanism of data graph building using the spatial arrangement of symbols is described in [START_REF] Lavirotte | Mathematical formula recognition using graph grammar[END_REF]. It was tested with paper printed documents. We have modified and enhanced the system to improve links between symbols in graph and we have reduced constraints for links creation to suit handwriting style, which is more "random" than style of printed documents.

With the first small tests, we had good results for the building process. But with bigger formulae, the process was too slow, due to a O(n 2 ) complexity. So we introduced an optimization for graph construction : we now make a subdivision of the space containing symbols, in order to avoid making some neighborhood tests with symbols which are obviously too far away from each other.

For a formula containing 116 symbols, without any optimization for the construction of the first data graph, computation time reaches 35 seconds on a Pentium 200. With a subdivision of space, it drops to less than 4 seconds. The observed speed-up (around 9 for this sample) is not always as high, but for smaller samples computation time is less than 1 second, with or without optimization. Figure 3 shows the evolution of computation time for the mentionned sample, regarding subdivision of the plane along the x and y axis.

Graph parsing

In [START_REF] Lavirotte | Optical formula recognition[END_REF] we have defined a general class of graph grammars with contexts, where, after a theoretical study of their properties, we showed how to precisely and automatically solve ambiguities in these grammars.

A graph grammar acts on a graph as a rewriting system in a bottom-up manner, rewriting matched sub-graph into a single node containing the syntax-tree of the recognized expression. Improvements have to be done on computation time for graph rewriting. This motivates the next section.

Parsing optimization

The parsing algorithm is simple: we just iteratively apply the first rule which can be, and stop when no more apply.

A rule is given by a term G -{C 1 , . . .} → N , where G is the sub-graph to be matched, {C 1 , . . .} is the set of excluded contexts, and N is the produced node. Such a rule can be applied to a graph G if:

• a substitution σ exists such that σG is a G sub-graph,

• for each context C i , there is no substitution τ such that τC i is a sub-graph of G , and τ = σ on the intersection of their supports.

When these conditions are satisfied, applying rule consists in replacing subgraph σG of G by a single node σN .

During the parsing process, only local modifications are made to graph. So we very frequently test matching of subgraphs, particularly contexts, with few success: if a context occurs in several rules (which is the case in practice), and if it occurs in graph, then these rules will not apply, and we will test these occurrences at each step of parsing.

To avoid this unnecessary complexity, we exploit the locality of rewriting by maintaining, during the parsing of a graph G , two global lists:

• a list G of all pairs (G, σ) such that G is the graph pattern of a rule, and σG is a sub-graph of G ,

• a list C of all pairs (C, τ ) such that C is a context of a rule, and τC is a sub-graph of G .

Searching a rule to apply can then be made by inspecting the lists G and C to find a pair (G, σ) such that no pair (C, τ ) exists such that τ = σ on the intersection of their supports.

After applying a rule, we have to update the lists G and C. But since only a small part of G is modified, the two lists are also locally modified. With an adapted data structure (with pointers from the graph G to lists G and C, and pointers from G and C to G ), this can be achieved efficiently.

In fact, this process allows to replace a O(n 2 ) by a O(n) complexity for parsing process (where n is the number of edges of the graph to be parsed), which is optimal.

Conclusion

Presented approach leads to two major improvements:

1. Constraints concerning the writing (from left to right and top to bottom) as introduced in [2] can be relaxed.

2. The output is a general description of the handwritten expression in a tree format which can be translated to any other format (Lisp, L A T E X, OpenMath. . . ).

Graph grammar was used to recognize mathematical expressions in printed documents as presented in [START_REF] Blostein | Recognition of Mathematical Notation[END_REF] and [START_REF] Lavirotte | Mathematical formula recognition using graph grammar[END_REF]. With some more work, we have adapted this method to handwriting recognition of mathematical expressions. The same software is used in both case, just needing to specify the input type (it could be automated). Considering the method used in [START_REF] Kosmala | Recognition of On-Line Handwritten Formulas[END_REF], some constraints were made on how the formula should be written (for left to right and from top to bottom). With this method, we do not have any assumption on how the formula should be written, so there is no constraint for writers and it is more adaptive to different writer style. Figure 4 gives two samples of recognized formulae.

The advantage of a graph grammar system is that it is adaptive to any kind of mathematical notation. To introduce a new notation, one just needs to write the right parsing rule. We are currently working on recognition of handwritten vectors or matrices notations.

In summary, graph rewriting is a good approach for mathematical expression recognition as well as for printed documents and for handwritten recognition. To our knowledge, it is the first experience in using graph grammars in handwritten mathematical formula recognition.

Figure 1 .

 1 Figure 1. System overview

Figure 2 .

 2 Figure 2. Spatial-from temporal alignment

Figure 3 .

 3 Figure 3. Time optimization for graph building

Figure 4 .

 4 Figure 4. Recognition results


René Van Bevern
email: rene.vanbevern@tu-berlin.de

Matthias Mnich
email: mmnich@mmci.uni-saarland.de

Rolf Niedermeier
email: rolf.niedermeier@tu-berlin.de

Mathias Weller
email: mathias.weller@tu-berlin.de

Interval Scheduling and Colorful Independent Sets

The NP-hard Independent Set problem is to determine for a given graph G and an integer k whether G contains a set of k pairwise nonadjacent vertices. The problem has numerous applications in scheduling, including resource allocation and steel manufacturing. There, one encounters restricted graph classes such as 2-union graphs, which are edge-wise unions of two interval graphs on the same vertex set, or strip graphs, where additionally one of the two interval graphs is a disjoint union of cliques.

We prove NP-hardness of Independent Set on a very restricted subclass of 2-union graphs and identify natural parameterizations to chart the possibilities and limitations of effective polynomial-time preprocessing (kernelization) and fixed-parameter algorithms. Our algorithms benefit from novel formulations of the computational problems in terms of (list-)colored interval graphs.

Introduction

Many scheduling problems can be formulated as finding maximum independent sets in certain generalizations of interval graphs [START_REF] Kolen | Interval scheduling: A survey[END_REF]. Intuitively, finding a maximum number of pairwise non-adjacent vertices in a graph (this is the Independent Set problem) corresponds to scheduling a maximum number of jobs (represented by intervals) without conflicts. In this context, we consider two popular and practically motivated graph models, namely 2-union interval graphs [START_REF] Bar-Yehuda | Scheduling split intervals[END_REF] (also called 2-union graphs) and strip graphs [START_REF] Halldórsson | Strip graphs: Recognition and scheduling[END_REF].

A graph G = (V, E) is a 2-union graph if it can be represented as the union of two interval graphs G 1 = (V, E 1 ) and G 2 = (V, E 2 ) on the same vertex set V , that is, G = (V, E 1 ∪ E 2 ). There are numerous applications of solving (weighted) Independent Set on 2-union graphs, including scheduling problems such as resource allocation [START_REF] Bar-Yehuda | Scheduling split intervals[END_REF] or coil coating in steel manufacturing [START_REF] Höhn | Integrated sequencing and scheduling in coil coating[END_REF].

2-Union Independent Set:

Input: Two interval graphs G 1 = (V, E 1 ), G 2 = (V, E 2 ) and an integer k. Question: Does G = (V, E 1 ∪ E 2 ) have an independent set of size k?

We found a helpful natural embedding of 2-Union Independent Set into a more general problem by replacing 2-union graphs with list-colored interval graphs and searching for colorful independent sets: 1Colorful Independent Set: Input: An interval graph G = (V, E), a multicoloring col : V → 2 {1,...,γ} , and an integer k. Question: Does G have a colorful independent set of size k? An advantage of this model is that we only have to deal with one interval graph instead of two merged ones. Indeed, the modeling proved very useful when studying Independent Set on strip graphs, an important subclass of 2-union graphs. We believe that introducing our colorful view on finding independent sets and scheduling is of independent interest and might be useful in further studies. This "colored view on scheduling" leads to a useful reformulation of the classic Job Interval Selection problem [START_REF] Halldórsson | Strip graphs: Recognition and scheduling[END_REF][START_REF] Nakajima | Complexity results for scheduling tasks with discrete starting times[END_REF]. The task is to find a maximum set of jobs that can be executed, where each job has multiple possible execution intervals, each job is executed at most once, and a machine can only execute one job at a time. We state this problem using its classical name, but formulate it in terms of colored interval graphs, where the colors correspond to jobs and intervals of the same color correspond to multiple possible execution times of this job:

Job Interval Selection: Input: An interval graph G = (V, E), a coloring col : V → {1, 2, . . . , γ}
and an integer k. Question: Does G have a colorful independent set of size k? Here, the definition of "colorful" 1 degenerates to "no two intervals in the independent set have the same color".

Previous results. For 2-Union Independent Set, the following results are known. The problem remains NP-hard even when the two interval graphs are proper (unit interval) [START_REF] Bafna | Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)[END_REF]. When restricted to so-called 5-claw-free graphs (which comprises the case that both input interval graphs are proper), Bafna et al. [START_REF] Bafna | Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)[END_REF] provided a polynomial-time ratio-3.25 approximation. Bar-Yehuda et al. [START_REF] Bar-Yehuda | Scheduling split intervals[END_REF] showed that the vertex-weighted optimization version of 2-Union Independent Set has a polynomial-time ratio-4 approximation (indeed, they showed a ratio-2t approximation for the generalization to t-union graphs). Recently, Höhn et al. [START_REF] Höhn | Integrated sequencing and scheduling in coil coating[END_REF] considered so-called m-composite 2-union graphs (which has applications in coil coating) and developed a dynamic programming algorithm running in polynomial time with the polynomial degree depending on m. This generalizes a result of Jansen [START_REF] Jansen | Generalizations of assignments of tasks with interval times[END_REF], who gave such an algorithm for a subclass of m-composite 2-union graphs. Concerning parameterized complexity, Jiang [START_REF] Jiang | On the parameterized complexity of some optimization problems related to multiple-interval graphs[END_REF] answered an open question of Fellows et al. [START_REF] Fellows | On the parameterized complexity of multiple-interval graph problems[END_REF] by proving 2-Union Independent Set to be W [START_REF] Bafna | Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)[END_REF]-hard for the parameter "solution size k". This W [START_REF] Bafna | Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)[END_REF]-hardness result holds even when both input interval graphs are proper.

Introduced by Nakajima and Hakimi [START_REF] Nakajima | Complexity results for scheduling tasks with discrete starting times[END_REF] (using a different notion), Job Interval Selection was shown APX-hard by Spieksma [START_REF] Spieksma | On the approximability of an interval scheduling problem[END_REF], who also provided a ratio-2 greedy approximation algorithm. Chuzhoy et al. [START_REF] Chuzhoy | Approximation algorithms for the job interval selection problem and related scheduling problems[END_REF] improved this ratio to 1.582. Halldórsson and Karlsson [8] introduced the equivalent notion of Job Interval Selection as Independent Set on strip graphs, which are 2-union graphs where one of the two input interval graphs is a cluster graph. They showed fixed-parameter tractability for a structural parameter and for the parameter "total number of jobs". In related work, Jansen [START_REF] Jansen | Transfer flow graphs[END_REF] considered Independent Set on unions of cographs and cluster graphs (the latter being disjoint unions of cliques).

New results. The main focus of this work is on initiating a systematic parameterized complexity study (particularly featuring kernelization results) for the three NP-hard problems Colorful Independent Set, 2-Union Independent Set, and Job Interval Selection (here listed in descending degree of generality). Doing so, we also discuss the relevance and interrelationships of several parameterizations. For Colorful Independent Set, we provide an O(2 γ • n 3 )-time dynamic-programming algorithm for the parameter "number γ of colors". For 2-Union Independent Set, this result translates to a O(2 #mC min • n 3 )-time algorithm, where #mC min denotes the minimum of the numbers of maximal cliques in the two input interval graphs. Moreover, we provide an NP-hardness proof for 2-Union Independent Set, even when restricted to the case that one input graph is a collection of paths on three vertices and the other is a collection of edges and triangles. In contrast, if both input graphs are cluster graphs, we show that, 2-Union Independent Set can be solved in O(n 1.5 ) time, improving on the O(n 3 ) time algorithm [START_REF] Sbihi | Algorithme de recherche d'un stable de cardinalite maximum dans un graphe sans etoile[END_REF] implied by the claw-freeness of unions of two cluster graphs. Next, stimulated by Jiang's [START_REF] Jiang | On the parameterized complexity of some optimization problems related to multiple-interval graphs[END_REF] W [START_REF] Bafna | Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)[END_REF]-hardness result for the parameter "solution size k", we discuss natural structural parameters that are lower-bounded by or closely related to k. Systematically exploring these parameters, we chart the border between tractability and intractability for 2-Union Independent Set. In particular, we initiate the study of the power of polynomial-time data reduction (known as kernelization in parameterized algorithmics) and show that 2-Union Independent Set has a cubic-vertex problem kernel with respect to the parameter "maximum number of maximal cliques in one of the two input interval graphs". This improves to a quadratic-vertex kernel if both input interval graphs are proper. We remark that parameterizing by the number(s) of maximal cliques allows for generalizing previous results of Halldórsson and Karlsson [START_REF] Halldórsson | Strip graphs: Recognition and scheduling[END_REF]. Our results for 2-Union Independent Set carry over to the vertex-weighted case.

For Job Interval Selection (or, equivalently, Independent Set restricted to strip graphs), our main result refers to polynomial-time preprocessing: while we prove the nonexistence (assuming a standard complexity-theoretic conjecture) of polynomial-size problem kernels even for Job Interval Selection with respect to the combination of the parameters "maximum clique size ω" and "number γ of colors", we also show that, while still NP-hard, Job Interval Selection restricted to proper interval graphs has a problem kernel with O(k 2 • ω) intervals that can be computed in linear time. Here, notably, k ≤ γ.

Due to the lack of space, most technical details are deferred to a full version.

Preliminaries. When speaking of interval graphs, we state our running times under the assumption that an interval representation is given in which the intervals are sorted with respect to their starting or ending points. Given a graph G that allows for such an interval representation, the representation can be computed in O(n + m) time [START_REF] Booth | Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms[END_REF]. A graph is a proper interval graph if it allows for an interval representation such that for no two intervals v and w it holds that v ⊆ w. Every interval graph allows for a total and linear-time computable clique ordering ≺ of its maximal cliques such that, for each vertex, the maximal cliques containing it occur consecutively [START_REF] Fulkerson | Incidence matrices and interval graphs[END_REF]. Moreover, all maximal cliques of an interval graph can be listed in linear time.

A problem is fixed-parameter tractable (FPT) with respect to a parameter k if there is an algorithm solving any problem instance of size n in f (k) • n O (1) time for some computable function f . A problem kernelization is a polynomialtime transformation of a problem instance x with a parameter k into a new instance x with parameter k such that |x | is bounded by a function in k (ideally, a polynomial in k), k ≤ k, and (x, k) is a yes-instance if and only if (x , k ) is a yes-instance. We call (x , k ) the problem kernel and |x | its size.

Independent Set and 2-Union Graphs

This section mainly investigates the standard and parameterized complexity of 2-Union Independent Set. We start by discussing a complexity dichotomy and thereafter consider various parameterizations of the problem. Finally, we provide parameterized tractability results with respect to number of maximal cliques in the input graphs.

A complexity dichotomy. 2-Union Independent Set is known to be NP-hard [START_REF] Bafna | Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)[END_REF] and APX-hard for 2-union graphs of maximum degree three [START_REF] Bar-Yehuda | Scheduling split intervals[END_REF] and for graphs that are the union of an interval graph with pairwise disjoint edges [START_REF] Spieksma | On the approximability of an interval scheduling problem[END_REF]. Using a reduction from 3-Sat, we can impose further restrictions on NP-hard instances, which are important for showing kernelization lower bounds in Section 3.

Theorem 1. 2-Union Independent Set is NP-hard, even if one of the input graphs is restricted to be a disjoint union of altogether k edges and triangles and the other is restricted to contain only paths of length two.

In the context of Theorem 1, note that paths of length two are the simplest graphs that are not cluster graphs. If, in contrast, G would be the union of two cluster graphs, then G is claw-free. Independent Set on claw-free graphs is solvable in O(n 3 ) time [START_REF] Sbihi | Algorithme de recherche d'un stable de cardinalite maximum dans un graphe sans etoile[END_REF]. However, for the union of two cluster graphs, we can provide a O(n 1.5 ) time algorithm based on computing a matching of the cliques in the two input cluster graphs. Proposition 1. 2-Union Independent Set is solvable in O(n 1.5 ) time if both input interval graphs are cluster graphs.

Theorem 1 and Proposition 1 give rise to a complexity dichotomy, stating that 2-Union Independent Set is polynomial-time solvable if both inputs are restricted to be cluster graphs, and NP-complete otherwise, even in the simplest case of non-cluster graphs. A more detailed investigation of our proof of Theorem 1 together with a result of Impagliazzo et al. [START_REF] Impagliazzo | Which problems have strongly exponential complexity?[END_REF] yields that, even in the restricted case covered by Theorem 1, there is no algorithm with running time 2 o(k) • poly(n) for 2-Union Independent Set unless the Exponential Time Hypothesis2 fails.

Corollary 1. Under the prerequisites of Theorem 1, there is no algorithm with running time 2 o(k) • poly(n) for 2-Union Independent Set unless the Exponential Time Hypothesis 2 fails.

Parameter identification. We now consider suitable parameters for 2-Union Independent Set. Since we have two input graphs, we often consider the maximum or minimum value of parameters taken over the two input graphs. For example, considering the maximum degrees ∆ 1 and ∆ 2 of G 1 and G 2 , respectively, natural parameters are ∆ min := min{∆ 1 , ∆ 2 } and ∆ max := max{∆ 1 , ∆ 2 }. However, Theorem 1 implies that 2-Union Independent Set is NP-hard even if ∆ max ≤ 2.

A second view on the parameterized landscape is

k α min α max #mC min #mC max centered around the fact that 2-Union Independent Set is W[1]
-hard with respect to the parameter "solution size k" [START_REF] Jiang | On the parameterized complexity of some optimization problems related to multiple-interval graphs[END_REF]. We therefore consider parameters that are lower-bounded by k. Unfortunately, the W[1]hardness proof for parameter k due to Jiang [START_REF] Jiang | On the parameterized complexity of some optimization problems related to multiple-interval graphs[END_REF] also shows that 2-Union Independent Set is W [START_REF] Bafna | Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)[END_REF]-hard for the the maximum α max of the respective independence numbers α 1 and α 2 of G 1 and G 2 . In interval graphs, a parameter that is lower bounded by the independence number α is the number of maximal cliques #mC. Indeed, we can show fixed-parameter tractability with respect to #mC min and #mC max , denoting the minimum, respspectively the maximum, of the numbers of maximal cliques in the two input interval graphs. For the parameter #mC min , we exploit an alternative problem formulation, additionally allowing us to obtain results for the well-known Job Interval Selection problem [START_REF] Nakajima | Complexity results for scheduling tasks with discrete starting times[END_REF]. An overview of the parameters that are lower-bounded by k is shown above.

Parameterized tractability. In the quest for polynomial-time preprocessing for 2-Union Independent Set, we considered simple-to-implement reduction rules. Surprisingly, a single twin-type reduction rule is sufficient to provide a polynomialsize problem kernel with respect to the parameter #mC max . We reduce the number of vertices having a given "signature" and then bound the number of signatures in a 2-union graph. Definition 1. Let (G 1 , G 2 , k) denote an instance of 2-Union Independent Set and let v be a vertex of G 1 and G 2 . The signature sig(v) of v is the set of all vertex sets C that contain v and form a maximal clique in either G 1 or G 2 .

Reduction Rule 1. Let (G 1 , G 2 , k) denote an instance of 2-Union Independent Set. For each pair of vertices u, v of G 1 and G 2 such that sig(v) ⊆ sig(u), delete u from G 1 and G 2 .

Theorem 2. 2-Union Independent Set admits a cubic-vertex problem kernel with respect to the parameter "larger number of maximal cliques #mC max ". A quadratic-vertex problem kernel can be shown if one of the input graphs is a proper interval graph. Both kernels can be computed in O(n log 2 n) time.

We can generalize Theorem 2 for the problem of finding an independent set of weight at least k: we keep the vertex with highest weight for each signature in the graph. Since each signature is uniquely determined by its first and last maximal cliques in G 1 and G 2 with respect to a clique ordering, there are at most #mC Given a list-colored interval graph G, the algorithm computes a table T indexed by pairs in {0, . . . , |C|} × 2 {1,...,γ} using the clique ordering ≺ of G. Let C[j] denote the j'th element in the ordering ≺, and let

G i = G -1≤ ≤i C[ ].
We define T [i, C] so that it contains the maximum cardinality of a colorful independent set of G minus the first i maximal cliques (with respect to ≺) using only colors in C. For the base case, we set T [|C|, C] = 0 for all C ⊆ {1, . . . , γ}. Next, observe that for each interval v, there is a unique maximal clique with largest index i v (according to the ordering ≺ of C) containing v. The dynamic programming table can now be filled according to the following recursion:

T [i -1, C] = max T [i, C], max v∈C[i] col(v)⊆C {1 + T [i v , C \ col(v)]} . ( 1
)
The cardinality of a maximum colorful independent set of G can be read from T [0, {1, . . . γ}]. This approach is easily-modifiable to also compute a maximum weighted independent set if the input graph is vertex-weighted.

Theorem 3. Colorful Independent Set can be solved in O(2 γ • γ • |C| • n) time 3
, even if all vertices are integer-weighted.

In terms of 2-Union Independent Set, Theorem 3 can be stated as follows.

Corollary 2. 2-Union Independent Set can be solved in O(2

#mC min •#mC max • #mC min • n) time.

Colorful Independent Sets and Strip Graphs

In Section 2 we reformulated 2-Union Independent Set in terms of finding a maximum colorful independent set in an interval graph and gave a fixed-parameter algorithm for the more general problem Colorful Independent Set. We now consider the variant of Colorful Independent Set where each vertex (resp. interval) has only one color instead of a list of colors. This restriction is equivalent to 2-Union Independent Set for input graphs that are the edge-wise union of an interval graph and a cluster graph,4 a class of graphs called strip graphs by Halldórsson and Karlsson [START_REF] Halldórsson | Strip graphs: Recognition and scheduling[END_REF]. They interpreted each clique in the input cluster graph as an equivalence class of vertices of the input interval graph; we reinterpret these equivalence classes in a natural way: as colors. In the literature, this problem is known as Job Interval Selection [START_REF] Nakajima | Complexity results for scheduling tasks with discrete starting times[END_REF] (see the definition in Section 1). In our model, colors represent jobs and intervals of the same color in the input graph are possible execution intervals for one job. A solution then shows how to execute at least k jobs. Jansen [START_REF] Jansen | Generalizations of assignments of tasks with interval times[END_REF] showed a polynomial-time algorithm for Job Interval Selection for a constant number γ of colors. The dynamic programming algorithm given by Höhn et al. [START_REF] Höhn | Integrated sequencing and scheduling in coil coating[END_REF] can be seen as a generalization of this algorithm, since strip graphs are a special case of m-composite graphs. In both cases, the degree of the polynomial depends on γ. Halldórsson and Karlsson [START_REF] Halldórsson | Strip graphs: Recognition and scheduling[END_REF] gave a fixed-parameter algorithm running in O(2 Q • n) time with Q denoting the "maximum number of live intervals". Omitting the detailed description of the parameter Q, we note that, in instances of the underlying scheduling problem in which there is more than one machine, Q equals the number γ of colors in our interpretation.

Fixed-parameter algorithms for combinations with k. As 2-Union Independent Set is W [START_REF] Bafna | Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)[END_REF]-hard for the single parameter "solution size k" [START_REF] Jiang | On the parameterized complexity of some optimization problems related to multiple-interval graphs[END_REF], we combine k with the maximum clique size ω in the input interval graph G, the maximum number φ of cliques in G that have a vertex in common, and the number γ of colors in G. These combinations allow for fixed-parameter tractability and kernelization results. In the following, let C 1 , C 2 , . . . denote the maximal cliques of G in order of the clique ordering of G. We will reuse the notion of "signatures" (see Definition 1). In the context of colored interval graphs, the signature sig(v) of an interval v is the pair of its color and the set of maximal cliques it is contained in. The algorithms presented in this section rely on the observation that an optimal solution can be assumed to contain an interval v of the first maximal clique C 1 . In the following, assume that there is an interval v ∈ C 1 that is in the sought colorful independent set. Our fixed-parameter algorithms branch on properties of v that allow us to either identify v or remove intervals from G so that an isolated clique containing v is created. These properties are (a) the size of C 1 , (b) the last clique containing v, and (c) the color of v. After at most k branchings, we end up with a cluster graph, on which the problem can be solved in polynomial time using Proposition 1. Depending on what property of v we branched on, the exponential components of the running times can be bounded in ω k , φ k , or γ k .

Proposition 2. Job Interval Selection can be solved in O(ω k • n), O(φ k • n 1.5 ), and O(γ k • n 2 log 2 n) time.
Non-existence of polynomial-size kernels for Job Interval Selection. We show that Job Interval Selection is unlikely to admit polynomial-size problem kernels with respect to various parameters. To this end, we employ the technique of "cross-composition" introduced by Bodlaender et al. [START_REF] Bodlaender | Cross-composition: A new technique for kernelization lower bounds[END_REF] using a bitmasking approach as standard in previous publications that exclude polynomial-size kernels for other problems. A cross-composition is a polynomial-time algorithm that, given t instances x i with 0 ≤ i < t of an NP-hard starting problem A, outputs an instance (y, k) of a parameterized problem B such that k ∈ poly(max i {|x i |}+log t) and (y, k) ∈ B if and only if there is some 0 ≤ i < t with x i ∈ A. A theorem by Bodlaender et al. [START_REF] Bodlaender | Cross-composition: A new technique for kernelization lower bounds[END_REF] states that if a problem B admits such a cross-composition, then there is no polynomial-size kernel for B unless coNP ⊆ NP/poly.

We use an operation on binary-encoded numbers: shifting a number i by j bits to the right, denoted by shift(i, j) := i/2 j . In the following, we present a cross-composition for Job Interval Selection with respect to (ω, γ). For the NP-hard starting problem we use the unparameterized version of Job Interval Selection with the restriction that k = c. The NP-hardness of this problem is a direct consequence of Theorem 1. We assume, without loss of generality, that log t is an integer. The framework of Bodlaender et al. [START_REF] Bodlaender | Cross-composition: A new technique for kernelization lower bounds[END_REF] allows us to force the input instances to all have the same value for k and, thus, each instance uses the same color set {1, 2, . . . , k}. The steps of the composition are as follows (see Figure 1):

Step 1. Place the t input instances in order of their index on the real line such that no interval of one instance overlaps an interval of another instance. Step 2. Introduce log t more colors k +1, k +2, . . . , k +log t (the resulting instance then asks for an independent set of size k + log t).

Step 3. For each 1 ≤ i ≤ log t, introduce 2 i new intervals v i 0 , v i 1 , . . . , v i 2 i -1 , each with color k + i, such that the new interval v i j spans over all instances x with shift( , log t -i) = j. It is easy to see that both the number of colors γ and the maximum clique size ω of the constructed instance are at most max i |x i | + log t. In order to show that the presented algorithm constitutes a cross-composition, it remains to prove that the resulting instance has a colorful independent set of size k + log t if and only if there is an input instance x i that has a colorful independent set of size k. The presented cross-composition implies the following theorem [START_REF] Bodlaender | Cross-composition: A new technique for kernelization lower bounds[END_REF].

Theorem 4. Job Interval Selection does not admit a polynomial-size problem kernel with respect to the combination of the parameters "number of colors γ" and "maximum clique size ω" unless coNP ⊆ NP/poly.

Polynomial-size kernel for proper interval graphs. We further restrict Job Interval Selection to proper interval graphs, on which it is still NP-hard, as evident from Section 2. Surprisingly, simple data reduction rules enable us to construct a problem kernel comprising 2ωk(k -1) intervals in this case, sharply contrasting Theorem 4, which excludes a polynomial-size problem kernel with respect to the combined parameter (k, ω) (since γ ≥ k).

Reduction Rule 2. Delete from G every interval that has a color that appears more than 2ω(k -1) times and decrease k by the number of removed colors.

Reduction Rule 3. If G contains more than 2ωk(k -1) intervals, then return a trivial yes-instance.

Reduction Rule 2 can be applied exhaustively in O(n) time. Thereafter executing Reduction Rule 3 immediately yields the following theorem.

Theorem 5. Job Interval Selection on proper interval graphs admits a problem kernel with at most 2ωk(k -1) intervals that can be computed in O(n) time.

Outlook

Besides hardness results, we also developed encouraging algorithmic results which might find use in practical applications, so future empirical studies seem worthwhile (also see the strong practical results of Höhn et al. [START_REF] Höhn | Integrated sequencing and scheduling in coil coating[END_REF] with respect to steel manufacturing). As a future challenge, it is interesting to know whether 2-Union Independent Set admits a polynomial-size problem kernel with respect to the parameter #mC min , denoting the smaller number of maximal cliques in one of the input interval graphs. Furthermore, we conjecture that Job Interval Selection with respect to the parameter "solution size k" is fixed-parameter tractable, whereas 2-Union Independent Set is known to be W [START_REF] Bafna | Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)[END_REF]-hard for this parameter [START_REF] Jiang | On the parameterized complexity of some optimization problems related to multiple-interval graphs[END_REF].

Fig. 1 :

 1 Fig.1: Schematic view of the construction of the cross-composition. Circles at the bottom represent the t input instances. Bars at the top represent the newly added intervals spanning over the input instances. Here, each of the log t rows stands for a new color. A solution (black intervals) for the instance must select one interval in each row, thereby selecting one of the t input instances (x 3 in this example).

We call an independent set colorful if no two of its vertices share a color.

The Exponential-Time Hypohesis basically states that there is no 2 o(n) -time algorithm for n-variable

3SAT.

Assuming that adding, subtracting, and comparing of integers work in O(1) time.

Recall that 2-Union Independent Set is solvable in O(n1.5 ) time if both input graphs are cluster graphs (see Proposition 1).

Acknowledgment. We are grateful to Michael Dom and Hannes Moser for earlier discussions on coil coating.

Supported by the DFG, projects DAPA, NI 369/12, and AREG, NI 369/9. † Supported by the DFG, project DARE, NI 369/11.


Xiaoqin Wang
email: 汪晓勤xqwang@math.ecnu.edu.cn

HISTORY-BASED PROBLEMS IN THE TEACHING OF SENIOR HIGH SCHOOL Mathematics in Mainland China

This paper deals with the integration of history in mathematics teaching. Four possible approaches are considered: complementation, replication, accommodation, reconstruction. The main focus is on the relation between. mathematical problems posed on the basis of historical information (history-based problems) and mathematics teaching from the HPM perspective. In this paper 20 HPM lessons are analysed.

Introduction

Integrating the history of mathematics into mathematics teaching is one of the important research fields in HPM. As shown in table 1, four ways are identified in which historical information is used in classroom teaching in Mainland China.

Table 1. Four Approaches to Using History in Mathematics Teaching

Approaches Description

Complementation Pictures, stories, etc.

Replication

Original problems, methods, etc. in the history, copied without any adaption Accommodation Problems adapted from original ones or based on historical information Reconstruction

The evolution of a subject (e.g. a concept or theory) inspired by the history of mathematics

In replication and accommodation approaches, most of historical materials used are mathematical problems. In the reconstruction approach, the reconstructed steps of evolution of a subject "are given as sequences of historically motivated problems of an increasing level of difficulty" (Tzanakis & Arcavi, 2000). Therefore, mathematical problem posing is involved in all approaches except the complementation one. In this paper, mathematical problems posed on the basis of historical information are called "history-based problems". The relation between history-based problems and mathematics teaching from the HPM perspective is shown in Figure 1. In mainland China, researches in HPM have focused on teaching practice and mathematics teachers' professional development and many lessons in which the history of mathematics is integrated (hereafter, abbreviated as HPM lessons) have been developed in recent years. Which history-based problems are used in these lessons? How are they posed? What roles do they play in these cases? How are they distributed at different stages of the lessons? In this paper, we will answer these research questions.

Selection of the HPM Lessons

A total of 20 HPM lessons (Chen, 2015;Chen, 2015;[START_REF] Chen | Teaching the definition of the ellipse based on double Dandelin spheres[END_REF]Fang & Wang, 2013;Guo & Wang, 2015;Jin & Wang, 2014;Li, 2015;Li & Wang, 2016;Li & Wang, 2016b;Shi, 2016;Wang & Wang, 2012); [START_REF] Wang | The application of the derivatives from the HPM perspective[END_REF][START_REF] Wang | Researches in HPM: what and how[END_REF][START_REF] Xu | Reconstructing the history to teach the concept of parabola[END_REF][START_REF] Yang | Teaching the concept of slope from the HPM perspective[END_REF][START_REF] Zhang | Integrating the history of mathematics into mathematics teaching: the case of the addition & subtraction formulas for sine and cosine[END_REF][START_REF] Zhang | Teaching of the mean value inequality with HPM work cards[END_REF][START_REF] Zhang | Teaching the concept of complex number from the HPM perspective[END_REF][START_REF] Zhang | Using history to teach the law of sine[END_REF][START_REF] Zhong | The concept of logarithm: from history to the classroom[END_REF][START_REF] Zhong | The concept of function: from the history to the classroom[END_REF], published from 2007 to 2016, are selected and examined, as shown in Figure 2. The subjects of the 20 instructional cases belong to algebra, geometry, trigonometry, analytical geometry and calculus respectively. Figure 3 shows their distribution in different areas. Figure 5 shows the frequency of each approach adopted in each lesson and Figure 6 shows the number of lessons in which different approaches are adopted. The reconstruction approach is mainly adopted in lessons on mathematics concepts. While designing such a lesson, the teacher need have a basic knowledge of the historical evolution of the relevant concept. In one and the same lesson, this approach is used only one time. Thus we see that it appears less frequently. History-based problems, most of which are adapted from historical information, are indispensable for most HPM lessons and can be used at different stages of the lessons. Therefore, the accommodation approach appears most frequently. Historical resources are limited for mathematics teachers and most of historical materials available to them are unsuitable for direct use and need to be adapted. This is the reason why the replication approach appears less frequently than the accommodation one.

Figure 6 shows that two approaches are adopted in 8 lessons, three in 6 lessons, four in 5 lessons, and one in only one lesson.

History-based problem posing

Silver et al (1996) identified four strategies of posing new problems in terms of the given situations or problems: constraint manipulation (i.e., systematic manipulation of the task conditions or implicit assumptions), goal manipulation (i.e., manipulation of the goal of a given or previously posed problem where the assumptions of the problem are accepted with no change), symmetry (a symmetrical exchange between the existing problem's goal and conditions), chaining (i.e., expanding an existing problem so that a solution to the new problem would require solving the existing one first). According to these strategies, combined with the approaches to using history in teaching, six strategies of posing history-based problems are identified: copying, free posing, situation manipulation, constraint manipulation, goal manipulation, symmetry and chaining.

The copying strategy is that of directly using original problems without any adaption, corresponding to the replication approach to using history, the used historical materials being mathematics problems. Free posing strategy is that of posing problems according to some historical information (stories, problems, methods, etc.) in which the conditions and goals are selected according to classroom requirements. The situation manipulation strategy is that of adapting the situation of a problem in the history or adding real situation to the existing historical problem which is familiar to students, keeping the given conditions and goals unchanged. Manipulation of the constraints or goals of the problems in the history is called constraint or goal manipulation strategy. The case in which both situations and conditions are changed is classified among the constraint manipulation strategy and that in which both situations and goals are changed is classified among the goal manipulation strategy. Symmetrical exchange between conditions and goals of problems in the history is called symmetry strategy. Taking the goals of the original problems as the conditions to pose new problem is called the chaining strategy.

Figure 7 shows the relation between the strategies of posing history-based problems and approaches to using historical materials in teaching.

History-based problems in 20 Lessons

In all 20 HPM lessons, a total of 63 history-based problems are found. Figure 8 is the frequency histogram of each type of problems. It is revealed from Figure 8 that the number of freely posed problems (FP problems) far exceed other types, followed by the copied original problems (CO problem). Only one problem posed by means of the goal manipulation strategy (GM problem) is found, and none of the problems posed by means of the symmetry or situation adaptation strategy appear. 9 problems posed by means of the constraint manipulation strategy (CM problem) appear only in four lessons, and 9 problems of the chaining strategy (CH problem) appear only in two lessons. On the one hand, few of original historical materials available to teachers are suitable for direct use in classroom teaching; on the other hand, it is easier for a teacher to pose a new problem freely on the basis of historical information than to pose a problem by means of constraint or goal manipulation.

The CO Problems

Table 2 shows the detailed information of some CO problems.

The CO problems are used in 10 HPM lessons. In the lesson "The Roots of an Equation & the Zeroes of a Function", the problem of solving the cubic equation 3 2 2 10 20

x x x + + = ,
which was solved approximately by Leonardo Fibonacci, is used to introduce the topic (Chen,2015). In the lesson "The Mean Value Inequality", the mean value inequality is used to solve Regiomontanus' angle maximization problem: "Viewed from which point on the ground, a pole hanging vertically looks the longest?" At the beginning of the lesson "The Introduction of the Complex Numbers (I)", the students are asked to solve Leibniz's system of quadratic equations with two unknowns: 2 2 2 x y xy + = = ,which creates students' motivation to learn the new type of numbers----the imaginary numbers. At the beginning of the lesson "The Introduction of the Complex Numbers (II), the teacher used Cardano's problem of dividing 10 to introduce the imaginary numbers: "To divide 10 into two parts so that their product is 40".

These problems are all original historical ones without any adaptation.

The FP Problems

Of 63 history-based problems, about half are FP ones. Table 2 gives their detailed information. Figure 9 shows that CO problems are mainly used at the stage of introduction and seldom appear at stages of exploration and example. Figure 10 shows that the accommodation problems are mainly used at the stage of exploration and seldom appear at stages of introduction and exercise. There are few lessons in which accommodation problems are used as examples. In most of lessons, history-based problems quit from the stage after playing relevant roles at stages of introduction and exploration. classroom teaching are very few, on the other hand, teachers usually believe that they don't need such problems at stages of example and exercise. In recent years, history-based problems appear in college entrance examination, and perhaps this fact will change teachers' opinions.

Distribution of history-based problems at different stages of the lessons

Functions of History-based problems

In Mainland China, one of the general objectives of the mathematics curriculum is to develop students' core competencies, i.e., mathematical abstraction, logical reasoning, mathematical operation, intuitive imagination and data analysis. Except for data analysis, these competencies are embodied in all 63 history-based problems. Figure 12 shows the number of problems corresponding to each type of the competency. Figure 13 shows the distribution of problems relating to different types of core competencies, indicating that history-based problems are effective in developing students' core competencies. Here arises a problem: are history-based problems irreplaceable in mathematics teaching? Undoubtedly, those problems unrelated to the history of mathematics can also develop students' core competencies. However, it is impossible for any mathematics problems to generate from the thin air. The history of mathematics offers us the origin of problems, from which endless new problems can be posed by means of various types of strategies. Moreover, history-based problems can easily form the chains of problems. For example, in the lesson "Curves and their Equations", the two-line problem, three-line problem and four-line problem form an inseparable whole, creating for students the opportunity to experience the birth process of analytical geometry. In the lesson "The Application of Derivatives", problems of cylinders, cones, prisms and pyramids with maximum volumes, a series of problems solved by mathematicians in the 17 th century, are reconstructed in the classroom.

On the other hand, history-based problems play unique roles in promoting positive affect and beliefs. In the lesson "The Concept of Number Sequence", the cat and rice problem of ancient Egypt and the Josephus' game aroused students' interest in number sequences. In the lesson "The Concept of Complex Numbers", Leibniz's system of equations with two unknowns stimulated students' learning motivation. In the lesson "The Concept of Prism", Euclid's incomplete definition of the prism told students that mathematicians might make mistakes and enabled them to recognize the nature of mathematics activity and reflect on their own mistakes and difficulties in learning mathematics. In the lesson "The Application of Derivatives", problems of can designing, dock locating, pipe installing and communication line connecting reveal the intimate links between mathematics and human real life, while the problem of deriving the refraction law shows that mathematics is closely related to other subjects. Moreover, history-based problems can humanize the classroom. While solving such problems, students seem to traverse the time and space and make a conversation with a mathematician living in other culture and time, who seems to be a student in the classroom. The dialogue across time and space makes students fell close to mathematics.

Conclusions

Of the seven types of history-based problems, five are found in the total twenty HPM lessons, which, according to the frequency of being used, are FP, CO, CM, CH and GM problems respectively. No problems posed by means of symmetry strategy (SE problems) or situation manipulation strategy (SM problems) are found. Some problems are posed by means of situation manipulation, they are, however, classified among FP, CM or GM problems because the constraints or goals of original problems are also changed.

History-based problems in the twenty lessons mainly come from such sources as old Babylonian mathematics tablets, Egyptian papyrus, Elements, Nine Chapters on the Mathematical Art, Pappus' Collection, Liber Abaci and works of such mathematicians as Fermat, Kepler, Leibniz, etc., which are not limited to one culture or one time but, among the tremendous mathematics literatures, just a drop in the ocean.

As far as core mathematics competencies are concerned, history-based problems in 20 HPM lessons involves mathematics abstraction, mathematics modelling, logical reasoning, mathematical operations and intuitive imagination. In contrast with those non-historical problems, history-based problems had advantages in affective and cultural aspects of mathematics education.

In 20 HPM lessons, mathematics motivated problems are mainly used at the introduction and exploration stages and seldom appear at other stages.

History-based problems are indispensable for HPM lessons. Therefore, researchers should make deep and systematic historical researches on relevant subjects in the senior high school mathematics curriculum in an effort to amplify the repertoire of mathematical problems in mathematics curriculum, textbooks and teaching.

They should also cooperate with high school mathematics teachers, discussing and disseminating the history motivated problem posing strategies. Teachers should know more about the educational values of the history-based problems and using them at more stages of classroom teaching, completely exerting their educational functions.

Figure 1 .

 1 Figure 1. History-based problems and mathematics teaching from the HPM perspective

Figure 2 .Mathematics

 2 Figure 2. 20 HPM Lessons from 2007 to 2016

Figure 3 .

 3 Figure 3. Subject Distribution of 20 HPM Lessons All these HPM lessons are developed by senior high school mathematics teachers in cooperation with the university researchers, as shown in figure 4.

Figure 4 .

 4 Figure 4. Development of the HPM Lessons

Figure 5 .Figure 6 .

 56 Figure 5. The Frequency of Each Approach Adopted in Each Lesson

Figure 7 .

 7 Figure 7. Strategies of posing problems based on historical information

Figure 8 .

 8 Figure 8. Various types of history-based problems

B

B

  The CH problems appear only in the lessons "The Addition and Subtraction Formulas for Sine and Cosine" and "The Mean Value Inequality", in which the HPM Work Cards are used.For Example, in the lesson "The Mean Value Inequality", after solving Regiomontanus' problem, a new problem is posed: How to solve this problem geometrically? Being based on the solution to the original problem, it is a CH problem.

Figure9

  Figure9 and Figure10 show the distribution of 12 CO problems and 51 Accommodation problems (FP, CM, GM & CH) at different stages of the lessons respectively.

Figure 9 .

 9 Figure 9. Distribution of the CO problems Figure10. Distribution of the Accommodation problems

Figure 11 .

 11 Figure 11. The number of history-based problems which reflect the key mathematics literacy Take Regiomontanus' angle maximization problem as an example. Through intuitive imagination, the geometrical figure is constructed: In Figure 12, the segment AB designates the hanging pole, P is the view point on the ground. Let OA a = , OB b = . OP x = ,

Figure 13 .

 13 Figure 13. The distribution of history-based problems involving different competencies

Table 2 .

 2 Part of the CO problems

	No.	CO Problems	HPM Lessons	Sources	Authors	Time
		The Cats & Mice problem	The Concept of the Number Sequence	Rhind Papyrus	Ahmes	ca. 1650 B.C.
		The Interest Problem	The Concept of Logarithm	Tablet	--	ca. 1700

Table 3 .

 3 The FP Problems

	No.	FP Problems	HPM Lessons	Sources	Authors	Time
		The Derivation of the Mean Value Inequality according to Euclid's Proposition	The Mean Value Inequality	Elements	Euclid	3 rd Century B.C.
		The Counterexample of Euclid's Definition of the Prism	The Definition of the Prism	Elements	Euclid	3 rd Century

Fang G. Q. & Wang F. (2013). Introduction of complex numbers from the HPM perspective. Mathematics Teaching, 4, 4-29. Gu Y. Q. & Wang X. Q. (2015). Using history to teach the law of cosine. Educational Research & Review, 2, 52-57. Jin H. P. & Wang F. (2014). Teaching the concept of logarithm from the HPM perspective. Educational Research & Review, 9, 28-34. Li L. (2015). The recurrent sequence: starting from the Hanoi tower game. Educational Research & Review, 9, 219-23. Li L. & Wang X. Q. (2016). Teaching the concept of number sequence from the HPM perspective. Educational Research & Review, 4. Li L. & Wang X. Q. (2016, to appear). Teaching the formula for the sum of a geometrical sequence from the HPM perspective. Educational Research & Review. Shi H. F. ( 2016). Using ancient Greek mathematics problems to teach "curves and their equations", Educational Research & Review, 3, 54-58. Silver, E. A. et al. (1996). Posing mathematical problems: an exploratory study. Journal for Research in Mathematics Education, 27(3), 293-309. Singer, F. M. et al. (2013). Problem-posing research in mathematics education: new questions and directions. Mathematics, 83,1-7. Tzanakis, C. & Arcavi, A. (2000). Integrating history of mathematics in the classroom: an analytic survey. In: J.

Educational Studies in

Fauvel & J. van Maanen (Eds.), History in Mathematics . Dordrecht: Kluwer

The FP problems appear in 11 lessons. One of the propositions in Pappus' Collection acts as the geometrical model of the addition formulas (Heath, 1921), based on which the problems of deriving the addition formulas are posed in the lesson "The Addition & Difference Formulas".

In his Nova Stereometria Doliorum Vinariorum, John Kepler (1571-1630) studied the ratio of the height of the cylinder to the diameter of its base while the cylinder has maximum volume. In the lesson "The Application of the Derivative", this problem was changed into that of a Pop-Top can: "What is the ratio of the height to the radius of the base when the tin has the minimum surface?" It should be noticed that the two bases and the side surface has different thickness. The constraints, goals and situations of Kepler's original problem being changed, the new problem is a FP one.

The CM and GM problems

Table 4 gives the detailed information about some CM problems. The CM problems appear only in four lessons. In the lesson "Curves & Their Equations", special cases of the Greek three-line problem and four-line problem are adopted in which the lines are perpendicular or parallel to each other. At the beginning of the lesson "The Introduction of Complex Numbers", the teacher first gave the problem of dividing 10 into two parts so that their product is 24, which is adapted from a problem in Cardano's Ars Magna, then Cardano's original problem is discussed.

In his Nova Stereometria Doliorum Vinariorum, John Kepler posed the following proposition: "Of all right cylinders with the fixed diagonal of the axial section, the one whose diameter is to the height as 2 : 1 has maximum volume." A problem solved in the lesson "The Application of the Derivatives" is adapted from this proposition, the cylinder being inscribed in a sphere.

Only one GM problem is found in all the 20 lessons, which is adapted from the chessboard problem in Fibonacci's Liber Abaci:

If one grain of corn is put in the first place and from the second place on, any place in the sequence of places is proposed to be double the sum of all preceding places, how many grains of corn are there in total on the whole chessboard? (Stigler, 2002, 437).

In a problem of the lesson "The Recurrent Sequence", the way of putting grains of corn remains the same but the goal is to find "the general term of the sequence of grains of corn in each place of the chessboard" instead of the sum of the sequence.

The CH Problems

Table 5 shows the detailed information about some of the CH problems.


Jaros Law B Lasiok

Marcin Kamiński

Jean-Florent Raymond

Théophile Trunck

Induced minors and well-quasi-ordering

Keywords: Well-quasi-ordering, induced minors, combinatorial dichotomies

A graph H is an induced minor of a graph G if it can be obtained from an induced subgraph of G by contracting edges. Otherwise, G is said to be H-induced minorfree. Robin Thomas showed in [Graphs without K 4 and well-quasi-ordering, Journal of Combinatorial Theory, Series B, 38(3):240 -247, 1985] that K 4 -induced minorfree graphs are well-quasi ordered by induced minors.

We provide a dichotomy theorem for H-induced minor-free graphs and show that the class of H-induced minor-free graphs is well-quasi-ordered by the induced minor relation if and only if H is an induced minor of the gem (the path on 4 vertices plus a dominating vertex) or of the graph obtained by adding a vertex of degree 2 to the complete graph on 4 vertices.

Introduction

A well-quasi-order (wqo for short) is a quasi-order which contains no infinite decreasing sequence, nor an infinite collection of pairwise incomparable elements (called an antichain). One of the most important results in this field is arguably the theorem by Robertson and Seymour which states that graphs are well-quasi-ordered by the minor relation [START_REF] Robertson | Graph Minors. XX. Wagner's conjecture[END_REF]. Other natural containment relations are not so generous; they usually do not wqo all graphs. In the last decades, much attention has been brought to the following question: given a partial order (S, ), what subclasses of S are well-quasi-ordered by ? For instance, Fellows et al. proved in [START_REF] Michael R Fellows | Well-quasiordering bounded treewidth graphs[END_REF] that graphs with bounded feedback-vertexset are well-quasi-ordered by topological minors. Other papers considering this question include [1, 3-6, 8, 9, 13, 15].

One way to approach this problem is to consider graph classes defined by excluded substructures. In this direction, Damaschke proved in [START_REF] Damaschke | Induced subgraphs and well-quasi-ordering[END_REF] that a class of graphs defined by one forbidden induced subgraph H is wqo by the induced subgraph relation iff H is the path on four vertices. Similarly, a bit later Ding proved in [START_REF] Ding | Subgraphs and well-quasi-ordering[END_REF] an analogous result for the subgraph relation. Other authors also considered this problem (see for instance [START_REF] Cherlin | Forbidden substructures and combinatorial dichotomies: Wqo and universality[END_REF][START_REF] Korpelainen | Two forbidden induced subgraphs and well-quasi-ordering[END_REF][START_REF] Korpelainen | Bipartite induced subgraphs and well-quasi-ordering[END_REF]). In this paper, we provide the answer to the same question for the induced minor relation, which we denote ≤ im . Before stating our main result, let us introduce two graphs which play a major role in this paper: K4 is obtained by adding a vertex of degree two to K 4 and the gem by adding a dominating vertex to P 4 . (cf. Figure 1).

Induced minors and well-quasi-ordering

Our main result is the following.

Theorem 2.1 (Dichotomy Theorem) Let H be a graph. The class of Hinduced minor-free graphs is wqo by

≤ im iff H ≤ im K4 or H ≤ im gem.
Our proof naturally has two parts: for different values of H, we need to show wqo of H-induced minor-free graphs or exhibit an H-induced minor-free infinite antichain. Due to space limitations, we only present the main ideas of the proof of the dichotomy theorem.

Classes that are wqo

The following two theorems describe the structure of graphs with H forbidden as an induced minor, when H is K4 and the gem, respectively. Theorem 2.2 (Decomposition of K4 -induced minor-free graphs) Let G be a 2-connected graph of Excl im ( K4 ). Then:

• either G ≤ im K 4 ;
• or G is a subdivision of a graph on at most 9 vertices;

• or V(G) has a partition (C, M ) such that G[C] is an induced cycle, G[M ]
is a complete multipartite graph and every vertex of C is either adjacent in G to all vertices of M , or to none of them.

Theorem 2.3 (Decomposition of gem-induced minor-free graph)

Let G be a 2-connected gem-induced minor-free graph. Then G has a subset X ⊆ V(G) of at most six vertices such that every connected component of G \ X is either a cograph, or a path whose internal vertices are of degree two in G.

Using these structural results, we are able to show the wqo of the two classes with respect to induced minors.

Classes that are not wqo

For classes not covered by previous subsection, that is for any graph H which is not an induced minor of one of K4 and gem, we need to show that the H-induced minor-free graphs are not wqo by ≤ im . The idea is to consider an infinite antichain for induced minors, and to show that infinitely many of its elements are H-induced minor-free. Let G denote the complement of any graph G. Using the infinite antichain {C n } n≥6 , we are able to prove the following lemma.

Lemma 2.4 If the class of H-induced minor-free graphs is wqo by ≤ im , then H is disjoint union of paths.

Using Lemma 2.4 and two antichains introduced in [START_REF] Ding | Chordal graphs, interval graphs, and wqo[END_REF] and in [START_REF] Matoušek | On polynomial time decidability of induced-minor-closed classes[END_REF], we can deduce the following properties of H. (Let cc(G) denote the number of connected components of a graph G.) Table 1 enumerates all the possible cases for H, where each line corresponds to a fixed number of vertices and each column to a fixed value of cc(H). A gray cell means that either that no such graph exists, or that the cell corresponds to cases where H-induced minor-free graphs are not wqo by ≤ im (according to Lemma 2.5). The complement of any of the twelve remaining graphs can easily be shown to be induced minor of K4 or gem.

|V(H)| \ cc(H

) 1 2 3 4 ≥ 5 1 K 1 (a) 2 K 2 2 • K 1 (a) 3 P 3 K 2 + K 1 3 • K 1 (a) 4
P 4 P 3 + K 1 K 2 + 2 • K 1 4 • K 1 (a) 5 (b) P 4 + K 1 P 3 + 2 • K 1 (d) (a) ≥ 6 (b) (b) (c) (d) (a)

Fig. 1 .

 1 Fig. 1. The graph K4 (on the left) and the gem (on the right).

Lemma 2 . 5

 25 If H-induced minor-free graphs are wqo by ≤ im , then (a) H has at most 4 connected components; (b) the largest connected component of H has at most 4 vertices; (c) if cc(H) = 3 then |V(H)| ≤ 5; and (d) if cc(H) = 4 then |V(H)| ≤ 4.

Table 1 If

 1 H-induced minors-free graphs are wqo by ≤ im , then H belongs to this table.

This work was done while the author was a student at Institute of Computer Science, University of Warsaw, Poland.

The research was partially supported by the Foundation for Polish Science (Jaros law B lasiok and Marcin Kamiński), the (Polish) National Science Centre grant SONATA UMO-2012/07/D/ST6/02432 (Marcin Kamiński and Jean-Florent Raymond), and by the Warsaw Center of Mathematics and Computer Science (Jean-Florent Raymond and Théophile Trunck).Emails: jblasiok@g.harvard.edu, mjk@mimuw.edu.pl, jean-florent.raymond@mimuw.edu.pl, and theophile.trunck@ens-lyon.org.