TY - GEN A1 - Beisegel, Jesse A1 - Ratajczak, Fabienne A1 - Scheffler, Robert T1 - Computing hamiltonian paths with partial order restrictions T2 - ACM Transactions on Computation Theory N2 - 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. KW - Hamiltonian path KW - Partial order KW - Outerplanar graph KW - Partial search order KW - TSP-PC KW - Parameterized complexity Y1 - 2025 UR - https://dl.acm.org/doi/10.1145/3711844 U6 - https://doi.org/10.1145/3711844 SN - 1942-3454 VL - 17 IS - 1 SP - 1 EP - 24 ER - TY - GEN A1 - Beisegel, Jesse A1 - Klost, Katharina A1 - Knorr, Kristin A1 - Ratajczak, Fabienne A1 - Scheffler, Robert ED - Agrawal, Akanksha ED - van Leeuwen, Erik Jan T1 - A graph width perspective on partially ordered Hamiltonian paths and cycles II : vertex and edge deletion numbers T2 - 20th International Symposium on Parameterized and Exact Computation (IPEC 2025) N2 - 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. KW - Hamiltonian path KW - Hamiltonian cycle KW - partial order KW - graph width parameter KW - parameterized complexity Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0030-drops-251623 UR - https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.30 SN - 978-3-95977-407-9 SP - 30:1 EP - 30:19 PB - Schloss Dagstuhl – Leibniz-Zentrum für Informatik CY - Wadern ER - TY - RPRT A1 - Gessenhardt, Judith A1 - Flechsig, Laura A1 - Nowakowski, Jan A1 - Soult, Sandra A1 - Ratajczak, Fabienne A1 - Auerswald, Rico T1 - Lausitz On-Demand : Wegweiser für moderne Bedarfsverkehre N2 - Dieser Wegweiser bietet eine fundierte Einführung in das Thema On-Demand-Verkehre und richtet sich in erster Linie an Kommunen, Landkreise und politische Entscheidungsträger, die bislang wenig Berührungspunkte mit dieser Form des öffentlichen Nahverkehrs hatten. Ziel ist nicht die Ausarbeitung einer konkreten Konzeption, sondern die Vermittlung von Grundlagenwissen, um Chancen, Herausforderungen und Einsatzmöglichkeiten besser einschätzen zu können. Im Mittelpunkt steht die Frage, wie On-Demand-Angebote bestehende Mobilitätslücken – insbesondere im ländlichen Raum – schließen und damit soziale Teilhabe, nachhaltige Verkehrsgestaltung und die Attraktivität des öffentlichen Nahverkehrs stärken können. Der Wegweiser erläutert zunächst Begrifflichkeiten, Systemarten und Betriebsformen von Bedarfsverkehren, geht auf die Rolle neuer Technologien ein und beschreibt die notwendigen Schritte auf dem Weg zur Einführung: von der Analyse des Status Quo über Bedarfs- und Raumanalysen bis hin zu Überlegungen zu Kosten, Fördermöglichkeiten und organisatorischen Rahmenbedingungen. Dabei wird nicht nur ein konventioneller Betrieb in Betracht gezogen, sondern auch eine Umsetzung mit autonomen Shuttles thematisiert. Darüber hinaus werden zentrale Umsetzungsbestandteile wie Leitstellen, Mobilitätsplattform, Marketingmaßnahmen oder Vergabeprozesse dargestellt. Durch praxisnahe Anwendungsbeispiele aus der Lausitz wird verdeutlicht, wie (autonome) On-Demand-Verkehre als Ergänzung zum Linienverkehr wirken können – etwa bei der Anbindung touristischer Ziele oder bei der Sicherung von Anschlüssen im ländlichen Raum. Damit stellt der Wegweiser einen Orientierungsrahmen bereit, der Kommunen und anderen Verantwortlichen eine erste Grundlage für fundierte Entscheidungen bietet. Er zeigt klar: On-Demand-Verkehre sind kein Ersatz für den klassischen ÖPNV, sondern eine strategische Ergänzung, die Mobilität flexibler, inklusiver und nachhaltiger gestalten kann. Y1 - 2025 UR - https://www.movetolausitz.de/images/Downloads/MoVeToLausitz_ODV_Wegweiser.pdf PB - [ui!] Urban Mobility Innovations GmbH CY - München ER -