Abstract
For a digraph D = (V, A) and a partition {S, T} of V, an arc set \({B \subseteq A}\) is called an S−T if each vertex in T is reachable from S and each vertex in S reaches T in the subgraph (V, B). Bibranchings commonly generalize bipartite edge covers and arborescences. A totally dual integral linear system determining the S−T polytope is provided by Schrijver, and the shortest S−T problem, whose objective is to find an S−T of minimum total arc weight, can be solved in polynomial time by the ellipsoid method or a faster combinatorial algorithm due to Keijsper and Pendavingh. The valuated matroid intersection problem, introduced by Murota, is a weighted generalization of the independent matching problem, including the independent assignment problem and the weighted matroid intersection problem. The valuated matroid intersection problem can be solved efficiently with polynomially many value oracles by extending classical combinatorial algorithms for the weighted matroid intersection problem. In this paper, we show that the shortest S−T problem is polynomially reducible to the valuated matroid intersection problem. This reduction suggests one answer to why the shortest S−T problem is tractable, and implies new combinatorial algorithms for the shortest S−T problem based on the valuated matroid intersection algorithm, where a value oracle corresponds to computing a minimum-weight arborescence.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Dress A.W.M., Wenzel W.: Valuated matroid: a new look at the greedy algorithm. Appl. Math. Lett 3, 33–35 (1990)
Dress A.W.M., Wenzel W.: Valuated matroids. Adv. Math. 93, 214–250 (1992)
Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. In: Guy R., Hanani H., Sauer N., Schönheim J. (eds.) Combinatorial Structures and Their Applications (Proceedings Calgary International Conference on Combinatorial Structures and Their Applications, Calgary, 1969), pp. 93–96 (1970)
Frank A.: A weighted matroid intersection algorithm. J. Algorithms 2, 328–336 (1981)
Frank, A.: Generalized polymatroids. In: Hajnal A., Lovász L., Sós V.T. (eds.) Finite and Infinite Sets, vol. I (Proceedings of the Sixth Hungarian Combinatorial Colloquium, Eger, 1981), pp. 285–294 (1984)
Fujishige, S.: Submodular Functions and Optimization, 2nd edn. Annals of Discrete Mathematics, vol. 58. Elsevier, Amsterdam (2005)
Gabow H.N., Galil Z., Spencer T., Tarjan R.E.: Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6, 109–122 (1986)
Iri M., Tomizawa N.: An algorithm for finding an optimal “independent assignment”. J. Oper. Res. Soc. Japan 19, 32–57 (1976)
Keijsper J., Pendavingh R.: An efficient algorithm for minimum-weight bibranching. J. Combin. Theory Ser. B 73, 130–145 (1998)
Lawler E.L.: Matroid intersection algorithms. Math. Program 9, 31–56 (1975)
Murota K.: Convexity and Steinitz’s exchange property. Adv. Math. 125, 272–331 (1996)
Murota K.: Valuated matroid intersection I: Optimality criteria. SIAM J. Discrete Math. 9, 545–561 (1996)
Murota K.: Valuated matroid intersection II: Algorithms. SIAM J. Discrete Math. 9, 562–576 (1996)
Murota K.: Discrete Convex Analysis. Society for Industrial and Applied Mathematics, Philadelphia (2003)
Murota K.: Matrices and Matroids for Systems Analysis. softcover edn. Springer, Berlin (2010)
Murota K., Shioura A.: M-convex function on generalized polymatroid. Math. Oper. Res. 24, 95–105 (1999)
Schrijver A.: Min–max relations for directed graphs. Ann. Discrete Math. 16, 261–280 (1982)
Schrijver A.: Total dual integrality of matching forest constraints. Combinatorica 20, 575–588 (2000)
Schrijver A.: Combinatorial Optimization—Polyhedra and Efficiency. Springer, Heidelberg (2003)
Shioura A.: A constructive proof for the induciton of M-convex functions through networks. Discrete Appl. Math. 82, 271–278 (1998)
Shioura, A.: Polynomial-time approximation schemes for maximizing gross substitutes utility under budget constraints. In: Demetrescu, C., Halldórsson, M.M. (eds.) Proceedings of the 19th Annual European Symposium on Algorithms. LNCS, vol. 6942 pp. 1–12. Springer, Berlin (2011)
Takazawa, K.: Optimal matching forests and valuated delta-matroids. In: Günlük, O., Woeginger, G.J. (eds.) Integer Programming and Combinatorial Optimization: Proceedings of the 15th International IPCO Conference. LNCS, vol. 6655, pp. 404–416. Springer, Berlin (2011)
Tardos, É: Generalized matroids and supermodular colourings. In: Lovász, L., Recski, A. (eds.) Matroid Theory (Proceedings Colloquium on Matroid Theory, Szeged, 1982), pp. 359–382 (1985)
Tomizawa N.: On some techniques useful for solution of transportation network problems. Networks 1, 173–194 (1971)
Author information
Authors and Affiliations
Corresponding author
About this article
Cite this article
Takazawa, K. Shortest bibranchings and valuated matroid intersection. Japan J. Indust. Appl. Math. 29, 561–573 (2012). https://doi.org/10.1007/s13160-012-0072-2
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s13160-012-0072-2