### The Minimum Shared Edges Problem on Planar Graphs

**2016-02-03**

1602.01385 | cs.CC

We study the Minimum Shared Edges problem introduced by Omran et al. [Journal
of Combinatorial Optimization, 2015] on planar graphs: Planar MSE asks, given a
planar graph G = (V,E), two distinct vertices s,t in V , and two integers p, k,
whether there are p s-t paths in G that share at most k edges, where an edges
is called shared if it appears in at least two of the p s-t paths. We show that
Planar MSE is NP-hard by reduction from Vertex Cover. We make use of a
grid-like structure, where the alignment (horizontal/vertical) of the edges in
the grid correspond to selection and validation gadgets respectively.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2019-05-24**

1905.10284 | cs.DS

This paper studies lower bounds for fundamental optimization problems in the
CONGEST model. We show … show more

**2019-04-10**

1904.05011 | cs.DS

The Max-Cut problem is known to be NP-hard on general graphs, while it can be
solved in polynomial t… show more

**2019-01-17**

1901.05594 | math.CO

Motivated by the question of whether planar graphs have bounded queue-number,
we prove that planar g… show more

**2019-03-07**

1903.03197 | cs.DM

A graph G is called well-indumatched if all of its maximal induced matchings
have the same size. In … show more

**2019-02-13**

1902.04828 | math.CO

In this paper, we generalize the concept of complete coloring and achromatic
number to 2-edge-colore… show more

**2019-01-11**

1901.03627 | cs.DS

We introduce and study the Bicolored $P_3$ Deletion problem defined as
follows. The input is a graph… show more

**2018-10-27**

1810.11700 | cs.CC

The concept of Reload cost in a graph refers to the cost that occurs while
traversing a vertex via t… show more

**2018-08-10**

1808.03496 | cs.DS

This paper revisits the classical Edge Disjoint Paths (EDP) problem, where
one is given an undirecte… show more

**2017-02-20**

1702.06095 | cs.DS

In this paper, we prove that, given a clique-width $k$-expression of an
$n$-vertex graph, \textsc{Ha… show more

**2016-05-29**

1605.09055 | math.CO

If a graph has $n\ge4k$ vertices and more than $n^2/4$ edges, then it
contains a copy of $C_{2k+1}$.… show more

**2017-08-25**

1708.07653 | cs.CG

We introduce the family of $k$-gap-planar graphs for $k \geq 0$, i.e., graphs
that have a drawing in… show more

**2017-02-20**

1702.06163 | cs.CG

Edge bundling is an important concept heavily used for graph visualization
purposes. To enable the c… show more

**2019-03-05**

1903.01800 | cs.CC

In this paper, we study the following problem: given a connected graph $G$,
can we reduce the domina… show more

**2018-11-02**

1811.00816 | cs.DS

A queue layout of a graph consists of a linear order of its vertices and a
partition of its edges in… show more

**2018-11-16**

1811.06871 | cs.DS

The Planar Steiner Tree problem is one of the most fundamental NP-complete
problems as it models man… show more

**2017-07-21**

1707.06808 | cs.DS

Given a directed graph $G$ and a list $(s_1,t_1),\dots,(s_d,t_d)$ of terminal
pairs, the Directed St… show more