Abstract
An instance of the maximum mixed graph orientation problem consists of a mixed graph and a collection of source-target vertex pairs. The objective is to orient the undirected edges of the graph so as to maximize the number of pairs that admit a directed source-target path. This problem has recently arisen in the study of biological networks, and it also has applications in communication networks. In this paper, we identify an interesting local-to-global orientation property. This property enables us to modify the best known algorithms for maximum mixed graph orientation and some of its special structured instances, due to Elberfeld et al. (Theor. Comput. Sci. 483:96–103, 2013), and obtain improved approximation ratios. We further proceed by developing an algorithm that achieves an even better approximation guarantee for the general setting of the problem. Finally, we study several well-motivated variants of this orientation problem.
Similar content being viewed by others
References
Afek, Y., Bremler, A.: Self-stabilizing unidirectional network algorithms by power supply. Chic. J. Theor. Comput. Sci. 3 (1998). doi:10.4086/cjtcs.1998.003.
Afek, Y., Gafni, E.: Distributed algorithms for unidirectional networks. SIAM J. Comput. 23(6), 1152–1178 (1994)
Arkin, E.M., Hassin, R.: A note on orientations of mixed graphs. Discrete Appl. Math. 116(3), 271–278 (2002)
Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discrete Math. 12(3), 289–297 (1999)
Becker, A.: Approximation algorithms for the loop cutset problem. In: Proceedings of the Tenth International Conference on Uncertainty in artificial intelligence, pp. 60–68. Morgan Kaufmann Publishers Inc., Burlington (1994)
Blokh, D., Segev, D., Sharan, R.: Approximation algorithms and hardness results for shortest path based graph orientations. In: Combinatorial Pattern Matching, pp. 70–82. Springer, Berlin (2012)
Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305–1317 (1996)
Chudak, F.A., Goemans, M.X., Hochbaum, D.S., Williamson, D.P.: A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Oper. Res. Lett. 22(4), 111–118 (1998)
Dorn, B., Hüffner, F., Krüger, D., Niedermeier, R., Uhlmann, J.: Exploiting bounded signal flow for graph orientation based on cause-effect pairs. Algorithms Mol Biol 6(1), 1–12 (2011)
Elberfeld, M., Bafna, V., Gamzu, I., Medvedovsky, A., Segev, D., Silverbush, D., Zwick, U., Sharan, R.: On the approximability of reachability-preserving network orientations. Internet Math. 7(4), 209–232 (2011)
Elberfeld, M., Segev, D., Davidson, C.R., Silverbush, D., Sharan, R.: Approximation algorithms for orienting mixed graphs. Theor. Comput. Sci. 483, 96–103 (2013)
Feige, U., Goemans, M.: Approximating the value of two power proof systems, with applications to max 2sat and max dicut. In: Third Israel Symposium on the Theory of Computing and Systems, pp. 182–189. IEEE (1995)
Fields, S.: High-throughput two-hybrid analysis. FEBS J. 272(21), 5391–5399 (2005)
Frederickson, G.N., Johnson, D.B.: Generating and searching sets induced by networks. In: Automata, Languages and Programming, pp. 221–223. Springer, Berlin (1980)
Gamzu, I., Medina, M.: Improved approximation for orienting mixed graphs. In: Structural Information and Communication Complexity, pp. 243–253. Springer, Berlin (2012)
Gamzu, I., Segev, D.: A sublogarithmic approximation for highway and tollbooth pricing. In Automata, Languages and Programming, pp. 582–593. Springer, Berlin (2010)
Gamzu, I., Segev, D., Sharan, R.: Improved orientations of physical networks. In: Algorithms in Bioinformatics, pp. 215–225. Springer, Berlin (2010)
Gavin, A.-C., Bösche, M., Krause, R., Grandi, P., Marzioch, M., Bauer, A., Schultz, J., Rick, J.M., Michon, A.-M., Cruciat, C.-M., et al.: Functional organization of the yeast proteome by systematic analysis of protein complexes. Nature 415(6868), 141–147 (2002)
Hakimi, S.L., Schmeichel, E.F., Young, N.E.: Orienting graphs to optimize reachability. Inf. Process. Lett. 63(5), 229–235 (1997)
Håstad, J.: Some optimal inapproximability results. J. ACM (JACM) 48(4), 798–859 (2001)
Khot, S., Kindler, G., Mossel, E., O’Donnell, R.: Optimal inapproximability results for max-cut and other 2-variable csps? SIAM J. Comput. 37(1), 319–357 (2007)
Lewin, M., Livnat, D., Zwick, U.: Improved rounding techniques for the max 2-sat and max di-cut problems. In: Integer Programming and Combinatorial Optimization, pp. 67–82. Springer, Berlin (2002)
Marina, M.K., Das, S.R.: Routing performance in the presence of unidirectional links in multihop wireless networks. In: Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking & Computing. Association for Computing Machinery, pp. 12–23 (2002)
Medvedovsky, A., Bafna, V., Zwick, U., Sharan, R.: An Algorithm for Orienting Graphs Based on Cause-Effect Pairs and its Applications to Orienting Protein Networks. Springer, Berlin (2008)
Silverbush, D., Elberfeld, M., Sharan, R.: Optimally orienting physical networks. J. Comput. Biol. 18(11), 1437–1448 (2011)
Yeang, C.-H., Ideker, T., Jaakkola, T.: Physical network models. J. Comput. Biol. 11(2–3), 243–262 (2004)
Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3, 103–128 (2007)
Acknowledgments
Moti Medina was partially funded by the Israeli Ministry of Science and Technology.
Author information
Authors and Affiliations
Corresponding author
Additional information
Preliminary version appeared in the proceedings of SIROCCO 2012 [15].
Rights and permissions
About this article
Cite this article
Gamzu, I., Medina, M. Improved Approximation for Orienting Mixed Graphs. Algorithmica 74, 49–64 (2016). https://doi.org/10.1007/s00453-014-9932-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-014-9932-2