Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userInapproximability of Diameter in super-linear time: Beyond the 5/3 ratio
136
0
0.0
(
0
)
Added by
\\'Edouard Bonnet
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Authors
Edouard Bonnet
Ask ChatGPT about the research
No Arabic abstract
We show, assuming the Strong Exponential Time Hypothesis, that for every $varepsilon > 0$, approximating directed Diameter on $m$-arc graphs within ratio $7/4 - varepsilon$ requires $m^{4/3 - o(1)}$ time. Our construction uses nonnegative edge weights but even holds for sparse digraphs, i.e., for which the number of vertices $n$ and the number of arcs $m$ satisfy $m = n log^{O(1)} n$. This is the first result that conditionally rules out a near-linear time $5/3$-approximation for Diameter.
rate research
Read More
We show, assuming the Strong Exponential Time Hypothesis, that for every $varepsilon > 0$, approximating undirected unweighted Diameter on $n$-vertex $n^{1+o(1)}$-edge graphs within ratio $7/4 - varepsilon$ requires $m^{4/3 - o(1)}$ time. This is the first result that conditionally rules out a near-linear time $5/3$-approximation for undirected Diameter.
The problem of finding a common refinement of a set of rooted trees with common leaf set $L$ appears naturally in mathematical phylogenetics whenever poorly resolved information on the same taxa from different sources is to be reconciled. This constitutes a special case of the well-studied supertree problem, where the leaf sets of the input trees may differ. Algorithms that solve the rooted tree compatibility problem are of course applicable to this special case. However, they require sophisticated auxiliary data structures and have a running time of at least $O(k|L|log^2(k|L|))$ for $k$ input trees. Here, we show that the problem can be solved in $O(k|L|)$ time using a simple bottom-up algorithm called LinCR. An implementation of LinCR in Python is freely available at https://github.com/david-schaller/tralda.
Multidimensional packing problems generalize the classical packing problems such as Bin Packing, Multiprocessor Scheduling by allowing the jobs to be $d$-dimensional vectors. While the approximability of the scalar problems is well understood, there has been a significant gap between the approximation algorithms and the hardness results for the multidimensional variants. In this paper, we close this gap by giving almost tight hardness results for these problems. 1. We show that Vector Bin Packing has no polynomial time $Omega( log d)$ factor asymptotic approximation algorithm when $d$ is a large constant, assuming $textsf{P} eq textsf{NP}$. This matches the $ln d + O(1)$ factor approximation algorithms (Chekuri, Khanna SICOMP 2004, Bansal, Caprara, Sviridenko SICOMP 2009, Bansal, Eli{a}s, Khan SODA 2016) upto constants. 2. We show that Vector Scheduling has no polynomial time algorithm with an approximation ratio of $Omegaleft( (log d)^{1-epsilon}right)$ when $d$ is part of the input, assuming $textsf{NP} subseteq textsf{ZPTIME}left( n^{(log n)^{O(1)}}right)$. This almost matches the $Oleft( frac{log d}{log log d}right)$ factor algorithms(Harris, Srinivasan JACM 2019, Im, Kell, Kulkarni, Panigrahi SICOMP 2019). We also show that the problem is NP-hard to approximate within $(log log d)^{omega(1)}$. 3. We show that Vector Bin Covering is NP-hard to approximate within $Omegaleft( frac{log d}{log log d}right)$ when $d$ is part of the input, almost matching the $O(log d)$ factor algorithm (Alon et al., Algorithmica 1998). Previously, no hardness results that grow with $d$ were known for Vector Scheduling and Vector Bin Covering when $d$ is part of the input and for Vector Bin Packing when $d$ is a fixed constant.
A natural way of increasing our understanding of NP-complete graph problems is to restrict the input to a special graph class. Classes of $H$-free graphs, that is, graphs that do not contain some graph $H$ as an induced subgraph, have proven to be an ideal testbed for such a complexity study. However, if the forbidden graph $H$ contains a cycle or claw, then these problems often stay NP-complete. A recent complexity study on the $k$-Colouring problem shows that we may still obtain tractable results if we also bound the diameter of the $H$-free input graph. We continue this line of research by initiating a complexity study on the impact of bounding the diameter for a variety of classical vertex partitioning problems restricted to $H$-free graphs. We prove that bounding the diameter does not help for Independent Set, but leads to new tractable cases for problems closely related to 3-Colouring. That is, we show that Near-Bipartiteness, Independent Feedback Vertex Set, Independent Odd Cycle Transversal, Acyclic 3-Colouring and Star 3-Colouring are all polynomial-time solvable for chair-free graphs of bounded diameter. To obtain these results we exploit a new structural property of 3-colourable chair-free graphs.
We examine the effect of bounding the diameter for well-studied variants of the Colouring problem. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. The corresponding decision problems are Acyclic Colouring, Star Colouring and Injective Colouring. The last problem is also known as $L(1,1)$-Labelling and we also consider the framework of $L(a,b)$-Labelling. We prove a number of (almost-)complete complexity classifications. In particular, we show that for graphs of diameter at most $d$, Acyclic $3$-Colouring is polynomial-time solvable if $dleq 2$ but NP-complete if $dgeq 4$, and Star $3$-Colouring is polynomial-time solvable if $dleq 3$ but NP-complete for $dgeq 8$. As far as we are aware, Star $3$-Colouring is the first problem that exhibits a complexity jump for some $dgeq 3$. Our third main result is that $L(1,2)$-Labelling is NP-complete for graphs of diameter $2$; we relate the latter problem to a special case of Hamiltonian Path.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
