Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHardness of Token Swapping on Trees
73
0
0.0
(
0
)
Added by
Jayson Lynch
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Given a graph where every vertex has exactly one labeled token, how can we most quickly execute a given permutation on the tokens? In (sequential) token swapping, the goal is to use the shortest possible sequence of swaps, each of which exchanges the tokens at the two endpoints of an edge of the graph. In parallel token swapping, the goal is to use the fewest rounds, each of which consists of one or more swaps on the edges of a matching. We prove that both of these problems remain NP-hard when the graph is restricted to be a tree. These token swapping problems have been studied by disparate groups of researchers in discrete mathematics, theoretical computer science, robot motion planning, game theory, and engineering. Previous work establishes NP-completeness on general graphs (for both problems); polynomial-time algorithms for simple graph classes such as cliques, stars, paths, and cycles; and constant-factor approximation algorithms in some cases. The two natural cases of sequential and parallel token swapping in trees were first studied over thirty years ago (as sorting with a transposition tree) and over twenty-five years ago (as routing permutations via matchings), yet their complexities were previously unknown. We also show limitations on approximation of sequential token swapping on trees: we identify a broad class of algorithms that encompass all three known polynomial-time algorithms that achieve the best known approximation factor (which is $2$) and show that no such algorithm can achieve an approximation factor less than $2$.
rate research
Read More
The problem of solving linear systems is one of the most fundamental problems in computer science, where given a satisfiable linear system $(A,b)$, for $A in mathbb{R}^{n times n}$ and $b in mathbb{R}^n$, we wish to find a vector $x in mathbb{R}^n$ such that $Ax = b$. The current best algorithms for solving dense linear systems reduce the problem to matrix multiplication, and run in time $O(n^{omega})$. We consider the problem of finding $varepsilon$-approximate solutions to linear systems with respect to the $L_2$-norm, that is, given a satisfiable linear system $(A in mathbb{R}^{n times n}, b in mathbb{R}^n)$, find an $x in mathbb{R}^n$ such that $||Ax - b||_2 leq varepsilon||b||_2$. Our main result is a fine-grained reduction from computing the rank of a matrix to finding $varepsilon$-approximate solutions to linear systems. In particular, if the best known $O(n^omega)$ time algorithm for computing the rank of $n times O(n)$ matrices is optimal (which we conjecture is true), then finding an $varepsilon$-approximate solution to a dense linear system also requires $tilde{Omega}(n^{omega})$ time, even for $varepsilon$ as large as $(1 - 1/text{poly}(n))$. We also prove (under some modified conjectures for the rank-finding problem) optimal hardness of approximation for sparse linear systems, linear systems over positive semidefinite matrices, well-conditioned linear systems, and approximately solving linear systems with respect to the $L_p$-norm, for $p geq 1$. At the heart of our results is a novel reduction from the rank problem to a decision version of the approximate linear systems problem. This reduction preserves properties such as matrix sparsity and bit complexity.
We prove several results about the complexity of the role colouring problem. A role colouring of a graph $G$ is an assignment of colours to the vertices of $G$ such that two vertices of the same colour have identical sets of colours in their neighbourhoods. We show that the problem of finding a role colouring with $1< k <n$ colours is NP-hard for planar graphs. We show that restricting the problem to trees yields a polynomially solvable case, as long as $k$ is either constant or has a constant difference with $n$, the number of vertices in the tree. Finally, we prove that cographs are always $k$-role-colourable for $1<kleq n$ and construct such a colouring in polynomial time.
The minimum linear ordering problem (MLOP) seeks to minimize an aggregated cost $f(cdot)$ due to an ordering $sigma$ of the items (say $[n]$), i.e., $min_{sigma} sum_{iin [n]} f(E_{i,sigma})$, where $E_{i,sigma}$ is the set of items that are mapped by $sigma$ to indices at most $i$. This problem has been studied in the literature for various special cases of the cost function $f$, and in a general setting for a submodular or supermodular cost $f$ [ITT2012]. Though MLOP was known to be NP-hard for general submodular functions, it was unknown whether the special case of graphic matroid MLOP (with $f$ being the matroid rank function of a graph) was polynomial-time solvable. Following this motivation, we explore related classes of linear ordering problems, including symmetric submodular MLOP, minimum latency vertex cover, and minimum sum vertex cover. We show that the most special cases of our problem, graphic matroid MLOP and minimum latency vertex cover, are both NP-hard. We further expand the toolkit for approximating MLOP variants: using the theory of principal partitions, we show a $2-frac{1+ell_{f}}{1+|E|}$ approximation to monotone submodular MLOP, where $ell_{f}=frac{f(E)}{max_{xin E}f({x})}$ satisfies $1 leq ell_f leq |E|$. Thus our result improves upon the best known bound of $2-frac{2}{1+|E|}$ by Iwata, Tetali, and Tripathi [ITT2012]. This leads to a $2-frac{1+r(E)}{1+|E|}$ approximation for the matroid MLOP, corresponding to the case when $r$ is the rank function of a given matroid. Finally, we show that MLVC can be $4/3$ approximated, matching the integrality gap of its vanilla LP relaxation.
There has been a resurgence of interest in lower bounds whose truth rests on the conjectured hardness of well known computational problems. These conditional lower bounds have become important and popular due to the painfully slow progress on proving strong unconditional lower bounds. Nevertheless, the long term goal is to replace these conditional bounds with unconditional ones. In this paper we make progress in this direction by studying the cell probe complexity of two conjectured to be hard problems of particular importance: matrix-vector multiplication and a version of dynamic set disjointness known as Patrascus Multiphase Problem. We give improved unconditional lower bounds for these problems as well as introducing new proof techniques of independent interest. These include a technique capable of proving strong threshold lower bounds of the following form: If we insist on having a very fast query time, then the update time has to be slow enough to compute a lookup table with the answer to every possible query. This is the first time a lower bound of this type has been proven.
We study sublinear and local computation algorithms for decision trees, focusing on testing and reconstruction. Our first result is a tester that runs in $mathrm{poly}(log s, 1/varepsilon)cdot nlog n$ time, makes $mathrm{poly}(log s,1/varepsilon)cdot log n$ queries to an unknown function $f$, and: $circ$ Accepts if $f$ is $varepsilon$-close to a size-$s$ decision tree; $circ$ Rejects if $f$ is $Omega(varepsilon)$-far from decision trees of size $s^{tilde{O}((log s)^2/varepsilon^2)}$. Existing testers distinguish size-$s$ decision trees from those that are $varepsilon$-far from from size-$s$ decision trees in $mathrm{poly}(s^s,1/varepsilon)cdot n$ time with $tilde{O}(s/varepsilon)$ queries. We therefore solve an incomparable problem, but achieve doubly-exponential-in-$s$ and exponential-in-$s$ improvements in time and query complexities respectively. We obtain our tester by designing a reconstruction algorithm for decision trees: given query access to a function $f$ that is close to a small decision tree, this algorithm provides fast query access to a small decision tree that is close to $f$. By known relationships, our results yield reconstruction algorithms for numerous other boolean function properties -- Fourier degree, randomized and quantum query complexities, certificate complexity, sensitivity, etc. -- which in turn yield new testers for these properties. Finally, we give a hardness result for testing whether an unknown function is $varepsilon$-close-to or $Omega(varepsilon)$-far-from size-$s$ decision trees. We show that an efficient algorithm for this task would yield an efficient algorithm for properly learning decision trees, a central open problem of learning theory. It has long been known that proper learning algorithms for any class $mathcal{H}$ yield property testers for $mathcal{H}$; this provides an example of a converse.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
