### Top 10 Arxiv Papers Today in Data Structures And Algorithms

##### #1. A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs
###### Lars Jaffke, Paloma T. Lima
A $b$-coloring of a graph $G$ is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The $b$-chromatic number of a graph $G$, denoted by $\chi_b(G)$, is the maximum number $k$ such that $G$ admits a $b$-coloring with $k$ colors. We consider the complexity of the problem of deciding whether a graph $G$ has a $b$-coloring with $k$ colors, whenever the value of $k$ is close to one of two upper bounds on $\chi_b(G)$: The maximum degree $\Delta(G)$ plus one, and the $m$-degree, denoted by $m(G)$, which is defined as the maximum number $i$ such that $G$ has $i$ vertices of degree at least $i-1$. We obtain a dichotomy result stating that for fixed $k \in \{\Delta(G) + 1 - p, m(G) - p\}$, the problem is polynomial-time solvable whenever $p \in \{0, 1\}$ and, even when $k = 3$, it is NP-complete whenever $p \ge 2$. We furthermore give an FPT-algorithm parameterized by $k + \ell$, where $\ell$ denotes the number of vertices of degree at least $k$,...
more | pdf | html
None.
###### Tweets
ComputerPapers: A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs. https://t.co/znaP1SGAta
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 8522
Unqiue Words: 1516

##### #2. A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest
###### Neil Olver, Frans Schalekamp, Suzanne van der Ster, Leen Stougie, Anke van Zuylen
We give a 2-approximation algorithm for the Maximum Agreement Forest problem on two rooted binary trees. This NP-hard problem has been studied extensively in the past two decades, since it can be used to compute the rooted Subtree Prune-and-Regraft (rSPR) distance between two phylogenetic trees. Our algorithm is combinatorial and its running time is quadratic in the input size. To prove the approximation guarantee, we construct a feasible dual solution for a novel linear programming formulation. In addition, we show this linear program is stronger than previously known formulations, and we give a compact formulation, showing that it can be solved in polynomial time
more | pdf | html
None.
###### Tweets
ComputerPapers: A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest. https://t.co/h5pRHTzcWo
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 5
Total Words: 17622
Unqiue Words: 2562

##### #3. Distributed Triangle Detection via Expander Decomposition
###### Yi-Jun Chang, Seth Pettie, Hengjie Zhang
We present improved distributed algorithms for triangle detection and its variants in the CONGEST model. We show that Triangle Detection, Counting, and Enumeration can be solved in $\tilde{O}(n^{1/2})$ rounds. In contrast, the previous state-of-the-art bounds for Triangle Detection and Enumeration were $\tilde{O}(n^{2/3})$ and $\tilde{O}(n^{3/4})$, respectively, due to Izumi and LeGall (PODC 2017). The main technical novelty in this work is a distributed graph partitioning algorithm. We show that in $\tilde{O}(n^{1-\delta})$ rounds we can partition the edge set of the network $G=(V,E)$ into three parts $E=E_m\cup E_s\cup E_r$ such that (a) Each connected component induced by $E_m$ has minimum degree $\Omega(n^\delta)$ and conductance $\Omega(1/\text{poly} \log(n))$. As a consequence the mixing time of a random walk within the component is $O(\text{poly} \log(n))$. (b) The subgraph induced by $E_s$ has arboricity at most $n^{\delta}$. (c) $|E_r| \leq |E|/6$. All of our algorithms are based on the following generic...
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 16055
Unqiue Words: 3127

##### #4. On Euclidean Methods for Cubic and Quartic Jacobi Symbols
We study the bit complexity of two methods, related to the Euclidean algorithm, for computing cubic and quartic analogs of the Jacobi symbol. The main bottleneck in such procedures is computation of a quotient for long division. We give examples to show that with standard arithmetic, if quotients are computed naively (by using exact norms as denominators, then rounding), the algorithms have $\Theta(n^3)$ bit complexity. It is a "folk theorem" that this can be reduced to $O(n^2)$ by modifying the division procedure. We give a self-contained proof of this, and show that quadratic time is best possible for these algorithms (with standard arithmetic or not). We also address the relative efficiency of using reciprocity, as compared to Euler's criterion, for testing if a given number is a cubic or quartic residue modulo an odd prime. Which is preferable depends on the number of residue tests to be done. Finally, we discuss the cubic and quartic analogs of Eisenstein's even-quotient algorithm for computing Jacobi symbols in ${\bf... more | pdf | html ###### Figures None. ###### Tweets ###### Github None. ###### Youtube None. ###### Other stats Sample Sizes : None. Authors: 2 Total Words: 7209 Unqiue Words: 2171 ###### 0.0 Mikeys ##### #5. MISSION: Ultra Large-Scale Feature Selection using Count-Sketches ###### Amirali Aghazadeh, Ryan Spring, Daniel LeJeune, Gautam Dasarathy, Anshumali Shrivastava, Richard G. Baraniuk Feature selection is an important challenge in machine learning. It plays a crucial role in the explainability of machine-driven decisions that are rapidly permeating throughout modern society. Unfortunately, the explosion in the size and dimensionality of real-world datasets poses a severe challenge to standard feature selection algorithms. Today, it is not uncommon for datasets to have billions of dimensions. At such scale, even storing the feature vector is impossible, causing most existing feature selection methods to fail. Workarounds like feature hashing, a standard approach to large-scale machine learning, helps with the computational feasibility, but at the cost of losing the interpretability of features. In this paper, we present MISSION, a novel framework for ultra large-scale feature selection that performs stochastic gradient descent while maintaining an efficient representation of the features in memory using a Count-Sketch data structure. MISSION retains the simplicity of feature hashing without sacrificing the... more | pdf | html ###### Figures None. ###### Tweets ###### Github MISSION: Ultra Large-Scale Feature Selection using Count-Sketches Repository: MISSION User: rdspring1 Language: C++ Stargazers: 3 Subscribers: 3 Forks: 1 Open Issues: 0 ###### Youtube None. ###### Other stats Sample Sizes : None. Authors: 6 Total Words: 8909 Unqiue Words: 2607 ###### 0.0 Mikeys ##### #6. Turning Cliques into Paths to Achieve Planarity ###### Patrizio Angelini, Peter Eades, Seok-Hee Hong, Karsten Klein, Stephen Kobourov, Giuseppe Liotta, Alfredo Navarra, Alessandra Tappini Motivated by hybrid graph representations, we introduce and study the following beyond-planarity problem, which we call$h$-Clique2Path Planarity: Given a graph$G$, whose vertices are partitioned into subsets of size at most$h$, each inducing a clique, remove edges from each clique so that the subgraph induced by each subset is a path, in such a way that the resulting subgraph of$G$is planar. We study this problem when$G$is a simple topological graph, and establish its complexity in relation to$k$-planarity. We prove that$h$-Clique2Path Planarity is NP-complete even when$h=4$and$G$is a simple$3$-plane graph, while it can be solved in linear time, for any$h$, when$G$is$1$-plane. more | pdf | html ###### Figures None. ###### Tweets ComputerPapers: Turning Cliques into Paths to Achieve Planarity. https://t.co/cxQEwhZqcR ###### Github None. ###### Youtube None. ###### Other stats Sample Sizes : None. Authors: 8 Total Words: 5352 Unqiue Words: 1235 ###### 0.0 Mikeys ##### #7. A deterministic polynomial kernel for Odd Cycle Transversal and Vertex Multiway Cut in planar graphs ###### Bart M. P. Jansen, Marcin Pilipczuk, Erik Jan van Leeuwen We show that Odd Cycle Transversal and Vertex Multiway Cut admit deterministic polynomial kernels when restricted to planar graphs and parameterized by the solution size. This answers a question of Saurabh. On the way to these results, we provide an efficient sparsification routine in the flavor of the sparsification routine used for the Steiner Tree problem in planar graphs (FOCS 2014). It differs from the previous work because it preserves the existence of low-cost subgraphs that are not necessarily Steiner trees in the original plane graph, but structures that turn into (supergraphs of) Steiner trees after adding all edges between pairs of vertices that lie on a common face. We also show connections between Vertex Multiway Cut and the Vertex Planarization problem, where the existence of a polynomial kernel remains an important open problem. more | pdf | html ###### Figures None. ###### Tweets M157q_News_RSS: A deterministic polynomial kernel for Odd Cycle Transversal and Vertex Multiway Cut in planar graphs. (arXiv:1810.01136v2 [cs.DS] UPDATED) https://t.co/jlKyQeoLv8 We show that Odd Cycle Transversal and Vertex Multiway Cut admit deterministic polynomial kernels when restricted to ComputerPapers: A deterministic polynomial kernel for Odd Cycle Transversal and Vertex Multiway Cut in planar graphs. https://t.co/ESUPKmJM1X ###### Github None. ###### Youtube None. ###### Other stats Sample Sizes : None. Authors: 3 Total Words: 27270 Unqiue Words: 3513 ###### 0.0 Mikeys ##### #8. Approximating optimal transport with linear programs ###### Kent Quanrud In the regime of bounded transportation costs, additive approximations for the optimal transport problem are reduced (rather simply) to relative approximations for positive linear programs, resulting in faster additive approximation algorithms for optimal transport. more | pdf | html ###### Figures None. ###### Tweets ComputerPapers: Approximating optimal transport with linear programs. https://t.co/BVu4gOrcj6 ###### Github None. ###### Youtube None. ###### Other stats Sample Sizes : None. Authors: 1 Total Words: 4021 Unqiue Words: 1115 ###### 0.0 Mikeys ##### #9. Independent Sets in Vertex-Arrival Streams ###### Graham Cormode, Jacques Dark, Christian Konrad We consider the classic maximal and maximum independent set problems in three models of graph streams: In the edge-arrival model we see a stream of edges which collectively define a graph, this model has been well-studied for a variety of problems. We first show that the space complexity for a one-pass streaming algorithm to find a maximal independent set is quadratic (i.e. we must store all edges). We further show that the problem does not become much easier if we only require approximate maximality. In the "explicit" vertex stream model, the input stream is a sequence of vertices making up the graph, where every vertex arrives along with its incident edges that connect to previously arrived vertices. Various graph problems require substantially less space to solve in this setting than for edge-arrival streams. We show that every one-pass$c$-approximation algorithm for maximum independent set (MIS) on explicit vertex streams requires space$\Omega(\frac{n^2}{c^7})$, where$n$is the number of vertices of the input graph, and... more | pdf | html ###### Figures None. ###### Tweets ###### Github None. ###### Youtube None. ###### Other stats Sample Sizes : None. Authors: 3 Total Words: 11440 Unqiue Words: 2476 ###### 0.0 Mikeys ##### #10. Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS ###### Karl Bringmann, Bhaskar Ray Chaudhury We study sketching and streaming algorithms for the Longest Common Subsequence problem (LCS) on strings of small alphabet size$|\Sigma|$. For the problem of deciding whether the LCS of strings$x,y$has length at least$L$, we obtain a sketch size and streaming space usage of$\mathcal{O}(L^{|\Sigma| - 1} \log L)$. We also prove matching unconditional lower bounds. As an application, we study a variant of LCS where each alphabet symbol is equipped with a weight that is given as input, and the task is to compute a common subsequence of maximum total weight. Using our sketching algorithm, we obtain an$\mathcal{O}(\textrm{min}\{nm, n + m^{{\lvert \Sigma \rvert}}\})$-time algorithm for this problem, on strings$x,y$of length$n,m$, with$n \ge m\$. We prove optimality of this running time up to lower order factors, assuming the Strong Exponential Time Hypothesis.
more | pdf | html
None.
###### Tweets
ComputerPapers: Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS. https://t.co/FJNYFXDDZe
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 10034
Unqiue Words: 2325

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

Tracking 72,893 papers.

###### Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Online
###### Stats
Tracking 72,893 papers.