We show a computational complexity dichotomy theorem for symmetric complex-weighted Boolean #CSP when the constraint graph of the input must be planar. The problems that are #P-hard over general graphs but tractable over planar graphs are precisely those with a holographic reduction to matchgates. We also obtain a dichotomy theorem for a symmetric arity 4 signature with complex weights in the planar Holant framework, which we use in the proof of our #CSP dichotomy. (C) 2019 Elsevier Inc. All rights reserved.
We study the width requirements of LR-drawings of n-node ordered rooted binary trees; these are the drawings produced by a family of tree drawing algorithms introduced by Chan, who showed how to construct LR-drawings with width O (n(0.48)). We prove that LR-drawings with minimum width can be constructed in O (n(1.48)) time. Further, we show an infinite family of n-node ordered rooted binary trees requiring Omega(n(0.418)) width in any LR-drawing and we present the results of an experimental evaluation that allowed us to determine the minimum width of all the ordered rooted binary trees with up to 455 nodes. We also show that, if n-node ordered rooted binary trees have LR-drawings with f (n) width, for any function f (n), then n-vertex outerplanar graphs have outerplanar straight-line drawings in O(f (n)) area. Finally, we prove that every n-vertex outerplanar graph has an outerplanar straight-line drawing in O (n . 2 root 2log(2)n root logn) area. (C) 2019 Elsevier Inc. All rights reserved.
We study consensus in asynchronous systems where membership is unknown, and where up to f degenerative Byzantine failures can happen. In our failure model a faulty process can have a Byzantine behavior (i.e., it deviates from its specification), and, furthermore, every faulty process will degenerate such that eventually it will have permanent physical or transmission failures. We present a simple algorithm that solves Consensus using the Omega failure detector and a new broadcast primitive called RFLOB in an asynchronous system with degenerative Byzantine failures, which is optimal with respect to failures because it works when f < n/3. RFLOB guarantees reliable, FIFO and local order broadcast in systems with Byzantine processes and unknown membership. Finally, we present an algorithm that implements an Omega failure detector with unknown membership and minimum connectivity (i.e., communication reliability, and synchrony properties) in a system with degenerative Byzantine failures. (C) 2019 Elsevier Inc. All rights reserved.
Temporal graphs have time-stamped edges. Building on previous work, we study the problem of finding a small vertex set (the separator) whose removal destroys all temporal paths between two designated terminal vertices. Herein, we consider two models of temporal paths: those that pass through arbitrarily many edges per time step (non-strict) and those that pass through at most one edge per time step (strict). Regarding the number of time steps of a temporal graph, we show a complexity dichotomy (NP-completeness versus polynomial-time solvability) for both problem variants. Moreover, we prove both problem variants to be NP-complete even on temporal graphs whose underlying graph is planar. Finally, we introduce the notion of a temporal core (vertices whose incident edges change over time) and prove that the non-strict variant is fixed-parameter tractable when parameterized by the temporal core size, while the strict variant remains NP-complete, even for constant-size temporal cores. (C) 2019 Elsevier Inc. All rights reserved.
We discuss the following family of problems, parameterized by integers C >= 2 and D >= 1: Does a given one-tape q-state Turing machine make at most Cn + D steps on all computations on all inputs of length n, for all n? Assuming a fixed tape and input alphabet, we show that these problems are co-NP-complete and we provide good lower bounds. Specifically, these problems cannot be solved in o (q((C)(-1)()/4)) nondeterministic time by multi-tape Turing machines. We also show that the complements of these problems can be solved in O(q(C+2)) nondeterministic time and cannot be solved in o(q((C-1)/4)) nondeterministic time by multi-tape Turing machines. (C) 2019 Elsevier Inc. All rights reserved.
Modern, inherently dynamic systems are usually characterized by a network structure which is subject to discrete changes over time. Given a static underlying graph, a temporal graph can be represented via an assignment of a set of integer time-labels to every edge, indicating the discrete time steps when this edge is active. While most of the recent theoretical research on temporal graphs focused on temporal paths and other "path-related" temporal notions, only few attempts have been made to investigate "non-path" temporal problems. In this paper we introduce and study two natural temporal extensions of the classical problem VERTEX COVER. We present a thorough investigation of the computational complexity and approximability of these two temporal covering problems. We provide strong hardness results, complemented by approximation and exact algorithms. Some of our algorithms are polynomial-time, while others are asymptotically almost optimal under the Exponential Time Hypothesis (ETH) and other plausible complexity assumptions. (C) 2019 Elsevier Inc. All rights reserved.
A robot game, also known as a Z-VAS game, is a two-player vector addition game played on the integer lattice Z(n), where one of the players, Adam, aims to avoid the origin while the other player, Eve, aims to reach the origin. The problem is to decide whether or not Eve has a winning strategy. In this paper we prove undecidability of the two-dimensional robot game closing the gap between undecidable and decidable cases. We also prove that deciding the winner in a robot game with states in dimension one is EXPSPACE-complete and study a subclass of robot games where deciding the winner is in EXPTIME. (C) 2019 Elsevier Inc. All rights reserved.
We call any consistent and sufficiently powerful formal theory that enables to algorithmically verify whether some text is a proof algorithmically verifiable mathematics (AV-mathematics). We say a decision problem L subset of Sigma* is almost everywhere solvable if for all but finitely many inputs x is an element of Sigma*, one can prove "x is an element of L" or "x is not an element of L" in AV-mathematics. We study what kind of problems related to algorithms and computational complexity are not almost everywhere solvable in AV-mathematics. We observe that this is true for all semantically nontrivial problems about programs and show several results of the kind "There exist programs that are provably algorithms for which it is neither provable that they do not work in polynomial time, nor that they do not solve SATISFIABILITY." Finally, we prove that, if DLOG = NLOG, or BPP = PSPACE, then there exist constructive proofs for it and almost constructive in the case P = NP. (C) 2019 Elsevier Inc. All rights reserved.
Analyzing pseudo-telepathy graph games, we propose a way to build contextuality scenarios exhibiting the quantum supremacy using graph states. We consider the combinatorial structures generating equivalent scenarios. We introduce a new tool called multipartiteness width to investigate which scenarios are hard to decompose and show that there exist graphs generating scenarios with a linear multipartiteness width. (C) 2019 Elsevier Inc. All rights reserved.
摘要：An HV-graph is a planar graph with vertex-degree at most four such that each edge is labeled either H (horizontal) or V (vertical). The HV-planarity testing problem asks whether an HV-graph admits an HV-drawing, that is, a planar drawing such that each edge with label H is drawn as a horizontal segment and each edge with label V is drawn as a vertical segment. We prove that the HV-planarity testing problem is NP-complete even for graphs with vertex-degree at most three, which answers an open question posed by both Manuch et al.  and Durocher et al. . On the positive side, we prove that the HV-planarity testing problem can be solved in polynomial-time for series-parallel graphs. This result significantly extends a previous result by Durocher et al. about HV-planarity testing of biconnected outerplanar graphs of maximum vertex-degree three. (C) 2018 Elsevier Inc. All rights reserved.
摘要：We study broadcasting in multiple access channels with dynamic packet arrivals and jamming. Communication environments are represented by adversarial models that specify constraints on packet arrivals and jamming. We consider deterministic distributed broadcast algorithms and give upper bounds on the worst-case packet latency and the number of queued packets in relation to the parameters defining adversaries. Packet arrivals are determined by a rate of injections and a number of packets that can be generated in one round. Jamming is constrained by a rate with which an adversary can jam rounds and by a number of consecutive rounds that can be jammed. (C) 2018 Elsevier Inc. All rights reserved.
摘要：In sum coloring, it is required to find a proper coloring of the vertices of a graph using positive integers, such that the sum of colors of the vertices is minimized. First Fit is the natural coloring algorithm that processes vertices one by one (in some order), and colors the current vertex with the minimum color that was not used for any of its already considered neighbors. Here, we study the approximation ratio of First Fit for sum coloring for the class of claw-free graphs, its most natural subclasses, and its generalizations, and get tight bounds for it. (C) 2018 Elsevier Inc. All rights reserved.
摘要：Shifted combinatorial optimization is a new nonlinear optimization framework broadly extending standard combinatorial optimization, involving the choice of several feasible solutions simultaneously. This framework captures well studied and diverse problems, from sharing and partitioning to so-called vulnerability problems. In particular, every standard combinatorial optimization problem has its shifted counterpart, typically harder. Already with explicitly given input set SCO may be NP-hard. Here we initiate a study of the parameterized complexity of this framework. First we show that SCO over an explicitly given set parameterized by its cardinality may be in XP, FPT or P, depending on the objective function. Second, we study SCO over sets definable in MSO logic (which includes, e.g., the well known MSO-partitioning problems). Our main results are that SCO over MSO definable sets is in XP parameterized by the MSO formula and treewidth (or clique-width) of the input graph, and W-hard even under further severe restrictions. (C) 2018 Elsevier Inc. All rights reserved.
摘要：The critical DNS authoritative infrastructure is increasingly targeted by DDoS attacks in recent years. This paper proposes a novel mitigating solution to DDoS attacks on DNS authoritative name servers. The solution uses DNAME record to signal domain redirection directive to recursive resolvers, which then accordingly redirect their subsequent query traffic to the redirection domains. In response to DDoS attacks, multiple domains can be chained to elastically and adaptiyely provision and release authoritative resources to scale rapidly on demand. The simulation results validate the efficacy of the solution. (C) 2017 Elsevier Inc. All rights reserved.
摘要：This paper solves three open problems about the decidability of the vector and scalar reachability problems and the point to point reachability by fractional linear transformations over finitely generated semigroups of matrices from SL(2, Z). Our approach to solving these problems is based on the characterization of reachability paths between vectors or points, which is then used to translate the numerical problems on matrices into computational problems on words and regular languages. We will also give geometric interpretations of these results. (C) 2018 Elsevier Inc. All rights reserved.
摘要：We develop a unifying approach to declarative entity linking by introducing the notion of an entity-linking framework and an accompanying notion of the certain links in such a framework. In an entity-linking framework, logic-based constraints are used to express properties of the desired link relations in terms of source relations and, possibly, in terms of other link relations. The definition of the certain links in such a framework makes use of weighted repairs and consistent answers in inconsistent databases. We demonstrate the modeling capabilities of this approach by showing that numerous concrete entity linking scenarios can be cast as such entity-linking frameworks for suitable choices of constraints and weights. By using the certain links as a measure of expressive power, we investigate the relative expressive power of several entity-linking frameworks and obtain sharp comparisons. (C) 2018 Elsevier Inc. All rights reserved.
摘要：We consider Markov decision processes (MDP) as generators of sequences of probability distributions over states. A probability distribution is p-synchronizing if the probability mass is at least p in a single state, or in a given set of states. We consider four temporal synchronizing modes: a sequence of probability distributions is always p-synchronizing, eventually p-synchronizing, weakly p-synchronizing, or strongly p-synchronizing if, respectively, all, some, infinitely many, or all but finitely many distributions in the sequence are p-synchronizing. We provide tight results on the expressiveness, decidability, complexity, and memory requirement for winning strategies for all synchronizing modes in MDPs. (C) 2018 Elsevier Inc. All rights reserved.
摘要：Cost register automata (CRA) and its subclass, copyless CRA, were recently proposed by Alur et al. as a new model for computing functions over strings. We study some structural properties, expressiveness, and closure properties of copyless CRA. We show that copyless CRA are strictly less expressive than weighted automata and are not closed under reverse operation. To find a better class we impose restrictions on copyless CRA, which ends successfully with a new robust computational model that is closed under reverse and other extensions. (C) 2018 Elsevier Inc. All rights reserved.
摘要：k-Hierarchical probabilistic automata (HPA) are probabilistic automata whose states are partitioned into k+1 levels such that for any state and input symbol, at most one transition goes to a state at the same level, and others go to higher level states. We show that 1-HPA, with acceptance threshold 1/2 (in the finite and infinite word cases) can recognize non regular languages, and the non-emptiness and non-universality problems for 1-HPA with threshold 1/2 are decidable in EXPTIME and are PSPACE-hard. We present a new sufficient condition when 1-HPA recognize regular languages. We show that the emptiness problem is undecidable for 2-HPAs. (C) 2018 Elsevier Inc. All rights reserved.
摘要：We prove that one can count in polynomial time the number of minimal transversals of beta-acyclic hypergraphs. In consequence, we can count in polynomial time the number of minimal dominating sets of strongly chordal graphs, continuing the line of research initiated in M.M. Kante and T. Uno (2017) . (C) 2018 Elsevier Inc. All rights reserved.