Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
View through CrossRef
We propose polynomial-time algorithms that sparsify planar and bounded-genus graphs while preserving optimal or near-optimal solutions to Steiner problems. Our main contribution is a polynomial-time algorithm that, given an unweighted undirected graph
G
embedded on a surface of genus
g
and a designated face
f
bounded by a simple cycle of length
k
, uncovers a set
F
⊆
E
(
G
) of size polynomial in
g
and
k
that contains an optimal Steiner tree for
any
set of terminals that is a subset of the vertices of
f
.
We apply this general theorem to prove that:
— Given an unweighted graph
G
embedded on a surface of genus
g
and a terminal set
S
⊆
V
(
G
), one can in polynomial time find a set
F
⊆
E
(
G
) that contains an optimal Steiner tree
T
for
S
and that has size polynomial in
g
and |
E
(
T
)|.
— An analogous result holds for an optimal Steiner forest for a set
S
of terminal pairs.
— Given an unweighted planar graph
G
and a terminal set
S
⊆
V
(
G
), one can in polynomial time find a set
F
⊆
E
(
G
) that contains an optimal (edge) multiway cut
C
separating
S
(i.e., a cutset that intersects any path with endpoints in different terminals from
S
) and that has size polynomial in |
C
|.
In the language of parameterized complexity, these results imply the first polynomial kernels for S
teiner
T
ree
and S
teiner
F
orest
on planar and bounded-genus graphs (parameterized by the size of the tree and forest, respectively) and for (E
dge
) M
ultiway
C
ut
on planar graphs (parameterized by the size of the cutset).
Additionally, we obtain a weighted variant of our main contribution: a polynomial-time algorithm that, given an undirected plane graph
G
with positive edge weights, a designated face
f
bounded by a simple cycle of weight
w
(
f
), and an accuracy parameter ε > 0, uncovers a set
F
⊆
E
(
G
) of total weight at most poly(ε
-1
)
w
(
f
) that, for any set of terminal pairs that lie on
f
, contains a Steiner forest within additive error ε
w
(
f
) from the optimal Steiner forest.
Association for Computing Machinery (ACM)
Title: Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
Description:
We propose polynomial-time algorithms that sparsify planar and bounded-genus graphs while preserving optimal or near-optimal solutions to Steiner problems.
Our main contribution is a polynomial-time algorithm that, given an unweighted undirected graph
G
embedded on a surface of genus
g
and a designated face
f
bounded by a simple cycle of length
k
, uncovers a set
F
⊆
E
(
G
) of size polynomial in
g
and
k
that contains an optimal Steiner tree for
any
set of terminals that is a subset of the vertices of
f
.
We apply this general theorem to prove that:
— Given an unweighted graph
G
embedded on a surface of genus
g
and a terminal set
S
⊆
V
(
G
), one can in polynomial time find a set
F
⊆
E
(
G
) that contains an optimal Steiner tree
T
for
S
and that has size polynomial in
g
and |
E
(
T
)|.
— An analogous result holds for an optimal Steiner forest for a set
S
of terminal pairs.
— Given an unweighted planar graph
G
and a terminal set
S
⊆
V
(
G
), one can in polynomial time find a set
F
⊆
E
(
G
) that contains an optimal (edge) multiway cut
C
separating
S
(i.
e.
, a cutset that intersects any path with endpoints in different terminals from
S
) and that has size polynomial in |
C
|.
In the language of parameterized complexity, these results imply the first polynomial kernels for S
teiner
T
ree
and S
teiner
F
orest
on planar and bounded-genus graphs (parameterized by the size of the tree and forest, respectively) and for (E
dge
) M
ultiway
C
ut
on planar graphs (parameterized by the size of the cutset).
Additionally, we obtain a weighted variant of our main contribution: a polynomial-time algorithm that, given an undirected plane graph
G
with positive edge weights, a designated face
f
bounded by a simple cycle of weight
w
(
f
), and an accuracy parameter ε > 0, uncovers a set
F
⊆
E
(
G
) of total weight at most poly(ε
-1
)
w
(
f
) that, for any set of terminal pairs that lie on
f
, contains a Steiner forest within additive error ε
w
(
f
) from the optimal Steiner forest.
Related Results
COMPUTING STEINER POINTS AND PROBABILITY STEINER POINTS IN ℓ1 AND ℓ2 METRIC SPACES
COMPUTING STEINER POINTS AND PROBABILITY STEINER POINTS IN ℓ1 AND ℓ2 METRIC SPACES
The Steiner tree problem is a well known network optimization problem which asks for a connected minimum network (called a Steiner minimum tree) spanning a given point set N. In th...
Sparsification for graph and matroid optimization problems
Sparsification for graph and matroid optimization problems
Sparsification pour des problèmes d'optimisation sur des graphes et des matroïdes
La sparsification (que l’on pourrait traduire en français par "éparsification") fa...
Analyzing Co-expression Networks with Network Skeleton Extraction
Analyzing Co-expression Networks with Network Skeleton Extraction
Abstract
Background
: A central question in systems biology is to infer how genes work together to perform a specific function....
Computing a Minimum Subset Feedback Vertex Set on Chordal Graphs Parameterized by Leafage
Computing a Minimum Subset Feedback Vertex Set on Chordal Graphs Parameterized by Leafage
Abstract
Chordal graphs are characterized as the intersection graphs of subtrees in a tree and such a representation is known as the tree model. Restricting the characteriz...
Independent Set in Neutrosophic Graphs
Independent Set in Neutrosophic Graphs
New setting is introduced to study neutrosophic independent number and independent neutrosophic-number arising neighborhood of different vertices. Neighbor is a key term to have th...
Failed Independent Number in Neutrosophic Graphs
Failed Independent Number in Neutrosophic Graphs
New setting is introduced to study neutrosophic failed-independent number and failed independent neutrosophic-number arising neighborhood of different vertices. Neighbor is a key t...
Planar graphs have bounded nonrepetitive chromatic number
Planar graphs have bounded nonrepetitive chromatic number
The following seemingly simple question with surprisingly many connections to various problems in computer science and mathematics can be traced back to the beginning of the 20th c...
Linear Operators That Preserve the Genus of a Graph
Linear Operators That Preserve the Genus of a Graph
A graph has genus k if it can be embedded without edge crossings on a smooth orientable surface of genus k and not on one of genus k − 1 . A mapping of the set of graphs on ...