ABSTRACT. Recent advances in the design of efficient parallel algorithmshave been largely focusing on the nowadays classical model of parallelcomputing called Massive Parallel Computation (MPC), which follows theframework of MapReduce systems. In this talk we survey recent advancesin the design of algorithms for graph problems for the MPC model andwill mention some interesting open questions in this area.

ABSTRACT. We extend the theory of formal languages in monoidal categories to the multi-sorted, symmetric case, and show how this theory permits a graphical treatment of topics in concurrency. In particular, we show that Mazurkiewicz trace languages are precisely symmetric monoidal languages over monoidal distributed alphabets. We introduce symmetric monoidal automata, which define the class of regular symmetric monoidal languages. Furthermore, we prove that Zielonka’s asynchronous automata coincide with symmetric monoidal automata over monoidal distributed alphabets. Finally, we apply the string diagrams for symmetric premonoidal categories to derive serializations of traces.

ABSTRACT. The paper completely characterizes the primality of acyclic DFAs, where a DFA A is prime if there do not exist DFAs A_1,...,A_t with L(A) = \bigcap_{i=1}^{t} L(A_i) such that each A_i has strictly less states than the minimal DFA recognizing the same language as A. A regular language is prime if its minimal DFA is prime. Thus, this result also characterizes the primality of finite languages.

Further, the NL-completeness of the corresponding decision problem Prime-DFA_fin is proven. The paper also characterizes the primality of acyclic DFAs under two different notions of compositionality, union and union-intersection compositionality.

Additionally, the paper introduces the notion of S-primality, where a DFA A is S-prime if there do not exist DFAs A_1,...,A_t with L(A) = \bigcap_{i=1}^{t} L(A_i) such that each A_i has strictly less states than A itself. It is proven that the problem of deciding S-primality for a given DFA is NL-hard. To do so, the NL-completeness of 2Minimal-DFA, the basic problem of deciding minimality for a DFA with at most two letters, is proven.

ABSTRACT. A probabilistic variant of input-driven pushdown automata (IDPDA, also known as visibly pushdown automata) is introduced. It is proved that these automata can be determinized: an n-state probabilistic IDPDA with an isolated \delta-cutpoint is transformed to a deterministic IDPDA with at most (1+\frac{1}{\delta})^{n^2-n} states recognizing the same language. An asymptotically close lower bound is provided: for infinitely many n, there is a probibilistic IDPDA with 4n+1 states and a \frac{1}{270n}-cutpoint, such that every equivalent deterministic IDPDA needs at least 7^{n^2/14} states. A few special cases of automata with reduced determinization complexity are identified.

ABSTRACT. The universality problem asks whether a given finite state automaton accepts all the input words. For quantitative models of automata, where input words are mapped to real values, this is naturally extended to ask whether all the words are mapped to values above (or below) a given threshold. This is known to be undecidable for commonly studied examples such as weighted automata over the positive rational (plus-times) or the integer tropical (min-plus) semirings, or equivalently cost register automata (CRAs) over these semirings. In this paper, we prove that when restricted to CRAs with only three registers, the universality problem is still undecidable, even with additional restrictions for the CRAs to be copyless linear with resets.

In contrast, we show that, assuming the unary encoding of updates, the $\forall$-exact problem (does the CRA output zero on all the words?) for integer min-plus linear CRAs can be decided in polynomial time if the number of registers is constant. Without the restriction on the number of registers this problem is known to be PSPACE-complete.

ABSTRACT. We study a two-player game on a graph between an attacker and a defender. To begin with, the defender places guards on a subset of vertices. In each move, the attacker attacks an edge. The defender must move at least one guard along the attacked edge to defend the attack. The defender wins if and only if they can defend an infinite sequence of attacks. The smallest number of guards with which the defender has a winning strategy is called the eternal vertex cover number of G and is denoted by evc(G). It is clear that evc(G) is at least mvc(G), the size of a minimum vertex cover of G. We say that G is Spartan if evc(G) = mvc(G). The characterization of Spartan graphs has been largely open. In the setting of bipartite graphs on 2n vertices where every edge belongs to a perfect matching, an easy strategy is to have n guards that always move along perfect matchings in response to attacks. We show that these are essentially the only Spartan bipartite graphs.

ABSTRACT. In 1992 Biro, Hujter and Tuza introduced, for every fixed connected graph H, the class of H-graphs, defined as the intersection graphs of connected subgraphs of some subdivision of H. Such classes of graphs are related to many known graph classes: for example, K_2-graphs coincide with interval graphs, K_3-graphs with circular-arc graphs, the union of T-graphs, where T ranges over all trees, coincide with chordal graphs. Recently, quite a lot of research has been devoted to understanding the tractability border for various computational problems, such as recognition or isomorphism testing, in classes of H-graphs for different graphs H.

In this work we undertake this research topic, focusing on the recognition problem. Chaplick, Toepfer, Vobornik, and Zeman showed an XP-algorithm testing whether a given graph is a T-graph, where the parameter is the size of the tree T. In particular, for every fixed tree T the recognition of T-graphs can be solved in polynomial time. Tucker showed a polynomial time algorithm recognizing K_3-graphs (circular-arc graphs). On the other hand, Chaplick at al. showed also that for every fixed graph H containing two distinct cycles sharing an edge the recognition of H-graphs is NP-hard.

The main two results of this work narrow the gap between the NP-hard and P cases of H-graphs recognition. First, we show that recognition of H-graphs is NP-hard when H contains two distinct cycles. On the other hand, we show a polynomial-time algorithm recognizing L-graphs, where L is a graph containing a cycle and an edge attached to it (which we call lollipop graphs). Our work leaves open the recognition problems of M-graphs for every unicyclic graph M different from a cycle and a lollipop.

Further, we study medusa graphs, which are defined as the union of M-graphs, where M runs over all unicyclic graphs. Note that medusa graphs extend both circular-arc graphs and chordal graphs. We show that the problem of recognizing medusa graphs is NP-complete.

ABSTRACT. We present a $9^k\cdot n^{O(1)}$-time algorithm for the proper circular-arc vertex deletion problem, resolving an open problem of van ’t Hof and Villanger~[Algorithmica 2013] and Crespelle et al.~[Computer Science Review 2023]. Our structural study also implies parameterized algorithms for modification problems toward proper Helly circular-arc graphs.

ABSTRACT. We study the partial search order problem (PSOP) proposed recently by Scheffler [WG 2022]. Given a graph~$G$ together with a partial order on the set of vertices of~$G$, this problem determines if there is an~$\mathcal{S}$-ordering that is consistent with the given partial order, where~$\mathcal{S}$ is a graph search paradigm like BFS, DFS, etc. This problem naturally generalizes the end-vertex problem which has received much attention over the past few years. It also generalizes the so-called ${\mathcal{F}}$-tree recognition problem which has just been studied in the literature recently. Our main contribution is a polynomial-time dynamic programming algorithm for the PSOP on chordal graphs with respect to the maximum cardinality search (MCS). This resolves one of the most intriguing open questions left in the work of Sheffler [WG 2022]. To obtain our result, we propose the notion of layer structure and study numerous related structural properties which might be of independent interest.

ABSTRACT. Selection of a group of representatives satisfying certain fairness constraints, is a commonly occurring scenario. Motivated by this, we initiate a systematic algorithmic study of a fair version of Hitting Set. In the classical Hitting Set problem, the input is a universe $U$, a family $F$ of subsets of $U$, and a non-negative integer $k$. The goal is to determine whether there exists subset $S \subseteq U$ of size $k$ that hits (i.e., intersects) every set in $F$. Inspired by several recent works, we formulate a fair version of this problem, as follows. The input additionally contains a family $B$ of subsets of $U$, where each subset in $B$ can be thought of as the group of elements of the same type. We want to find a set $S \subseteq U$ of size $k$ that (i) hits all sets of $F$, and (ii) does not contain too many elements of each type. We call this problem Fair Hitting Set, and chart out its tractability boundary from both classical as well as multivariate perspective. Our results use a multitude of techniques from parameterized complexity including classical to advanced tools, such as, methods of representative sets for matroids, FO model checking, and a generalization of best known kernels for Hitting Set.

ABSTRACT. Orienting the edges of an undirected graph such that the resulting digraph satisfies some given constraints is a classical problem in graph theory, with multiple algorithmic applications. In particular, an $st$-orientation orients each edge of the input graph such that the resulting digraph is acyclic, and it contains a single source $s$ and a single sink $t$. Computing an $st$-orientation of a graph can be done efficiently, and it finds notable applications in graph algorithms and in particular in graph drawing. On the other hand, finding an $st$-orientation with at most $k$ transitive edges is more challenging and it was recently proven to be NP-hard already when $k=0$. We strengthen this result by showing that the problem remains NP-hard even for graphs of bounded diameter, and for graphs of bounded vertex degree. These computational lower bounds naturally raise the question about which structural parameters can lead to tractable parameterizations of the problem. Our main result is a fixed-parameter tractable algorithm parameterized by treewidth.

ABSTRACT. For a graph class G, we define the G-modular cardinality of a graph as the minimum size of a vertex partition of the graph into modules that each induces a graph in G. This generalizes other module-based graph parameters such as neighborhood diversity and iterated type partition. Moreover, if G has bounded modular-width, the W[1]-hardness of a problem in G-modular cardinality implies hardness on modular-width, clique-width, and other related parameters. On the other hand, fixed-parameter tractable (FPT) algorithms in G-modular cardinality may provide new ideas for algorithms using such parameters.

Several FPT algorithms based on modular partitions compute a solution table in each module, then combine each table into a global solution. This works well when each table has a succinct representation, but as we argue, when no such representation exists, the problem is typically W[1]-hard. We illustrate these ideas on the generic (alpha, beta)-domination problem, which asks for a set of vertices that contains at least a fraction alpha of the adjacent vertices of each unchosen vertex, plus some (possibly negative) amount beta. This generalizes known domination problems such as Bounded Degree Deletion, k-Domination, and alpha-Domination. We show that for graph classes G that require arbitrarily large solution tables, these problems are W[1]-hard in the G-modular cardinality, whereas they are fixed-parameter tractable when they admit succinct solution tables. This leads to several new positive and negative results for many domination problems parameterized by known and novel structural graph parameters such as clique-width, modular-width, and clusters-modular cardinality.

ABSTRACT. Feedback Vertex Set (FVS) is one of the most studied vertex deletion problems in the field of graph algorithms. In the decision version of the problem, given a graph G and an integer k, the question is whether there exists a set S of at most k vertices in G such that G-S is acyclic. It is one of the first few problems which were shown to be NP-complete, and has been extensively studied from the viewpoint of approximation and parameterized algorithms. The best-known polynomial time approximation algorithm for FVS} is a 2-factor approximation, while the best known deterministic and randomized FPT algorithms run in time O^*(3.460^k) and O^*(2.7^k) respectively (here $O^*()$ notations hides the polynomial factors in the running time of the algorithm).

In this paper, we contribute to the newly established area of parameterized approximation, by studying FVS in this paradigm. In particular, we combine the approaches of parameterized and approximation algorithms for the study of FVS, and achieve an approximation guarantee with a factor better than 2 in randomized FPT running time, that improves over the best known parameterized algorithm for FVS. We give three simple (1+\epsilon)-factor randomized approximation algorithms for FVS, running in times O^*(2^{\epsilon k} \cdot 2.7^{(1-\epsilon)k}), O^*(((\frac{4}{1+\epsilon})^{(1+\epsilon)} \cdot {(\frac{\epsilon}{3})^{\epsilon}})^{k}), and O^*(4^{(1-\epsilon)k}) respectively for every \epsilon \in (0,1). Combining these three algorithms, we obtain a (1+\epsilon)-factor approximation algorithm for FVS, which has better running time than the best-known (randomized) FPT algorithm for every \epsilon \in (0, 1). This is the first attempt to look at a parameterized approximation of FVS to the best of our knowledge. Our algorithms are very simple, and they rely on some well-known reduction rules used for arriving at FPT algorithms for FVS.

ABSTRACT. We introduce and develop a set-based semantics for asynchronous TeamLTL. We consider two canonical logics in this setting: the extensions of TeamLTL by the Boolean disjunction and by the Boolean negation. We establish fascinating connections between the original semantics based on multisets and the new set-based semantics as well as show one of the first positive complexity theoretic results in the temporal team semantics setting. In particular we show that both logics enjoy normal forms that can be utilised to obtain results related to expressivity and complexity (decidability) of the new logics. We also relate and apply our results to recently defined logics whose asynchronicity is formalized via time evaluation functions.

ABSTRACT. We show a quadratic separation between resolution and cut-free sequent calculus width. We use this gap to get, for the first time, first, a super-polynomial separation between resolution and cut-free sequent calculus for refuting CNF formulas, and secondly, a quadratic separation between resolution width and monomial space in polynomial calculus with resolution. Our super-polynomial separation between resolution and cut-free sequent calculus only applies when clauses are seen as disjunctions of unbounded arity; our examples have linear size cut-free sequent calculus proofs writing, in a particular way, their clauses using binary disjunctions. Interestingly, this shows that the complexity of sequent calculus depends on how disjunctions are represented.

ABSTRACT. Well-partial orders, and the ordinal invariants used to measure them, are relevant in set theory, program verification, proof theory and many other areas of computer science and mathematics. In this article we focus on one of the most common data structure in programming, the finite multisets of some well partial order. There are two natural orders one can define on the set M(X) of finite multisets of a partial order X: the multiset embedding and the multiset ordering, for which M(X) remains a wpo when X is. Though the maximal order type of these orders is already known, the other ordinal invariants remain mostly unknown. Our main contributions are expressions to compute compositionally the width of the multiset embedding and the height of the multiset ordering. Furthermore, we provide a new ordinal invariant useful for characterizing the width of the multiset ordering.

ABSTRACT. Bayes' rule tells us how to invert a causal process in order to update our beliefs in light of new evidence. If the process is believed to have a complex compositional structure, we may observe that the inversion of the whole can be computed piecewise in terms of the component processes. We study the structure of this compositional rule, noting that it relates to the lens pattern in functional programming.

Working in a suitably general axiomatic presentation of a category of Markov kernels, we see how we can think of Bayesian inversion as a particular instance of a state-dependent morphism in a fibred category. We discuss the compositional nature of this, formulated as a functor on the underlying category and explore how this can used for a more type-driven approach to statistical inference.