ML p(r)ior | The Minimum Shared Edges Problem on Planar Graphs

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

Highlights - Most important sentences from the article

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

Related Articles

2019-05-24

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

Highlights - Most important sentences from the article

2019-04-10

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2019-01-11

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

Highlights - Most important sentences from the article

2018-10-27

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2017-02-20

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2017-08-25

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

Highlights - Most important sentences from the article

2017-02-20

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

Highlights - Most important sentences from the article

2019-03-05

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

Highlights - Most important sentences from the article

2018-11-02

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

Highlights - Most important sentences from the article

2018-11-16

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article