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.

We present a new subclass of interval graphs that generalizes connected proper interval graphs. These graphs are characterized by vertex orderings called connected perfect elimination orderings (PEO), i.e., PEOs where consecutive vertices are adjacent. Alternatively, these graphs can also be characterized by special interval models and clique orderings. We present a linear-time recognition algorithm that uses PQ-trees. Furthermore, we study the behavior of multi-sweep graph searches on this graph class. This study also shows that Corneil’s well-known LBFS-recognition algorithm for proper interval graphs can be generalized to a large family of graph searches. Finally, we show that a strong result on the existence of Hamiltonian paths and cycles in proper interval graphs can be generalized to semi-proper interval graphs. • Introduction of semi-proper interval graphs, a novel subclass of interval graphs generalizing connected proper interval graphs. • Linear-time recognition algorithm for semi-proper interval graphs. • Generalization of Corneil’s LBFS recognition algorithm of proper interval graphs. • Generalization of Hamilton properties of proper interval graphs to semi-proper intervals.

The last in-tree recognition problem asks whether a given spanning tree can be derived by connecting each vertex with its rightmost left neighbor of some search ordering. In this study, we demonstrate that the last-in-tree recognition problem for Generic Search is NP-complete. We utilize this finding to strengthen a complexity result from order theory. Given a partial order π and a set of triples, the NP-complete intermezzo problem asks for a linear extension of π where each first element of a triple is not between the other two. We show that this problem remains NP-complete even when the Hasse diagram of the partial order forms a tree of bounded height. In contrast, we give an XP-algorithm for the problem when parameterized by the width of the partial order. Furthermore, we show that - under the assumption of the Exponential Time Hypothesis - the running time of this algorithm is asymptotically optimal. LIPIcs, Vol. 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), pages 22:1-22:18

The graph searches Breadth First Search (BFS) and Depth First Search (DFS) and the spanning trees constructed by them are some of the most basic concepts in algorithmic graph theory. BFS trees are first-in trees, i.e., every vertex is connected to its first visited neighbor. DFS trees are last-in trees, i.e., every vertex is connected to the last visited neighbor before it. The problem whether a given spanning tree can be the first-in tree or last-in tree of a graph search ordering was introduced in the 1980s and has been studied for several graph searches and graph classes. Here, we consider the problem of deciding whether a given spanning tree of a bipartite graph can be a first-in tree or a last-in tree of the Lexicographic Breadth First Search (LBFS), a special variant of BFS that is commonly used in graph algorithms. We show that the recognition of both first-in trees and last-in trees of LBFS is NP-hard even if the start vertex of the search ordering is fixed and the height of the tree is four. We prove that the bound on the height is tight (unless P=NP) by showing that for all spanning trees of bipartite graphs with height smaller than four we can solve both search tree recognition problems of LBFS in polynomial time. Finally, we give a linear-time algorithm that solves both problems for chordal bipartite graphs and fixed start vertices.

Abstract Solving problems on graphs dynamically calls for algorithms to function under repeated modifications to the graph and to be more efficient than solving the problem for the whole graph from scratch after each modification. Dynamic algorithms have been considered for several graph properties, for example connectivity, shortest paths and graph recognition. In this paper we present fully dynamic algorithms for the recognition of threshold graphs and chain graphs, which are optimal in the sense that the costs per modification are linear in the number of modified edges. Furthermore, our algorithms also consider the addition and deletion of sets of vertices as well as edges. In the negative case, i.e., where the graph is not a threshold graph or chain graph anymore, our algorithms return a certificate of constant size. Additionally, we present optimal fully dynamic algorithms for the Hamiltonian cycle problem and the Hamiltonian path problem on threshold and chain graphs which return a vertex cutset as certificate for the non-existence of such a path or cycle in the negative case.

The Distance Orientation Problem (DOP) is formulated as follows: Given a graph with positive weights on its edges, are there weights for the vertices, such that for every edge x y it holds that the absolute difference between the weights of x and y is equal to the weight of x y ? This problem can also be formulated as a problem of finding a special orientation of G and was motivated by an application in Shape from Shading, a method in the field of Computer Vision. We present a linear-time algorithm for complete 3-cover graphs, a generalization of chordal graphs and planar triangulations. For outerplanar graphs we show that the DOP is fixed-parameter tractable and present a pseudo-polynomial time algorithm for integral edge weights. Both algorithms use the idea that the existence of feasible weights for the vertices of an outerplanar graph can be decided by only looking at the edge weights of each face of its outerplane embedding separately. We show that this property does not hold for any embedding of a planar graph which is not outerplanar. Furthermore, we prove that the DOP is strongly NP -complete for grid graphs, i.e., there is no pseudo-polynomial algorithm to solve it unless P = NP .

The spanning trees of a graph constructed by the graph searches BFS and DFS are some of the most elementary structures in algorithmic graph theory. BFS-trees are first-in trees, i.e., every vertex is connected to its first visited neighbor. DFS-trees are last-in trees, i.e., every vertex is connected to its most recently visited neighbor. It is known since the 1980s that the problem of deciding whether a given spanning tree of a graph is a BFS-tree or a DFS-tree can be solved in linear time. Here, we will show that swapping the search-tree paradigms between these searches makes the problem hard, i.e., it is NP-complete to decide whether a spanning tree of a graph is a first-in-tree of a DFS or a last-in-tree of a BFS. To the best of our knowledge the latter result is the first hardness result for the recognition of last-in-trees for some graph search. Additionally, we study the complexity of both problems on split graphs.

Graph searches and the corresponding search trees can exhibit important structural properties and are used in various graph algorithms. The problem of deciding whether a given spanning tree of a graph is a search tree of a particular search on this graph was introduced by Hagerup in 1985, where the author showed that this problem is efficiently solvable for depth first search (DFS) trees and breadth first search (BFS) trees. If one defines such a search tree in the same way as done for BFS, i.e., by connecting every vertex to its first neighbor, then we call this an ${\cal F}$-tree. If, on the other hand, we connect it with its most recently visited neighbor (as in DFS) we call this an ${\cal L}$-tree. In this paper, we consider related search paradigms. We prove that the search tree problem can be solved in polynomial time for ${\cal L}$-trees of lexicographic depth first search, whereas the ${\cal F}$-tree recognition problem is $\mathcal{NP}$-complete for lexicographic breadth first search, lexicographic depth first search, maximum cardinality search, and maximal neighborhood search. Furthermore, we present polynomial results for both types of trees on chordal graphs.

Lexicographic Depth First Search (LexDFS) is a special variant of a Depth First Search (DFS), which was introduced by Corneil and Krueger in 2008. While this search has been used in various applications, in contrast to other graph searches, no general linear time implementation is known to date. In 2014, Köhler and Mouatadid achieved linear running time to compute some special LexDFS orders for cocomparability graphs. In this paper, we present a linear time implementation of LexDFS for chordal graphs. Our algorithm is able to find any LexDFS order for this graph class. To the best of our knowledge this is the first unrestricted linear time implementation of LexDFS on a non-trivial graph class. In the algorithm we use a search tree computed by Lexicographic Breadth First Search (LexBFS).

In order to promote public transport many municipalities use traffic signal control with a priority for buses or trams. In this paper, we address the problem of finding optimal passive transit signal priority settings. Building on a cyclically time-expanded network model for the combined traffic assignment traffic signal coordination problem, we introduce a suitable queuing model and several modifications to model public transport vehicles appropriately. We evaluate the applicability of this approach by computing and analyzing optimal solutions for several instances of a real-world scenario.

Most approaches for optimizing traffic signal timings deal with the daily traffic. However, there are a few occasional events like football matches or concerts of musicians that lead to exceptional traffic situations. Still, such events occur more or less regularly and place and time are known in advance. Hence, it is possible to anticipate such events with special signal timings. In this paper, we present an extension of a cyclically time-expanded network flow model and a corresponding mixed-integer linear programming formulation for simultaneously optimizing traffic signal timings and traffic assignment for such events. Besides the mathematical analysis of this approach, we demonstrate its capabilities by computing signal timings for a real world scenario.