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.

okateim:
2019/09/20 [3]
Hardness and approximation for the geodetic set problem in some graph classes (https://t.co/zvVwRQAn6V)

None.

None.

Sample Sizes : None.

Authors: 5

Total Words: 7486

Unqiue Words: 1505

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.

Sample Sizes : None.

Authors: 6

Total Words: 0

Unqiue Words: 0

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.

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.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible