TR-2012-16

Parameterized Complexity of Spare Capacity Allocation and the Multicost Steiner Subgraph Problem

Tibor Jordán, Ildikó Schlotter

Published in:
Journal of Discrete Algorithms, Volume 30, 2015, Pages 29-44. DOI link

We study the computational complexity of the Spare Capacity Allocation problem arising in optical networks that use shared mesh restoration scheme. We focus on the setting where we deal with a group of demands together, and select their restoration paths simultaneously in order to minimize the total cost. We investigate how the computational complexity of this problem is affected by certain parameters, such as the number of restorations paths to be selected, or the treewidth of the network graph. To analyze the complexity of the problem, we introduce a generalization of the Steiner Forest problem that we call Multicost Steiner Subgraph. We study its parameterized complexity, and identify computationally easy and hard cases by providing hardness proofs as well as efficient (fixed-parameter tractable) algorithms.

Bibtex entry:

@techreport{egres-12-16,

AUTHOR	=	{Jord{\'a}n, Tibor and Schlotter, Ildik{\'o}},
TITLE	=	{Parameterized Complexity of Spare Capacity Allocation and the Multicost Steiner Subgraph Problem},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2012},
NUMBER	=	{TR-2012-16}

}