×

Parameterized complexity of directed Steiner network with respect to shared vertices and arcs. (English) Zbl 1415.68160

Summary: We consider the directed Steiner network problem, where given a weighted directed graph \(G\) and \(p\) pairs of vertices \(P = \{(s_1, t_1), \dots,(s_p, t_p) \}\), one has to find the minimum weight subgraph \(H\) of \(G\) that contains path from \(s_i\) to \(t_i\) for all \(i\). We search for the main cause of the complexity of the problem and introduce the notions of junction vertex and shared segment in an optimal solution. We study the parameterized complexity of the problem with respect to these parameters and achieve several parameterized hardness results. Also, we present two output-sensitive algorithms for the problem, which are much simpler and easier to implement than the previously best known one; and in addition, when the paths corresponding to the input pairs have few shared vertices or arcs in the optimal solution, these algorithms outperform the previous one.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Downey, R. G. and Fellows, M. R., Parameterized Complexity (Springer-Verlag, 1999). · Zbl 0961.68533
[2] Feldman, J. and Ruhl, M., The directed Steiner network problem is tractable for a constant number of terminals, SIAM J. Comput.36(2) (2006) 543-561. · Zbl 1118.05039
[3] Fredman, M. L. and Tarjan, R. E., Fibonacci heaps and their uses in improved network optimization algorithms, J. ACM34(3) (1987) 596-615. · Zbl 1412.68048
[4] Gamzu, I. and Medina, M., Improved approximation for orienting mixed graphs, Struct. Inf. Commun. Complex.7355 (2012) 243-253. · Zbl 1503.05050
[5] Guo, J., Niedermeier, R. and Suchy, O., Parameterized complexity of arc-weighted directed Steiner problems, SIAM J. Discret. Math.25(2) (2011) 583-599. · Zbl 1230.05268
[6] Hu, T. C. and Kuh, E. S., VLSI Circuit Layout: Theory and Design (IEEE, 1985).
[7] Koh, K. M. and Tay, E. G., Optimal orientations of graphs and digraphs: A survey, Graphs Comb.18(4) (2002) 745-756. · Zbl 1009.05063
[8] Leung, J. M. Y., Magnanti, T. L. and Singhal, V., Routing in point-to-point delivery systems: Formulations and solution heuristics, Transp. Sci.24(4) (1990) 245-260. · Zbl 0723.90019
[9] Natu, M. and Fang, S. C., On the point-to-point connection problem, Inf. Process. Lett.53(6) (1995) 333-336. · Zbl 0875.68444
[10] Natu, M. and Shu-Cherng, F., The point-to-point connection problem-analysis and algorithms, Discret. Appl. Math.78(1) (1997) 207-226. · Zbl 0890.68104
[11] Niedermeier, R., Invitation to Fixed Parameter Algorithms (Oxford University Press, 2006). · Zbl 1095.68038
[12] Robbins, H. E., A theorem on graphs, with an application to a problem of traffic control, Am. Math. Mon.46(5) (1939) 281-283. · Zbl 0021.35703
[13] Fellows, M. R., Hermelin, D., Rosamond, F. and Vialette, S., On the parameterized complexity of multiple-interval graph problems, Theor. Comput. Sci.410(1) (2009) 53-61. · Zbl 1161.68038
[14] Yen, J. Y., Finding the \(k\) shortest loopless paths in a network, Manage. Sci.17(11) (1971) 712-716. · Zbl 0218.90063
[15] Mouawad, A. E., Nishimura, N., Raman, V., Simjour, N. and Suzuki, A., On the parameterized complexity of reconfiguration problems, in Int. Symp. on Parameterized and Exact Computation (Springer, 2013), pp. 281-294. · Zbl 1350.68155
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.