ABSTRACT. Kempe changes were introduced in 1879 in an attempt to prove the 4-colour theorem. They are a convenient if not crucial tool to prove various colouring theorems. Here, we consider how to navigate from a colouring to another through Kempe changes. When is it possible? How fast?

ABSTRACT. We introduce the 2-sorted counting logic GC^k that expresses properties of hypergraphs. This logic has available k variables to address hyperedges, an unbounded number of variables to address vertices, and atomic formulas E(e,v) to express that a vertex v is contained in a hyperedge e. We show that two hypergraphs H, H' satisfy the same sentences of the logic GC^k if, and only if, they are homomorphism indistinguishable over the class of hypergraphs of generalised hypertree width at most k. Here, H, H' are called homomorphism indistinguishable over a class C if for every hypergraph G in C the number of homomorphisms from G to H equals the number of homomorphisms from G to H'. This result can be viewed as a generalisation (from graphs to hypergraphs) of a result by Dvorak (2010) stating that any two (undirected, simple, finite) graphs H, H' are indistinguishable by the (k+1)-variable counting logic C^{k+1} if, and only if, they are homomorphism indistinguishable on the class of graphs of tree width at most k.

ABSTRACT. Since three decades \emph{binary decision diagrams}, a data structure representing efficiently Boolean functions, are widely used in many distinct contexts like model verification, machine learning, cryptography or also resolution of combinatorial problems. The most famous variant, called reduced ordered binary decision diagram (\textsc{robdd} for short), can be viewed as the result of a compaction procedure on the full decision tree. This structure has a useful property: once an order over the Boolean variables is fixed, each Boolean function is represented by exactly one \textsc{robdd}. In this paper we aim at computing the \emph{exact distribution of the Boolean functions in $k$~variables according to the \textsc{robdd} size}, where the \textsc{robdd} size is equal to the number of decision nodes of the underlying directed acyclic graph (\textsc{dag}) structure. Recall the number of Boolean functions with $k$ variables is equal to $2^{2^k}$, which is of double exponential growth with respect to the number of variables. The maximal size of a \textsc{robdd} with $k$ variables is $M_k \approx 2^k / k$ and thus, the support of the \textsc{robdd} size distribution is also of length $M_k$. Apart from the natural combinatorial explosion observed, another difficulty for computing the distribution according to size is to take into account dependencies within the \textsc{dag} structure of \textsc{robdd}s. In this paper, we develop the first polynomial algorithm (in $n$) to derive the distribution of the Boolean functions with respect to their \textsc{robdd} size denoted by $n$. The algorithm computes the (enumerative) generating function of \textsc{robdd}s with $k$ variables (for fixed $k$) up to size $n$. It performs $O(k\; n^4)$ arithmetical operations on integers and necessitates to store $O(n^2)$ integers, where integers involved have bit length $O(n)$. Our new approach relies on a decomposition of \textsc{robdd}s layer by layer and on an inclusion-exclusion argument.

ABSTRACT. The concept of Roman domination has recently been studied concerning enumerating and counting in F. N. Abu-Khzam et al. (WG 2022). More technically speaking, a function that assigns 0, 1, 2 to the vertices of an undirected graph is called a Roman dominating function if each vertex assigned zero has a neighbor assigned two. Such a function is called minimal if decreasing any assignment to any vertex would yield a function that is no longer a Roman dominating function. It has been shown that minimal Roman dominating functions can be enumerated with polynomial delay, i.e., between any two outputs of a solution, no more than polynomial time will elapse. This contrasts what is known about minimal dominating sets, where the question whether or not these can be enumerated with polynomial delay is open for more than 40 years. This makes the concept of Roman domination rather special and interesting among the many variants of domination problems studied in the literature, as it has been shown for several of these variants that the question of enumerating minimal solutions is tightly linked to that of enumerating minimal dominating sets, see M. Kanté et al. in SIAM J. Disc. Math., 2014. The running time of the mentioned enumeration algorithm for minimal Roman dominating functions (Abu-Khzam et al., WG 2022) could be estimated as O(1.9332^n) on general graphs of order n. Here, we focus on special graph classes, as has been also done for enumerating minimal dominating sets before. More specifically, for chordal graphs, we present an enumeration algorithm running in time O(1.8940^n). It is unknown if this gives a tight bound on the maximum number of minimal Roman dominating functions in chordal graphs. For interval graphs, we can lower this time bound further to O(1.7321^n), which also matches the known lower bound concerning the maximum number of minimal Roman dominating functions. We can also provide a matching lower and upper bound for forests, which is (incidentally) the same, namely O*(3^{n/2}). Furthermore, we present an optimal enumeration algorithm running in time O*(3^{n/3}) for split graphs and for cobipartite graphs, i.e., we can also give a matching lower bound example for these graph classes. Hence, our enumeration algorithms for interval graphs, forests, split graphs and cobipartite graphs are all optimal. The importance of our results stems from the fact that, for other types of domination problems, optimal enumeration algorithms are not always found. Interestingly, we use a different form of analysis for the running times of our different algorithms, and the branchings had to be tailored and tweaked to obtain the intended optimality results. Our Roman dominating functions enumeration algorithm for trees and forests is distinctively different from the one for minimal dominating sets by Rote (SODA 2019). Our Roman dominating functions enumeration algorithm for cobipartite graphs incidentally also improves on the best known enumeration algorithms for minimal dominating sets, as discussed in Couturier et al. (Theoret. Comp. Sci. 2013). Our approach also allows to give concrete formulas for counting minimal Roman dominating functions on more concrete graph families like paths.

ABSTRACT. We present quantitative logics with two-step semantics based on the framework of quantitative logics introduced by Arenas et al. (2020) and the two-step semantics defined in the context of weighted logics by Gastin & Monmege (2018). We show that some of the fragments of our logics augmented with a least fixed point operator capture interesting classes of counting problems. Specifically, we answer an open question in the area of descriptive complexity of counting problems by providing logical characterizations of two subclasses of #P, namely SpanL and TotP, that play a significant role in the study of approximable counting problems. Moreover, we define logics that capture FPSPACE and SPANPSPACE, which are counting versions of PSPACE.

ABSTRACT. In this work, we study two natural generalizations of clique-width introduced by Martin Fürer. Multi-clique-width allows every vertex to hold multiple labels~[ITCS 2017], while for fusion-width we have a possibility to merge all vertices of a certain label~[LATIN 2014]. Fürer has shown that both parameters are upper-bounded by treewidth thus making them more appealing from an algorithmic perspective than clique-width and asked for applications of these parameters for problem solving. First, we determine the relation between these two parameters by showing that $\mcw \leq \fw + 1$. Then we show that when parameterized by multi-clique-width, many problems (e.g., \textsc{Connected Dominating Set}) admit algorithms with the same running time as for clique-width despite the exponential gap between these two parameters. For some problems (e.g., \textsc{Hamiltonian Cycle}) we show an analogous result for fusion-width: For this we present an alternative view on fusion-width by introducing so-called glue-expressions which might be interesting on their own. All algorithms obtained in this work are tight up to (Strong) Exponential Time Hypothesis.

ABSTRACT. Given a graph $G$ and an integer $k$, \textsc{Max Min FVS} asks whether there exists a minimal set of vertices of size at least $k$ whose deletion destroys all cycles. We present several results that improve upon the state of the art of the parameterized complexity of this problem with respect to both structural and natural parameters.

Using standard DP techniques, we first present an algorithm of time $\textrm{tw}^{O(\textrm{tw})}n^{O(1)}$, significantly generalizing a recent algorithm of Gaikwad et al. of time $\textrm{vc}^{O(\textrm{vc})}n^{O(1)}$, where $\textrm{tw}, \textrm{vc}$ denote the input graph's treewidth and vertex cover respectively. Subsequently, we show that both of these algorithms are essentially optimal, since a $\textrm{vc}^{o(\textrm{vc})}n^{O(1)}$ algorithm would refute the ETH.

With respect to the natural parameter $k$, the aforementioned recent work by Gaikwad et al. claimed an FPT branching algorithm with complexity $10^k n^{O(1)}$. We point out that this algorithm is incorrect and present a branching algorithm of complexity $9.34^k n^{O(1)}$.

ABSTRACT. A set $S$ of isometric paths of a graph $G$ is ``$v$-rooted'', where $v$ is a vertex of $G$, if $v$ is one of the end-vertices of all the isometric paths in $S$. The \emph{isometric path complexity} of a graph $G$, denoted by $\ipco{G}$, is the minimum integer $k$ such that there exists a vertex $v\in V(G)$ satisfying the following property: the vertices of any isometric path $P$ of $G$ can be covered by $k$ many $v$-rooted isometric paths.

First, we provide an $O(n^2 m)$-time algorithm to compute the isometric path complexity of a graph with $n$ vertices and $m$ edges. Then we show that the isometric path complexity remains bounded for graphs in three seemingly unrelated graph classes, namely, \emph{hyperbolic graphs}, \emph{(theta, prism, pyramid)-free graphs}, and \emph{outerstring graphs}. Hyperbolic graphs are extensively studied in \emph{Metric Graph Theory}. The class of (theta, prism, pyramid)-free graphs are extensively studied in \emph{Structural Graph Theory}, \textit{e.g.} in the context of the \emph{Strong Perfect Graph Theorem}. The class of outerstring graphs is studied in \emph{Geometric Graph Theory} and \emph{Computational Geometry}. Our results also show that the distance functions of these (structurally) different graph classes are more similar than previously thought.

We show that there is a direct algorithmic consequence of having small isometric path complexity. Specifically, we show that if the isometric path complexity of a graph $G$ is bounded by a constant, then there exists a polynomial-time constant-factor approximation algorithm for \IPC whose objective is to cover all vertices of a graph with a minimum number of isometric paths. This applies to all the above graph classes.

ABSTRACT. The paper proposes dynamic parallel algorithms for connectivity and bipartiteness of undirected graphs that require constant-time and n^{1/2} times polylog(n) work on the (arbitrary) CRCW PRAM model. The work of these algorithms almost matches the work of the O(log n) time algorithm for Connectivity by Kopelowitz et al. (2018) on the EREW PRAM model and the time of the sequential algorithm for bipartiteness by Eppstein et al. (1997). In particular, we show that the sparsification technique, which has been used in both mentioned papers, can in principle also be used for constant time algorithms in the CRCW PRAM model, despite the logarithmic depth of sparsification trees.

ABSTRACT. We study the separability problem for automatic relations (i.e., relations on finite words definable by synchronous automata) in terms of recognizable relations (i.e., finite unions of products of regular languages). This problem takes as input two automatic relations R and R', and asks if there exists a recognizable relation S that contains R and does not intersect R'. We show this problem to be undecidable when the number of products allowed in the recognizable relation is fixed. In particular, checking if there exists a recognizable relation S with at most k products of regular languages that separates R from R' is undecidable, for each fixed k≥2.

ABSTRACT. Positive data languages are languages over an infinite alphabet closed under possibly non-injective renamings of data values. Informally, they model properties of data words expressible by assertions about equality, but not inequality, of data values occurring in the word. We investigate the class of positive data languages recognizable by nondeterministic orbit-finite nominal automata, an abstract form of register automata introduced by Bojanczyk, Klin, and Lasota. As our main contribution we provide a number of equivalent characterizations of that class in terms of positive register automata, monadic second-order logic with positive equality tests, and finitely presentable nondeterministic automata in the categories of nominal renaming sets and of presheaves over finite sets.

ABSTRACT. A rewb is a regular expression extended with a feature called backreference. It is broadly known that backreference is a practical extension of regular expressions, and is supported by most modern regular expression engines, such as those in the standard libraries of Java, Python, and more. Meanwhile, indexed languages are the languages generated by indexed grammars, a formal grammar class proposed by A.V.Aho. We show that these two models' expressive powers are related in the following way: every language described by a rewb is an indexed language. As the smallest formal grammar class previously known to contain rewbs is the class of context sensitive languages, our result strictly improves the known upper-bound. Moreover, we prove the following two claims: there exists a rewb whose language does not belong to the class of stack languages, which is a proper subclass of indexed languages, and the language described by a rewb without a captured reference is in the class of nonerasing stack languages, which is a proper subclass of stack languages. Finally, we show that the hierarchy investigated in a prior study, which separates the expressive power of rewbs by the notion of nested levels, is within the class of nonerasing stack languages.

ABSTRACT. Planar Embedding is a drawing of a graph on the plane such that the edges do not intersect each other, except at the vertices. We know that testing the planarity of a graph and computing its embedding (if it exists) can efficiently be computed, both sequentially [HT74] and in parallel [RR94], when the entire graph is presented as input.

In the dynamic setting, the input graph changes one edge at a time through insertion and deletions and planarity testing/embedding has to be updated after every change. By storing auxiliary information we can improve the complexity of dynamic planarity testing/embedding over the obvious recomputation from scratch. In the sequential dynamic setting, there has been a series of works [EGIS96, IPR93, HIKLR18, HR20], culminating in the breakthrough result of polylog(n) sequential time planarity testing algorithm of Holm and Rotenberg [HR20].

In this paper, we study planar embedding through the lens of DynFO, a parallel dynamic complexity class introduced by Patnaik and Immerman [PI97] (also [DST95]). We show that it is possible to dynamically maintain whether an edge can be inserted into a planar graph without causing non-planarity in DynFO. We extend this to show how to maintain an embedding of a planar graph under both edge insertions and deletions while rejecting edge insertions that violate planarity.

Our main idea is to maintain embeddings of only the triconnected components and a special two-colouring of separating pairs that enables us to side-step cascading flips when embedding of a biconnected planar graph changes, a major issue for sequential dynamic algorithms [HR20].

ABSTRACT. For any finite set $\mathcal{H} = \{H_1,\ldots,H_p\}$ of graphs, a graph is $\mathcal{H}$-subgraph-free if it does not contain any of $H_1,\ldots,H_p$ as a subgraph. In recent work, meta-classifications have been studied: these show that if graph problems satisfy certain prescribed conditions, their complexity is determined on classes of $\mathcal{H}$-subgraph-free graphs. We continue this work and focus on problems that have polynomial-time solutions on classes that have bounded treewidth or maximum degree at most~$3$ and examine their complexity on $H$-subgraph-free graph classes where $H$ is a connected graph. With this approach, we obtain comprehensive classifications for {\sc (Independent) Feedback Vertex Set}, {\sc Connected Vertex Cover}, {\sc Colouring} and {\sc Matching Cut}. This resolves a number of open problems.

We highlight that, to establish that {\sc Independent Feedback Vertex Set} belongs to this collection of problems, we first show that it can be solved in polynomial time on graphs of maximum degree $3$. We demonstrate that, with the exception of the complete graph on four vertices, each graph in this class has a minimum size feedback vertex set that is also an independent set.

ABSTRACT. Two graphs G and H are homomorphism indistinguishable over a class of graphs F if for all graphs F ∊ F the number of homomorphisms from F to G is equal to the number of homomorphisms from F to H. Many natural equivalence relations comparing graphs such as (quantum) isomorphism, spectral, and logical equivalences can be characterised as homomorphism indistinguishability relations over certain graph classes.

Abstracting from the wealth of such instances, we show in this paper that equivalences w.r.t. any self-complementarity logic admitting a characterisation as homomorphism indistinguishability relation can be characterised by homomorphism indistinguishability over a minor-closed graph class. Self-complementarity is a mild property satisfied by most well-studied logics. This result follows from a correspondence between closure properties of a graph class and preservation properties of its homomorphism indistinguishability relation.

Furthermore, we classify all graph classes which are in a sense finite (essentially profinite) and satisfy the maximality condition of being homomorphism distinguishing closed, i.e. adding any graph to the class strictly refines its homomorphism indistinguishability relation. Thereby, we answer various questions raised by Roberson (2022) on general properties of the homomorphism distinguishing closure.

ABSTRACT. We consider the problem of estimating the support size of a distribution $D$. Our investigations are pursued through the lens of distribution testing and seek to understand the power of conditional sampling (denoted as COND), wherein one is allowed to query the given distribution conditioned on an arbitrary subset $S$. The primary contribution of this work is to introduce a new approach to lower bounds for the COND model that relies on using powerful tools from information theory and communication complexity.

Our approach allows us to obtain surprisingly strong lower bounds for the COND model and its extensions.

\begin{itemize}

\item We bridge the longstanding gap between the upper bound $O\left(\log \log n + \frac{1}{\epsilon^2}\right)$ and the lower bound $\Omega\left(\sqrt{\log \log n}\right)$ for the {\CO} model by providing a nearly matching lower bound. Surprisingly, we show that even if we get to know the actual probabilities along with {\CO} samples, still $\Omega\left(\log \log n + \frac{1}{\epsilon^2 \log (1/\epsilon)}\right)$ queries are necessary.

\item We obtain the first non-trivial lower bound for the COND equipped with an additional oracle that reveals the actual as well as the conditional probabilities of the samples (to the best of our knowledge, this subsumes all of the models previously studied): in particular, we demonstrate that $\Omega\left(\log \log \log n + \frac{1}{\epsilon^2 \log (1/\epsilon)}\right)$ queries are necessary.

ABSTRACT. Let $M$ be a $n\times m$ $(0,1)$-matrix. We define the $s$-binary rank, $\br_s(M)$, of $M$ to be the minimal integer $d$ such that there are $d$ monochromatic rectangles that cover all the $1$-entries in the matrix, and each $1$-entry is covered by at most $s$ rectangles. When $s=1$, this is the binary rank,~$\br(M)$, known from the literature.

Let $R(M)$ and $C(M)$ be the set of rows and columns of~$M$, respectively. We use the result of Sgall~\cite{Sgall99} to prove that if $M$ has $s$-binary rank at most~$d$, then $|R(M)|\cdot |C(M)|\le {d\choose \le s}2^{d}$ where ${d\choose \le s}=\sum_{i=0}^s{d\choose i}$. This bound is tight; that is, there exists a matrix $M'$ of $s$-binary rank $d$ such that $|R(M')|\cdot |C(M')|= {d\choose \le s}2^{d}$.

Using this result, we give a new one-sided adaptive and non-adaptive testers for $(0,1)$-matrices of $s$-binary rank at most $d$ (and exactly $d$) that makes $\tilde O\left({d\choose \le s}2^d/\epsilon\right)$ and $\tilde O\left({d\choose \le s}2^d/\epsilon^2\right)$ queries, respectively.

For a fixed $s$, this improves the query complexity of the tester of Parnas et al. in ~\cite{ParnasRS21} by a factor of $\tilde \Theta (2^d)$.

ABSTRACT. Specialized hereditary systems, e.g., matroids, are known to have many applications in algorithm design. We define a new notion called d-polynomoid as a hereditary system (E , F \subseteq 2^E) so that every two maximal sets in F have less than d elements in common. We study the problem that, given a d-polynomoid (E,F), asks if the ground set E contains \ell disjoint k-subsets that are not in F, and obtain a complexity trichotomy result for all pairs of $k \ge 1$ and $d \ge 0$. Our algorithmic result yields a sufficient and necessary condition that decides whether each hypergraph in some classes of r-uniform hypergraphs has a perfect matching, which has a number of algorithmic applications.

ABSTRACT. We introduce the \emph{$k$-variable-occurrence fragment}, which is the set of terms having at most $k$ occurrences of variables. We give a sufficient condition for the decidability of the equational theory of the $k$-variable-occurrence fragment using the finiteness of a monoid. As a case study, we prove that for Tarski's calculus of relations with bounded dot-dagger alternation (an analogy of quantifier alternation in first-order logic), the equational theory of the $k$-variable-occurrence fragment is decidable for each $k$.

ABSTRACT. This paper introduces a generic framework that provides sufficient conditions for guaranteeing polynomial-time decidability of fixed-negation fragments of first-order theories that adhere to certain fixed-parameter tractability requirements. It enables deciding sentences of such theories with arbitrary existential quantification, conjunction and a fixed number of negation symbols in polynomial time. It was recently shown by Nguyen and Pak [SIAM J. Comput. 51(2): 1–31 (2022)] that an even more restricted such fragment of Presburger arithmetic (the first-order theory of the integers with addition and order) is NP-hard. In contrast, by application of our framework, we show that the fixed negation fragment of weak Presburger arithmetic, which drops the order relation from Presburger arithmetic, is decidable in polynomial time.

ABSTRACT. A first-order formula is called primitive positive (pp) if it only admits the use of existential quantifiers and conjunction. Pp-formulas are a central concept in (fixed-template) constraint satisfaction since CSP(Gamma) can be viewed as the problem of deciding the primitive positive theory of Gamma, and pp-definability captures gadget reductions between CSPs.

An important class of tractable constraint languages Gamma is characterized by having few subpowers, that is, the number of n-ary relations pp-definable from Gamma is bounded by 2^p(n) for some polynomial p(n). In this paper we study a restriction of this property, stating that every pp-definable relation is already definable by a pp-formula of polynomial length. We conjecture that the existence of such short definitions is actually equivalent to Gamma having few subpowers, and verify this conjecture for a large subclass that, in particular, includes all constraint languages on three-element domains. We furthermore discuss how our conjecture imposes an upper complexity bound of co-NP on the subpower membership problem of algebras with few subpowers.