This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Takazawa, K. Search for Related Content

A Weighted k_{t, t}-Free t-Factor Algorithm for Bipartite Graphs

Graduate School of Information Science and Technology, University of Tokyo, Tokyo 113-8656, Japan, and Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan
takazawa{at}misojiro.t.u-tokyo.ac.jp, http://www.misojiro.t.u-tokyo.ac.jp/takazawa/

For a simple bipartite graph and an integer t 2, we consider the problem of finding a minimum-weight k_{t, t}-free t-factor, which is a t-factor containing no complete bipartite graph k_{t, t} as a subgraph. When t = 2, this problem amounts to the square-free 2-factor problem in a bipartite graph. For the unweighted square-free 2-factor problem, a combinatorial algorithm is given by Hartvigsen, and the weighted version of the problem is NP-hard. For general t, Pap designed a combinatorial algorithm for the unweighted version, and Makai gave a dual integral description of k_{t, t}-free t-matchings for a certain case where the weight vector is vertex-induced on any subgraph isomorphic to k_{t, t}. For this class of weight vectors, we propose a strongly polynomial algorithm to find a minimum-weight k_{t, t}-free t-factor. The algorithm adapts the unweighted algorithms of Hartvigsen and Pap and a primal-dual approach to the minimum-cost flow problem. The algorithm is fully combinatorial and thus provides a dual integrality theorem, which is tantamount to Makai's one.

Key Words: square-free 2-factor; k_{t, t}-free t-factor; combinatorial primal-dual algorithm; dual integrality
History: Received: February 21, 2008; revision received: September 19, 2008;