Search

We show that simple modifications to van der Hoeven's forward and inverse truncated Fourier transforms allow the algorithms to be performed in-place, and with only a linear overhead in complexity.

Finding communities in the form of cohesive subgraphs is a fundamental problem in network analysis. In domains that model networks as undirected graphs, communities are generally associated with dense subgraphs, and many community models have been proposed. Maximal cliques are arguably the most widely studied among such models, with early works dating back to the ’60s, and a continuous stream of research up to the present. In domains that model networks as directed graphs, several approaches for community detection have been proposed, but there seems to be no clear model of cohesive subgraph, i.e., of what a community should look like. We extend the fundamental model of clique to directed graphs, adding the natural constraint of strong connectivity within the clique. We consider in this paper the problem of listing all maximal strongly connected cliques in a directed graph. We first investigate the combinatorial properties of strongly connected cliques and use them to prove that every n -vertex directed graph has at most 3 n / 3 maximal strongly connected cliques. We then exploit these properties to produce the first algorithms with polynomial delay for enumerating maximal strongly connected cliques: a first algorithm with polynomial delay and exponential space usage, and a second one, based on reverse-search, with higher (still polynomial) delay but which uses linear space. 1

In this paper, we design a framework to obtain efficient algorithms for several problems with a global constraint (acyclicity or connectivity) such as Connected Dominating Set, Node Weighted Steiner Tree, Maximum Induced Tree, Longest Induced Path, and Feedback Vertex Set. We design a meta-algorithm that solves all these problems and whose running time is upper bounded by $2^{O(k)}\cdot n^{O(1)}$, $2^{O(k \log(k))}\cdot n^{O(1)}$, $2^{O(k^2)}\cdot n^{O(1)}$, and $n^{O(k)}$ where $k$ is respectively the clique-width, $\mathbb{Q}$-rank-width, rank-width, and maximum induced matching width of a given decomposition. Our approach simplifies and unifies the known algorithms for each of the parameters and its running time matches asymptotically also the running times of the best known algorithms for basic \sf NP-hard problems such as Vertex Cover and Dominating Set. Our framework is based on the $d$-neighbor equivalence defined in [B. Bui-Xuan, J. A. Telle, and M. Vatshelle, Theoret. Comput. Sci., (2013), pp. 66--76] and the rank-based approach introduced in [H. L. Bodlaender, M. Cygan, S. Kratsch, and J. Nederlof, Inform. and Comput., 243 (2015), pp. 86--111]. The results we obtain highlight the importance of the $d$-neighbor equivalence relation on the algorithmic applications of width measures. We also prove that our framework could be useful for ${\sf W}[1]$-hard problems parameterized by clique-width such as Max Cut and Maximum Minimal Cut. For these latter problems, we obtain $n^{O(k)}$, $n^{O(k)}$, and $n^{2^{O(k)}}$ time algorithms where $k$ is respectively the clique-width, the $\mathbb{Q}$-rank-width, and the rank-width of the input graph. publishedVersion

International audience; We consider a time-dependent shortest path problem with possible waiting at some nodes of the graph and a global bound W on the total waiting time. The goal is to minimize the time traveled along the edges of the path, not including the waiting time. We prove that the problem can be solved in polynomial time when the travel time functions are piecewise linear and continuous. The algorithm relies on a recurrence relation characterized by a bound ω on the total waiting time, where 0 ≤ ω ≤ W . We show that only a small number of values ω 1 , ω 2 , . . . , ω K need to be considered, where K depends on the total number of breakpoints of all travel time functions.

Let p be a prime of the form p = σ2 k + 1 with σ small and let F p denote the finite field with p elements. Let P ( z ) be a polynomial of degree d in F p [ z ] with d distinct roots in F p . For p =5 · 2 55 + 1 we can compute the roots of such polynomials of degree 10 9 . We believe we are the first to factor such polynomials of size one billion. We used a multi-core computer with two 10 core Intel Xeon E5 2680 v2 CPUs and 128 gigabytes of RAM. The factorization takes just under 4,000 seconds on 10 cores and uses 121 gigabytes of RAM. We used the tangent Graeffe root finding algorithm from [27, 19] which is a factor of O (log d ) faster than the Cantor-Zassenhaus algorithm. We implemented the tangent Graeffe algorithm in C using our own library of 64 bit integer FFT based in-place polynomial algorithms then parallelized the FFT and main steps using Cilk C. In this article we discuss the steps of the tangent Graeffe algorithm, the sub-algorithms that we used, how we parallelized them, and how we organized the memory so we could factor a polynomial of degree 10 9 . We give both a theoretical and practical comparison of the tangent Graeffe algorithm with the Cantor-Zassenhaus algorithm for root finding. We improve the complexity of the tangent Graeffe algorithm by a factor of 2. We present a new in-place product tree multiplication algorithm that is fully parallelizable. We present some timings comparing our software with Magma's polynomial factorization command. Polynomial root finding over smooth finite fields is a key ingredient for algorithms for sparse polynomial interpolation that are based on geometric sequences. This application was also one of our main motivations for the present work.

International audience; In a vertex-coloured graph, a set of vertices S is said to be a rainbow set if every colour in the graph appears exactly once in S. We investigate the complexities of various problems dealing with domination in vertex-coloured graphs (existence of rainbow dominating sets, of rainbow locating-dominating sets, of rainbow identifying sets), including when we ask for a unique solution: we show equivalence between these complexities and those of the well-studied Boolean satisfiability problems.

International audience; This paper presents new fast algorithms for Hermite interpolation and evaluation over finite fields of characteristic two. The algorithms reduce the Hermite problems to instances of the standard multipoint interpolation and evaluation problems, which are then solved by existing fast algorithms. The reductions are simple to implement and free of multiplications, allowing low overall multiplicative complexities to be obtained. The algorithms are suitable for use in encoding and decoding algorithms for multiplicity codes.

International audience; We introduce the notion of pre-expansivity for cellular automata (CA): it is the property of being positively expansive on asymptotic pairs of configurations (i.e. configurations that differ in only finitely many positions). Pre-expansivity therefore lies between positive expansivity and pre-injectivity, two important notions of CA theory.We show that there exist one-dimensional pre-expansive CAs which are not positively expansive and they can be chosen reversible (while positive expansivity is impossible for reversible CAs). We provide both linear and non-linear examples. In the one-dimensional setting, we also show that pre-expansivity implies sensitivity to initial conditions in any direction. We show however that no two-dimensional Abelian CA can be pre-expansive. We also consider the finer notion of k-expansivity (positive expansivity over pairs of configurations with exactly k differences) and show examples of linear CA in dimension 2 and on the free group that are k-expansive depending on the value of k, whereas no (positively) expansive CA exists in this setting.

International audience; In the localization game, introduced by Seager in 2013, an invisible and immobile target is hidden at some vertex of a graph $G$. At every step, one vertex $v$ of $G$ can be probed which results in the knowledge of the distance between $v$ and the secret location of the target. The objective of the game is to minimize the number of steps needed to locate the target whatever be its location.We address the generalization of this game where $k\geq 1$ vertices can be probed at every step. Our game also generalizes the notion of the {\it metric dimension} of a graph.Precisely, given a graph $G$ and two integers $k,\ell \geq 1$, the {\sc Localization} problem asks whether there exists a strategy to locate a target hidden in $G$ in at most $\ell$ steps and probing at most $k$ vertices per step. We first show that, in general, this problem is \textsf{NP}-complete for every fixed $k \geq 1$ (resp., $\ell \geq 1$).We then focus on the class of trees.On the negative side,we prove that the \Localization problem is \textsf{NP}-complete in trees when $k$ and $\ell$ are part of the input. On the positive side, we design a $(+1)$-approximation algorithm for the problem in $n$-node trees, {\it i.e.}, an algorithm that computes in time $O(n \log n)$ (independent of $k$) a strategy to locate the target in at most one more step than an optimal strategy. This algorithm can be used to solve the \Localization problem in trees in polynomial time if $k$ is fixed.We also consider some of these questions in the context where, upon probing the vertices,the relative distances to the target are retrieved.This variant of the problem generalizes the notion of the {\it centroidal dimension} of a graph.

We study the complexity of the two dual covering and packing distance-based problems Broadcast Domination and Multipacking in digraphs. A dominating broadcast of a digraph D is a function \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f:V(D)\rightarrow \mathbb {N}$$\end{document} such that for each vertex v of D, there exists a vertex t with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f(t)>0$$\end{document} having a directed path to v of length at most f(t). The cost of f is the sum of f(v) over all vertices v. A multipacking is a set S of vertices of D such that for each vertex v of D and for every integer d, there are at most d vertices from S within directed distance at most d from v. The maximum size of a multipacking of D is a lower bound to the minimum cost of a dominating broadcast of D. Let Broadcast Domination denote the problem of deciding whether a given digraph D has a dominating broadcast of cost at most k, and Multipacking the problem of deciding whether D has a multipacking of size at least k. It is known that Broadcast Domination is polynomial-time solvable for the class of all undirected graphs (that is, symmetric digraphs), while polynomial-time algorithms for Multipacking are known only for a few classes of undirected graphs. We prove that Broadcast Domination and Multipacking are both NP-complete for digraphs, even for planar layered acyclic digraphs of small maximum degree. Moreover, when parameterized by the solution cost/solution size, we show that the problems are respectively W[2]-hard and W[1]-hard. We also show that Broadcast Domination is FPT on acyclic digraphs, and that it does not admit a polynomial kernel for such inputs, unless the polynomial hierarchy collapses to its third level. In addition, we show that both problems are FPT when parameterized by the solution cost/solution size together with the maximum out-degree. Finally, we give for both problems polynomial-time algorithms for some subclasses of acyclic digraphs.

International audience; A normal form system (NFS) for representing Boolean functions is thought of as a set of stratified terms over a fixed set of connectives. For a fixed NFS A, the complexity of a Boolean function f with respect to A is the minimum of the sizes of terms in A that represent f. This induces a preordering of NFSs: an NFS A is polynomially as efficient as an NFS B if there is a polynomial P with nonnegative integer coefficients such that the complexity of any Boolean function f with respect to A is at most the value of P in the complexity of f with respect to B. In this paper we study monotonic NFSs, i.e., NFSs whose connectives are increasing or decreasing in each argument. We describe the monotonic NFSs that are optimal, i.e., that are minimal with respect to the latter preorder. We show that these minimal monotonic NFSs are all equivalent. Moreover, we address some natural questions, e.g.: does optimality depend on the arity of connectives? Does it depend on the number of connectives used? We show that optimal monotonic NFSs are exactly those that use a single connective or one connective and the negation. Finally, we show that optimality does not depend on the arity of the connectives.

A subset $D \subseteq V$ is an \emph{independent} (or \emph{stable}) \emph{dominating set} of a graph $G = (V,E)$ if $D$ is an independent set (no edges between vertices of $D$) and dominates all the vertices of $G$ (each vertex of $V-D$ has a neighbour in $D$). In this paper we study a generalisation of this classical notion. Namely, an instance of our problem is a graph $G=(V, E)$ and $\Pi=(V_1, \dots, V_k)$ a partition of $V$. Each subset $V_i$ of $\Pi$ is called an \emph{obligation}. An \emph{Independent Dominating set with Obligation} (\IDO) $D$ in an instance $(G, \Pi)$ is an independent dominating set of $G$ with the additional property that if a vertex $u$ of obligation $V_i$ is in $D$, then \emph{all} the others vertices of $V_i$ must also be in $D$; i.e., for all $i=1,\dots,k$, either $V_i\cap D=\emptyset$ or $V_i \subseteq D$ (we say that $D$ \emph{respects} the obligations). Note that when each obligation of $\Pi$ is a singleton, an \IDO is just an independent dominating set of $G$ that can be constructed with a greedy algorithm. Among other things, we show that determining if an instance $(G=(V,E),\Pi)$ has an \IDO is $NP$-complete, even if $G$ is a path (each vertex of $G$ exactly has two neighbours, except two extremities that have one), all the obligations are independent sets of $G$ and they all have the same constant size $\lambda > 1$. We also show that the problem is also $NP$-complete, even if $\Pi$ is composed of $\sqrt{|V|}$ independent obligations each of size $\sqrt{|V|}$ or if the diameter of $G$ is three. Our results clearly show that this problem is very difficult, even in extremely restricted instances. Hence, in a second part of the paper, we relax the condition to dominate all the vertices of $G$. However, we show that determining if $(G=(V, E), \Pi)$ contains an independent set $D$ respecting the obligations and dominating at least $3\sqrt{|V|} -2$ vertices of $G$ is $NP$-complete, even if $G$ is a collection of disjoint paths and obligations are all independent sets of $G$. On the positive side, we propose a greedy algorithm constructing a solution dominating at least $2\sqrt{|V|} - 1$ vertices in any instance $(G=(V, E), \Pi)$ if all obligations of $\Pi$ are independent sets of $G$.

International audience; We propose a general framework that allows for the study of enumeration of vertex set properties in graphs. We prove that when such a property is locally definable with respect to some order on the set of vertices, then it can be enumerated with linear delay. Our method consists in reducing the considered enumeration problem to the enumeration of paths in directed acyclic graphs. We then apply this general method to enumerate minimal connected dominating sets and maximal irredundant sets in interval graphs and in permutation graphs, as well as maximal irredundant sets in circular-arc graphs and in circular permutation graphs, with linear delay.

International audience; Let S = {K1,3, K3, P4} be the set of connected graphs of size 3. We study the problem of partitioning the edge set of a graph G into graphs taken from any non-empty S ⊆ S. The problem is known to be NP-complete for any possible choice of S in general graphs. In this paper, we assume that the input graph is subcubic (i.e. all its vertices have degree at most 3), and study the computational complexity of the problem of partitioning its edge set for any choice of S. We identify all polynomial and NP-complete problems in that setting.

P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? A precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. Another major complexity class is coNP. Whether NP = coNP is another fundamental question that it is as important as it is unresolved. In 1979, Fortune showed that if any sparse language is coNP-complete, then P = NP. We prove there is a possible sparse language in coNP-complete. In this way, we demonstrate the complexity class P is equal to NP.

We study the decomposition of multivariate polynomials as sums of powers of linear forms. As one of our main results we give an algorithm for the following problem: given a homogeneous polynomial of degree 3, decide whether it can be written as a sum of cubes of linearly independent linear forms with complex coefficients. Compared to previous algorithms for the same problem, the two main novel features of this algorithm are: (i) It is an algebraic algorithm, i.e., it performs only arithmetic operations and equality tests on the coefficients of the input polynomial. In particular, it does not make any appeal to polynomial factorization. (ii) For an input polynomial with rational coefficients, the algorithm runs in polynomial time when implemented in the bit model of computation. The algorithm relies on methods from linear and multilinear algebra (symmetric tensor decomposition by simultaneous diagonalization). We also give a version of our algorithm for decomposition over the field of real numbers. In this case, the algorithm performs arithmetic operations and comparisons on the input coefficients. Finally we give several related derandomization results on black box polynomial identity testing, the minimization of the number of variables in a polynomial, the computation of Lie algebras and factorization into products of linear forms., This version takes the referee's comments into account

We introduce the rendezvous game with adversaries. In this game, two players, Facilitator and Divider, play against each other on a graph. Facilitator has two agents, and Divider has a team of k agents located in some vertices of the graph. They take turns in moving their agents to adjacent vertices (or staying put). Facilitator wins if his agents meet in some vertex of the graph. The goal of Divider is to prevent the rendezvous of Facilitator’s agents. Our interest is to decide whether Facilitator can win. It appears that, in general, the problem is \(\mathsf{PSPACE} \)-hard and, when parameterized by k, \(\mathsf{{co}}{\text {-}}\mathsf{{W}}[2]\)-hard. Moreover, even the game’s variant where we ask whether Facilitator can ensure the meeting of his agents within \(\tau \) steps is \(\mathsf{{co}}{\text {-}}\mathsf{{NP}}\)-complete already for \(\tau =2.\) On the other hand, for chordal and \(P_5\)-free graphs, we prove that the problem is solvable in polynomial time. These algorithms exploit an interesting relation of the game and minimum vertex cuts in certain graph classes. Finally, we show that the problem is fixed-parameter tractable parameterized by both the graph’s neighborhood diversity and \(\tau \).

International audience; The core is a well-known and fundamental notion of stability in games intended to model coalition formation such as hedonic games. The fact that the number of deviating agents (that have to coordinate themselves) can be arbitrarily high, and the fact that agents may benefit only by a tiny amount from their deviation (while they could incur in a cost for deviating), suggest that the core is not able to suitably model many practical scenarios in large and highly distributed multi-agent systems. For this reason, we consider relaxed core stable outcomes where the notion of permissible deviations is modified along two orthogonal directions: the former takes into account the size of the deviating coalition, and the latter the amount of utility gain for each member of the deviating coalition. These changes result in two different notions of stability, namely, the q-size core and k-improvement core. We investigate these concepts of stability in fractional hedonic games, that is a well-known subclass of hedonic games for which core stable outcomes are not guaranteed to exist and it is computationally hard to decide nonemptiness of the core. Interestingly, the considered relaxed notions of core also possess the appealing property of recovering, in some notable cases, the convergence, the existence and the possibility of computing stable solutions in polynomial time.

A graph is Helly if every family of pairwise intersecting balls has a nonempty common intersection. The class of Helly graphs is the discrete analogue of the class of hyperconvex metric spaces. It is also known that every graph isometrically embeds into a Helly graph, making the latter an important class of graphs in Metric Graph Theory. We study diameter, radius and all eccentricity computations within the Helly graphs. Under plausible complexity assumptions, neither the diameter nor the radius can be computed in truly subquadratic time on general graphs. In contrast to these negative results, it was recently shown that the radius and the diameter of an n-vertex m-edge Helly graph G can be computed with high probability in \(\tilde{\mathcal O}(m\sqrt{n})\) time (i.e., subquadratic in \(n+m\)). In this paper, we improve that result by presenting a deterministic \({\mathcal O}(m\sqrt{n})\) time algorithm which computes not only the radius and the diameter but also all vertex eccentricities in a Helly graph. Furthermore, we give a parameterized linear-time algorithm for this problem on Helly graphs, with the parameter being the Gromov hyperbolicity \(\delta \). More specifically, we show that the radius and a central vertex of an m-edge \(\delta \)-hyperbolic Helly graph G can be computed in \(\mathcal O(\delta m)\) time and that all vertex eccentricities in G can be computed in \(\mathcal O(\delta ^2 m)\) time. To show this more general result, we heavily use our new structural properties obtained for Helly graphs.

International audience; Discontinuous Galerkin (dG) methods on meshes consisting of polygonal/polyhedral (henceforth, collectively termed as polytopic) elements have received considerable attention in recent years. Due to the physical frame basis functions used typically and the quadrature challenges involved, the matrix-assembly step for these methods is often computationally cumbersome. To address this important practical issue, this work proposes two parallel assembly implementation algorithms on CUDA-enabled graphics cards for the interior penalty dG method on polytopic meshes for various classes of linear PDE problems. We are concerned with both single GPU parallelization, as well as with implementation on distributed GPU nodes. The results included showcase almost linear scalability of the quadrature step with respect to the number of GPU-cores used since no communication is needed for the assembly step. In turn, this can justify the claim that polytopic dG methods can be implemented extremely efficiently, as any assembly computing time overhead compared to finite elements on ‘standard’ simplicial or box-type meshes can be effectively circumvented by the proposed algorithms.

We consider families of symmetric linear programs (LPs) that decide a property of graphs (or other relational structures) in the sense that, for each size of graph, there is an LP defining a polyhedral lift that separates the integer points corresponding to graphs with the property from those corresponding to graphs without the property. We show that this is equivalent, with at most polynomial blow-up in size, to families of symmetric Boolean circuits with threshold gates. In particular, when we consider polynomial-size LPs, the model is equivalent to definability in a non-uniform version of fixed-point logic with counting (FPC). Known upper and lower bounds for FPC apply to the non-uniform version. In particular, this implies that the class of graphs with perfect matchings has polynomial-size symmetric LPs, while we obtain an exponential lower bound for symmetric LPs for the class of Hamiltonian graphs. We compare and contrast this with previous results (Yannakakis 1991), showing that any symmetric LPs for the matching and TSP polytopes have exponential size. As an application, we establish that for random, uniformly distributed graphs, polynomial-size symmetric LPs are as powerful as general Boolean circuits. We illustrate the effect of this on the well-studied planted-clique problem. First author partially funded by European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant agreement ERC-2014-CoG 648276 (AUTAR) and MICCIN grant TIN2016-76573-C2-1P (TASSAT3). The second author was partially supported by a Fellowship of the Alan Turing Institute under the EPSRC grant EP/N510129/1. The third author funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 795936.

International audience

We say that a given graph G = ( V , E ) has pathbreadth at most ρ , denoted pb ( G ) ≤ ρ , if there exists a Robertson and Seymour’s path decomposition where every bag is contained in the ρ -neighbourhood of some vertex. Similarly, we say that G has strong pathbreadth at most ρ , denoted spb ( G ) ≤ ρ , if there exists a Robertson and Seymour’s path decomposition where every bag is the complete ρ -neighbourhood of some vertex. It is straightforward that pb ( G ) ≤ spb ( G ) for any graph G . Inspired from a close conjecture in Leitert and Dragan, (2016), we prove in this note that spb ( G ) ≤ 4 ⋅ pb ( G ) .

International audience; Various optimization problems result from the introduction of nonlinear terms into combinatorial optimization problems. In the context of energy optimization for example, energy sources can have very different characteristics in terms of power range and energy demand/cost function, also known as efficiency function or energy conversion function. Introducing these energy sources characteristics in combinatorial optimization problems, such as energy resource allocation problems or energy-consuming activity scheduling problems may result into mixed integer nonlinear problems neither convex nor concave. Approximations via piecewise linear functions have been proposed in the literature. Non-convex optimization models and heuristics exist to compute optimal breakpoint positions under a bounded absolute error-tolerance. We present an alternative solution method based on the upper and lower bounding of nonlinear terms using non necessarily continuous piecewise linear functions with a relative epsilon-tolerance. Conditions under which such approach yields a pair of mixed integer linear programs with a performance guarantee are analyzed. Models and algorithms to compute the non necessarily continuous piecewise linear functions with absolute and relative tolerances are also presented. Computational evaluations performed on energy optimization problems for hybrid electric vehicles show the efficiency of the method with regards to the state of the art.

International audience; In this work we study robust scheduling problems assuming that the processing times can take any value in the budgeted uncertainty set introduced by Bertsimas and Sim (2003, 2004). We consider problems on a single machine that minimize the (weighted and unweighted) sum of completion times and problems that minimize the makespan on parallel and unrelated machines. We provide approximation algorithms: constant factor, average non-constant factor, (fully or not) polynomial time approximation schemes. In addition, we prove that the robust version of minimizing the weighted completion time on a single machine is in the strong sense.

A spanning tree T of a graph G = ( V , E ) is called eccentricity k -approximating if we have e c c T ( v ) ≤ e c c G ( v ) + k for every v ∈ V . Let e t s ( G ) be the minimum k such that G admits an eccentricity k -approximating spanning tree. As our main contribution in this paper, we prove that e t s ( G ) can be computed in O ( n m ) -time along with a corresponding spanning tree. This answers an open question of Dragan et al. (2017). Moreover we also prove that for some classes of graphs such as chordal graphs and hyperbolic graphs, one can compute an eccentricity O ( e t s ( G ) ) -approximating spanning tree in quasi linear time. Our proofs are based on simple relationships between eccentricity approximating trees and shortest-path trees.

International audience; We investigate the complexity of four decision problems dealing with the uniqueness of a solution in a graph: “Uniqueness of an r-Locating–Dominating Code with bounded size” (U-LDCr), “Uniqueness of an Optimal r-Locating–Dominating Code” (U-OLDCr), “Uniqueness of an r-Identifying Code with bounded size” (U-IdCr), “Uniqueness of an Optimal r-Identifying Code” (U-OIdCr), for any fixed integer r ≥ 1In particular, we describe a polynomial reduction from “Unique Satisfiability of a Boolean formula” (U-SAT) to U-OLDCr, and from U-SAT to U-OIdCr; for U-LDCr and U-IdCr, we can do even better and prove that their complexity is the same as that of U-SAT, up to polynomials. Consequently, all these problems are NP-hard, and U-LDCr and U-IdCr belong to the class DP.

International audience; In this paper, we generalize the concept of complete coloring and achromatic number to 2-edge-colored graphs and signed graphs. We give some useful relationships between different possible definitions of such achromatic numbers and prove that computing any of them is NP-complete.

International audience; The evaluation of a polynomial at several points is called the problem of multi-point evaluation. Sometimes, the set of evaluation points is fixed and several polynomials need to be evaluated at this set of points. Efficient algorithms for this kind of “amortized” multi-point evaluation were recently developed for the special case when the set of evaluation points is sufficiently generic. In this paper, we design a new algorithm for arbitrary sets of points, while restricting ourselves to bivariate polynomials.

We prove essentially tight lower bounds, conditionally to the Exponential Time Hypothesis, for two fundamental but seemingly very different cutting problems on surface-embedded graphs: the Shortest Cut Graph problem and the Multiway Cut problem. A cut graph of a graph G embedded on a surface S is a subgraph of G whose removal from S leaves a disk. We consider the problem of deciding whether an unweighted graph embedded on a surface of genus G has a cut graph of length at most a given value. We prove a time lower bound for this problem of n Ω( g log g ) conditionally to the ETH. In other words, the first n O(g) -time algorithm by Erickson and Har-Peled [SoCG 2002, Discr. Comput. Geom. 2004] is essentially optimal. We also prove that the problem is W[1]-hard when parameterized by the genus, answering a 17-year-old question of these authors. A multiway cut of an undirected graph G with t distinguished vertices, called terminals , is a set of edges whose removal disconnects all pairs of terminals. We consider the problem of deciding whether an unweighted graph G has a multiway cut of weight at most a given value. We prove a time lower bound for this problem of n Ω( gt + g 2 + t log ( g + t )) , conditionally to the ETH, for any choice of the genus g ≥ 0 of the graph and the number of terminals t ≥ 4. In other words, the algorithm by the second author [Algorithmica 2017] (for the more general multicut problem) is essentially optimal; this extends the lower bound by the third author [ICALP 2012] (for the planar case). Reductions to planar problems usually involve a gridlike structure. The main novel idea for our results is to understand what structures instead of grids are needed if we want to exploit optimally a certain value G of the genus.

Characterizing the graph classes such that, on $n$-vertex $m$-edge graphs in the class, we can compute the diameter faster than in ${\cal O}(nm)$ time is an important research problem both in theory and in practice. We here make a new step in this direction, for some metrically defined graph classes. Specifically, a subgraph $H$ of a graph $G$ is called a retract of $G$ if it is the image of some idempotent endomorphism of $G$. Two necessary conditions for $H$ being a retract of $G$ is to have $H$ is an isometric and isochromatic subgraph of $G$. We say that $H$ is an absolute retract of some graph class ${\cal C}$ if it is a retract of any $G \in {\cal C}$ of which it is an isochromatic and isometric subgraph. In this paper, we study the complexity of computing the diameter within the absolute retracts of various hereditary graph classes. First, we show how to compute the diameter within absolute retracts of bipartite graphs in randomized $\tilde{\cal O}(m\sqrt{n})$ time. For the special case of chordal bipartite graphs, it can be improved to linear time, and the algorithm even computes all the eccentricities. Then, we generalize these results to the absolute retracts of $k$-chromatic graphs, for every fixed $k \geq 3$. Finally, we study the diameter problem within the absolute retracts of planar graphs and split graphs, respectively.

Let G be a graph and D s and D t be two dominating sets of G of size k . Does there exist a sequence 〈 D 0 = D s , D 1 , … , D l − 1 , D l = D t 〉 of dominating sets of G such that D i + 1 can be obtained from D i by replacing one vertex with one of its neighbors? In this paper, we investigate the complexity of this decision problem. We first prove that this problem is PSPACE-complete, even when restricted to split, bipartite or bounded treewidth graphs. On the other hand, we prove that it can be solved in polynomial time on dually chordal graphs (a superclass of both trees and interval graphs) or cographs.

We consider the complexity of the Independent Set Reconfiguration problem under the Token Sliding rule. In this problem we are given two independent sets of a graph and are asked if we can transform one to the other by repeatedly exchanging a vertex that is currently in the set with one of its neighbors, while maintaining the set independent. Our main result is to show that this problem is PSPACE-complete on split graphs (and hence also on chordal graphs), thus resolving an open problem in this area. We then go on to consider the $c$-Colorable Reconfiguration problem under the same rule, where the constraint is now to maintain the set $c$-colorable at all times. As one may expect, a simple modification of our reduction shows that this more general problem is PSPACE-complete for all fixed $c\ge 1$ on chordal graphs. Somewhat surprisingly, we show that the same cannot be said for split graphs: we give a polynomial time ($n^{O(c)}$) algorithm for all fixed values of $c$, except $c=1$, for which the problem is PSPACE-complete. We complement our algorithm with a lower bound showing that $c$-Colorable Reconfiguration is W[2]-hard on split graphs parameterized by $c$ and the length of the solution, as well as a tight ETH-based lower bound for both parameters., 17 pages, 1 figure. STACS 2019

Tseitin-formulas are systems of parity constraints whose structure is described by a graph. These formulas have been studied extensively in proof complexity as hard instances in many proof systems. In this paper, we prove that a class of unsatisfiable Tseitin-formulas of bounded degree has regular resolution refutations of polynomial length if and only if the treewidth of all underlying graphs $G$ for that class is in $O(\log|V(G)|)$. To do so, we show that any regular resolution refutation of an unsatisfiable Tseitin-formula with graph $G$ of bounded degree has length $2^{\Omega(tw(G))}/|V(G)|$, thus essentially matching the known $2^{O(tw(G))}poly(|V(G)|)$ upper bound up. Our proof first connects the length of regular resolution refutations of unsatisfiable Tseitin-formulas to the size of representations of \textit{satisfiable} Tseitin-formulas in decomposable negation normal form (DNNF). Then we prove that for every graph $G$ of bounded degree, every DNNF-representation of every satisfiable Tseitin-formula with graph $G$ must have size $2^{\Omega(tw(G))}$ which yields our lower bound for regular resolution., Comment: 20 pages including references

We prove that the resultant of two “sufficiently generic” bivariate polynomials over a finite field can be computed in quasi-linear expected time, using a randomized algorithm of Las Vegas type. A similar complexity bound is proved for the computation of the lexicographical Grobner basis for the ideal generated by the two polynomials.

A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for \textsc{Maximum Clique} on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematics '90]. Since then, it has been an intriguing open question whether or not tractability can be extended to general disk graphs. We show that the disjoint union of two odd cycles is never the complement of a disk graph nor of a unit (3-dimensional) ball graph. From that fact and existing results, we derive a simple QPTAS and a subexponential algorithm running in time $2^{\tilde{O}(n^{2/3})}$ for \textsc{Maximum Clique} on disk and unit ball graphs. We then obtain a randomized EPTAS for computing the independence number on graphs having no disjoint union of two odd cycles as an induced subgraph, bounded VC-dimension, and linear independence number. This, in combination with our structural results, yields a randomized EPTAS for \textsc{Max Clique} on disk and unit ball graphs. \textsc{Max Clique} on unit ball graphs is equivalent to finding, given a collection of points in $\mathbb R^3$, a maximum subset of points with diameter at most some fixed value. In stark contrast, \textsc{Maximum Clique} on ball graphs and unit $4$-dimensional ball graphs, as well as intersection graphs of filled ellipses (even close to unit disks) or filled triangles is unlikely to have such algorithms. Indeed, we show that, for all those problems, there is a constant ratio of approximation which cannot be attained even in time $2^{n^{1-\varepsilon}}$, unless the Exponential Time Hypothesis fails., arXiv admin note: substantial text overlap with arXiv:1712.05010, arXiv:1803.01822

A sparse language is a formal language such that the number of strings of length $n$ is bounded by a polynomial function of $n$. We create a class with the opposite definition, that is a class of languages that are dense instead of sparse. We define a dense language on $m$ as a formal language (a set of binary strings) where there exists a positive integer $n_{0}$ such that the counting of the number of strings of length $n \geq n_{0}$ in the language is greater than or equal to $2^{n - m}$ where $m$ is a real number and $0 < m \leq 1$. We call the complexity class of all dense languages on $m$ as $DENSE(m)$. We prove that there exists an $\textit{NP--complete}$ problem that belongs to $DENSE(m)$ for every possible value of $0 < m \leq 1$.

We define a continuation-passing style (CPS) translation for a typed λ-calculus with probabilistic choice, unbounded recursion, and a tick operator — for modeling cost. The target language is a (non-probabilistic) λ-calculus, enriched with a type of extended positive reals and a fixpoint operator. We then show that applying the CPS transform of an expression M to the continuation λ v . 0 yields the expected cost of M . We also introduce a formal system for higher-order logic, called EHOL, prove it sound, and show it can derive tight upper bounds on the expected cost of classic examples, including Coupon Collector and Random Walk. Moreover, we relate our translation to Kaminski et al.’s ert-calculus, showing that the latter can be recovered by applying our CPS translation to (a generalization of) the classic embedding of imperative programs into λ-calculus. Finally, we prove that the CPS transform of an expression can also be used to compute pre-expectations and to reason about almost sure termination.

International audience; This paper introduces the largest connected subgraph game played on an undirected graph G. In each round, Alice first colours an uncoloured vertex of G red, and then, Bob colours an uncoloured vertex of G blue, with all vertices initially uncoloured. Once all the vertices are coloured, Alice (Bob, resp.) wins if there is a red (blue, resp.) connected subgraph whose order is greater than the order of any blue (red, resp.) connected subgraph. We first prove that, if Alice plays optimally, then Bob can never win, and define a large class of graphs (called reflection graphs) in which the game is a draw. We then show that determining the outcome of the game is PSPACE-complete, even in bipartite graphs of small diameter, and that recognising reflection graphs is GI-hard. We also prove that the game is a draw in paths if and only if the path is of even order or has at least 11 vertices, and that Alice wins in cycles if and only if the cycle is of odd length. Lastly, we give an algorithm to determine the outcome of the game in cographs in linear time.

We consider the problem of the existence of natural improvement dynamics leading to approximate pure Nash equilibria, with a reasonable small approximation, and the problem of bounding the efficiency of such equilibria in the fundamental framework of weighted congestion game with polynomial latencies of degree at most $\d \geq 1$.\\ In this work, by exploiting a simple technique, we firstly show that the game always admits a $\d$-approximate potential function. This implies that every sequence of $\d$-approximate improvement moves by the players always leads the game to a $\d$-approximate pure Nash equilibrium. As a corollary, we also obtain that, under mild assumptions on the structure of the players' strategies, the game always admits a constant approximate potential function. Secondly, by using a simple potential function argument, we are able to show that in the game there always exists a $(\d+\delta)$-approximate pure Nash equilibrium, with $\delta\in [0,1]$, whose cost is $2/(1+\delta)$ times the cost of any optimal state.

This paper studies the statistical query (SQ) complexity of estimating $d$-dimensional submanifolds in $\mathbb{R}^n$. We propose a purely geometric algorithm called Manifold Propagation, that reduces the problem to three natural geometric routines: projection, tangent space estimation, and point detection. We then provide constructions of these geometric routines in the SQ framework. Given an adversarial $\mathrm{STAT}(\tau)$ oracle and a target Hausdorff distance precision $\varepsilon = \Omega(\tau^{2 / (d + 1)})$, the resulting SQ manifold reconstruction algorithm has query complexity $O(n \operatorname{polylog}(n) \varepsilon^{-d / 2})$, which is proved to be nearly optimal. In the process, we establish low-rank matrix completion results for SQ's and lower bounds for randomized SQ estimators in general metric spaces.