Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userApproximating MIS over equilateral $B_1$-VPG graphs
87
0
0.0
(
0
)
Added by
C R Subramanian
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We present an approximation algorithm for the maximum independent set (MIS) problem over the class of equilateral $B_1$-VPG graphs. These are intersection graphs of $L$-shaped planar objects % (and their rotations by multiples of $90^o$) with both arms of each object being equal. We obtain a $36(log 2d)$-approximate algorithm running in $O(n(log n)^2)$ time for this problem, where $d$ is the ratio $d_{max}/d_{min}$ and $d_{max}$ and $d_{min}$ denote respectively the maximum and minimum length of any arm in the input equilateral $L$-representation of the graph. In particular, we obtain $O(1)$-factor approximation of MIS for $B_1$-VPG -graphs for which the ratio $d$ is bounded by a constant. % formed by unit length $L$-shapes. In fact, algorithm can be generalized to an $O(n(log n)^2)$ time and a $36(log 2d_x)(log 2d_y)$-approximate MIS algorithm over arbitrary $B_1$-VPG graphs. Here, $d_x$ and $d_y$ denote respectively the analogues of $d$ when restricted to only horizontal and vertical arms of members of the input. This is an improvement over the previously best $n^epsilon$-approximate algorithm cite{FoxP} (for some fixed $epsilon>0$), unless the ratio $d$ is exponentially large in $n$. In particular, $O(1)$-approximation of MIS is achieved for graphs with $max{d_x,d_y}=O(1)$.
rate research
Read More
We study the problem of finding a minimum weight connected subgraph spanning at least $k$ vertices on planar, node-weighted graphs. We give a $(4+eps)$-approximation algorithm for this problem. We achieve this by utilizing the recent LMP primal-dual $3$-approximation for the node-weighted prize-collecting Steiner tree problem by Byrka et al (SWAT16) and adopting an approach by Chudak et al. (Math. Prog. 04) regarding Lagrangian relaxation for the edge-weighted variant. In particular, we improve the procedure of picking additional vertices (tree merging procedure) given by Sadeghian (2013) by taking a constant number of recursive steps and utilizing the limited guessing procedure of Arora and Karakostas (Math. Prog. 06). More generally, our approach readily gives a $( icefrac{4}{3}cdot r+eps)$-approximation on any graph class where the algorithm of Byrka et al. for the prize-collecting version gives an $r$-approximation. We argue that this can be interpreted as a generalization of an analogous result by Konemann et al. (Algorithmica~11) for partial cover problems. Together with a lower bound construction by Mestre (STACS08) for partial cover this implies that our bound is essentially best possible among algorithms that utilize an LMP algorithm for the Lagrangian relaxation as a black box. In addition to that, we argue by a more involved lower bound construction that even using the LMP algorithm by Byrka et al. in a emph{non-black-box} fashion could not beat the factor $ icefrac{4}{3}cdot r$ when the tree merging step relies only on the solutions output by the LMP algorithm.
We study the design of schedules for multi-commodity multicast; we are given an undirected graph $G$ and a collection of source destination pairs, and the goal is to schedule a minimum-length sequence of matchings that connects every source with its respective destination. Multi-commodity multicast models a classic information dissemination problem in networks where the primary communication constraint is the number of connections that a node can make, not link bandwidth. Multi-commodity multicast is closely related to the problem of finding a subgraph, $H$, of optimal poise, where the poise is defined as the sum of the maximum degree of $H$ and the maximum distance between any source-destination pair in $H$. We first show that the minimum poise subgraph for single-commodity multicast can be approximated to within a factor of $O(log k)$ with respect to the value of a natural LP relaxation in an instance with $k$ terminals. This is the first upper bound on the integrality gap of the natural LP. Using this poise result and shortest-path separators in planar graphs, we obtain a $O(log^3 klog n/(loglog n))$-approximation for multi-commodity multicast for planar graphs. We also study the minimum-time radio gossip problem in planar graphs where a message from each node must be transmitted to all other nodes under a model where nodes can broadcast to all neighbors in a single step but only nodes with a single broadcasting neighbor get a message. We give an $O(log^2 n)$-approximation for radio gossip in planar graphs breaking previous barriers. This is the first bound for radio gossip that does not rely on the maximum degree of the graph. Finally, we show that our techniques for planar graphs extend to graphs with excluded minors. We establish polylogarithmic-approximation algorithms for both multi-commodity multicast and radio gossip problems in minor-free graphs.
The girth of a graph, i.e. the length of its shortest cycle, is a fundamental graph parameter. Unfortunately all known algorithms for computing, even approximately, the girth and girth-related structures in directed weighted $m$-edge and $n$-node graphs require $Omega(min{n^{omega}, mn})$ time (for $2leqomega<2.373$). In this paper, we drastically improve these runtimes as follows: * Multiplicative Approximations in Nearly Linear Time: We give an algorithm that in $widetilde{O}(m)$ time computes an $widetilde{O}(1)$-multiplicative approximation of the girth as well as an $widetilde{O}(1)$-multiplicative roundtrip spanner with $widetilde{O}(n)$ edges with high probability (w.h.p). * Nearly Tight Additive Approximations: For unweighted graphs and any $alpha in (0,1)$ we give an algorithm that in $widetilde{O}(mn^{1 - alpha})$ time computes an $O(n^alpha)$-additive approximation of the girth w.h.p, and partially derandomize it. We show that the runtime of our algorithm cannot be significantly improved without a breakthrough in combinatorial Boolean matrix multiplication. Our main technical contribution to achieve these results is the first nearly linear time algorithm for computing roundtrip covers, a directed graph decomposition concept key to previous roundtrip spanner constructions. Previously it was not known how to compute these significantly faster than $Omega(min{n^omega, mn})$ time. Given the traditional difficulty in efficiently processing directed graphs, we hope our techniques may find further applications.
A piecewise linear curve in the plane made up of $k+1$ line segments, each of which is either horizontal or vertical, with consecutive segments being of different orientation is called a $k$-bend path. Given a graph $G$, a collection of $k$-bend paths in which each path corresponds to a vertex in $G$ and two paths have a common point if and only if the vertices corresponding to them are adjacent in $G$ is called a $B_k$-VPG representation of $G$. Similarly, a collection of $k$-bend paths each of which corresponds to a vertex in $G$ is called an $B_k$-EPG representation of $G$ if any two paths have a line segment of non-zero length in common if and only if their corresponding vertices are adjacent in $G$. The VPG bend-number $b_v(G)$ of a graph $G$ is the minimum $k$ such that $G$ has a $B_k$-VPG representation. Similarly, the EPG bend-number $b_e(G)$ of a graph $G$ is the minimum $k$ such that $G$ has a $B_k$-EPG representation. Halin graphs are the graphs formed by taking a tree with no degree $2$ vertex and then connecting its leaves to form a cycle in such a way that the graph has a planar embedding. We prove that if $G$ is a Halin graph then $b_v(G) leq 1$ and $b_e(G) leq 2$. These bounds are tight. In fact, we prove the stronger result that if $G$ is a planar graph formed by connecting the leaves of any tree to form a simple cycle, then it has a VPG-representation using only one type of 1-bend paths and an EPG-representation using only one type of 2-bend paths.
We revisit Min-Mean-Cycle, the classical problem of finding a cycle in a weighted directed graph with minimum mean weight. Despite an extensive algorithmic literature, previous work falls short of a near-linear runtime in the number of edges $m$--in fact, there is a natural barrier which precludes such a runtime for solving Min-Mean-Cycle exactly. Here, we give a much faster approximation algorithm that, for graphs with polylogarithmic diameter, has near-linear runtime. In particular, this is the first algorithm whose runtime for the complete graph scales in the number of vertices $n$ as $tilde{O}(n^2)$. Moreover--unconditionally on the diameter--the algorithm uses only $O(n)$ memory beyond reading the input, making it memory-optimal. The algorithm is also simple to implement and has remarkable practical performance. Our approach is based on solving a linear programming (LP) relaxation using entropic regularization, which effectively reduces the LP to a Matrix Balancing problem--a la the popular reduction of Optimal Transport to Matrix Scaling. We then round the fractional LP solution using a variant of the classical Cycle-Cancelling algorithm that is sped up to near-linear runtime at the expense of being approximate, and implemented in a memory-optimal manner. We also provide an alternative algorithm with slightly faster theoretical runtime, albeit worse memory usage and practicality. This algorithm uses the same rounding procedure, but solves the LP relaxation by leveraging recent developments in area-convexity regularization. Its runtime scales inversely in the approximation accuracy, which we show is optimal--barring a major breakthrough in algorithmic graph theory, namely faster Shortest Paths algorithms.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
