ABSTRACT. The well-known Cluster Vertex Deletion problem (Cluster-VD) asks for a given graph $G$ and an integer k whether it is possible to delete at most k vertices of G such that the resulting graph is a cluster graph (a disjoint union of cliques).

We give a complete characterization of graphs H for which Cluster-VD on H-free graphs is polynomially solvable and for which it is NP-complete.

We also obtain partial results towards a complexity dichotomy for two forbidden induced subgraphs.

ABSTRACT. In the \emph{Exact Matching Problem} (EM), we are given a graph equipped with a fixed coloring of its edges with two colors (red and blue), as well as a positive integer $k$. The task is then to decide whether the given graph contains a perfect matching exactly $k$ of whose edges have color red. EM generalizes several important algorithmic problems such as \emph{perfect matching} and restricted minimum weight spanning tree problems.

When introducing the problem in 1982, Papadimitriou and Yannakakis conjectured EM to be \textbf{NP}-complete. Later however, Mulmuley et al.~presented a randomized polynomial time algorithm for EM, which puts EM in \textbf{RP}. Given that to decide whether or not \textbf{RP}$=$\textbf{P} represents a big open challenge in complexity theory, this makes it unlikely for EM to be \textbf{NP}-complete, and in fact indicates the possibility of a \emph{deterministic} polynomial time algorithm. EM remains one of the few natural combinatorial problems in \textbf{RP} which are not known to be contained in \textbf{P}, making it an interesting instance for testing the hypothesis \textbf{RP}$=$\textbf{P}.

Despite EM being quite well-known, attempts to devise deterministic polynomial algorithms have remained illusive during the last 40 years and progress has been lacking even for very restrictive classes of input graphs. In this paper we finally push the frontier of positive results forward by proving that EM can be solved in deterministic polynomial time for input graphs of bounded independence number, and for bipartite input graphs of bounded bipartite independence number. This generalizes previous positive results for complete (bipartite) graphs which were the only known results for EM on dense graphs.

ABSTRACT. For a graph $G$, a subset $S \subseteq V(G)$ is called a \emph{resolving set} if for any two vertices $u,v \in V(G)$, there exists a vertex $w \in S$ such that $d(w,u) \neq d(w,v)$. The {\sc Metric Dimension} problem takes as input a graph $G$ and a positive integer $k$, and asks whether there exists a resolving set of size at most $k$. This problem was introduced in the 1970s and is known to be \NP-hard~[GT~61 in Garey and Johnson's book]. In the realm of parameterized complexity, Hartung and Nichterlein~[CCC~2013] proved that the problem is \W[2]-hard when parameterized by the natural parameter $k$. They also observed that it is \FPT\ when parameterized by the vertex cover number and asked about its complexity under \emph{smaller} parameters, in particular the feedback vertex set number. We answer this question by proving that {\sc Metric Dimension} is \W[1]-hard when parameterized by the feedback vertex set number. This also improves the result of Bonnet and Purohit~[IPEC 2019] which states that the problem is \W[1]-hard parameterized by the treewidth. Regarding the parameterization by the vertex cover number, we prove that {\sc Metric Dimension} does not admit a polynomial kernel under this parameterization unless $\NP\subseteq \coNP/poly$. We observe that a similar result holds when the parameter is the distance to clique. On the positive side, we show that {\sc Metric Dimension} is \FPT\ when parameterized by either the distance to cluster or the distance to co-cluster, both of which are smaller parameters than the vertex cover number.

ABSTRACT. We introduce regular languages of morphisms in free strict monoidal categories, with their associated grammars and automata. These subsume the classical theory of regular languages of words and trees, but also open up a much wider class of languages of string diagrams. We use the algebra of monoidal categories to investigate the properties of regular monoidal languages, define a class of determinizable monoidal automata, and provide a sufficient condition for recognizability by deterministic monoidal automata.

ABSTRACT. Regular nested word languages (a.k.a. visibly pushdown languages) strictly extend regular word languages, while preserving their main closure and decidability properties. Previous works have shown that considering languages of 2-nested words, i.e. words enriched with two matchings (a.k.a. $2$-visibly pushdown languages), is not as successful: the corresponding model of automata is not closed under determinization. In this work, inspired by homomorphic representations of indexed languages, we identify a subclass of $2$-nested words, which we call $2$-wave words. This class strictly extends the class of nested words, while preserving its main properties. More precisely, we prove closure under determinization of the corresponding automaton model, we provide a logical characterization of the recognized languages, and show that the corresponding graphs have bounded treewidth. As a consequence, we derive important closure and decidability properties. Last, we show that the word projections of the languages we define belong to the class of linear indexed languages.

ABSTRACT. Generalizing the notion of the boundary sequence introduced by Chen and Wen, the $n$th term of the $\ell$-boundary sequence of an infinite word is the finite set of pairs $(u,v)$ of prefixes and suffixes of length $\ell$ appearing in factors $uyv$ of length $n+\ell$ ($n\ge \ell\ge 1$). Otherwise stated, for increasing values of $n$, one looks for all pairs of factors of length $\ell$ separated by $n-\ell$ symbols.

For the large class of addable numeration systems $U$, we show that if an infinite word is $U$-automatic, then the same holds for its $\ell$-boundary sequence. In particular, they are both morphic (or generated by an HD0L system). We also provide examples of numeration systems and $U$-automatic words with a boundary sequence that is not $U$-automatic. In the second part of the paper, we study the $\ell$-boundary sequence of a Sturmian word. We show that it is obtained through a sliding block code from the characteristic Sturmian word of the same slope. We also show that it is the image under a morphism of some other characteristic Sturmian word.

ABSTRACT. Quantifying the similarity between two graphs is a fundamental algorithmic problem at the heart of many data analysis tasks for graph-based data. In this paper, we study the computational complexity of a family of similarity measures based on quantifying the mismatch between the two graphs, that is, the “symmetric difference” of the graphs under an optimal alignment of the vertices. An important example is similarity based on graph edit distance. While edit distance calculates the “global” mismatch, that is, the number of edges in the symmetric difference, our main focus is on “local” measures calculating the maximum mismatch per vertex. Mathematically, our similarity measures are best expressed in terms of the adjacency matrices: the mismatch between graphs is expressed as the difference of their adjacency matrices (under an optimal alignment), and we measure it by applying some matrix norm. Roughly speaking, global measures like graph edit distance correspond to entrywise matrix norms like the Frobenius norm and local measures correspond to operator norms like the spectral norm. We prove a number of strong NP-hardness and inapproximability results even for every restricted graph classes such as bounded-degree trees.

ABSTRACT. Given a graph, the general problem to cover the maximum number of vertices by a collection of vertex-disjoint long paths seemingly escapes from the literature. A path containing at least $k$ vertices is considered long. When $k \le 3$, the problem is polynomial time solvable; when $k$ is the total number of vertices, the problem reduces to the Hamiltonian path problem, which is NP-complete. For a fixed $k \ge 4$, the problem is NP-hard and the best known approximation algorithm for the weighted set packing problem implies a $k$-approximation algorithm. To the best of our knowledge, there is no approximation algorithm directly designed for the general problem, except a recent $4$-approximation algorithm when $k = 4$. We propose the first $(0.4394 k + O(1))$-approximation algorithm for the general problem and an improved $2$-approximation algorithm when $k = 4$. Both algorithms are based on local improvement, and their performance analyses are done via amortization.

ABSTRACT. The CONTRACTION(vc) problem takes as input a graph $G$ on $n$ vertices and two integers $k$ and $d$, and asks whether one can contract at most $k$ edges to reduce the size of a minimum vertex cover of $G$ by at least $d$. Recently, Lima et al. [MFCS 2020] proved, among other results, that unlike most of the so-called blocker problems, CONTRACTION(vc) admits an XP algorithm running in time $f(d) \cdot n^{O(d)}$. They left open the question of whether this problem is FPT under this parameterization. In this article, we continue this line of research and prove the following results:

1. CONTRACTION(vc) is W[1]-hard parameterized by $k+d$. Moreover, unless the ETH fails, the problem does not admit an algorithm running in time $f(k+d) \cdot n^{o(k+d)}$ for any function $f$. In particular, this answers the open question stated in Lima et al. [MFCS 2020] in the negative.

2. It is NP-hard to decide whether an instance $(G,k,d)$ of CONTRACTION(vc) is a yes-instance even when $k=d$, hence enhancing our understanding of the classical complexity of the problem.

3. CONTRACTION(vc) can be solved in time $2^{O(d)} \cdot n^{k−d+O(1)}$. This XP algorithm improves the one of Lima et al. [MFCS 2020], which uses Courcelle's theorem as a subroutine and hence, the $f(d)$-factor in the running time is non-explicit and probably very large. On the other hard, it shows that when $k=d$, the problem is FPT parameterized by $d$ (or by $k$).

ABSTRACT. A Conflict-Free Open Neighborhood coloring, abbreviated CFON^* coloring, of a graph G=(V,E) using k colors is an assignment of colors from a set of k colors to a subset of vertices of V(G) such that every vertex sees some color exactly once in its open neighborhood. The minimum k for which G has a CFON^* coloring using k colors is called the CFON^ chromatic number of G, denoted by \chi^*_{ON}(G). The analogous notion for closed neighborhood is called CFCN^* coloring and the analogous parameter is denoted by \chi^*_{CN}(G). The problem of deciding whether a given graph admits a CFON^* (or CFCN^*) coloring that uses k colors is NP-complete. Below, we describe briefly the main results of this paper.

* For k\geq 3, we show that if G is a K_{1,k}-free graph then \chi^*_{ON}(G) = O(k^2\log \Delta)$, where \Delta denotes the maximum degree of G. Debski and Przybylo in [J. Graph Theory, 2021] had shown that if G is a line graph, then \chi^*_{ON}(G) = O(\log \Delta). As an open question, they had asked if their result could be extended to claw-free (K_{1,3}-free) graphs, which are a superclass of line graphs. Since it is known that the CFCN^* chromatic number of a graph is at most twice its CFON^* chromatic number, our result positively answers the open question posed by Debski and Przybylo.

* We show that if the minimum degree of any vertex in G is \Omega(\frac{\Delta}{\log^{\epsilon} \Delta}) for some \epsilon \geq 0, then \chi^*_{ON}(G) = O(\log^{1+\epsilon}\Delta). This is a generalization of the result given by Debski and Przybylo in the same paper where they showed that if the minimum degree of any vertex in G is \Omega(\Delta), then \chi^*_{ON}(G) = O(\log\Delta).

* We give a polynomial time algorithm to compute \chi_{ON}^*(G) for interval graphs G. This answers in positive the open question posed by Reddy [Theoretical Comp. Science, 2018] to determine whether the CFON$^*$ chromatic number can be computed in polynomial time on interval graphs.

* We explore subclasses of bipartite graphs that include bipartite permutation, biconvex bipartite graphs and give polynomial time algorithms to compute their CFON^* chromatic number. This is interesting as Abel et al. [SIDMA, 2018] had shown that it is NP-complete to decide whether a planar bipartite graph G has \chi_{ON}^*(G) = k where k \in {1, 2, 3}.

ABSTRACT. A rotor walk in a directed graph can be thought of as a deterministic version of a Markov Chain, where a pebble moves from vertex to vertex following a simple rule until a terminal vertex, or sink, has been reached. The ARRIVAL problem, as defined by Dohrau and al. [7], consists in determining which sink will be reached. While the walk itself can take an exponential number of steps, this problem belongs to the complexity class NP ∩ co-NP without being known to be in P. In this work, we define a class of directed graphs, namely tree-like multigraphs, which are multigraphs having the global shape of an undirected tree. We prove that in this class, ARRIVAL can be solved in almost linear time, while the number of steps of a rotor walk can still be exponential. Then, we give an application of this result to solve some deterministic analogs of stochastic models (e.g., Markovian decision processes, Stochastic Games).

ABSTRACT. The celebrated Skolem-Mahler-Lech theorem states that the set of zeros of a linear recurrence sequence is the union of a finite set and finitely many arithmetic progressions. The corresponding computational question, the Skolem Problem, asks to decide whether a given linear recurrence sequence has a zero term. Although the Skolem-Mahler-Lech theorem is almost 90 years old, decidability of the Skolem Problem remains open. The main contribution of this paper is an algorithm to solve the Skolem Problem for simple linear recurrence sequences (those with simple characteristic roots). Whenever the algorithm terminates, it produces a certificate that its output is correct---either a zero of the sequence or a witness that no zero exists. We give a proof that the algorithm terminates assuming two classical number-theoretic conjectures: the Skolem Conjecture (also known as the exponential local-global principle) and the p-adic Schanuel conjecture.

ABSTRACT. When computing stable matchings, it is usually assumed that the preferences of the agents in the matching market are fixed. However, in many realistic scenarios, preferences change over time. Consequently, an initially stable matching may become unstable. Then, a natural goal is to find a matching which is stable with respect to the modified preferences and as close as possible to the initial one. For Stable Marriage/Roommates, this problem was formally defined as Incremental Stable Marriage/Roommates by Bredereck et al. [AAAI '20]. As they showed that Incremental Stable Roommates and Incremental Stable Marriage with Ties are NP-hard, we focus on the parameterized complexity of these problems. We answer two open questions of Bredereck et al. [AAAI '20]: We show that Incremental Stable Roommates is W[1]-hard parameterized by the number of changes in the preferences, yet admits an intricate XP-algorithm, and we show that Incremental Stable Marriage with Ties is W[1]-hard parameterized by the number of ties. Furthermore, we analyze the influence of the degree of ``similarity'' between the agents' preference lists, identifying several polynomial-time solvable and fixed-parameter tractable cases, but also proving that Incremental Stable Roommates and Incremental Stable Marriage with Ties parameterized by the number of different preference lists are W[1]-hard.

ABSTRACT. Given an integer linear recurrence sequence ⟨X_0, X_1, X_2,...⟩, the Skolem Problem asks to determine whether there is a natural number n such that X_n = 0. The decidability of the Skolem Problem is a long-standing open problem in verification. In a recent preprint, Lipton, Luca, Nieuwveld, Ouaknine, Purser, and Worrell prove that the Skolem Problem is decidable for a class of reversible sequences of order at most seven. Herein, we give an alternative proof of the result. The novelty of our approach arises from our employment of theorems concerning the polynomial relations between Galois conjugates. In particular, we make repeated use of a result due to Dubickas and Smyth for algebraic integers that lie alongside all their Galois conjugates on two (but not one) concentric circles centred at the origin.

ABSTRACT. In an upward-planar L-drawing of a directed acyclic graph (DAG) each edge e is represented as a polyline composed of a vertical segment with its lowest endpoint at the tail of $e$ and of a horizontal segment ending at the head of e. Distinct edges may overlap, but not cross. Recently, upward-planar L-drawings have been studied for st-graphs, i.e., planar DAGs with a single source s and a single sink t containing an edge directed from s to t. It is known that a plane st-graph, i.e., an embedded st-graph in which the edge (s,t) is incident to the outer face, admits an upward-planar L-drawing if and only if it admits a bitonic st-ordering, which can be tested in linear time.

We study upward-planar L-drawings of DAGs that are not necessarily st-graphs. On the combinatorial side, we show that a plane DAG admits an upward-planar L-drawing if and only if it is a subgraph of a plane st-graph admitting a bitonic st-ordering. This allows us to show that not every tree with a fixed bimodal embedding admits an upward-planar L-drawing. Moreover, we prove that any acyclic cactus with a single source (or a single sink) admits an upward-planar L-drawing, which respects a given outerplanar~embedding if there are no transitive edges. On the algorithmic side, we consider DAGs with a single source (or a single sink). We give linear-time testing algorithms for these DAGs in two cases: (i) when the drawing must respect a prescribed embedding and (ii) when no restriction is given on the embedding, but each biconnected component is series-parallel.

ABSTRACT. The \emph{partial representation extension problem} generalizes the recognition problem for geometric intersection graphs. The input consists of a graph $G$, a subgraph $H \subseteq G$ and a representation~$\mathcal H$ of $H$. The question is whether $G$ admits a representation $\mathcal G$ whose restriction to $H$ is $\mathcal H$. We study this question for \emph{circle graphs}, which are intersection graphs of chords of a circle. Their representations are called \emph{chord diagrams}.

We show that for a graph with $n$ vertices and $m$ edges the partial representation extension problem can be solved in $O((n + m) \alpha(n + m))$ time, where $\alpha$ is the inverse Ackermann function. This improves over an $O(n^3)$-time algorithm by Chaplick, Fulek and Klav\'ik~[2019]. The main technical contributions are a canonical way of orienting chord diagrams and a novel compact representation of the set of all canonically oriented chord diagrams that represent a given circle graph $G$, which is of independent interest.

ABSTRACT. Motivated by cognitive experiments providing evidence that large crossing-angles have a limited impact on the readability of a graph drawing, RAC (Right Angle Crossing) drawings were introduced to address the problem of producing readable representations of non-planar graphs by supporting the optimal case in which all crossings form 90° angles.

In this work, we make progress on the problem of finding RAC drawings of graphs of low degree. In this context, a long-standing open question asks whether all degree-3 graphs admit straight-line RAC drawings. This question has been positively answered for the Hamiltonian degree-3 graphs. We improve on this result by extending to the class of 3-edge-colorable degree-3 graphs. When each edge is allowed to have one bend, we prove that degree-4 graphs admit such RAC drawings, a result which was previously known only for degree-3 graphs. Finally, we show that 7-edge-colorable degree-7 graphs admit RAC drawings with two bends per edge. This improves over the previous result on degree-6 graphs.

ABSTRACT. A word-to-word function is rational if it can be realized by a non-deterministic one-way transducer. Over finite words, it is a classical result that any rational function is regular, i.e. it can be computed by a deterministic two-way transducer, or equivalently, by a deterministic streaming string transducer (a one-way automaton which manipulates string registers).

This result no longer holds for infinite words, since a non-deterministic one-way transducer can guess, and check along its run, properties such as infinitely many occurrences of some pattern, which is impossible for a deterministic machine. In this paper, we identify the class of rational functions over infinite words which are also computable by a deterministic two-way transducer. It coincides with the class of rational functions which are continuous, and this property can thus be decided. This solves an open question raised in a previous paper of Dave et al.

ABSTRACT. We study constraint automata that recognize data languages on finite string values. Each transition of the automaton is labelled with a constraint restricting the string value at the current and the next position of the data word in terms of the prefix and the suffix order. We prove that the emptiness problem for such constraint automata with Büchi acceptance condition is NL-complete. We remark that since the constraints are formed by two partial orders, prefix and suffix, we cannot exploit existing techniques for similar formalisms. Our decision procedure relies on a decidable characterization for those infinite paths in the graph underlying the automaton that can be complemented with string values to yield a Büchi-accepting run. Our result is - to the best of our knowledge - the first work in this context that considers both prefix and suffix, and it is a first step into answering an open question posed by Demri and Deters.

ABSTRACT. We study the problem of active learning deterministic visibly pushdown automata. We show that in the classical L*-setting, efficient active learning algorithms are not possible. To overcome this difficulty, we propose the accessible stack setting, where the algorithm has the read and write access to the stack. In this setting, we show that active learning can be done in polynomial time in the size of the target automaton and the counterexamples provided by the teacher. As counterexamples of exponential size are sometimes inevitable, we consider an algorithm working with words in a compressed representation via (visibly) Straight-Line Programs. Employing compression allows us to obtain an algorithm where the teacher and the learner work in time polynomial in the size of the target automaton alone.