Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTowards Better Approximation of Graph Crossing Number
78
0
0.0
(
0
)
Added by
Zihan Tan
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Graph Crossing Number is a fundamental problem with various applications. In this problem, the goal is to draw an input graph $G$ in the plane so as to minimize the number of crossings between the images of its edges. Despite extensive work, non-trivial approximation algorithms are only known for bounded-degree graphs. Even for this special case, the best current algorithm achieves a $tilde O(sqrt n)$-approximation, while the best current negative result is APX-hardness. All current approximation algorithms for the problem build on the same paradigm: compute a set $E$ of edges (called a emph{planarizing set}) such that $Gsetminus E$ is planar; compute a planar drawing of $Gsetminus E$; then add the drawings of the edges of $E$ to the resulting drawing. Unfortunately, there are examples of graphs, in which any implementation of this method must incur $Omega (text{OPT}^2)$ crossings, where $text{OPT}$ is the value of the optimal solution. This barrier seems to doom the only known approach to designing approximation algorithms for the problem, and to prevent it from yielding a better than $O(sqrt n)$-approximation. In this paper we propose a new paradigm that allows us to overcome this barrier. We show an algorithm that, given a bounded-degree graph $G$ and a planarizing set $E$ of its edges, computes another set $E$ with $Esubseteq E$, such that $|E|$ is relatively small, and there exists a near-optimal drawing of $G$ in which only edges of $E$ participate in crossings. This allows us to reduce the Crossing Number problem to emph{Crossing Number with Rotation System} -- a variant in which the ordering of the edges incident to every vertex is fixed as part of input. We show a randomized algorithm for this new problem, that allows us to obtain an $O(n^{1/2-epsilon})$-approximation for Crossing Number on bounded-degree graphs, for some constant $epsilon>0$.
rate research
Read More
Given an n-vertex graph G, a drawing of G in the plane is a mapping of its vertices into points of the plane, and its edges into continuous curves, connecting the images of their endpoints. A crossing in such a drawing is a point where two such curves intersect. In the Minimum Crossing Number problem, the goal is to find a drawing of G with minimum number of crossings. The value of the optimal solution, denoted by OPT, is called the graphs crossing number. This is a very basic problem in topological graph theory, that has received a significant amount of attention, but is still poorly understood algorithmically. The best currently known efficient algorithm produces drawings with $O(log^2 n)(n + OPT)$ crossings on bounded-degree graphs, while only a constant factor hardness of approximation is known. A closely related problem is Minimum Edge Planarization, in which the goal is to remove a minimum-cardinality subset of edges from G, such that the remaining graph is planar. Our main technical result establishes the following connection between the two problems: if we are given a solution of cost k to the Minimum Edge Planarization problem on graph G, then we can efficiently find a drawing of G with at most $poly(d)cdot kcdot (k+OPT)$ crossings, where $d$ is the maximum degree in G. This result implies an $O(ncdot poly(d)cdot log^{3/2}n)$-approximation for Minimum Crossing Number, as well as improved algorithms for special cases of the problem, such as, for example, k-apex and bounded-genus graphs.
Among the most important graph parameters is the Diameter, the largest distance between any two vertices. There are no known very efficient algorithms for computing the Diameter exactly. Thus, much research has been devoted to how fast this parameter can be approximated. Chechik et al. showed that the diameter can be approximated within a multiplicative factor of $3/2$ in $tilde{O}(m^{3/2})$ time. Furthermore, Roditty and Vassilevska W. showed that unless the Strong Exponential Time Hypothesis (SETH) fails, no $O(n^{2-epsilon})$ time algorithm can achieve an approximation factor better than $3/2$ in sparse graphs. Thus the above algorithm is essentially optimal for sparse graphs for approximation factors less than $3/2$. It was, however, completely plausible that a $3/2$-approximation is possible in linear time. In this work we conditionally rule out such a possibility by showing that unless SETH fails no $O(m^{3/2-epsilon})$ time algorithm can achieve an approximation factor better than $5/3$. Another fundamental set of graph parameters are the Eccentricities. The Eccentricity of a vertex $v$ is the distance between $v$ and the farthest vertex from $v$. Chechik et al. showed that the Eccentricities of all vertices can be approximated within a factor of $5/3$ in $tilde{O}(m^{3/2})$ time and Abboud et al. showed that no $O(n^{2-epsilon})$ algorithm can achieve better than $5/3$ approximation in sparse graphs. We show that the runtime of the $5/3$ approximation algorithm is also optimal under SETH. We also show that no near-linear time algorithm can achieve a better than $2$ approximation for the Eccentricities and that this is essentially tight: we give an algorithm that approximates Eccentricities within a $2+delta$ factor in $tilde{O}(m/delta)$ time for any $0<delta<1$. This beats all Eccentricity algorithms in Cairo et al.
In this paper, we consider the colorful $k$-center problem, which is a generalization of the well-known $k$-center problem. Here, we are given red and blue points in a metric space, and a coverage requirement for each color. The goal is to find the smallest radius $rho$, such that with $k$ balls of radius $rho$, the desired number of points of each color can be covered. We obtain a constant approximation for this problem in the Euclidean plane. We obtain this result by combining a pseudo-approximation algorithm that works in any metric space, and an approximation algorithm that works for a special class of instances in the plane. The latter algorithm uses a novel connection to a certain matching problem in graphs.
Readability criteria, such as distance or neighborhood preservation, are often used to optimize node-link representations of graphs to enable the comprehension of the underlying data. With few exceptions, graph drawing algorithms typically optimize one such criterion, usually at the expense of others. We propose a layout approach, Graph Drawing via Gradient Descent, $(GD)^2$, that can handle multiple readability criteria. $(GD)^2$ can optimize any criterion that can be described by a smooth function. If the criterion cannot be captured by a smooth function, a non-smooth function for the criterion is combined with another smooth function, or auto-differentiation tools are used for the optimization. Our approach is flexible and can be used to optimize several criteria that have already been considered earlier (e.g., obtaining ideal edge lengths, stress, neighborhood preservation) as well as other criteria which have not yet been explicitly optimized in such fashion (e.g., vertex resolution, angular resolution, aspect ratio). We provide quantitative and qualitative evidence of the effectiveness of $(GD)^2$ with experimental data and a functional prototype: url{http://hdc.cs.arizona.edu/~mwli/graph-drawing/}.
Lokshtanov et al.~[STOC 2017] introduced emph{lossy kernelization} as a mathematical framework for quantifying the effectiveness of preprocessing algorithms in preserving approximation ratios. emph{$alpha$-approximate reduction rules} are a central notion of this framework. We propose that carefully crafted $alpha$-approximate reduction rules can yield improved approximation ratios in practice, while being easy to implement as well. This is distinctly different from the (theoretical) purpose for which Lokshtanov et al. designed $alpha$-approximate Reduction Rules. As evidence in support of this proposal we present a new 2-approximate reduction rule for the textsc{Dominating Set} problem. This rule, when combined with an approximation algorithm for textsc{Dominating Set}, yields significantly better approximation ratios on a variety of benchmark instances as compared to the latter algorithm alone. The central thesis of this work is that $alpha$-approximate reduction rules can be used as a tool for designing approximation algorithms which perform better in practice. To the best of our knowledge, ours is the first exploration of the use of $alpha$-approximate reduction rules as a design technique for practical approximation algorithms. We believe that this technique could be useful in coming up with improved approximation algorithms for other optimization problems as well.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
