@misc{SchefflerStrehlerVargasKoch, author = {Scheffler, Robert and Strehler, Martin and Vargas Koch, Laura}, title = {Routing Games with Edge Priorities}, series = {ACM Transactions on Economics and Computation}, volume = {10}, journal = {ACM Transactions on Economics and Computation}, number = {1}, issn = {2167-8375}, doi = {10.1145/3488268}, pages = {1:1 -- 1:27}, language = {en} } @misc{Scheffler, author = {Scheffler, Robert}, title = {The partial search order problem}, series = {The electronic journal of combinatorics}, volume = {32}, journal = {The electronic journal of combinatorics}, number = {4}, issn = {1077-8926}, doi = {10.37236/12654}, pages = {1 -- 37}, abstract = {In recent years, questions about the construction of special orderings of a given graph search were studied by several authors. On the one hand, the so called end-vertex problem introduced by Corneil et al. in 2010 asks for search orderings ending in a particular vertex. On the other hand, the problem of finding orderings that induce a given search tree was introduced already in the 1980s by Hagerup and received new attention most recently. Here, we consider a generalization of some of these problems by studying the question whether there is a search ordering that is a linear extension of a given partial order on a graph's vertex set. We show that this problem can be solved in polynomial time for Generic Search on general graphs as well as for searches called forgetful and partial orders of bounded width. Furthermore, we present polynomial-time algorithms on the classes of chordal bipartite graphs and split graphs for some searches including (Lexicographic) Breadth First Search. These algorithms generalize known algorithmic results for the End-Vertex Problem and the Search Tree Recognition Problem.}, language = {en} } @misc{Scheffler, author = {Scheffler, Robert}, title = {On the leaves of graph search trees}, series = {Ars Mathematica Contemporanea}, volume = {26}, journal = {Ars Mathematica Contemporanea}, number = {1}, publisher = {University of Primorska Press}, address = {Koper}, issn = {1855-3974}, doi = {10.26493/1855-3974.3238.2a8}, pages = {1 -- 29}, abstract = {Graph searches and their respective search trees are widely used in algorithmic graph theory. The problem whether a given spanning tree can be a graph search tree has been considered for different searches, graph classes and search tree paradigms. Similarly, the question whether a particular vertex can be visited last by some search has been studied extensively in recent years. We combine these two problems by considering the question whether a vertex can be a leaf of a graph search tree. We show that for particular search trees, including DFS trees, this problem is easy if we allow the leaf to be the first vertex of the search ordering. We contrast this result by showing that the problem becomes hard for many searches, including DFS and BFS, if we forbid the leaf to be the first vertex. Additionally, we present several structural and algorithmic results for search tree leaves of chordal graphs.}, 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} }