### Top 3 Arxiv Papers Today in Discrete Mathematics

##### #1. Hardness and approximation for the geodetic set problem in some graph classes
###### Dibyayan Chakraborty, Florent Foucaud, Harmender Gahlawat, Subir Kumar Ghosh, Bodhayan Roy
In this paper, we study the computational complexity of finding the \emph{geodetic number} of graphs. A set of vertices $S$ of a graph $G$ is a \emph{geodetic set} if any vertex of $G$ lies in some shortest path between some pair of vertices from $S$. The \textsc{Minimum Geodetic Set (MGS)} problem is to find a geodetic set with minimum cardinality. In this paper, we prove that solving the \textsc{MGS} problem is NP-hard on planar graphs with a maximum degree six and line graphs. We also show that unless $P=NP$, there is no polynomial time algorithm to solve the \textsc{MGS} problem with sublogarithmic approximation factor (in terms of the number of vertices) even on graphs with diameter $2$. On the positive side, we give an $O\left(\sqrt[3]{n}\log n\right)$-approximation algorithm for the \textsc{MGS} problem on general graphs of order $n$. We also give a $3$-approximation algorithm for the \textsc{MGS} problem on the family of solid grid graphs which is a subclass of planar graphs.
more | pdf | html
None.
###### Tweets
okateim: 2019/09/20 [3] Hardness and approximation for the geodetic set problem in some graph classes (https://t.co/zvVwRQAn6V)
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 5
Total Words: 7486
Unqiue Words: 1505

##### #2. The Maximum Binary Tree Problem
###### Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubhang Kulkarni, Young-San Lin, Minshen Zhu
We introduce and investigate the approximability of the maximum binary tree problem (MBT) in directed and undirected graphs. The goal in MBT is to find a maximum-sized binary tree in a given graph. MBT is a natural generalization of the well-studied longest path problem, since both can be viewed as finding a maximum-sized tree of bounded degree in a given graph. The connection to longest path motivates the study of MBT in directed acyclic graphs (DAGs), since the longest path problem is solvable efficiently in DAGs. In contrast, we show that MBT in DAGs is in fact hard: it has no efficient $\exp(-O(\log n/ \log \log n))$-approximation algorithm under the exponential time hypothesis. In undirected graphs, we show that MBT has no efficient $\exp(-O(\log^{0.63}{n}))$-approximation under the exponential time hypothesis. Our hardness results rely on self-improving reductions and structural properties of binary trees. We also show constant-factor inapproximability assuming $\mathbf{P} \neq \mathbf{NP}$. Furthermore, motivated by the...
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 6
Total Words: 0
Unqiue Words: 0

##### #3. Lower Bound for (Sum) Coloring Problem
###### Alexandre Gondran, Vincent Duchamp, Laurent Moalic
The Minimum Sum Coloring Problem is a variant of the Graph Vertex Coloring Problem, for which each color has a weight. This paper presents a new way to find a lower bound of this problem, based on a relaxation into an integer partition problem with additional constraints. We improve the lower bound for 18 graphs of standard benchmark DIMACS, and prove the optimal value for 4 graphs by reaching their known upper bound.
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

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 192,930 papers.

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