Abstract
A feedback vertex set (FVS) is a subset of vertices whose removal renders the remaining graph a forest. We show that finding the minimum FVS is tractable in the so-called triad convex bipartite graphs.
To whom the correspondence should be addressed: Tian Liu (lt@pku.edu.cn) and Ke Xu (kexu@nlsde.buaa.edu.cn).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bar-Yehuda, R., Geiger, D., Naor, J., Roth, R.: Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference. SIAM J. Comput. 27, 942–959 (1998)
Becker, A., Bar-Yehuda, R., Geiger, D.: Randomized Algorithms for the Loop Cutset Problem. J. Artif. Intell. Res. 12, 219–234 (2000)
Becker, A., Geiger, D.: Optimization of Pearls method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artificial Intelligence 83, 167–188 (1996)
Cai, M., Deng, X., Zang, W.: An approximation algorithm for feedback vertex sets in tournaments. SIAM J. Comput. 30, 1993–2007 (2001)
Cai, M., Deng, X., Zang, W.: A min-max theorem on feedback vertex sets. Math. Oper. Res. 27(2), 361–371 (2002)
Cao, Y., Chen, J., Liu, Y.: On Feedback Vertex Set: New Measure and New Structures. In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol. 6139, pp. 93–104. Springer, Heidelberg (2010)
Caragiannis, I., Kaklamanis, C., Kanellopoulos, P.: New bounds on the size of the feedback vertex set on meshes and butterflies. Inform. Process. Lett. 83(5), 275–280 (2002)
Chen, J., Fomin, F., Liu, Y., Lu, S., Villanger, T.: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci. 74(7), 1188–1198 (2008)
Chen, J., Liu, Y., Lu, S., O’Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55(5) (2008)
Festa, P., Pardalos, P.M., Resende, M.G.C.: Feedback set problems. In: Du, D.-Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization. Handbook of Combinatorial Optimization, Supplement vol. A, pp. 209–259. Kluwer Academic Publishers, Dordrecht (2000)
Fomin, F.V., Gaspers, S., Pyatkin, A., Razgon, I.: On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms. Algorithmica 52(2), 293–307 (2008)
Fomin, F.V., Villanger, Y.: Finding Induced Subgraphs via Minimal Triangulations. In: Proc. of STACS, pp. 383–394 (2010)
Focardi, R., Luccio, F.L., Peleg, D.: Feedback vertex set in hypercubes. Inform. Process. Lett. 76(1-2), 1–5 (2000)
Gavril, F.: Minimum weight feedback vertex sets in circle graphs. Information Processing Letters 107, 1–6 (2008)
Gusfield, D.: A graph theoretic approach to statistical data security. SIAM J. Comput. 17(3), 552–571 (1998)
Hsu, C.C., Lin, H.R., Chang, H.C., Lin, K.K.: Feedback Vertex Sets in Rotator Graphs. In: Gavrilova, M.L., Gervasi, O., Kumar, V., Tan, C.J.K., Taniar, D., Laganá, A., Mun, Y., Choo, H. (eds.) ICCSA 2006. LNCS, vol. 3984, pp. 158–164. Springer, Heidelberg (2006)
Jiang, W., Liu, T., Ren, T., Xu, K.: Two Hardness Results on Feedback Vertex Sets. In: Zhu, B. (ed.) FAW-AAIM 2011. LNCS, vol. 6681, pp. 233–243. Springer, Heidelberg (2011)
Jiang, W., Liu, T., Xu, K.: Feedback Vertex Sets in Restricted Bipartite Graphs, paper in preparation
Karp, R.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)
Kuo, C., Hsu, C., Lin, H., Lin, K.: An efficient algorithm for minimum feedback vertex sets in rotator graphs. Information Processing Letters 109, 450–453 (2009)
Kralovic, R., Ruzicka, P.: Minimum feedback vertex sets in shufflebased interconnection networks. Inform. Process. Lett. 86(4), 191–196 (2003)
Liang, Y.D., Chang, M.S.: Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs. Acta Informatica 34, 337–346 (1997)
Lipski Jr., W., Preparata, F.P.: Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems. Acta Informatica 15(4), 329–346 (1981)
Lu, C., Tang, C.: A linear-time algorithm for the weighted feedback vertex problem on interval graphs. Information Processing Letters 61, 107–111 (1997)
Luccio, F.L.: Exact minimum feedback vertex set in meshes and butterflies. Inform. Process. Lett. 66(2), 59–64 (1998)
Madelaine, F.R., Stewart, I.A.: Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies. Discrete Math. 308, 4144–4164 (2008)
Sasatte, P.: Improved approximation algorithm for the feedback set problem in a bipartite tournament. Operations Research Letters 36, 602–604 (2008)
Silberschatz, A., Galvin, P.B., Gagne, G.: Operating Systems Concepts, 6th edn. John Wiley and Sons, Inc., New York (2003)
Wang, F.H., Wang, Y.L., Chang, J.M.: Feedback vertex sets in star graphs. Inform. Process. Lett. 89(4), 203–208 (2004)
Williams, R., Gomes, C.P., Selman, B.: Backdoors To Typical Case Complexity. In: Proc. of IJCAI, pp. 1173–1178 (2003)
Yannakakis, M.: Node-deletion problem on bipartite graphs. SIAM J. Comput. 10, 310–327 (1981)
Zhang, Y., Bao, F.S.: A Survey of Tree Convex Sets Test. CoRR abs/0906.0205 (2009)
van Zuylen, A.: Linear programming based approximation algorithms for feedback set problems in bipartite tournaments. Theor. Comput. Sci. (in press)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jiang, W., Liu, T., Xu, K. (2011). Tractable Feedback Vertex Sets in Restricted Bipartite Graphs. In: Wang, W., Zhu, X., Du, DZ. (eds) Combinatorial Optimization and Applications. COCOA 2011. Lecture Notes in Computer Science, vol 6831. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22616-8_33
Download citation
DOI: https://doi.org/10.1007/978-3-642-22616-8_33
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22615-1
Online ISBN: 978-3-642-22616-8
eBook Packages: Computer ScienceComputer Science (R0)