Procópio Stein
email: procopiostein@gmail.com

Anne Spalanzani1
email: anne.spalanzani@inria.fr

Vítor Santos

Christian Laugier
email: christian.laugier@inria.fr

Experiments in Leader Classification and Following with an Autonomous Wheelchair

Keywords: leader selection, leader following, assistance robotics, humanaware navigation

With decreasing costs in robotic platforms, mobile robots that provide assistance to humans are becoming a reality. A key requirement for these types of robots is the ability to efficiently and safely navigate in populated environments. This work proposes to address this issue by studying how robots can select and follow human leaders, to take advantage of their motion in complex situations. To accomplish this, a machine learning framework is proposed, comprising data acquisition with a real robot, data labeling, feature extraction and the training of a leader classifier. Preliminary experiments combined the classification system with a multi-mode navigation algorithm, to validate this approach using an autonomous wheelchair.

Motivation, problem statement and related framework

The development of assistance and service robots requires special attention to the problem of navigation in populated environments, as how to interact with humans, respect social conventions and deal with unpredicted situations. The capacity of a robot to address these requirements directly impact its acceptance by humans.

Several successful techniques of motion planning address the problem of navigation in populated environments using probabilistic and predictive approaches [START_REF] Fulgenzi | Probabilistic navigation in dynamic environment using rapidly-exploring random trees and gaussian processes[END_REF], [START_REF] Bennewitz | Learning motion patterns of people for compliant robot motion[END_REF] and on models of social interactions [START_REF] Rios-Martinez | Understanding human interaction for probabilistic autonomous navigation using Risk-RRT approach[END_REF]. The idea is that, by estimating areas that ought to be occupied in the future, these algorithms can create collision-free motion plans that may also respect social conventions.

Unfortunately, these algorithms usually do not incorporate the notion that humans will also adapt their motion to the environment, and it is usually assumed that the robot is the sole responsible for collision avoidance maneuvers.

One consequence of these assumptions, is that, due to the uncertainty in predictions allied with situations of high human density, these algorithms may fail to find a path. This problem has been described in [START_REF] Trautman | Unfreezing the robot: Navigation in dense, interacting crowds[END_REF] and is known as the Freezing Robot Problem (FRP).

The motivation for this work derives from the observation that humans can seamlessly move in highly populated environments, while addressing complex situations and interactions with other humans. Due to this complexity, the mechanisms that take place in this behavior are not yet fully understood. This is an active topic of research [START_REF] Mombaur | From human to humanoid locomotion -an inverse optimal control approach[END_REF], [START_REF] Dyer | Leadership, consensus decision making and collective behaviour in humans[END_REF] with some findings incorporated into motion planning algorithms [START_REF] Althoff | Safety assessment of trajectories for navigation in uncertain and dynamic environments[END_REF], [START_REF] Henry | Learning to navigate through crowded environments[END_REF].

According to these observations, we study the novel hypothesis that a robot can that properly select persons as leaders in a complex environment, will benefit from their advanced navigation and interaction skills, by following them [START_REF] Stein | Navigating in populated environments by following a leader[END_REF]. Figure 1 illustrates the advantages of this approach in comparison with a state of the art motion planning algorithm (RiskRRT), using a pedestrian simulator in a narrow corridor.

Technical Approach

Our experiments investigated how humans perform leader selection in populated environments. The approach was to associate LIDAR measurements with leader behaviors, in order to train a machine learning algorithm to classify persons as good or bad leaders. The general framework was built using ROS [START_REF] Quigley | ROS: an open-source robot operating system[END_REF], while for machine learning we used the OpenCV library.

Data acquisition

Data was acquired using a small car-like robot. Only two sensors were used: a laser scanning range finder and a camera fitted with a wide-angle lens. In this way, videos could be recorded and associated with laser scans during tests. Figure 2 shows the robotic platform, and a sample of the data collected from both sensors at a time instant. The purpose of this setup was to obtain information relative to the behavior and reactions of persons being followed by the robot.

Data Labeling and Feature Extraction

In many datasets, the labeling process is clear and objective, as marking faces in images, or pedestrians in laser scans. However, in this work the objective is to learn how humans decide when to start or stop following someone, or in other words, when someone is a good or bad leader. In order to do so, participants create labels based on their feeling about someone being a good leader or not.

A binary labeling system was used, with candidates identified either as good or bad leader. The process is depicted in . Volunteers should press a button whenever they felt a transition from good to bad leader occurred, while watching a video of persons being followed by the robot. This results in a mark that is stored along with all the original data recorded from experiments.

Videos of tests were shown to participants, who created labels based on their feeling about someone being a good leader or not. In the labeling process, the volunteers watched a video of persons being followed by the robot, and pressed a button whenever they felt a transition from good to bad leader occurred, as shown in Figure 3.

As a result, a mark is stored along with all the original data recorded from experiments. The final label was computed as an average of individual inputs and then, LIDAR measurements were used to obtain the descriptors of each followed person. Figure 4 depicts the following features, which were calculated based on the robot's and subject's current state:

subject's absolute velocity v ci ; -relative heading between the robot and the subject α rci ; -subject's relative velocity w.r.t. the robot reference frame vx rci and vy rci ; angle between the robot heading and the subject's position β ci ; -distance between the subject and the robot d ci ; -lateral and sagittal displacement of the subject ld ci and sd ci ;

All the laser measurements were transformed to a fixed frame, to compensate for the robot's motion. Then, a motion tracker [START_REF] Almeida | Target tracking using laser range finder with occlusion[END_REF] was used to manage the identification and tracking of moving targets. The standard deviation and first derivative of each feature were also used, totaling 24 features.

Classifier Training and Features Evaluation

The chosen classifier is the adaptive Boosting (or AdaBoost) [START_REF] Freund | A decision-theoretic generalization of on-line learning and an application to boosting[END_REF]. Among the advantages of this algorithm is the exponential convergence of the training error to zero and good generalization properties. But most important to the experiments conducted here, is the capacity of the algorithm to inherently select the features that contribute the most to the classification process.

This allows us to study of feature contribution, which is an important aspect of this work, enabling us to draw conclusions about why some features are more important than others, giving insights on what are the criteria used by humans when engaging or disengaging in following behaviors.

Learning and understanding what matters in following-leading engagements will be essential to the development of a more refined theory about humanfollowing behaviors for robots.

Results

Data Acquisiton

In total 47 runs of the robot following persons or group of persons were recorded, with a mean duration of about 20 seconds each. Tests were conducted in an open corridor, about 3m wide. The robot operator's goal was to move along this corridor back and forth, covering a distance of about 20m in each pass.

Although each test had its own peculiarities, after the acquisition process, the data could be organized in four different classes, according to the type of transition from good to bad leader.

Before the labeling began, examples of different classes of good and bad leader situations were shown to the volunteers. Later they were asked to tell which of these situations occurred in each experiment. Although each test has its own peculiarities, the experiments can roughly fit one of the following classes:

1. good leader (gd) -leader(s) maintained their speed and orientation, withouth changing their behavior while being followed (Figure 5); 2. bad leader, moved aside (as) -leaders gave room for the robot to pass, generally moving aside, while keeping their original motion direction (Figure 6); 3. bad leader, far or fast (fr) -the distance between the leader and the robot grew to a point where it was not advantageous to keep following them (Figure 7); 4. bad leader, stopped (st) -when the person being followed stops moving (Figure 8). Besides the four typical situations mentioned before, two other situations were recorded, which did not involve leader following, but could enhance the classifier training. These are the case when candidates were not moving, but rather standing close to the robot's path (nm), or when they were moving towards the opposite direction (od).

Classifier Training

After labeling, each resulting dataset was given a name to identify the situation they represented, together with a number to differentiate them. This organization allowed training and test datasets to encompass all the cases encountered. In total, 12911 samples were obtained, with the proportion of 37% of bad leader labels and 63% of good leader labels. This is equivalent to 451 seconds of tests, divided in 47 experiments. Two datasets were created, one for the training comprising 8504 samples with 34% cases of bad leader, and a test dataset with 2715 samples and 39% cases of bad leader. The training dataset is composed of the following situations:

An iterative process was used in the training of AdaBoost structures. In each iteration, the most important features were kept and then the training data was reprocessed and a new AdaBoost was trained. The objective of this procedure was to evaluate the influence played by different sets of features in the classifier performance and on the importance of features.

Feature Contribution

Figure 9 shows the contribution ratio of each feature used, after the first training the classifier using 24 features. The most important features are the lateral displacement and the distance between the robot and the leader. Besides those, the standard deviation of the distance, of the relative heading and of the target velocity have significant impact on the classification process. Finally, the derivatives features have almost no role at all in classification. After an iterative process of picking the most important features and retraining the AdaBoost algorithm, results pointed to the standard deviation of the distance between the robot and the leader and the lateral displacement of the leader as the two most important features, as shown in Table 2. Together they contribution ratio was approximately 35% when training the classifier using only the eight most important features.

Classifier Performance

To evaluate classification, two metrics were created. The first is the false good leader, where the classifier labeled a sample as good leader but the ground truth has a bad leader label. This is the most critical error, because it means that the algorithm would potentially select a bad leader to be followed, possibly disturbing the person. The second metrics is the false bad leader, that occurred when the classifier output a bad leader and the ground truth is labeled as good leader. This error is less critical because it translates only in a lost opportunity to classify someone as a good leader.

Regarding the performance of the classifiers, applied to the registered data, the false good leader relative error was particularly large at the move aside situations. However, the error was much smaller in the remaining situations, and the overall performance of the classifier was remarkable, with the total relative error across all the situations around 3%.

Experiments

Platform and Setup

Although the aforementioned framework provided promising results, the classifier only operates over instantaneous measurements, and the ground truth was based on subjective impressions of volunteers. Therefore, to properly validate the proposed approach, interactive experiments are required.

Such experiments were conducted with an autonomous robotic wheelchair, equipped with two LIDAR sensors, the bottom one at 0.1m and the top other at aproximately 0.55m in height. The platform also incorporated a RGBD camera, an on-board computer that takes care of low-level hardware control tasks and also a notebook computer that hosts the high-level algorithms, as the localization, planning and leader selection and following.

Figure 11 illustrates the developed setup: after the score of a subject passes a threshold, that person can be considered a good leader to be followed. An example of this system is shown in Figure 12.

Such a difference of vote values means that someone needs several classifications of good leader to be considered to be followed, while only a couple of bad leader classifications is enough for a leader to be abandoned. Another advantage of this method is that a list with candidates scores allows for an easy switching of leaders. Once a leader is chosen, this module uses two proportional controllers, one for the distance and other for the heading, to compute velocity commands that are sent to the robot driver module, as shown in Figure 13.

4. RiskRRT Navigation: if no feasible leader was found, the robot still needs to be able to navigate in dynamic environments. To accomplish this, this module uses the RiskRRT [START_REF] Fulgenzi | Probabilistic navigation in dynamic environment using rapidly-exploring random trees and gaussian processes[END_REF] algorithm to compute paths that avoid risky situations, based on the motion prediction of persons. This module is always active and computing possible paths, even when the robot is engaged in a leader following behavior. In this way it can keep navigating when a leader is abandoned.

5. Velocity command multiplexer : in this setup, there are two modules that generate velocity commands to the robot. To manage which command will be sent to the robot, a simple multiplexer is used, which forwards the command with higher priority. The leader selector has the preference, but once a leader is lost or abandoned, it stops sending commands and them the RiskRRT module takes over.

Fig. 14. Switching navigation method between leader following and independent navigation.

Tests on Switching Navigation Method

The first experiment tests the performance of the proposed setup in switching between the leader following mode and the independent navigation, using the RiskRRT navigation algorithm. Figure 14 illustrates this experiment, where detected persons are represented by either a red circle (bad leaders) or a green circle (goo leaders). The chosen leader is represented by a light blue circle overlapping a green one. The small blue nodes are the exploration nodes of RiskRRT and the black line is the best path to navigate. The first image of the sequence (1) shows the robot following a leader while, at the same time, the independent algorithm computes possible navigation routes. Once the leader stops moving (2), a sequence of bad leader classifications makes his score fall below an acceptable threshold, and the robot abandons that leader. As soon as this happens, the robot starts to follow the path computed by the independent navigation algorithm, avoiding a collision with the former leader and also with another person crossing its path (3 -5), which is also classified as a bad leader. The robot later continues to navigate using only the RiskRRT algorithm (6).

Tests on Leader Switching

This experiment tests the setup capacity of maintaining a list of feasible leaders and switching among them when the score of one surpass the score from another. Figure 15 shows two experiments (one in each column), and as in previous tests, a green circle means an instantaneous good leader classification, while a red one means the opposite. The blue circle marks the person with the highest leader score.

On the first examples (left column), the robot is behind two persons that are classified as good leaders and following the one on the right. As this person slows down to enter an office, he looses score points and the algorithm promptly switches to the other person, who continues to move along the corridor.

The second example (right column), shows the robot following a leader along a corridor. At a given moment, the leader slows down and another persons, which is moving faster passes the robot. According to the voting setup, the person that passes by the robot receives a higher score and then the robot changes the leader and starts to follow the new subject.

Tests on Leader Following Among Crowds

On the final experiment the robot must be able to select and follow leader in densely populated environments. The test occurs in a narrow corridor, where even small groups of people create difficult conditions for robot navigation. This test is shown in Figure 16, and follow the same nomenclature from previous examples.

The experiment starts with the robot behind two persons moving along a corridor and following the one in the right side. Soon, a group of persons appear coming from the opposite direction and at the same time, the current leader stops to enter an office. The proposed setup manages to correctly identify a suitable leader among several subjects and successfully navigates through the crowd, taking advantage of the natural interactions among persons.

Conclusions

This study and experiments provided insightful findings about the limitations and advantages of the proposed leader selection and following approach.

-Autonomous wheelchairs are very interesting for experiments among persons. This is mainly because people are used to see wheelchairs, and normally assume there is a human on the control of it. As a result, their reactions and behavior are more natural, which allows studies with minimal interference from the robot. -A robust person tracker is essential for a leader selection system. When the robot followed someone, even short interruptions on the tracker resulted in erroneous leader classification and, therefore, in poor leader scoring, which hindered the navigation performance. Therefore, the identification of persons can be enhanced by using different sensors and detection methods, which must combined to provide a more robust detection and tracking system. Examples can be the fusion of images and laser scans to increase the reliability of people detection. -A balance must be found between taking advantage of a person's motion and disturbing that person. Sometimes if the robotic wheelchair was too close to a leader, such person would stop to give room for the robot to pass, invalidating the advantages of the proposed method. -Distance-related features play an important role in leader selection. Tests shown that the total and lateral distance to a candidate, together with their variance are crucial measurements to engage or disengage in a following behavior.

-The feature space should be enriched with additional sensors and descriptors.

In some situations the selected features were not sufficient to properly classify a candidate. Different sensors and features must be used to improve the performance of machine learning classifiers. For example, a camera could be used detect gaze direction, and a RGBD camera could detect torso, head and arm patterns. Another interesting descriptor would be a distance from a subject to a precomputed path for the robot, which could avoid the situation where the robot drifts away from an objective. -Leader following has a great potential for enhancing robot navigations. The presented framework and experiments validated the initial assumption that leader following can improve robotic navigation in dynamic environments, taking advantage of complex interactions among persons.

Fig. 1 .

 1 Fig. 1. Qualitative comparison of two navigation techniques in a narrow corridor. Left column: RiskRRT, right: leader following. Each row depicts the same instant during tests. Agents are represented by circles, the robot by the black rectangle and its path by a sequence of red arrows, showing its orientation in each instant.

Fig. 2 .

 2 Fig. 2. Left: platform used for data acquisition; middle: sample image from a wideangle camera; right: sample of laser measurements showing three tracked subjects and their orientation as the dark vectors. The robot is represented as a black rectangle.

Fig. 3 .

 3 Fig. 3. Diagram of the data labeling process.

Fig. 4 .

 4 Fig.4. Graphical representation of the features extracted while following. The robot is represented as a blue square while the human being followed as a red circle.

Fig. 5 .Fig. 6 .

 56 Fig. 5. Good leader behavior, although the robot is noticed, the leaders kept moving without changing their behaviors

Fig. 7 .

 7 Fig. 7. Bad leader: the subject marked with a white circle moves to fast compared to the robot's speed and gets too far from it.

Fig. 8 .

 8 Fig. 8. Bad leader: the person stops moving.

Fig. 9 .

 9 Fig.9. Feature contribution ratio using 24 features, number of weak learners: 548.

Fig. 10 .

 10 Fig. 10. Experimental platform, showing the two LIDARs and a RGBD camera.

Fig. 11 . 1 .

 111 Fig. 11. Experimental architecture.

Fig. 12 .

 12 Fig. 12. Leader score example.

Fig. 13 .

 13 Fig. 13. Leader follower controllers.

Fig. 15 .

 15 Fig. 15. Two tests on leader switching. On the left column the leader stops and the robot switches to follow another person. On the right a better leader appears on the scene.

Fig. 16 .

 16 Fig. 16. Leader score example.

Table 1 .

 1 Composition of training dataset

	number of	dataset
	datasets used	situation
	9	good leader
	7	bad leader, leader moved aside
	5	bad leader, leader too far or fast
	9	bad leader, leader stopped
	7	bad leader, candidate not moving
	10	bad leader, candidate coming from opposite direction

Table 2 .

 2 Contribution Ratio of Most Important Features

		size of feature set
	feature 24	16	12	8
	σ distance 0.077 0.085 0.104 0.181
	lateral displacement 0.120 0.130 0.118 0.169
	distance 0.120 0.131 0.125 0.122
	angle to robot 0.087 0.080 0.090 0.119
	sagittal displacement 0.052 0.053 0.078 0.118
	relative heading 0.078 0.083 0.081 0.113
	target velocity 0.068 0.068 0.082 0.093
	σ relative velocity in y 0.057 0.062 0.075 0.085

⋆ Procópio Stein is funded by INRIA's Large-scale initiative action PAL (Personally Assisted Living) pal.inria.fr


Bi Li

Fatima Zahra Moataz

Nicolas Nisse

Minimum Size Tree-Decompositions ⋆

Tree-Decompositions are the corner-stone of many dynamic programming algorithms for solving graph problems. Since the complexity of such algorithms generally depends exponentially on the width (size of the bags) of the decomposition, much work has been devoted to compute treedecompositions with small width. However, practical algorithms computing tree-decompositions only exist for graphs with treewidth less than 4. In such graphs, the time-complexity of dynamic programming algorithms based on tree-decompositions is dominated by the size (number of bags) of the treedecompositions. It is then interesting to try to minimize the size of the tree-decompositions. In this extended abstract, we consider the problem of computing a tree-decomposition of a graph with width at most k and minimum size. More precisely, we focus on the following problem: given a fixed k ≥ 1, what is the complexity of computing a tree-decomposition of width at most k with minimum size in the class of graphs with treewidth at most k? We prove that the problem is NP-complete for any fixed k ≥ 4 and polynomial for k ≤ 2. On going work also suggests it is polynomial for k = 3.

Introduction

A tree-decomposition of a graph G [START_REF] Robertson | Graph minors. ii. algorithmic aspects of tree-width[END_REF] is a way to represent G by a family of subsets of its vertex-set organized in a tree-like manner and satisfying some connectivity property. The treewidth of G measures the proximity of G with a tree. More formally, a tree decomposition of G = (V, E) is a pair (T, X ) where X = {X t |t ∈ V (T )} is a family of subsets, called bags, of V , and T is a tree, such that:

-t∈V (T ) X t = V ; -for any edge uv ∈ E, there is a bag X t (for some node t ∈ V (T )) containing both u and v; -for any vertex v ∈ V , the set {t ∈ V (T )|v ∈ X t } induces a subtree of T .

The width of a tree-decomposition (T, X ) is max t∈V (T ) |X t |-1 and its size is order |V (T )| of T . The treewidth of G, denoted by tw(G), is the minimum width over all possible tree-decompositions of G.

If T is constrained to be a path, (T, X ) is called a path-decomposition of G. The pathwidth of G, denoted by pw(G), is the minimum width over all possible path-decompositions of G.

Tree-Decompositions are the corner-stone of many dynamic programming algorithms for solving graph problems. As an example, the famous Courcelle's Theorem states that any problem expressible in MSOL can be solved in linear-time in the class of bounded treewidth graphs [START_REF] Courcelle | The monadic second-order logic of graphs. i. recognizable sets of finite graphs[END_REF]. Another framework based on graph decompositions is the bi-dimensionality theory that allowed the design of sub-exponential-time algorithms for many problems in the class of graphs excluding some fixed graph as a minor (e.g., [START_REF] Demaine | The bidimensionality theory and its algorithmic applications[END_REF]). Given a tree-decomposition with width w and size n, the time-complexity of most of such dynamic programming algorithms can be expressed as O(2 w n) (or O(2 w log w n) in the case of global problems). Therefore, the problem of computing tree-decompositions with small width has drawn much attention in the last decades. It has been extensively studied and investigated from different angles: parametrized complexity, exact or approximation algorithms.

The above mentioned algorithms have mainly a theoretical interest because, on the one hand, their timecomplexity exponential depends on the treewidth of graphs and, on the other hand, as far as we know, no practical algorithm exists that computes a "good" tree-decomposition for graphs with treewidth at least 5. However, in case of small (≤ 4) treewidth graphs, efficient (i.e., practical) algorithms exist to compute ⋆ tree-decompositions with optimal width. Moreover, in such case, the time-complexity of above-mentioned dynamic programming algorithms becomes dominated by the size of the tree-decompositions and, therefore, it becomes interesting to minimize it.

In this extended abstract, we deal with the problem of computing tree-decompositions with minimum size. Obviously, if the width is not constrained, then the problem is trivial since there always exists a treedecomposition of a graph with one bag (the full vertex-set). Hence, given a graph G and an integer k ≥ tw(G), we consider the problem of minimizing the size of a tree-decomposition of G with width at most k. Our results. Let k be any positive integer and G be any graph with treewidth at most k. Let s k (G) denote the smallest size of a tree-decomposition of G with width at most k. We first prove that, for any (fixed) k ≥ 4, the problem of computing s k is NP-hard in the class of graphs with treewidth at most k. Then, we prove that computing s 2 can be solved in polynomial-time in the class of graphs with treewidth at most 2. Related Work. The problem of computing "good" tree-decompositions has been extensively studied. Computing optimal tree-decomposition -i.e., with width tw(G) -is NP-complete in the class of general graphs G [START_REF] Arnborg | Complexity of finding embeddings in a k-tree[END_REF]. For any fixed k ≥ 1, Bodlaender designed an algorithm that computes, in time O(k k3 n), a treedecomposition of width k of any n-node graph with treewidth at most k [START_REF] Bodlaender | A linear-time algorithm for finding tree-decompositions of small treewidth[END_REF]. Very recently, a single-exponential (in k) algorithm has been proposed that computes a tree-decomposition with width at most 5k in the class of graphs with treewidth at most k [START_REF] Bodlaender | (c k n) 5-approximation algorithm for treewidth[END_REF]. As far as we know, the only practical algorithms for computing optimal tree-decompositions hold for graphs with treewidth at most 1 (trivial since tw(G) = 1 if and only if G is a tree), 2 (graphs excluding K 4 as a minor) [START_REF] Wald | Steiner trees, partial 2-trees, and minimum ifi networks[END_REF], 3 [2, 9, 10] and 4 [START_REF] Sanders | On linear recognition of tree-width at most four[END_REF].

We are not aware of any work dealing with the computation of tree-decompositions with minimum size. In [START_REF] Dereniowski | Minimum length path decompositions[END_REF], Dereniowski et al. consider the problem of size-constrained path-decompositions. Given any positive integer k and any graph G with pathwidth at most k. Let l k (G) denote the smallest size (length) of a pathdecomposition of G with width at most k. For any fixed k ≥ 4, computing l k is NP-complete in the class of general graphs and it is NP-complete, for any fixed k ≥ 5, in the class of connected graphs [START_REF] Dereniowski | Minimum length path decompositions[END_REF]. Moreover, computing l k can be solved in polynomial-time in the class of graphs with pathwidth at most k for any k ≤ 3. Finally, the "dual" problem is also hard: for any fixed s ≥ 2, it is NP-complete in general graphs to compute the minimum width of a tree-decomposition with size s [7] 3 .

NP-hardness in the class of graphs with treewidth at least 4

In this section, we prove that: Theorem 1. For any fixed integer k ≥ 4 (resp., k ≥ 5), the problem of computing s k is NP-complete in the class of graphs (resp., of connected graphs) with treewidth at most k.

Note that the corresponding decision problem is clearly in NP, hence, we only need to prove it is NP-hard. Our proof mainly follows the one of [START_REF] Dereniowski | Minimum length path decompositions[END_REF] for size-constrained path-decompositions. Hence, we recall here the two steps of the proof in [START_REF] Dereniowski | Minimum length path decompositions[END_REF]. First, it is proved that, if computing l k is NP-hard for some k ≥ 4 in general graphs, then the computation of l k+1 is NP-hard in the class of connected graphs. Then, it is shown that computing l 4 is NP-hard in general graphs with pathwidth at least 4, resp., computing l 5 is NP-hard in the class of connected graphs with pathwidth at least 5. The second step consists of a reduction from the 3-PARTITION problem [] to the one of computing l 4 (resp., of l 5 in connected graphs). Precisely, for any instance I of 3-PARTITION, a graph G I is built such that I is a YES instance if and only if l 4 (G I ) equals some defined value ℓ I .

Our contribution consists first in showing that the first step of [START_REF] Dereniowski | Minimum length path decompositions[END_REF] directly extends to the case of treedecompositions. That is, it directly implies that, if computing s k is NP-hard for some k ≥ 4 in general graphs, then the computation of s k+1 is NP-hard in connected graphs. Our main contribution of this section is to show that, for the graphs G I built in the reduction proposed in [START_REF] Dereniowski | Minimum length path decompositions[END_REF], any tree-decomposition of G I with width at most 4 and minimum size is a path decomposition. Hence, in this class of graphs, l 4 = s 4 and, therefore, for any instance I of 3-PARTITION, I is a YES instance if and only if s 4 (G I ) equals ℓ I . Theorem 1 follows.

Conclusion

In this extended abstract, we gave preliminary results on the complexity of minimizing the size of treedecompositions with given width. Table 1 summarizes our results as well as the remaining open questions. We currently investigate the case of s 3 in the class of graphs with treewidth 2 or 3 and we conjecture it is polynomially solvable. The problem of computing s k , for k ≥ 4, seems more intricate already in the case of trees. Indeed, our polynomial-time algorithms to compute s k , k ≤ 3, in trees mainly rely on the fact that, for any tree T , there exists a minimum-size tree-decomposition of T with width at most 3, where each bag induces a connected subtree. This is unfortunately not true anymore in the case of tree-decomposition with width 5. As an example, consider the tree (with 10 nodes) obtained from a star with three 3 leaves by subdividing twice each edge.

Table 1 .

 1 Summary of the complexity results.

		s1	s2	s3 s k , k ≥ 4
	tw = 1 P (trivial) P	P	?
	tw = 2	-	P	?	?
	tw = 3	-	-	?	?
	tw ≥ 4	-	-	-NP-hard

This result was proved in[START_REF] Dereniowski | Minimum length path decompositions[END_REF] in terms of path-decomposition but it is straightforward to extend it to treedecomposition.

Polynomial cases

In this section, we give preliminary results on when minimum size tree-decompositions can be computed in polynomial-time. We first investigate the case of forests. Theorem 2. For any k ∈ {1, 2, 3}, a tree-decomposition with size s k (F ) and width k can be computed in polynomial-time in the class of forests F .

Note that the computation of s 1 is trivially polynomial since, in particular, s 1 (T ) = n -1 for any n-node tree. For k ∈ {2, 3}, we design polynomial-time algorithms for computing s k in the class of forests. These are recursive algorithms that proceed greedily. Intuitively, in any forest F , we can identify a subgraph S of size at most k + 1 such that S is a bag in a minimum-size tree-decomposition of F with width k.

Due to lack of space, we only give an example in the case k = 3. Let F be a forest and let v ∈ V (F ) adjacent to exactly one non-leaf node. Moreover, assume that v is adjacent to at least three leaves a, b, c ∈ V (F ). Our algorithm first computes (recursively) a minimum-size tree-decomposition T of F \ {a, b, c} with width at most 3. Let B be any bag of T containing v. We prove that the tree-decomposition obtained from T by adding a bag {v, a, b, c} adjacent to B is a minimum-size tree-decomposition of F with width 3.

The key point is that the number of cases to consider is relatively small. In particular, in the case of trees, we prove that there always exists a minimum-size tree-decomposition with width at most k ≤ 3 where each bag induces a (connected) subtree. That is, in case of trees, the cases to consider are all trees with at most 4 nodes. It seems that our algorithms cannot be easily extended for k ≥ 4 since, in particular, this connectivity property is not valid anymore for k > 4 (see conclusion).

Then, we focus on graphs with treewidth 2. Theorem 3. A tree-decomposition of size s 2 (G) and width 2 can be computed in polynomial-time in the class of graphs G with treewidth 2.

The first step of the proof of the above theorem is to consider 2-connected graphs with treewidth 2. It is known that any 2-connected graph has treewidth 2 if and only if it has an open nested ear decomposition starting from a single edge [START_REF] Eppstein | Parallel recognition of series-parallel graphs[END_REF]. In particular, this implies that any such a graph contains a node with degree 2. Given a 2-connected graph G with treewidth 2, let v be a node with degree 2 and u and w its neighbors. Let G ′ obtained from G by contracting the edge {u, v} (or equivalently, removing v and adding an edge between u and w). Our algorithm first computes (recursively) a minimum-size tree-decomposition T of G ′ with width 2. One bag B of it contains {u, w}. We prove that the tree-decomposition obtained from T by adding a bag {v, u, w} adjacent to B is a minimum-size tree-decomposition of G with width 2.

Then, we consider the case of general graphs with treewidth 2. Given such a graph G, let G 1 , • • • , G r be its blocks, i.e., its inclusion-maximal 2-connected components and let G ′ be the graph obtained by removing all edges of the G i s (i ≤ r) and removing all nodes that are not cut-vertices. By definition G ′ is a forest. We prove that a minimum-size tree-decomposition of G with width 2 can easily be obtained by combining minimum-size tree-decompositions with width 2 of the subgraphs G i (computable in polynomial-time by above paragraph) and of F (using Theorem 2). More precisely, we prove that there always exists a minimumsize tree-decomposition of G with width 2 that does not contain mixed bags, i.e., bags containing two nodes in some G i and one node not in G i .

Finally, we consider the case k = 3 for graphs with treewidth 2. We prove that: Theorem 4. A tree-decomposition of size s 3 (G) and width at most 3 can be computed in polynomial-time in the class of 2-connected graphs G with treewidth 2.

Unfortunately, in the case k = 3, minimum-size tree-decomposition with width 3 may always contain mixed bags. This makes the computation of s 3 in the case of connected graphs with treewidth 2 more tricky. We are currently investigated this case.