The greedy spanner in a low dimensional Euclidean space is a fundamental geometric construction that has been extensively studied over three decades as it possesses the two most basic properties of a good spanner: constant maximum degree and constant lightness. Recently, Eppstein and Khodabandeh showed that the greedy spanner in $\mathbb{R}^2$ admits a sublinear separator in a strong sense: any subgraph of $k$ vertices of the greedy spanner in $\mathbb{R}^2$ has a separator of size $O(\sqrt{k})$. Their technique is inherently planar and is not extensible to higher dimensions. They left showing the existence of a small separator for the greedy spanner in $\mathbb{R}^d$ for any constant $d\geq 3$ as an open problem. In this paper, we resolve the problem of Eppstein and Khodabandeh by showing that any subgraph of $k$ vertices of the greedy spanner in $\mathbb{R}^d$ has a separator of size $O(k^{1-1/d})$. We introduce a new technique that gives a simple characterization for any geometric graph to have a sublinear separator that we dub $\tau$-lanky: a geometric graph is $\tau$-lanky if any ball of radius $r$ cuts at most $\tau$ edges of length at least $r$ in the graph. We show that any $\tau$-lanky geometric graph of $n$ vertices in $\mathbb{R}^d$ has a separator of size $O(\tau n^{1-1/d})$. We then derive our main result by showing that the greedy spanner is $O(1)$-lanky. We indeed obtain a more general result that applies to unit ball graphs and point sets of low fractal dimensions in $\mathbb{R}^d$. Our technique naturally extends to doubling metrics. We use the $\tau$-lanky characterization to show that there exists a $(1+\epsilon)$-spanner for doubling metrics of dimension $d$ with a constant maximum degree and a separator of size $O(n^{1-\frac{1}{d}})$; this result resolves an open problem posed by Abam and Har-Peled a decade ago.
相關內容
In this work, we study functions that can be obtained by restricting a vectorial Boolean function $F \colon \mathbb{F}_2^n \rightarrow \mathbb{F}_2^n$ to an affine hyperplane of dimension $n-1$ and then projecting the output to an $n-1$-dimensional space. We show that a multiset of $2 \cdot (2^n-1)^2$ EA-equivalence classes of such restrictions defines an EA-invariant for vectorial Boolean functions on $\mathbb{F}_2^n$. Further, for all of the known quadratic APN functions in dimension $n < 10$, we determine the restrictions that are also APN. Moreover, we construct 6,368 new quadratic APN functions in dimension eight up to EA-equivalence by extending a quadratic APN function in dimension seven. A special focus of this work is on quadratic APN functions with maximum linearity. In particular, we characterize a quadratic APN function $F \colon \mathbb{F}_2^n \rightarrow \mathbb{F}_2^n$ with linearity of $2^{n-1}$ by a property of the ortho-derivative of its restriction to a linear hyperplane. Using the fact that all quadratic APN functions in dimension seven are classified, we are able to obtain a classification of all quadratic 8-bit APN functions with linearity $2^7$ up to EA-equivalence.
In this paper we show that every graph of pathwidth less than $k$ that has a path of order $n$ also has an induced path of order at least $\frac{1}{3} n^{1/k}$. This is an exponential improvement and a generalization of the polylogarithmic bounds obtained by Esperet, Lemoine and Maffray (2016) for interval graphs of bounded clique number. We complement this result with an upper-bound. This result is then used to prove the two following generalizations: - every graph of treewidth less than $k$ that has a path of order $n$ contains an induced path of order at least $\frac{1}{4} (\log n)^{1/k}$; - for every non-trivial graph class that is closed under topological minors there is a constant $d \in (0,1)$ such that every graph from this class that has a path of order $n$ contains an induced path of order at least $(\log n)^d$. We also describe consequences of these results beyond graph classes that are closed under topological minors.
In the Partial Vertex Cover (PVC) problem, we are given an $n$-vertex graph $G$ and a positive integer $k$, and the objective is to find a vertex subset $S$ of size $k$ maximizing the number of edges with at least one end-point in $S$. This problem is W[1]-hard on general graphs, but admits a parameterized subexponential time algorithm with running time $2^{O(\sqrt{k})}n^{O(1)}$ on planar and apex-minor free graphs [Fomin et al. (FSTTCS 2009, IPL 2011)], and a $k^{O(k)}n^{O(1)}$ time algorithm on bounded degeneracy graphs [Amini et al. (FSTTCS 2009, JCSS 2011)]. Graphs of bounded degeneracy contain many sparse graph classes like planar graphs, $H$-minor free graphs, and bounded tree-width graphs. In this work, we prove the following results: 1) There is an algorithm for PVC with running time $2^{O(k)}n^{O(1)}$ on graphs of bounded degeneracy which is an improvement on the previous $k^{O(k)}n^{O(1)}$ time algorithm by Amini et al. 2) PVC admits a polynomial compression on graphs of bounded degeneracy, resolving an open problem posed by Amini et al.
In the $(1+\varepsilon,r)$-approximate near-neighbor problem for curves (ANNC) under some distance measure $\delta$, the goal is to construct a data structure for a given set $\mathcal{C}$ of curves that supports approximate near-neighbor queries: Given a query curve $Q$, if there exists a curve $C\in\mathcal{C}$ such that $\delta(Q,C)\le r$, then return a curve $C'\in\mathcal{C}$ with $\delta(Q,C')\le(1+\varepsilon)r$. There exists an efficient reduction from the $(1+\varepsilon)$-approximate nearest-neighbor problem to ANNC, where in the former problem the answer to a query is a curve $C\in\mathcal{C}$ with $\delta(Q,C)\le(1+\varepsilon)\cdot\delta(Q,C^*)$, where $C^*$ is the curve of $\mathcal{C}$ closest to $Q$. Given a set $\mathcal{C}$ of $n$ curves, each consisting of $m$ points in $d$ dimensions, we construct a data structure for ANNC that uses $n\cdot O(\frac{1}{\varepsilon})^{md}$ storage space and has $O(md)$ query time (for a query curve of length $m$), where the similarity between two curves is their discrete Fr\'echet or dynamic time warping distance. Our method is simple to implement, deterministic, and results in an exponential improvement in both query time and storage space compared to all previous bounds. Further, we also consider the asymmetric version of ANNC, where the length of the query curves is $k \ll m$, and obtain essentially the same storage and query bounds as above, except that $m$ is replaced by $k$. Finally, we apply our method to a version of approximate range counting for curves and achieve similar bounds.
We introduce a natural knapsack intersection hierarchy for strengthening linear programming relaxations of packing integer programs, i.e., $\max\{w^Tx:x\in P\cap\{0,1\}^n\}$ where $P=\{x\in[0,1]^n:Ax \leq b\}$ and $A,b,w\ge0$. The $t^{th}$ level $P^{t}$ corresponds to adding cuts associated with the integer hull of the intersection of any $t$ knapsack constraints (rows of the constraint matrix). This model captures the maximum possible strength of "$t$-row cuts", an approach often used by solvers for small $t$. If $A$ is $m \times n$, then $P^m$ is the integer hull of $P$ and $P^1$ corresponds to adding cuts for each associated single-row knapsack problem. Thus, even separating over $P^1$ is NP-hard. However, for fixed $t$ and any $\epsilon>0$, results of Pritchard imply there is a polytime $(1+\epsilon)$-approximation for $P^{t}$. We then investigate the hierarchy's strength in the context of the well-studied all-or-nothing flow problem in trees (also called unsplittable flow on trees). For this problem, we show that the integrality gap of $P^t$ is $O(n/t)$ and give examples where the gap is $\Omega(n/t)$. We then examine the stronger formulation $P_{\text{rank}}$ where all rank constraints are added. For $P_{\text{rank}}^t$, our best lower bound drops to $\Omega(1/c)$ at level $t=n^c$ for any $c>0$. Moreover, on a well-known class of "bad instances" due to Friggstad and Gao, we show that we can achieve this gap; hence a constant integrality gap for these instances is obtained at level $n^c$.
The intersection graph induced by a set $\Disks$ of $n$ disks can be dense. It is thus natural to try and sparsify it, while preserving connectivity. Unfortunately, sparse graphs can always be made disconnected by removing a small number of vertices. In this work, we present a sparsification algorithm that maintains connectivity between two disks in the computed graph, if the original graph remains ``well-connected'' even after removing an arbitrary ``attack'' set $\BSet \subseteq \Disks$ from both graphs. Thus, the new sparse graph has similar reliability to the original disk graph, and can withstand catastrophic failure of nodes while still providing a connectivity guarantee for the remaining graph. The new graphs has near linear complexity, and can be constructed in near linear time. The algorithm extends to any collection of shapes in the plane, such that their union complexity is near linear.
A graph is called a sum graph if its vertices can be labelled by distinct positive integers such that there is an edge between two vertices if and only if the sum of their labels is the label of another vertex of the graph. Most papers on sum graphs consider combinatorial questions like the minimum number of isolated vertices that need to be added to a given graph to make it a sum graph. In this paper, we initiate the study of sum graphs from the viewpoint of computational complexity. Notice that every $n$-vertex sum graph can be represented by a sorted list of $n$ positive integers where edge queries can be answered in $O(\log n)$ time. Therefore, limiting the size of the vertex labels also upper-bounds the space complexity of storing the graph in the database. We show that every $n$-vertex, $m$-edge, $d$-degenerate graph can be made a sum graph by adding at most $m$ isolated vertices to it, such that the size of each vertex label is at most $O(n^2d)$. This enables us to store the graph using $O(m\log n)$ bits of memory. For sparse graphs (graphs with $O(n)$ edges), this matches the trivial lower bound of $\Omega(n\log n)$. Since planar graphs and forests have constant degeneracy, our result implies an upper bound of $O(n^2)$ on their label size. The previously best known upper bound on the label size of general graphs with the minimum number of isolated vertices was $O(4^n)$, due to Kratochv\'il, Miller & Nguyen. Furthermore, their proof was existential, whereas our labelling can be constructed in polynomial time.
$\newcommand{\Emph}[1]{{\it{#1}}} \newcommand{\FF}{\mathcal{F}}\newcommand{\region}{\mathsf{r}}\newcommand{\restrictY}[2]{#1 \cap {#2}}$For a set of points $P \subseteq \mathbb{R}^2$, and a family of regions $\FF$, a $\Emph{local~t-spanner}$ of $P$, is a sparse graph $G$ over $P$, such that, for any region $\region \in \FF$, the subgraph restricted to $\region$, denoted by $\restrictY{G}{\region} = G_{P \cap \region}$, is a $t$-spanner for all the points of $\region \cap P$. We present algorithms for the construction of local spanners with respect to several families of regions, such as homothets of a convex region. Unfortunately, the number of edges in the resulting graph depends logarithmically on the spread of the input point set. We prove that this dependency can not be removed, thus settling an open problem raised by Abam and Borouny. We also show improved constructions (with no dependency on the spread) of local spanners for fat triangles, and regular $k$-gons. In particular, this improves over the known construction for axis parallel squares. We also study a somewhat weaker notion of local spanner where one allows to shrink the region a "bit". Any spanner is a weak local spanner if the shrinking is proportional to the diameter. Surprisingly, we show a near linear size construction of a weak spanner for axis-parallel rectangles, where the shrinkage is $\Emph{multiplicative}$.
In Defective Coloring we are given a graph $G$ and two integers $\chi_d$, $\Delta^*$ and are asked if we can $\chi_d$-color $G$ so that the maximum degree induced by any color class is at most $\Delta^*$. We show that this natural generalization of Coloring is much harder on several basic graph classes. In particular, we show that it is NP-hard on split graphs, even when one of the two parameters $\chi_d$, $\Delta^*$ is set to the smallest possible fixed value that does not trivialize the problem ($\chi_d = 2$ or $\Delta^* = 1$). Together with a simple treewidth-based DP algorithm this completely determines the complexity of the problem also on chordal graphs. We then consider the case of cographs and show that, somewhat surprisingly, Defective Coloring turns out to be one of the few natural problems which are NP-hard on this class. We complement this negative result by showing that Defective Coloring is in P for cographs if either $\chi_d$ or $\Delta^*$ is fixed; that it is in P for trivially perfect graphs; and that it admits a sub-exponential time algorithm for cographs when both $\chi_d$ and $\Delta^*$ are unbounded.
In this paper, we study the optimal convergence rate for distributed convex optimization problems in networks. We model the communication restrictions imposed by the network as a set of affine constraints and provide optimal complexity bounds for four different setups, namely: the function $F(\xb) \triangleq \sum_{i=1}^{m}f_i(\xb)$ is strongly convex and smooth, either strongly convex or smooth or just convex. Our results show that Nesterov's accelerated gradient descent on the dual problem can be executed in a distributed manner and obtains the same optimal rates as in the centralized version of the problem (up to constant or logarithmic factors) with an additional cost related to the spectral gap of the interaction matrix. Finally, we discuss some extensions to the proposed setup such as proximal friendly functions, time-varying graphs, improvement of the condition numbers.
小貼士
登錄享
相關主題
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191