@misc{BeisegelRatajczakScheffler, author = {Beisegel, Jesse and Ratajczak, Fabienne and Scheffler, Robert}, title = {Computing hamiltonian paths with partial order restrictions}, series = {ACM Transactions on Computation Theory}, volume = {17}, journal = {ACM Transactions on Computation Theory}, number = {1}, issn = {1942-3454}, doi = {10.1145/3711844}, pages = {1 -- 24}, abstract = {When solving the Hamiltonian path problem it seems natural to be given additional precedence constraints for the order in which the vertices are visited. For example, one could decide whether a Hamiltonian path exists for a fixed starting point, or that some vertices are visited before another vertex. We consider the problem of finding a Hamiltonian path that observes all precedence constraints given in a partial order on the vertex set. We show that this problem is NP-complete even if restricted to complete bipartite graphs and posets of height 2. In contrast, for posets of width k there is a known O(k^2 n^k) algorithm for arbitrary graphs with n vertices. We show that it is unlikely that the running time of this algorithm can be improved significantly, i.e., there is no f(k) n^o(k) time algorithm under the assumption of the Exponential Time Hypothesis. Furthermore, for the class of outerplanar graphs, we give an O(n^2) algorithm for arbitrary posets.}, language = {en} } @misc{BeisegelKlostKnorretal., author = {Beisegel, Jesse and Klost, Katharina and Knorr, Kristin and Ratajczak, Fabienne and Scheffler, Robert}, title = {A graph width perspective on partially ordered Hamiltonian paths and cycles II : vertex and edge deletion numbers}, series = {20th International Symposium on Parameterized and Exact Computation (IPEC 2025)}, journal = {20th International Symposium on Parameterized and Exact Computation (IPEC 2025)}, editor = {Agrawal, Akanksha and van Leeuwen, Erik Jan}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik}, address = {Wadern}, isbn = {978-3-95977-407-9}, doi = {10.4230/LIPIcs.IPEC.2025.30}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-251623}, pages = {30:1 -- 30:19}, abstract = {We consider the problem of finding a Hamiltonian path or cycle with precedence constraints in the form of a partial order on the vertex set. We study the complexity for graph width parameters for which the ordinary problems Hamiltonian Path and Hamiltonian Cycle are in FPT. In particular, we focus on parameters that describe how many vertices and edges have to be deleted to become a member of a certain graph class. We show that the problems are W[1]-hard for such restricted cases as vertex distance to path and vertex distance to clique. We complement these results by showing that the problems can be solved in XP time for vertex distance to outerplanar and vertex distance to block. Furthermore, we present some FPT algorithms, e.g., for edge distance to block. Additionally, we prove para-NP-hardness when considered with the edge clique cover number.}, language = {en} } @techreport{GessenhardtFlechsigNowakowskietal., author = {Gessenhardt, Judith and Flechsig, Laura and Nowakowski, Jan and Soult, Sandra and Ratajczak, Fabienne and Auerswald, Rico}, title = {Lausitz On-Demand : Wegweiser f{\"u}r moderne Bedarfsverkehre}, publisher = {[ui!] Urban Mobility Innovations GmbH}, address = {M{\"u}nchen}, pages = {IX, 45}, abstract = {Dieser Wegweiser bietet eine fundierte Einf{\"u}hrung in das Thema On-Demand-Verkehre und richtet sich in erster Linie an Kommunen, Landkreise und politische Entscheidungstr{\"a}ger, die bislang wenig Ber{\"u}hrungspunkte mit dieser Form des {\"o}ffentlichen Nahverkehrs hatten. Ziel ist nicht die Ausarbeitung einer konkreten Konzeption, sondern die Vermittlung von Grundlagenwissen, um Chancen, Herausforderungen und Einsatzm{\"o}glichkeiten besser einsch{\"a}tzen zu k{\"o}nnen. Im Mittelpunkt steht die Frage, wie On-Demand-Angebote bestehende Mobilit{\"a}tsl{\"u}cken - insbesondere im l{\"a}ndlichen Raum - schließen und damit soziale Teilhabe, nachhaltige Verkehrsgestaltung und die Attraktivit{\"a}t des {\"o}ffentlichen Nahverkehrs st{\"a}rken k{\"o}nnen. Der Wegweiser erl{\"a}utert zun{\"a}chst Begrifflichkeiten, Systemarten und Betriebsformen von Bedarfsverkehren, geht auf die Rolle neuer Technologien ein und beschreibt die notwendigen Schritte auf dem Weg zur Einf{\"u}hrung: von der Analyse des Status Quo {\"u}ber Bedarfs- und Raumanalysen bis hin zu {\"U}berlegungen zu Kosten, F{\"o}rderm{\"o}glichkeiten und organisatorischen Rahmenbedingungen. Dabei wird nicht nur ein konventioneller Betrieb in Betracht gezogen, sondern auch eine Umsetzung mit autonomen Shuttles thematisiert. Dar{\"u}ber hinaus werden zentrale Umsetzungsbestandteile wie Leitstellen, Mobilit{\"a}tsplattform, Marketingmaßnahmen oder Vergabeprozesse dargestellt. Durch praxisnahe Anwendungsbeispiele aus der Lausitz wird verdeutlicht, wie (autonome) On-Demand-Verkehre als Erg{\"a}nzung zum Linienverkehr wirken k{\"o}nnen - etwa bei der Anbindung touristischer Ziele oder bei der Sicherung von Anschl{\"u}ssen im l{\"a}ndlichen Raum. Damit stellt der Wegweiser einen Orientierungsrahmen bereit, der Kommunen und anderen Verantwortlichen eine erste Grundlage f{\"u}r fundierte Entscheidungen bietet. Er zeigt klar: On-Demand-Verkehre sind kein Ersatz f{\"u}r den klassischen {\"O}PNV, sondern eine strategische Erg{\"a}nzung, die Mobilit{\"a}t flexibler, inklusiver und nachhaltiger gestalten kann.}, language = {de} }