ABSTRACT. The Skolem Problem asks to decide whether a given integer linear recurrence sequence has a zero term. Decidability of this problem has been open for many decades, with little progress since the 1980s. Recently, a new approach was initiated via the notion of a Universal Skolem Set -- a set of positive integers relative to which the Skolem Problem is decidable. More precisely, S is a Universal Skolem Set if there is an effective procedure that, given any integer linear recurrence sequence, decides whether the sequence has a zero in S. A recent work exhibited an infinite such set, albeit very sparse (having density zero). In the present work we construct a Universal Skolem Set of strictly positive lower density.

ABSTRACT. Coalition formation considers the question of how to partition a set of agents into coalitions with respect to their preferences. Additively separable hedonic games (ASHGs) are a dominant model where cardinal single-agent values are aggregated into preferences by taking sums. Output partitions are typically measured by means of stability, and we follow this approach by considering stability based on single-agent movements (to join other coalitions), where a coalition is defined as stable if there exists no beneficial single-agent deviation. Permissible deviations should always lead to an improvement for the deviator, but they may also be constraint by demanding consent of agents involved in the deviations, i.e., by agents in the abandoned or welcoming coalition. Most of the existing research focusses on unanimous consent of one or both of these coalitions, but more recent research relaxes this to majority-based consent. Our contribution is twofold. First, we settle the computational complexity of the existence of contractually Nash stable partitions, where deviations are constraint by unanimous consent of the abandoned coalition. This resolves the complexity of the last classical stability notion for ASHGs. Second, we identify clear boundaries to the tractability of stable partitions under majority-based stability concepts by proving elaborate hardness results for restricted classes of ASHGs. Slight further restrictions lead to positive results.

ABSTRACT. The computational complexity of pairwise energy minimisation of N points in real space is a long-standing open problem. The idea of the potential intractability of the problem was supported by a lack of progress in finding efficient algorithms. In this paper we provide a firm answer to the problem by showing that for a large class of pairwise energy functions the problem of periodic energy minimisation is NP-hard if the size of the period (known as a unit cell) is fixed, and is undecidable otherwise. We do so by introducing a new abstraction of pairwise average energy minimisation as a mathematical problem, which covers many existing models. The most influential new aspects of this work are showing for the first time: 1) undecidability of average pairwise energy minimisation in general 2) computational hardness for the most natural model with periodic boundary conditions, and 3) new reductions for a class of pairwise energy functions covering many physical abstractions at once. In particular, we develop a new tool of overlapping digital rhombuses to incorporate the properties of the physical force fields, and we connect it with classical tiling problems. Moreover, we illustrate the power of such reductions by incorporating more physical properties such as charge neutrality, and we show an inapproximability result for the extreme case of the 1D average energy minimisation problem.

ABSTRACT. Finding exact circuit size is notoriously hard. Whereas modern computers and algorithmic techniques allow to find a circuit of size seven in the blink of an eye, it may take more than a week to search for a circuit of size thirteen. One of the reasons of this behavior is that the search space is enormous: the number of circuits of size s is s^{Θ(s)}, the number of Boolean functions on n variables is 2^{2^n}.

In this paper, we explore the following natural heuristic idea for decreasing the size of a given circuit: go through all its subcircuits of moderate size and check whether any of them can be improved by reducing to SAT. This may be viewed as a local search approach: we search for a smaller circuit in a ball around a given circuit. Through this approach, we prove new upper bounds on the circuit size of various symmetric functions. We also demonstrate that some upper bounds that were proved by hand decades ago, nowadays can be found automatically in a few seconds.

ABSTRACT. We refine the complexity landscape for enumeration problems by introducing very low classes defined by using Boolean circuits as enumerators. We locate well-known enumeration problems e. g. from graph theory, Gray code enumeration, and propositional satisfiability in our classes. In this way we obtain a framework to distinguish between the complexity of different problems known to be in DelayP, for which a formal way of comparison was not possible to this day.

ABSTRACT. We show that any product-depth \Delta algebraic circuit for the Iterated Matrix Multiplication Polynomial \IMM_{n,d} (when d=O(\log n)) must be of size at least n^{\Omega\left(d^{1/(\varphi^2)^{\Delta}}\right)} where \varphi = 1.618\ldots is the golden ratio. This improves the recent breakthrough result of Limaye, Srinivasan and Tavenas (FOCS'21) who showed a super polynomial lower bound of the form n^{\Omega\left(d^{1/4^{\Delta}}\right)} for constant-depth circuits.

One crucial idea of the (LST21) result was to use set-multilinear polynomials where each of the sets in the underlying partition of the variables could be of different sizes. By picking the set sizes more carefully (depending on the depth we are working with), we first show that any product-depth \Delta \emph{set-multilinear} circuit for \IMM_{n,d} (when d = O(\log n)) needs size at least n^{\Omega\left(d^{1/\varphi^{\Delta}}\right)}. This improves the n^{\Omega\left(d^{1/2^{\Delta}}\right)} lower bound of (LST21). We then use their Hardness Escalation technique to lift this to general circuits.

We also show that our lower bound cannot be improved significantly using these same techniques. For the \emph{specific} two set sizes used in (LST21), they showed that their lower bound cannot be improved. We show that for any d^{o(1)} set sizes (out of maximum possible d), the scope for improving our lower bound is minuscule: there exists a set-multilinear polynomial that has product-depth $\Delta$ set-multilinear circuits of size n^{O\left(d^{1/\varphi^{\Delta-1}}\right)} such that the value of the measure used to prove the lower bound is maximum for this polynomial. This results in a barrier to further improvement using the same measure.

ABSTRACT. For PLS-complete local search problems, there is presumably no polynomial-time algorithm which finds a locally optimal solution, even though determining whether a solution is locally optimal and replacing it by a better one if this is not the case can be done in polynomial time. We study local search for Independent Set and Dominating Set on weighted graphs with the $3$-swap neighborhood. The $3$-swap neighborhood of a vertex set $S$ in $G$ is the set of vertex sets which can be obtained from $S$ by exchanging at most three vertices. We prove the following dichotomy: On the negative side, the problem of finding a $3$-swap-optimal independent set or dominating set is PLS-complete. On the positive side, locally optimal independent sets or dominating sets can be found in polynomial time when allowing all $3$-swaps except either a) the swaps that remove two vertices from the current solution and add one vertex to the solution or b) the swaps that remove one vertex from the current solution and add two vertices to the solution.

ABSTRACT. In this paper we study the kernelization of d-Path Vertex Cover (d-PVC) problem. Given a graph G, the problem requires finding whether there exists a set of at most k vertices whose removal from G results in a graph that does not contain a path (not necessarily induced) with d vertices. It is known that d-PVC is NP-complete for d >= 2. Since the problem generalizes to d-Hitting Set, it is known to admit a kernel with O(dk^d) edges. We improve on this by giving better kernels. Specifically, we give kernels with O(k^2) vertices and edges for the cases when d=4 and d=5. Further, we give a kernel with O(k^4) vertices and edges for general d.

ABSTRACT. The study of the \textsc{Knot-Free Vertex Deletion} problem emerges from its applications in the resolution of deadlocks called knots, detected in a classical distributed computation model, that is, the OR-model. A strongly connected subgraph $Q$ of a digraph $D$ with at least two vertices is said to be a knot if there is no arc $(u,v)$ of $D$ with $u \in V(Q)$ and $v \notin V(Q)$. Given a directed graph $D$, the \textsc{Knot-Free Vertex Deletion} ({\KFProb}) problem asks to compute a minimum-size subset $S\subset V(D)$ such that $D[V\setminus S]$ contains no knots. There is no exact algorithm known for the {\KFProb} problem in the literature that is faster than the trivial $\bigoh^\star(2^n)$ brute-force algorithm. In this paper, we obtain the first non-trivial upper bounds for {\KFProb} by designing an exact algorithm running in time $\mathcal{O}^\star(1.576^n)$, where $n$ is the size of the vertex set in $D$.

ABSTRACT. For a connected graph $G = (V, E)$ and $s, t \in V$, a non-separating $s$-$t$ path is a path $P$ between $s$ and $t$ such that the set of vertices of $P$ does not separate $G$, that is, $G - V(P)$ is connected. An $s$-$t$ path $P$ is non-disconnecting if $G - E(P)$ is connected. The problems of finding shortest non-separating and non-disconnecting paths are both known to be NP-hard. In this paper, we consider the problems from the viewpoint of parameterized complexity. We show that the problem of finding a non-separating $s$-$t$ path of length at most $k$ is W[1]-hard parameterized by $k$, while the non-disconnecting counterpart is fixed-parameter tractable (FPT) parameterized by $k$. We also consider the shortest non-separating path problem on several classes of graphs and show that this problem is NP-hard even on bipartite graphs, split graphs, and planar graphs. As for positive results, the shortest non-separating path problem is FPT parameterized by $k$ on planar graphs and on unit disk graphs (where no $s$, $t$ is given). Further, we give a polynomial-time algorithms on chordal graphs if $k$ is the shortest path distance between $s$ and $t$.

ABSTRACT. One of the open problems in machine learning is whether any set-family of VC-dimension $d$ admits a sample compression scheme of size $O(d)$. In this paper, we study this problem for balls in graphs. For balls of arbitrary radius $r$, we design proper sample compression schemes of size 4 for interval graphs, of size 6 for trees of cycles, and of size 22 for cube-free median graphs. We also design approximate sample compression schemes of size 2 for balls of $\delta$-hyperbolic graphs.

ABSTRACT. Schelling’s famous model of segregation assumes agents of different types, who would like to be located in neighborhoods having at least a certain fraction of agents of the same type. We consider natural generalizations that allow for the possibility of agents being tolerant towards other agents, even if they are not of the same type. In particular, we consider an ordering of the types, and make the realistic assumption that the agents are in principle more tolerant towards agents of types that are closer to their own according to the ordering. Based on this, we study the strategic games induced when the agents aim to maximize their utility, for a variety of tolerance levels. We provide a collection of results about the existence of equilibria, and their quality in terms of social welfare.

ABSTRACT. We show that the subset sum problem, the knapsack problem and the rational subset membership problem for permutation groups are NP-complete. Concerning the knapsack problem we obtain NP-completeness for every fixed n > 2, where n is the number of permutations in the knapsack equation. In other words: membership in products of three cyclic permutation groups is NP-complete. This sharpens a result of Luks, stating NP-completeness of the membership problem for products of three abelian permutation groups. We also consider the context-free membership problem in permutation groups and prove that it is PSPACE-complete but NP-complete for a restricted class of context-free grammars where acyclic derivation trees must have constant Horton-Strahler number. Our upper bounds hold for black box groups. The results for context-free membership problems in permutation groups yield new complexity bounds for various intersection non-emptiness problems for DFAs and a single context-free grammar.

ABSTRACT. It is well known [Lovasz, 1967] that up to isomorphism a graph $G$ is determined by the homomorphism counts $\textup{hom}(F, G)$, i.e., by the number of homomorphisms from $F$ to $G$ where $F$ ranges over all graphs. Moreover, it suffices that $F$ ranges over the graphs with at most as many vertices as $G$. Thus, in principle, we can answer any query concerning $G$ with only accessing the $\textup{hom}(\cdot, G)$'s instead of $G$ itself. In this paper, we deal with queries for which there is a \emph{hom algorithm}, i.e., there are \emph{finitely many} graphs $F_1, \ldots, F_k$ such that for any graph $ G$ whether it is a \textsc{Yes}-instance of the query is already determined by the vector $\vec{hom}_{F_1, \ldots, F_k}(G):= (\textup{hom}(F_1, G), \ldots, \hom(F_k, G))$.

We observe that planarity of graphs and 3-colorability of graphs, properties expressible in monadic second-order logic, have no hom algorithm. On the other hand, queries expressible as a Boolean combination of universal sentences in first-order logic FO have a hom algorithm. Even though it is not easy to find FO definable queries without a hom algorithm, we succeed to show this for the existence of an isolated vertex, a property expressible by the FO sentence $\exists x\forall y \neg Exy$, somehow the ``simplest'' graph property not definable by a Boolean combination of universal sentences. These results provide a characterization of the prefix classes of first-order logic with the property that each query definable by a sentence of the prefix class has a hom algorithm.

For \emph{adaptive} hom algorithms, i.e., algorithms that might access a $\hom(F_{i+1}, G)$ with $F_{i+1}$ depending on $\hom(F_j, G)$ for $1\le j \le i$ we show that \emph{three} homomorphism counts $\hom(\cdot, G)$ are sufficient and in general necessary to determine the (isomorphism type of) $G$. In particular, by three adaptive queries we can answer any question on $G$. Moreover, adaptively accessing two $\hom(\cdot, G)$'s is already enough to detect an isolated vertex.

In 1993 Chaudhuri and Vardi showed the analogue of the Lovasz Isomorphism Theorem for the right homomorphism vector of a graph $G$, i.e., the vector of values $\textup{hom}(G,F)$ where $F$ ranges over all graphs characterizes the isomorphism type of $G$. We study to what extent our results carry over to the right homomorphism vector.