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
Engineering Design Methodology for Robot-Based Non-Planar Additive Manufacturing (RbNPAM)
Engineering Design Methodology for Robot-Based Non-Planar Additive Manufacturing (RbNPAM)
Robot-Based Non-Planar Additive Manufacturing (RbNPAM) explores advancements in integrating robotics with additive manufacturing, focusing on the development and application of non...
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...
Dynamic Algorithms for Approximate Steiner Trees
Dynamic Algorithms for Approximate Steiner Trees
ABSTRACTThis study investigates the dynamic Steiner tree problem. The objective of the Steiner tree problem is to compute a minimum‐weight tree connecting a set of designated verti...
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...
Weakly Modular Graphs and Nonpositive Curvature
Weakly Modular Graphs and Nonpositive Curvature
This article investigates structural, geometrical, and topological characterizations and properties of weakly modular graphs and of cell complexes derived from them. The unifying t...
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...