Search

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]

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]

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