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]

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]

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]

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]

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 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]

The goal of this paper is to open up a new research direction aimed at understanding the power of preprocessing in speeding up algorithms that solve NP-hard problems exactly. We explore this direction for the classic Feedback Vertex Set problem on undirected graphs, leading to a new type of graph structure called antler decomposition , which identifies vertices that belong to an optimal solution. It is an analogue of the celebrated crown decomposition which has been used for Vertex Cover. We develop the graph structure theory around such decompositions and develop fixed-parameter tractable algorithms to find them, parameterized by the number of vertices for which they witness presence in an optimal solution. This reduces the search space of fixed-parameter tractable algorithms parameterized by the solution size that solve Feedback Vertex Set. [ABSTRACT FROM AUTHOR]

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

In this paper, we investigate the structure of the most general kind of substitution shifts, including non-minimal ones, and allowing erasing morphisms. We prove the decidability of many properties of these morphisms with respect to the shift space generated by iteration, such as aperiodicity, recognizability and (under an additional assumption) irreducibility, or minimality. [ABSTRACT FROM AUTHOR]

A set M of vertices of a graph G is a distance-edge-monitoring set if for every edge e ∈ G , there is a vertex x ∈ M and a vertex y ∈ G such that e belongs to all shortest paths between x and y. We denote by dem (G) the smallest size of such a set in G. In this paper, we prove that dem (G) ≤ n − ⌊ g (G) / 2 ⌋ for any connected graph G , which is not a tree, of order n , where g (G) is the length of a shortest cycle in G , and give the graphs with dem (G) = n − ⌊ g (G) / 2 ⌋. We also obtain that | V (G) | ≥ k + ⌊ g (G) / 2 ⌋ for every connected graph G with dem (G) = k and g (G) = g. Furthermore, the lower bound holds if and only if g = 3 and k = n − 1 or g = 4 and k = 2. We prove that dem (G) ≤ 2 n / 5 for g (G) ≥ 5. [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]

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]

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 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]

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]

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]