Turau, VolkerVolkerTurauWeyer, ChristophChristophWeyer2023-01-242023-01-242022-072nd Workshop on Combinatorial Reconfiguration, affiliated with The 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)http://hdl.handle.net/11420/14638In this work we consider reconfiguration problems for independent sets using the token sliding model. For some classes of graphs efficient algorithms are known to decide whether one independent set can be transformed into the other, e.g. for cographs, claw-free graphs, and trees. Demaine et al. showed that this decision problem is solvable in O(n) time for trees with n nodes. They also proved that in this case reconfiguration sequences have length O(n^2). In particular they provided an infinite family of instances on paths for which any reconfiguration sequence has length Omega(n^2). In this work we aim at determining the maximum lengths of reconfiguration sequences for trees with n nodes and independent sets of size s. We present preliminary results and conjectures.enIngenieurwissenschaftenConference Paper not in ProceedingsConference Paper