Search

In this paper, we focus on Hitting-Set , a fundamental problem in combinatorial optimization, through the lens of sublinear time algorithms. Given access to the hypergraph through a subset query oracle in the query model, we give sublinear time algorithms for Hitting-Set with almost tight parameterized query complexity. In parameterized query complexity , we estimate the number of queries to the oracle based on the parameter k , the size of the Hitting-Set. The subset query oracle we use in this paper is called Generalized d -partite Independent Set query oracle (GPIS) and it was introduced by Bishnu et al. (ISAAC'18). GPIS is a generalization to hypergraphs of the Bipartite Independent Set query oracle (BIS) introduced by Beame et al. (ITCS'18 and TALG'20) for estimating the number of edges in graphs. Since its introduction GPIS query oracle has been used for estimating the number of hyperedges independently by Dell et al. (SODA'20 and SICOMP'22) and Bhattacharya et al. (STACS'22), and for estimating the number of triangles in a graph by Bhattacharya et al. (ISAAC'19 and TOCS'21). Formally, GPIS is defined as follows: GPIS oracle for a d-uniform hypergraph H takes as input d pairwise disjoint non-empty subsets A 1 , ... , A d of vertices in H and answers whether there is a hyperedge in H that intersects each set A i , where i ∈ { 1 , 2 , ... , d }. For d = 2 , the GPIS oracle is nothing but BIS oracle. We show that d - Hitting-Set , the hitting set problem for d -uniform hypergraphs, can be solved using O ˜ d (k d log ⁡ n) GPIS queries. Additionally, we also showed that d - Decision-Hitting-Set , the decision version of d - Hitting-Set can be solved with O ˜ d (min ⁡ { k d log ⁡ n , k 2 d 2 }) GPIS queries. We complement these parameterized upper bounds with an almost matching parameterized lower bound that states that any algorithm that solves d - Decision-Hitting-Set requires Ω (( k + d d )) GPIS queries. [ABSTRACT FROM AUTHOR]

We study population protocols whose dynamics are modeled by the discrete Lotka-Volterra equations. Such protocols capture the dynamics of some opinion spreading models and generalize the Rock-Paper-Scissors discrete dynamics. Pairwise interactions among agents are scheduled uniformly at random. We consider convergence time and show that any such protocol on an n -agent population converges to an absorbing state in time polynomial in n , w.h.p., when any pair of agents is allowed to interact. When the interaction graph is a star, even the Rock-Paper-Scissors protocol requires exponential time to converge. We study threshold effects with three and more species under interactions between any pair of agents. We prove that the Rock-Paper-Scissors protocol reaches each of its three possible absorbing states with almost equal probability, starting from any configuration satisfying some sub-linear lower bound on the initial size of each species. Thus Rock-Paper-Scissors is a realization of "coin-flip consensus" in a distributed system. [ABSTRACT FROM AUTHOR]

Given a graph G and two independent sets I s and I t of size k , the Independent Set Reconfiguration problem asks whether there exists a sequence of independent sets that transforms I s to I t such that each independent set is obtained from the previous one using a so-called reconfiguration step. Viewing each independent set as a collection of k tokens placed on the vertices of a graph G , the two most studied reconfiguration steps are token jumping and token sliding. Over a series of papers, it was shown that the Token Jumping problem is fixed-parameter tractable (for parameter k) when restricted to sparse graph classes, such as planar, bounded treewidth, and nowhere dense graphs. As for the Token Sliding problem, almost nothing is known. We remedy this situation by showing that Token Sliding is fixed-parameter tractable on graphs of bounded degree, planar graphs, and chordal graphs of bounded clique number. [ABSTRACT FROM AUTHOR]

The problem of deletion of vertices to a hereditary graph class is a well-studied problem in parameterized complexity. Recently, a natural extension of the problem was initiated where we are given a finite set of hereditary graph classes and we determine whether k vertices can be deleted from a given graph so that the connected components of the resulting graph belong to one of the given hereditary graph classes. The problem is shown to be fixed parameter tractable (FPT) when the deletion problem to each of the given hereditary graph classes is fixed-parameter tractable, and the property of being in any of the graph classes is expressible in the counting monodic second order (CMSO) logic. This paper focuses on pairs of specific graph classes (Π 1 , Π 2) in which we would like the connected components of the resulting graph to belong to, and design simpler and more efficient FPT algorithms. [ABSTRACT FROM AUTHOR]

Unambiguous automata are nondeterministic automata in which every word has at most one accepting run. In this paper we give a polynomial-time algorithm for model checking discrete-time Markov chains against ω -regular specifications represented as unambiguous automata. We furthermore show that the complexity of this model checking problem lies in NC: the subclass of P comprising those problems solvable in poly-logarithmic parallel time. These complexity bounds match the known bounds for model checking Markov chains against specifications given as deterministic automata, notwithstanding the fact that unambiguous automata can be exponentially more succinct than deterministic automata. We report on an implementation of our procedure, including an experiment in which the implementation is used to model check LTL formulas on Markov chains. [ABSTRACT FROM AUTHOR]

The asynchronous automaton of a Boolean network f : { 0 , 1 } n → { 0 , 1 } n , considered in many applications, is the finite deterministic automaton where the set of states is { 0 , 1 } n , the alphabet is [ n ] , and the action of letter i on a state x consists in either switching the i th component if f i (x) ≠ x i or doing nothing otherwise. In this paper, we ask for the existence of synchronizing words for this automaton, and their minimal length, when f is the and-net over an arc-signed digraph G on [ n ] : for every i ∈ [ n ] , f i (x) = 1 if and only if x j = 1 (x j ≠ 0) for every positive (negative) arc from j to i. Our main result is that if G is strongly connected and has no positive cycles, then either there exists a synchronizing word of length at most 10 (5 + 1) n or G is a cycle and there are no synchronizing words. We also give complexity results showing that the situation is much more complex if one of the two hypothesis made on G is removed. [ABSTRACT FROM AUTHOR]

Over the past few decades, a large body of works studied the (in)tractability of various computational problems on grid graphs, which often yield substantially faster algorithms than general graphs. Unfortunately, the recognition of a grid graph is hard—it was shown to be NP-hard already in 1987. In this paper, we provide several positive results in this regard in the framework of parameterized complexity. Specifically, our contribution is threefold. First, we show that the problem is FPT parameterized by k + mcc where mcc is the maximum size of a connected component of G. Second, we present a new parameterization, denoted a G , relating graph distance to geometric distance. We show that the problem is para-NP-hard parameterized by a G , but FPT parameterized by a G on trees, as well as FPT parameterized by k + a G. Third, we show that the recognition of k × r grid graphs is NP-hard on graphs of pathwidth 2 where k = 3. [ABSTRACT FROM AUTHOR]

The computational complexity of the word problem in HNN-extension of groups is studied. HNN-extension is a fundamental construction in combinatorial group theory. It is shown that the word problem for an ascending HNN-extension of a group H is logspace reducible to the so-called compressed word problem for H. The main result of the paper states that the word problem for an HNN-extension of a hyperbolic group H with cyclic associated subgroups can be solved in polynomial time. This result can be easily extended to fundamental groups of graphs of groups with hyperbolic vertex groups and cyclic edge groups. [ABSTRACT FROM AUTHOR]

Trees with many leaves have applications for broadcasting a message to all recipients simultaneously. Internal nodes of a broadcasting tree require more expensive technology to forward the messages received. We address a problem that captures the main goal: finding spanning trees with few internal nodes in a given network. The Maximum Leaf Spanning Arborescence problem consists of, given a directed graph D , finding a spanning arborescence of D , if one exists, with the maximum number of leaves. This problem is NP-hard in general and MaxSNP-hard in the rooted directed acyclic graphs class. This paper explores a relationship between Maximum Leaf Spanning Arborescence in rooted directed acyclic graphs and maximum weight set packing. The latter problem is related to independent sets on particular classes of intersection graphs. Exploiting this relation, we derive a 7/5-approximation for Maximum Leaf Spanning Arborescence on rooted directed acyclic graphs, improving on the previous 3/2-approximation. [ABSTRACT FROM AUTHOR]

In the possible winner problem, we need to compute if a set of partial votes can be completed such that a given candidate wins the election under some specific voting rule. In this paper, we determine the smallest number of undetermined pairs per partial vote for which the Possible Winner problem is NP -complete. In particular, we find the exact values of t for which the Possible Winner problem transitions to being NP -complete from being in P , where t is the maximum number of undetermined pairs in every vote. We demonstrate tight results for a broad class of scoring rules, Copeland α for every α ∈ [ 0 , 1 ] , maximin, and Bucklin voting rules. A somewhat surprising aspect of our results is that for many of these rules, the Possible Winner problem turns out to be hard even if every vote has at most one undetermined pair of candidates. [ABSTRACT FROM AUTHOR]

A temporal graph G is a pair (G , λ) where G is a graph and λ is a function on the edges of G describing when each edge is active. Temporal connectivity then concerns only paths that respect the flow of time. In this context, it is known that Menger's Theorem does not hold. In a seminal paper, Kempe, Kleinberg and Kumar (STOC'2000) defined a graph to be Mengerian if equality holds for every time-function. They then proved that, if each edge is allowed to be active only once in (G , λ) , then G is Mengerian if and only if G has no gem as topological minor. In this paper, we generalize their result by allowing edges to be active more than once, giving a characterization also in terms of forbidden structures. We additionally provide a polynomial time recognition algorithm. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be an undirected graph on n vertices and λ : E → 2 N a mapping that assigns to every edge a non-empty set of integer labels (discrete times when the edge is present). Such a labelled graph G = (G , λ) is temporally connected if a path exists with non-decreasing times from every vertex to every other vertex. In a seminal paper, Kempe, Kleinberg, and Kumar [17] asked whether, given such a temporally connected graph, a sparse subset of edges always exists whose labels suffice to preserve temporal connectivity – a temporal spanner. Axiotis and Fotakis [5] answered negatively by exhibiting a family of Θ (n 2) -dense temporal graphs which admit no temporal spanner of density o (n 2). In this paper, we give the first positive answer as to the existence of o (n 2) -sparse spanners in a dense class of temporal graphs, by showing (constructively) that if G is a complete graph, then one can always find a temporal spanner with O (n log ⁡ n) edges. [ABSTRACT FROM AUTHOR]

The temporal graph exploration problem TEXP is the problem of computing a foremost exploration schedule for a temporal graph, i.e., a temporal walk that starts at a given start node, visits all nodes of the graph, and has the smallest arrival time. In the first and second part of the paper, we consider only undirected temporal graphs that are connected at each time step. For such temporal graphs with n nodes, we show that it is NP -hard to approximate TEXP with ratio O (n 1 − ε) for every ε > 0 and present several solutions for special graph classes. In the third part of the paper, we consider settings where the graphs in future time steps are not known. We show that m -edge temporal graphs with regularly present edges and with probabilistically present edges can be explored online in O (m) time steps and O (m log ⁡ n) time steps with high probability, respectively. [ABSTRACT FROM AUTHOR]

In a multiple access channel, autonomous stations are able to transmit and listen to a shared device. A fundamental problem, called contention resolution , is to allow any station to successfully deliver its message by resolving the conflicts that arise when several stations transmit simultaneously. Despite a long history on such a problem, most of the results deal with the static setting when all stations start simultaneously, while many fundamental questions remain open in the realistic scenario when stations can join the channel at arbitrary times. In this paper, we explore the impact that three major channel features (asynchrony among stations, knowledge of the number of contenders and possibility of switching off stations after a successful transmission) can have on the time complexity of non-adaptive deterministic algorithms. We establish upper and lower bounds allowing to understand which parameters permit time-efficient contention resolution and which do not. [ABSTRACT FROM AUTHOR]

We consider the circular pattern matching with k mismatches (k -CPM) problem in which one is to compute the minimal Hamming distance of every length- m substring of T and any cyclic rotation of P , if this distance is no more than k. It is a variation of the well-studied k -mismatch problem. A multitude of papers has been devoted to solving the k -CPM problem, but only average-case upper bounds are known. In this paper, we present the first non-trivial worst-case upper bounds for this problem. Specifically, we show an O (n k) -time algorithm and an O (n + n m k 4) -time algorithm. The latter algorithm applies in an extended way a technique that was very recently developed for the k -mismatch problem Bringmann et al. (2019) [10]. A preliminary version of this work appeared at FCT 2019 [35]. In this version we improve the time complexity of the second algorithm from O (n + n m k 5) to O (n + n m k 4). [ABSTRACT FROM AUTHOR]

Real-world point sets tend to be clustered, so using a machine word for each point is wasteful. In this paper we first show how a compact representation of quadtrees using O (1) bits per node can break this bound on clustered point sets, while offering efficient range searches. We then describe a new compact quadtree representation based on heavy-path decompositions, which supports queries faster than previous compact structures. We present experimental evidence showing that our structure is competitive in practice. [ABSTRACT FROM AUTHOR]

A graph G = (V , E) is δ -hyperbolic if for any four vertices u , v , w , x , the two larger of the three distance sums d (u , v) + d (w , x) , d (u , w) + d (v , x) , d (u , x) + d (v , w) differ by at most 2 δ ≥ 0. This paper describes the eccentricity terrain of a δ -hyperbolic graph. The eccentricity function e G (v) = max ⁡ { d (v , u) : u ∈ V } partitions vertices of G into eccentricity layers C k (G) = { v ∈ V : e G (v) = r a d (G) + k } , k ∈ N , where r a d (G) = min ⁡ { e G (v) : v ∈ V } is the radius of G. The paper studies the eccentricity layers of vertices along shortest paths, identifying such terrain features as hills, plains, valleys, terraces, and plateaus. It introduces the notion of β -pseudoconvexity, which implies Gromov's ϵ -quasiconvexity, and illustrates the abundance of pseudoconvex sets in δ -hyperbolic graphs. It shows that all sets C ≤ k (G) = { v ∈ V : e G (v) ≤ r a d (G) + k } , k ∈ N , are (2 δ − 1) -pseudoconvex. Several bounds on the eccentricity of a vertex are obtained which yield a few approaches to efficiently approximating all eccentricities. [ABSTRACT FROM AUTHOR]

A tree cover of a metric space (X , d) is a collection of trees, so that every pair x , y ∈ X has a low distortion path in one of the trees. If it has the stronger property that every point x ∈ X has a single tree with low distortion paths to all other points, we call this a Ramsey tree cover. In this paper we devise efficient algorithms to construct tree covers and Ramsey tree covers for general, planar and doubling metrics. We pay particular attention to the desirable case of distortion close to 1, and study what can be achieved when the number of trees is small. In particular, our work shows a large separation between what can be achieved by tree covers vs. Ramsey tree covers. [ABSTRACT FROM AUTHOR]

In this paper, we focus on the shortest link scheduling (SLS) in wireless networks under the Signal-to-Interference-plus-Noise-Ratio (SINR) constraints. We introduce a consistent graph G ¯ = (V ¯ , E ¯) where V ¯ is the links set and each edge in E ¯ indicates that its two ends can be active simultaneously. We interpret SLS as the finding of a clique partition in G ¯ and propose a fast approximation algorithm, MCBS (Maximum Clique Based Scheduling), for SLS with a uniform power assignment and with an approximation ratio to the optimal solution of O (1). Theoretical analysis demonstrates the correctness and effectiveness of the proposed algorithm. Our simulation results show that the MCBS algorithm overcomes the best known algorithms in terms of execution time and the number of time slots. [ABSTRACT FROM AUTHOR]

In the Graph bipartization (or Odd Cycle Transversal) problem, the objective is to decide whether a given graph G can be made bipartite by the deletion of k vertices for some given k. The parameterized complexity of Odd Cycle Transversal was resolved in the breakthrough paper of Reed, Smith and Vetta [Operations Research Letters, 2004], who developed an algorithm running in time O (3 k k m n). The question of improving the dependence on the input size to linear, which was another long standing open problem in the area, was resolved by Iwata et al. [SICOMP 2016] and Ramanujan and Saurabh [TALG 2017], who presented O (4 k (m + n)) and 4 k k O (1) (m + n) algorithms respectively. In this paper, we obtain a faster algorithm that runs in time 3 k k O (1) (m + n) and hence preserves the linear dependence on the input size while nearly matching the dependence on k incurred by the algorithm of Reed, Smith and Vetta. [ABSTRACT FROM AUTHOR]

Approaches based on the idea generically called distributional learning have been making great success in the algorithmic learning of several rich subclasses of context-free languages and their extensions. Those language classes are defined by properties concerning string-context relation. In this paper, we present a distributional learning algorithm for conjunctive grammars with the k -finite context property (k - fcp) for each natural number k. We also compare our result with the closely related work by Clark et al. (JMLR 2010) [5] on learning some context-free grammars using contextual binary feature grammars (cbfg s). We prove that the context-free grammars targeted by their algorithm have the k - fcp. Moreover, we show that every exact cbfg has the k - fcp , too, while not all of them are learnable by their algorithm. Clark et al. conjectured a learning algorithm for exact cbfg s should exist. This paper answers their conjecture in a positive way. • We present a distributional learning algorithm for conjunctive grammars with the finite context property. • We show that exact contextual binary feature grammars have the finite context property. • We show that the learnability condition for CFGs presented by Clark et al. (2010) implies the finite context property. [ABSTRACT FROM AUTHOR]

Improvements in data storage may be constrained by the lower performance of hard disk drives (HDD) and the higher cost per gigabyte of solid-state drives (SSD). To mitigate these issues, hybrid storage architectures have been conceived. Some works evaluate the performance of storage architectures, but energy consumption is usually neglected and not simultaneously evaluated with performance. This paper presents an approach based on generalized stochastic Petri nets (GSPN) for performance and energy consumption evaluation of individual and hybrid storage systems. The proposed models can represent distinct workloads and also estimate throughput, response time and energy consumption of storage systems. Experiments based on industry-standard benchmarks are adopted to demonstrate the feasibility of the proposed approach. [ABSTRACT FROM AUTHOR]

In the study of rooted phylogenetic networks, analyzing the set of rooted phylogenetic trees that are embedded in such a network is a recurring task. Algorithmically, this analysis requires a search of the exponential-sized multiset S of rooted phylogenetic trees that are embedded in a rooted phylogenetic network N. In this paper, we introduce the notion of a non-essential arc, which is an arc whose deletion from N results in a rooted phylogenetic network N ′ that embeds the same set of rooted phylogenetic trees as N but whose associated multiset is smaller than S. We characterize non-essential arcs for the popular class of tree-child networks and show that identifying and deleting such arcs takes time that is cubic in the number of leaves of the network. Moreover, we show that deciding if a given arc of an arbitrary phylogenetic network is non-essential is Π 2 P -complete. [ABSTRACT FROM AUTHOR]

By introducing programmability, automated verification, and innovative debugging tools, Software-Defined Networks (SDNs) are poised to meet the increasingly stringent dependability requirements of today's communication networks. However, the design of fault-tolerant SDNs remains an open challenge. This paper considers the design of dependable SDNs through the lenses of self-stabilization—a very strong notion of fault-tolerance. In particular, we develop algorithms for an in-band and distributed control plane for SDNs, called Renaissance, which tolerate a wide range of failures. Our self-stabilizing algorithms ensure that after the occurrence of arbitrary failures, (i) every non-faulty SDN controller can reach any switch (or another controller) within a bounded communication delay (in the presence of a bounded number of failures) and (ii) every switch is managed by a controller. We evaluate Renaissance through a rigorous worst-case analysis as well as a prototype implementation (based on OVS and Floodlight, and Mininet). [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of PAC learning halfspaces in the non-interactive local differential privacy model (NLDP). To breach the barrier of exponential sample complexity, previous results studied a relaxed setting where the server has access to some additional public but unlabeled data. We continue in this direction. Specifically, we consider the problem under the standard setting instead of the large margin setting studied before. Under different mild assumptions on the underlying data distribution, we propose two approaches that are based on the Massart noise model and self-supervised learning and show that it is possible to achieve sample complexities that are only linear in the dimension and polynomial in other terms for both private and public data, which significantly improve the previous results. Our methods could also be used for other private PAC learning problems. [ABSTRACT FROM AUTHOR]

The median of a set of vertices P of a graph G is the set of all vertices x of G minimizing the sum of distances from x to all vertices of P. In this paper, we present a linear time algorithm to compute medians in median graphs. We also present a linear time algorithm to compute medians in the associated ℓ 1 -cube complexes. Our algorithm is based on the majority rule characterization of medians in median graphs and on a fast computation of parallelism classes of edges (Θ-classes) via Lexicographic Breadth First Search (LexBFS). We show that any LexBFS ordering of the vertices of a median graph satisfies the following fellow traveler property : the parents of any two adjacent vertices are also adjacent. Using the fast computation of the Θ-classes, we also compute the Wiener index (total distance) in linear time and the distance matrix in optimal quadratic time. [ABSTRACT FROM AUTHOR]

Cloud service for data outsourcing has triggered security and privacy needs that can be satisfied by encrypting data prior to outsourcing to the cloud. Searchable Encryption that uses methods like homomorphic encryption is inefficient and impractical. In this paper, we have proposed a secure searchable encryption scheme using Hash based Indexing that consists of Elliptic curve based ElGamal additive homomorphic encryption. The use of indexing reduces computational load on the cloud server and users. The scheme obviates the need for generation and resource intensive processing on complex trapdoor system and binary query scheme. The security of this system relies on the Elliptic curve discrete logarithm problem assumption. Comparison analysis is performed and experimental results prove the suitability for the large data sets, while efficiently supporting the dynamic updates and effective ranking of precise files corresponding to the requested multi keywords. [ABSTRACT FROM AUTHOR]

The Existential Theory of the Reals (ETR) consists of existentially quantified Boolean formulas over equalities and inequalities of polynomial functions of real variables. In this paper we propose and study the approximate existential theory of the reals (ϵ -ETR) in which the constraints are only satisfied approximately. We first show that when the domain of the variables is the reals then ϵ -ETR = ETR under polynomial time reductions, and then study the constrained ϵ -ETR problem where groups of variables are constrained to lie in bounded convex sets. Our main result is a sampling theorem that discretizes the domain in a grid-like manner whose density depends on various properties of the ETR formula. A consequence of our theorem is that we obtain a (quasi-)polynomial time approximation scheme ((Q)PTAS) for a fragment of constrained ϵ -ETR. We use this theorem to create several new PTAS and QPTAS for problems from a variety of fields. [ABSTRACT FROM AUTHOR]

This paper studies the problem of finding a path centdian on a tree in which vertex weights are uncertain and the uncertainty is characterized by given intervals. It is required to find a minmax regret solution, which minimizes the worst-case loss in the objective function. Puerto et al. had an O ( n 5 log ⁡ n ) -time algorithm for this problem. In this paper, we first show that there is a special case which their algorithm does not handle and it is easy to modify their algorithm to cope with this exception. Then, we further present an improved O ( n 4 ) -time algorithm. [ABSTRACT FROM AUTHOR]

The present paper establishes a new homotopy, called an LMA -homotopy, and further, an LMA -homotopy equivalence suitable for studying the homotopic properties of both Euclidean topology and M -topology. Indeed, the LMA -map (see Definition 12 of the present paper) is an advanced version of that of [18] . Besides, the paper studies relations among an ordinary homotopy equivalence ( resp. contractibility) for spaces ( X , U X ) , an LMA -homotopy equivalence ( resp. LMA -contractibility) for spaces ( X , U X ) and an MA -homotopy equivalence ( resp. MA -contractibility) for MA -spaces. Finally, we classify ( X , U X ) in terms of the LMA -homotopy equivalence. This approach will facilitate studies of applied topology, approximation theory and digital geometry. [ABSTRACT FROM AUTHOR]

The Super-SAT (SSAT) problem was introduced in [1,2] to prove the NP-hardness of approximation of two popular lattice problems - Shortest Vector Problem and Closest Vector Problem. SSAT is conjectured to be NP-hard to approximate to within a factor of n c (c is positive constant, n is the size of the SSAT instance). In this paper we prove this conjecture assuming the Projection Games Conjecture (PGC) [3]. This implies hardness of approximation of these lattice problems within polynomial factors, assuming PGC. We also reduce SSAT to the Nearest Codeword Problem and Learning Halfspace Problem [4]. This proves that both these problems are NP-hard to approximate within a factor of N c ′ / log ⁡ log ⁡ n (c ′ is positive constant, N is the size of the instances of the respective problems). Assuming PGC these problems are proved to be NP-hard to approximate within polynomial factors. [ABSTRACT FROM AUTHOR]

Read-only memory (ROM) model is a classical model of computation to study time-space tradeoffs of algorithms. More recently, several graph algorithms have been studied under ROM model. In this paper, we study graph algorithms under two different relaxations of ROM model, referred to as the implicit and rotate models, and show that these simple relaxations allow us to implement fundamental graph search methods like BFS and DFS more space efficiently than in ROM model. All our algorithms are simple but quite subtle, and we believe that these models are practical enough to spur interest for other graph problems in these models. [ABSTRACT FROM AUTHOR]

Satisfiability of word equations problem is: Given two sequences consisting of letters and variables decide whether there is a substitution for the variables that turns this equation into true equality. The exact computational complexity of this problem remains unknown, with the best lower and upper bounds being, respectively, NP and PSPACE. Recently, the novel technique of recompression was applied to this problem, simplifying the known proofs and lowering the space complexity to (non-deterministic) O (n log ⁡ n). In this paper we show that satisfiability of word equations is in non-deterministic linear space, thus the language of satisfiable word equations is context-sensitive. We use the known recompression-based algorithm and additionally employ Huffman coding for letters. The proof, however, uses analysis of how the fragments of the equation depend on each other as well as a new strategy for non-deterministic choices of the algorithm. [ABSTRACT FROM AUTHOR]

Counting the number of nodes in Anonymous Dynamic Networks is enticing from an algorithmic perspective: an important computation in a restricted platform with promising applications. Starting with Michail, Chatzigiannakis, and Spirakis [1] , a flurry of papers sped up the running time guarantees from doubly-exponential to polynomial [2,3]. There is a common theme across all those works: a distinguished node is assumed to be present, because Counting cannot be solved deterministically without at least one. In the present work we study challenging questions that naturally follow: how to efficiently count with more than one distinguished node, or how to count without any distinguished node. More importantly, what is the minimal information needed about these distinguished nodes and what is the best we can aim for (count precision, stochastic guarantees, etc.) without any. We present negative and positive results to answer these questions. To the best of our knowledge, this is the first work that addresses them. [ABSTRACT FROM AUTHOR]

A power assignment is an assignment of transmission power to each of the wireless nodes of a wireless network, so that the induced graph satisfies some desired properties. The cost of a power assignment is the sum of the assigned powers. In this paper, we consider the dual power assignment problem, in which each wireless node is assigned a high- or low-power level, so that the induced graph is strongly connected and the cost of the assignment is minimized. We improve the best known approximation ratio from π 2 6 − 1 36 + ϵ ≈ 1.617 to 11 7 ≈ 1.571 . Moreover, we show that the algorithm of Khuller et al. [11] for the strongly connected spanning subgraph problem, which achieves an approximation ratio of 1.617, is 1.522-approximation algorithm for symmetric directed graphs. The innovation of this paper is in achieving these results by using interesting conditions for the existence of a second Hamiltonian cycle. [ABSTRACT FROM AUTHOR]

A complete weighted graph G = ( V , E , w ) is called Δ β -metric, for some β ≥ 1 / 2 , if G satisfies the β -triangle inequality, i.e., w ( u , v ) ≤ β ⋅ ( w ( u , x ) + w ( x , v ) ) for all vertices u , v , x ∈ V . Given a Δ β -metric graph G = ( V , E , w ) and a center c ∈ V , and an integer p , the Δ β -Star p -Hub Center problem ( Δ β -S p HCP) is to find a depth-2 spanning tree T of G rooted at c such that c has exactly p children (also called hubs) and the diameter of T is minimized. In this paper, we study Δ β -S p HCP for all β ≥ 1 2 . We show that for any ϵ > 0 , to approximate the Δ β -S p HCP to a ratio g ( β ) − ϵ is NP-hard and give r ( β ) -approximation algorithms for the same problem where g ( β ) and r ( β ) are functions of β . A subclass of metric graphs is identified that Δ β -S p HCP is polynomial-time solvable. Moreover, some r ( β ) -approximation algorithms given in this paper meet approximation lower bounds. [ABSTRACT FROM AUTHOR]

The maximum parsimony distance d MP (T 1 , T 2) and the bounded-state maximum parsimony distance d MP t (T 1 , T 2) measure the difference between two phylogenetic trees T 1 , T 2 in terms of the maximum difference between their parsimony scores for any character (with t a bound on the number of states in the character, in the case of d MP t (T 1 , T 2)). While computing d MP (T 1 , T 2) was previously shown to be fixed-parameter tractable with a linear kernel, no such result was known for d MP t (T 1 , T 2). In this paper, we prove that computing d MP t (T 1 , T 2) is fixed-parameter tractable for all t. Specifically, we prove that this problem has a kernel of size O (k lg ⁡ k) , where k = d MP t (T 1 , T 2). As the primary analysis tool, we introduce the concept of leg-disjoint incompatible quartets, which may be of independent interest. [ABSTRACT FROM AUTHOR]

In their 2006 seminal paper in Distributed Computing, Angluin et al. present a construction that, given any Presburger predicate, outputs a leaderless population protocol that decides the predicate. The protocol for a predicate of size m runs in O (m ⋅ n 2 log ⁡ n) expected number of interactions, which is almost optimal in n , the number of interacting agents. However, the number of states is exponential in m. Blondin et al. presented at STACS 2020 another construction that produces protocols with a polynomial number of states, but exponential expected number of interactions. We present a construction that produces protocols with O (m) states that run in expected O (m 7 ⋅ n 2) interactions, optimal in n , for all inputs of size Ω (m). For this, we introduce population computers, a generalization of population protocols, and show that our computers for Presburger predicates can be translated into fast and succinct population protocols. [ABSTRACT FROM AUTHOR]

This paper studies the relationship between undirected (unrooted) and directed (rooted) phylogenetic networks. We describe a polynomial-time algorithm for deciding whether an undirected nonbinary phylogenetic network, given the locations of the root and reticulation vertices, can be oriented as a directed nonbinary phylogenetic network. Moreover, we characterize when this is possible and show that, in such instances, the resulting directed nonbinary phylogenetic network is unique. In addition, without being given the location of the root and the reticulation vertices, we describe an algorithm for deciding whether an undirected binary phylogenetic network N can be oriented as a directed binary phylogenetic network of a certain class. The algorithm is fixed-parameter tractable (FPT) when the parameter is the level of N and is applicable to classes of directed phylogenetic networks that satisfy certain conditions. As an example, we show that the well-studied class of binary tree-child networks satisfies these conditions. [ABSTRACT FROM AUTHOR]

Given a connected graph G and a non-negative integer g , the g-extra connectivity κ g ( G ) of G is the minimum cardinality of a set of vertices in G , if it exists, whose deletion disconnects G and leaves each remaining component with more than g vertices. This paper focuses on the g -extra connectivity of hypercube-like networks (HL-networks for short). All the known results suggest the equality κ g ( X n ) = f n ( g ) holds, where X n is an n -dimensional HL-network, f n ( g ) = n ( g + 1 ) − g ( g + 3 ) 2 , n ≥ 5 and 0 ≤ g ≤ n − 3 . However, in this paper, we show that this equality does not hold in general. We also prove that κ g ( X n ) ≥ f n ( g ) holds for n ≥ 5 and 0 ≤ g ≤ n − 3 . This enables us to give a sufficient condition for the equality κ g ( X n ) = f n ( g ) , which is then used to determine the g -extra connectivity of HL-networks for some small g or the g -extra connectivity of some particular subfamily of HL-networks. [ABSTRACT FROM AUTHOR]

We study clustering problems such as k -Median, k -Means, and Facility Location in graphs of low highway dimension, which is a graph parameter modeling transportation networks. It was previously shown that approximation schemes for these problems exist, which either run in quasi-polynomial time (assuming constant highway dimension) (Feldmann et al., 2018) [8] or run in FPT time (parameterized by the number of clusters k , the highway dimension, and the approximation factor) (Becker et al., 2018; Braverman et al., 2021) [9,10]. In this paper we show that a polynomial-time approximation scheme (PTAS) exists (assuming constant highway dimension). We also show that the considered problems are NP-hard on graphs of highway dimension 1. [ABSTRACT FROM AUTHOR]

In a proxy re-signature scheme, a semi-trusted proxy can convert Alice's (also called as delegatee's) signature into Bob's (also called as delegator's) signature on the same message. However, the proxy itself cannot produce any signatures on behalf of either Alice or Bob. There exists some unidirectional one-use and multi-use (a message can be re-signed a polynomial number of times) proxy re-signature schemes. In some scenarios of big data, it is required to design unidirectional infinite-use (a message can be re-signed infinite number of times) proxy re-signature schemes. In this paper, we propose the first unidirectional infinite-use proxy re-signature scheme and identity-based unidirectional infinite-use proxy re-signature scheme with private re-signature keys based on lattice and prove that they are secure in the random oracle model. [ABSTRACT FROM AUTHOR]

The parity argument principle states that every finite graph has an even number of odd degree vertices. We consider the problem whose totality is guaranteed by the parity argument on a graph with potential. In this paper, we show that the problem of finding an unknown odd-degree vertex or a local optimum vertex on a graph with potential is polynomially equivalent to EndOfPotentialLine if the maximum degree is at most three. However, even if the maximum degree is 4, such a problem is PPA ∩ PLS -complete. To show the complexity of this problem, we provide new results on multiple-source variants of EndOfPotentialLine , which is the canonical problem for EOPL. This result extends the work by Goldberg and Hollender; they studied similar variants of EndOfLine. [ABSTRACT FROM AUTHOR]

We study multiplayer reachability games played on a finite directed graph equipped with target sets, one for each player. In those reachability games, it is known that there always exists a Nash equilibrium. But sometimes several equilibria may coexist. For instance we can have two equilibria: a first one where no player reaches his target set and an other one where all the players reach their target set. It is thus very natural to identify "relevant" equilibria. In this paper, we consider different notions of relevant Nash equilibria including Pareto optimal equilibria and equilibria with high social welfare. We also study relevant subgame perfect equilibria in reachability games. We provide complexity results for various related decision problems for both Nash equilibria and subgame perfect equilibria. [ABSTRACT FROM AUTHOR]

In a recent paper, the authors introduced the notion of sample width for binary classifiers defined on the set of real numbers. It was shown that the performance of such classifiers could be quantified in terms of this sample width. This paper considers how to adapt the idea of sample width so that it can be applied in cases where the classifiers are multi-category and are defined on some arbitrary metric space. [ABSTRACT FROM AUTHOR]

The definition of a support for multi-attribute range queries is mandatory for highly distributed systems. Even if several solutions have been proposed in the last decade, most of them do not meet the requirements of recent platforms, like IoT or smart cities. The paper presents an approach that builds a multidimensional Voronoi graph by exploiting the attributes of the objects published by a node. Our solution overcomes the curse of dimensionality issue affecting Voronoi Tessellations in high dimensional spaces by defining a Voronoi hierarchy. The paper formally defines the structure, analysis the complexity of the operations and presents experimental results. [ABSTRACT FROM AUTHOR]

The expensive cost and intermittent availability of renewable energy bring great challenges to its efficient utilization in green data centers. In this paper, we propose a new way to achieve an explicit trade-off between operational cost and carbon emission by dynamic storing off-site renewable energy in distributed data centers. We first formulate a constrained stochastic optimization problem for cost minimization of data centers. Then, by leveraging Lyapunov optimization theory, we design an online Carbon Capped Cost Minimization algorithm (CCCM) to achieve a near-optimal cost with rigorous mathematical proof. Specially, the decisions at each time slot are determined with an efficient iterative algorithm based on the Generalized Benders Decomposition (GBD) technique. Finally, extensive simulations are conducted to show the effectiveness of our algorithm. The results show that our algorithm can save about 6% total costs compared with the algorithm without offsite energy storage. [ABSTRACT FROM AUTHOR]

In this paper we characterize normal sequences and finite-state dimension in terms of the automatic Kolmogorov complexity and finite-state a priori probability. We show that many known results about normal sequences and finite-state dimension, including the equivalence between aligned and non-aligned normality, Wall's theorem, Piatetski–Shapiro's theorem, Champernowne's example of normal number and its modifications, equivalences between different definitions of finite-state dimension, Agafonov's and Schnorr's results about finite-state selection rules, become easy corollaries of this characterization. For that we use notions of automatic (finite-state) complexity and finite-state a priori probability that are the natural counterparts of the notions of Kolmogorov complexity and Solomonoff–Levin a priori probability in the algorithmic information theory. We also give a machine-independent characterization of normality and finite-state dimension in terms of superadditive calibrated functions. We compare our approach with previous results and notions relating finite automata and complexity. [ABSTRACT FROM AUTHOR]