An-approximation algorithm forminimum power edge-disjoint -paths
Zeev Nutov, The Open University of IsraelNetwork Design Problems
Input: A graphwith edge/node costs.
Output: A min-cost subgraph of that satisfies a given property.
Examples of properties
has minimum degree 1
is connected
contains an -path
contains disjoint -paths Etc.

Edge-CoverMinimum Spanning Tree
Shortest Path
Min-Cost k-Flowmany other problems

Wired versus Wireless
Wired Networks
connecting two nodes
incurs a certain cost.

Wireless Networks
We pay at a node (transmitter)for a range, to connect toall nodes in the range.

Minimum Power Problems
 Nodes in the network are transmitters.
 Every node connects to all nodes in its range.
 More power  larger transmission range.
 Transmission range: a disk centered at the node.

Goal: Assign energy levels
to the nodes such that: the communication network satisfies a given property;
 the total energy
is minimal.

Example

cbdedcbf

aRange assignmentefaDirected

Communication network
Undirectedcbadef

The Min-PowerEdge Disjoint

Min-Power -EDPInput: A graph
Output: An edge set
Minimize:
Exampletotal power of-Paths Problem

with edge-costs,, integer .
that contains edge-disjoint -paths.
, wherepower ofat.

The Min-Power

Edge Disjoint

Min-Power -EDP
Input: A graph
Output: An edge set
Minimize:
Exampletotal power of-Paths problem

with edge-costs,, integer .
that contains edge-disjoint -paths.
, wherepower ofat.

Relation to the Node-Weighted -EDP problem
Min-Power -EDP
Input: A graph
Output: An edge set
Minimize:with edge-costs,, integer .
that contains edge-disjoint -paths.
, where.

Node-Weighted -EDP
Node weights
instead of edge costs.
Minimize the weightof the setof end-nodes of the edges in .

Observation: Node-Weighted -EDP with unit node weights isequivalent to Min-Power -EDP with unit costs.

What do we know about Min-Power -EDP?
: Polynomial algorithm [ACMP 03], reduction to Shortest Path.
: We have a 2-approximation algorithm, but ….
we don’t know if the problem is in P or is NPC.
The edge-disjoint and node-disjoint versions are equivalent.

What do we know about Min-Power -EDP?
: Polynomial algorithm [ACMP 03], reduction to Shortest Path.
: We have a 2-approximation algorithm, but ….
we don’t know if the problem is in P or is NPC.
The edge-disjoin and node-disjoint versions are equivalent.
Large values of :• Polynomial algorithm for increasing the number of paths by ,when hasedge disjoint -paths of cost zero [LN 10].
This implies -approximation for Min-Power -EDP.
• Ratio for Min-Power -EDP with unit costs implies
ratio
for the Densest -Subgraph problem [N 08].
Currently[BCCFV 10], so probably.

Two Open Questions
Question 1: Best known ratio is , approximation threshold is
Can we achieve approximation ratio sublinear in ?
Question 2: For:• Is the problem in P or is it NPC?
• Can we achieve approximation ratio better than ?

Open questions
Question 1: Best known ratio is , approximation threshold is
Can we achieve approximation ratio sublinear in ?
Question 2: For:• The problem is in P or is NPC?
• Can we achieve approximation ratio better than ?
Theorem: Min-Power k-EDP admits ratio.

Open questions
Question 1: Best known ratio is , approximation threshold isCan we achieve approximation ratio sublinear in ?
Question 2: For:• The problem is in P or is NPC?
• Can we achieve approximation ratio better than ?
Theorem: Min-Power k-EDP admits ratioon simple graphs.
The Algorithm: Return a set of cheapest,edge-disjoint-paths.

Howandare related?

Easy to see:(tight example: single edge)

Hard to see:(tight example: clique)Ifandare optimal solutions to Min-Cost and Min-Power -EDP,

Main Theorem:
If is an inclusion minimal edge set ofwithout parallel edges thenedge-disjoint.

-pathsCorollary: Ifis an inclusion minimal graph that
contains edge-disjoint -paths then.

A tight example for unit costs
Corollary:.

A tight example for unit costs
Corollary:.

Proof of the Theorem
Let be an inclusion minimal edge set ofwithout parallel edges. For
let
The main Lemma:edge-disjoint

for any node subset .

We use the lemma to prove thatLet-paths.

be the power of.
at node . ThenThus it is sufficient to prove that for any node weights

Proof of the Theorem

Main Lemma:

for any node subset .

We need to prove: For any node weights

Proof: By induction on the number of distinct
Forthis follows from the Main Lemma.
For•
•
•

we use “peeling”:
the set of max-weight nodes.
max-weight minus second max-weight.
for,values.

otherwise.

Proof of the Theorem

Main Lemma:

for any node subset .

We need to prove:•••the set of max-weight nodes.
max-weight minus second max-weight.
for,otherwise.

Proof sketch of the Main Lemma:

1. By minimality, there exists a nested family of -cuts such that:every cut has at most edges and every edge is in some cut.
2. This partition into layers.
3. An edge from to has length. Let.
4. The number of “short” edges of length
is at most.
5. The number of “long” edges of length
is at most.

Summary• For Min-Power -EDP we showed that the simplest algorithm(that computes a min-cost solution) achieves ratio• The proof is based on a combinatorial result – in an inclusion
minimal simple graph that contains edge-disjoint -paths,
the number of edges
the number of nodes.
• [Maier, Mecke, Wagner 07] showed that the ratio is at least

Open Questions• Is Min-Power -EDP in P, or is it NPC?
• Approximation ratio better than for Min-Power -EDP?

Thank you for attention!

Questions?
23