We study the computational complexity of determining structural properties of edge-periodic temporal graphs (EPGs). EPGs are time-varying graphs that compactly represent periodic behavior of components of a dynamic network, for example, train schedules on a rail network. In EPGs, for each edge e of the graph, a binary string τ ( e ) determines in which time steps the edge is present, namely e is present in time step t if and only if τ ( e ) contains a 1 at position t mod | τ ( e ) | . Due to this periodicity, EPGs serve as very compact representations of complex periodic systems and can even be exponentially smaller than classic temporal graphs representing one period of the same system, as the latter contain the whole sequence of graphs explicitly. In this paper, we study the computational complexity of fundamental questions of the concept of EPGs such as : Is there a time step or a sliding window of size Δ in which the graph (1) is minor-free; (2) contains a minor; (3) is induced subgraph-free; (4) contains an induced subgraph; with respect to a given minor or subgraph. We give a detailed parameterized analysis for multiple combinations of parameters for the problems stated above including several algorithms. Additionally, we study the parameterized complexity of the short traversal problem in EPGs. In this problem, one asks whether there exists a time step t such that one can reach a vertex b from a vertex a at time step at most t + k for given k .

The analysis of social networks and community detection is a central theme in Artificial Intelligence. One line of research deals with finding groups of agents that could work together to achieve a certain goal. To this end, different notions of so-called clusters or communities have been introduced in the literature of graphs and networks. Among these, a defensive alliance is a kind of quantitative group structure. However, all studies on alliances so far have ignored one aspect that is central to the formation of alliances on a very intuitive level, assuming that the agents are preconditioned concerning their attitude towards other agents: they prefer to be in some group (or in an alliance) together with the agents they like, so that they are happy to help each other towards their common aim, possibly then working against the agents outside of their group that they dislike. Signed networks were introduced in the psychology literature to model liking and disliking between agents, generalizing graphs in a natural way. Hence, we propose the novel notion of a defensive alliance in the context of signed networks. We then investigate several natural algorithmic questions related to this notion. These, and also combinatorial findings, connect our notion to that of correlation clustering, which is a well-established idea of finding groups of agents within a signed network. Also, we introduce a new structural parameter for signed graphs, the signed neighborhood diversity snd, and exhibit a snd-parameterized algorithm that finds one of the smallest defensive alliances in a signed graph.

In the periodic temporal graph realization problem introduced by Klobas et al. [SAND '24] one is given a period Δ and an n × n matrix D of desired fastest travel times, and the task is to decide if there is a simple periodic temporal graph with period Δ such that the fastest travel time between any pair of vertices matches the one specified by D . We generalize the problem from simple temporal graphs to temporal graphs where each edge can appear up to ℓ times in each period, for some given integer ℓ . For the resulting problem Multi-Label Periodic TGR , we show that it is fixed-parameter tractable for parameter n and for parameter vc + Δ , where vc is the vertex cover number of the underlying graph. We also show the existence of a polynomial kernel for parameter nu + d max , where nu is the number of non-universal vertices of the underlying graph and d max is the largest entry of D . Furthermore, we show that the problem is NP -hard for each ℓ ≥ 5 , even if the underlying graph is a tree, a case that was known to be solvable in polynomial time if the task is to construct a simple periodic temporal graph, that is, if ℓ = 1 .

A temporal graph is a graph whose edges only appear at certain points in time. Reachability in these graphs is defined in terms of paths that traverse the edges in chronological order (temporal paths). This form of reachability is neither symmetric nor transitive, the latter having important consequences on the computational complexity of even basic questions, such as computing temporal connected components. In this paper, we introduce several parameters that capture how far a temporal graph $\mathcal{G}$ is from being transitive, namely, \emph{vertex-deletion distance to transitivity} and \emph{arc-modification distance to transitivity}, both being applied to the reachability graph of $\mathcal{G}$. We illustrate the impact of these parameters on the temporal connected component problem, obtaining several tractability results in terms of fixed-parameter tractability and polynomial kernels. Significantly, these results are obtained without restrictions of the underlying graph, the snapshots, or the lifetime of the input graph. As such, our results isolate the impact of non-transitivity and confirm the key role that it plays in the hardness of temporal graph problems.

Given a finite set 𝒜 of square matrices and a square matrix B, all of the same dimension, the membership problem asks if B belongs to the monoid ℳ(𝒜) generated by 𝒜. The rank one problem asks if there is a matrix of rank one in ℳ(𝒜). We study the membership and the rank one problems in the case where all matrices are upper triangular matrices over the Boolean semiring. We characterize the computational complexity of these problems, and identify their PSPACE-complete and NP-complete special cases. We then consider, for a set 𝒜 of matrices from the same class, the problem of finding in ℳ(𝒜) a matrix of minimum rank with no zero rows. We show that the minimum rank of such matrix can be computed in linear time.We also characterize the space complexity of this problem depending on the size of 𝒜, and apply all these results to the ergodicity problem asking if ℳ(𝒜) contains a matrix with a column consisting of all ones. Finally, we show that our results give better upper bounds for the case where each row of every matrix in 𝒜 contains at most one non-zero entry than for the general case.

One of the most fundamental problems in computational learning theory is the problem of learning a finite automaton A consistent with a finite set P of positive examples and with a finite set N of negative examples. By consistency, we mean that A accepts all strings in P and rejects all strings in N. It is well known that this problem is NP-complete. In the literature, it is stated that NP-hardness holds even in the case of a binary alphabet. As a standard reference for this theorem, the work of Gold from 1978 is either cited or adapted. Nevertheless, the results in Gold's work are stated in terms of Mealy machines, and not in terms of deterministic finite automata (DFAs) as most commonly defined. As Mealy machines are equipped with an output function, they can be more compact than DFAs which accept the same language. We show that the adaptations of Gold's construction for Mealy machines stated in the literature have some issues, and provide a correct proof for the fact that the DFA-consistency problem for binary alphabets is NP-complete.

We introduce a cops and robbers game with one cop and one robber on a special type of time-varying graphs (TVGs), namely edge-periodic graphs. These are TVGs in which, for each edge e, a binary string τ(e) is given such that the edge e is present in time step t if and only if τ(e) contains a 1 at position tmod|τ(e)|. This periodicity allows for a compact representation of infinite TVGs. We prove that even for very simple underlying graphs, i.e., directed and undirected cycles, the problem of deciding whether a cop-winning strategy exists is NP-hard and W[1]-hard parameterized by the number of vertices. Furthermore, we show that this decision problem can be solved on general edge-periodic graphs in PSPACE. Finally, we present tight bounds on the minimum length of a directed or undirected cycle that guarantees the cycle to be robber-winning.

A central computational problem in the realm of automata theory is the problem of determining whether a finite automaton A has a synchronizing word. This problem has found applications in a variety of subfields of artificial intelligence, including planning, robotics, and multi-agent systems. In this work, we study this problem within the framework of diversity of solutions, an up-and-coming trend in the field of artificial intelligence where the goal is to compute a set of solutions that are sufficiently distinct from one another. We define a notion of diversity of solutions that is suitable for contexts were solutions are strings that may have distinct lengths. Using our notion of diversity, we show that for each fixed r ∈ N, each fixed finite automaton A, and each finite automaton B given at the input, the problem of determining the existence of a diverse set {w1,w2, . . . ,wr} ⊆ L(B) of words that are synchronizing for A can be solved in polynomial time. Finally, we generalize this result to the realm of conformant planning, where the goal is to devise plans that achieve a goal irrespectively of initial conditions and of nondeterminism that may occur during their execution.

We study the kernelization of exploration problems on temporal graphs. A temporal graph consists of a finite sequence of snapshot graphs $\mathcal{G}=(G_1, G_2, \dots, G_L)$ that share a common vertex set but might have different edge sets. The non-strict temporal exploration problem (NS-TEXP for short) introduced by Erlebach and Spooner, asks if a single agent can visit all vertices of a given temporal graph where the edges traversed by the agent are present in non-strict monotonous time steps, i.e., the agent can move along the edges of a snapshot graph with infinite speed. The exploration must at the latest be completed in the last snapshot graph. The optimization variant of this problem is the $k$-arb NS-TEXP problem, where the agent's task is to visit at least $k$ vertices of the temporal graph. We show that under standard computational complexity assumptions, neither of the problems NS-TEXP nor $k$-arb NS-TEXP allow for polynomial kernels in the standard parameters: number of vertices $n$, lifetime $L$, number of vertices to visit $k$, and maximal number of connected components per time step $γ$; as well as in the combined parameters $L+k$, $L + γ$, and $k+γ$. On the way to establishing these lower bounds, we answer a couple of questions left open by Erlebach and Spooner. We also initiate the study of structural kernelization by identifying a new parameter of a temporal graph $p(\mathcal{G}) = \sum_{i=1}^{L} (|E(G_i)|) - |V(G)| +1$. Informally, this parameter measures how dynamic the temporal graph is. Our main algorithmic result is the construction of a polynomial (in $p(\mathcal{G})$) kernel for the more general Weighted $k$-arb NS-TEXP problem, where weights are assigned to the vertices and the task is to find a temporal walk of weight at least $k$.

Abstract Traditionally, graph algorithms get a single graph as input, and then they should decide if this graph satisfies a certain property $$\varPhi $$ Φ . What happens if this question is modified in a way that we get a possibly infinite family of graphs as an input, and the question is if there is a graph satisfying $$\varPhi $$ Φ in the family? We approach this question by using formal languages for specifying families of graphs, in particular by regular sets of words. We show that certain graph properties can be decided by studying the syntactic monoid of the specification language L if a certain torsion condition is satisfied. This condition holds trivially if L is regular. More specifically, we use a natural binary encoding of finite graphs over a binary alphabet $$\varSigma $$ Σ , and we define a regular set $$\mathbb {G}\subseteq \varSigma ^*$$ G ⊆ Σ ∗ such that every nonempty word $$w\in \mathbb {G}$$ w ∈ G defines a finite and nonempty graph. Also, graph properties can then be syntactically defined as languages over $$\varSigma $$ Σ . Then, we ask whether the automaton $$\mathcal {A}$$ A specifies some graph satisfying a certain property $$\varPhi $$ Φ . Our structural results show that we can answer this question for all “typical” graph properties. In order to show our results, we split L into a finite union of subsets and every subset of this union defines in a natural way a single finite graph F where some edges and vertices are marked. The marked graph in turn defines an infinite graph $$F^\infty $$ F ∞ and therefore the family of finite subgraphs of $$F^\infty $$ F ∞ where F appears as an induced subgraph. This yields a geometric description of all graphs specified by L based on splitting L into finitely many pieces; then using the notion of graph retraction, we obtain an easily understandable description of the graphs in each piece.

Hamburg was the place where he used to live from his childhood onwards.There, he also obtained his doctoral degree with his dissertation entitled "Kontextfrei kontrollierte ET0L-Systeme" (engl."Context-free Controlled ET0L-Systems") in 1983, and his habilitation with the thesis "Nichtdeterministische Reduktionen und logarithmische Hierarchien" (engl."Nondeterministic Reductions and Logarithmic Hierarchies") in 1986.During his Hamburg years he visited

Abstract The regular intersection emptiness problem for a decision problemP( $${{\textit{int}}_{{\mathrm {Reg}}}}$$ intReg (P)) is to decide whether a potentially infinite regular set of encodedP-instances contains a positive one. Since $${{\textit{int}}_{{\mathrm {Reg}}}}$$ intReg (P) is decidable for some NP-complete problems and undecidable for others, its investigation provides insights in the nature of NP-complete problems. Moreover, the decidability of the $${{\textit{int}}_{{\mathrm {Reg}}}}$$ intReg -problem is usually achieved by exploiting the regularity of the set of instances; thus, it also establishes a connection to formal language and automata theory. We consider the $${{\textit{int}}_{{\mathrm {Reg}}}}$$ intReg -problem for the well-known NP-complete problemInteger Linear Programming(ILP). It is shown that any DFA that describes a set ofILP-instances (in a natural encoding) can be reduced to a finite core of instances that contains a positive one if and only if the original set of instances did. This result yields the decidability of $${{\textit{int}}_{{\mathrm {Reg}}}}$$ intReg (ILP).

A deterministic finite automaton (DFA) 𝒜 is composite if its language L(𝒜) can be decomposed into an intersection ⋂_{i = 1}^k L(𝒜_i) of languages of smaller DFAs. Otherwise, 𝒜 is prime. This notion of primality was introduced by Kupferman and Mosheiff in 2013, and while they proved that we can decide whether a DFA is composite, the precise complexity of this problem is still open, with a doubly-exponential gap between the upper and lower bounds. In this work, we focus on permutation DFAs, i.e., those for which the transition monoid is a group. We provide an NP algorithm to decide whether a permutation DFA is composite, and show that the difficulty of this problem comes from the number of non-accepting states of the instance: we give a fixed-parameter tractable algorithm with the number of rejecting states as the parameter. Moreover, we investigate the class of commutative permutation DFAs. Their structural properties allow us to decide compositionality in NL, and even in LOGSPACE if the alphabet size is fixed. Despite this low complexity, we show that complex behaviors still arise in this class: we provide a family of composite DFAs each requiring polynomially many factors with respect to its size. We also consider the variant of the problem that asks whether a DFA is k-factor composite, that is, decomposable into k smaller DFAs, for some given integer k ∈ ℕ. We show that, for commutative permutation DFAs, restricting the number of factors makes the decision computationally harder, and yields a problem with tight bounds: it is NP-complete. Finally, we show that in general, this problem is in PSPACE, and it is in LOGSPACE for DFAs with a singleton alphabet.

The binary representation of an arbitrary string does not contain long runs of repeating bits, but, first, reading all most significant bits of all bytes, then all second most significant bits and so on, results in much longer average runs. We use this observation in combination with several preprocessing steps to obtain a lossless RLE based compression algorithm comparable to ZIP: First, the uncompressed byte array is analyzed and for each byte its number of occurrences is counted. In parallel, a bijective Burrows-Wheeler-Scott Transform is applied, which produces a reversible permutation of the input byte array with long repetitions of similar symbols. Afterwards, each byte is remapped, where the most frequent byte values are mapped to the lowest binary values. The resulting byte array is interpreted in a specific way, known as Bit-Layers text representation, where all bits of same significance are read consecutively, starting with the most significant bits, resulting in long average runs of identical bits. On this representation, a run length encoding (RLE) is applied and the runs are counted to generate a Huffman tree. Then, the runs are output with a variable length code, together with the mapping needed to decompress the file.

In the Intersection Non-Emptiness problem, we are given a list of finite automata $A_1,A_2,\dots,A_m$ over a common alphabet $Σ$ as input, and the goal is to determine whether some string $w\in Σ^*$ lies in the intersection of the languages accepted by the automata in the list. We analyze the complexity of the Intersection Non-Emptiness problem under the promise that all input automata accept a language in some level of the dot-depth hierarchy, or some level of the Straubing-Thérien hierarchy. Automata accepting languages from the lowest levels of these hierarchies arise naturally in the context of model checking. We identify a dichotomy in the dot-depth hierarchy by showing that the problem is already NP-complete when all input automata accept languages of the levels zero or one half and already PSPACE-hard when all automata accept a language from the level one. Conversely, we identify a tetrachotomy in the Straubing-Thérien hierarchy. More precisely, we show that the problem is in AC$^0$ when restricted to level zero; complete for LOGSPACE or NLOGSPACE, depending on the input representation, when restricted to languages in the level one half; NP-complete when the input is given as DFAs accepting a language in from level one or three half; and finally, PSPACE-complete when the input automata accept languages in level two or higher. Moreover, we show that the proof technique used to show containment in NP for DFAs accepting languages in the Straubing-Thérien hierarchy levels one ore three half does not generalize to the context of NFAs. To prove this, we identify a family of languages that provide an exponential separation between the state complexity of general NFAs and that of partially ordered NFAs. To the best of our knowledge, this is the first superpolynomial separation between these two models of computation.

In its most traditional setting, the main concern of optimization theory is the search for optimal solutions for instances of a given computational problem. A recent trend of research in artificial intelligence, called solution diversity, has focused on the development of notions of optimality that may be more appropriate in settings where subjectivity is essential. The idea is that instead of aiming at the development of algorithms that output a single optimal solution, the goal is to investigate algorithms that output a small set of sufficiently good solutions that are sufficiently diverse from one another. In this way, the user has the opportunity to choose the solution that is most appropriate to the context at hand. It also displays the richness of the solution space. When combined with techniques from parameterized complexity theory, the paradigm of diversity of solutions offers a powerful algorithmic framework to address problems of practical relevance. In this work, we investigate the impact of this combination in the field of Kemeny Rank Aggregation, a well-studied class of problems lying in the intersection of order theory and social choice theory and also in the field of order theory itself. In particular, we show that KRA is fixed-parameter tractable with respect to natural parameters providing natural formalizations of the notions of diversity and of the notion of a sufficiently good solution. Our main results work both when considering the traditional setting of aggregation over linearly ordered votes, and in the more general setting where votes are partially ordered.

In this work, we consider the following order reconfiguration problem: Given a graph G together with linear orders ω and ω' of the vertices of G, can one transform ω into ω' by a sequence of swaps of adjacent elements in such a way that at each time step the resulting linear order has cutwidth (pathwidth) at most k? We show that this problem always has an affirmative answer when the input linear orders ω and ω' have cutwidth (pathwidth) at most k/2. Using this result, we establish a connection between two apparently unrelated problems: the reachability problem for two-letter string rewriting systems and the graph isomorphism problem for graphs of bounded cutwidth. This opens an avenue for the study of the famous graph isomorphism problem using techniques from term rewriting theory.

We consider the cops and robbers game variant consisting of one cop and one robber on time-varying graphs (TVG). The considered TVGs are edge periodic graphs, i.e., for each edge, a binary string s_e determines in which time step the edge is present, namely the edge e is present in time step t if and only if the string s_e contains a 1 at position t mod |s_e|. This periodicity allows for a compact representation of an infinite TVG. We prove that even for very simple underlying graphs, i.e., directed and undirected cycles the problem whether a cop-winning strategy exists is NP-hard and W[1]-hard parameterized by the number of vertices. Our second main result are matching lower bounds for the ratio between the length of the underlying cycle and the least common multiple (lcm) of the lengths of binary strings describing edge-periodicies over which the graph is robber-winning. Our third main result improves the previously known EXPTIME upper bound for Periodic Cop & Robber on general edge periodic graphs to PSPACE-membership.

Imagine an assembly line where a box with a lid and liquid in it enters in some unknown orientation. The box should leave the line with the open lid facing upwards with the liquid still in it. To save costs there are no complex sensors or image recognition software available on the assembly line, so a reset sequence needs to be computed. But how can the dependencies of the deforming impact of a transformation of the box, such as 'do not tilt the box over when the lid is open' or 'open the lid again each time it gets closed' be modeled? We present three attempts to model constraints of these kinds on the order in which the states of an automaton are transitioned by a synchronizing word. The first two concepts relate the last visits of states and form constraints on which states still need to be reached, whereas the third concept concerns the first visits of states and forms constraints on which states might still be reached. We examine the computational complexity of different variants of the problem, whether an automaton can be synchronized with a word that respects the constraints defined in the respective concept, and obtain nearly a full classification. While most of the problems are PSPACE-complete we also observe NP-complete variants and variants solvable in polynomial time. We will also observe a drop of the complexity if we track the orders of states on several paths simultaneously instead of tracking the set of active states. Further, we give upper bounds on the length of a synchronizing word depending on the size of the input relation and show that the Cerny conjecture holds for partial weakly acyclic automata.

We are studying a weighted version of a linear extension problem, given some finite partial order ρ, called Completion of an Ordering. While this problem is NP-complete, we show that it lies in FPT when parameterized by the interval width of ρ. This ordering problem can be used to model several ordering problems stemming from diverse application areas, such as graph drawing, computational social choice, or computer memory management. Each application yields a special ρ. We also relate the interval width of ρ to parameterizations such as maximum range that have been introduced earlier in these applications, sometimes improving on parameterized algorithms that have been developed for these parameterizations before. This approach also gives some practical sub-exponential time algorithms for ordering problems.

We generalize the concept of synchronizing words for finite automata, which map all states of the automata to the same state, to deterministic visibly push-down automata. Here, a synchronizing word w does not only map all states to the same state but also fulfills some conditions on the stack content of each run after reading w. We consider three types of these stack constraints: after reading w, the stack (1) is empty in each run, (2) contains the same sequence of stack symbols in each run, or (3) contains an arbitrary sequence which is independent of the other runs. We show that in contrast to general deterministic push-down automata, it is decidable for deterministic visibly push-down automata whether there exists a synchronizing word with each of these stack constraints, i.e., the problems are in EXPTIME. Under the constraint (1) the problem is even in P. For the sub-classes of deterministic very visibly push-down automata the problem is in P for all three types of constraints. We further study variants of the synchronization problem where the number of turns in the stack height behavior caused by a synchronizing word is restricted, as well as the problem of synchronizing a variant of a sequential transducer, which shows some visibly behavior, by a word that synchronizes the states and produces the same output on all runs.

The question if a deterministic finite automaton admits a software reset in the form of a so-called synchronizing word can be answered in polynomial time. In this paper, we extend this algorithmic question to deterministic automata beyond finite automata. We prove that the question of synchronizability becomes undecidable even when looking at deterministic one-counter automata. This is also true for another classical mild extension of regularity, namely that of deterministic one-turn push-down automata. However, when we combine both restrictions, we arrive at scenarios with a PSPACE-complete (and hence decidable) synchronizability problem. Likewise, we arrive at a decidable synchronizability problem for (partially) blind deterministic counter automata. There are several interpretations of what synchronizability should mean for deterministic push-down automata. This is depending on the role of the stack: should it be empty on synchronization, should it be always the same or is it arbitrary? For the automata classes studied in this paper, the complexity or decidability status of the synchronizability problem is mostly independent of this technicality, but we also discuss one class of automata where this makes a difference.