×

Circular convex bipartite graphs: feedback vertex set. (English) Zbl 1339.05399

Widmayer, Peter (ed.) et al., Combinatorial optimization and applications. 7th international conference, COCOA 2013, Chengdu, China, December 12–14, 2013. Proceedings. Berlin: Springer (ISBN 978-3-319-03779-0/pbk). Lecture Notes in Computer Science 8287, 272-283 (2013).
Summary: A feedback vertex set is a subset of vertices, such that the removal of this subset renders the remaining graph cycle-free. The weight of a feedback vertex set is the sum of weights of its vertices. Finding a minimum weighted feedback vertex set is tractable for convex bipartite graphs, but \(\mathcal{NP}\)-complete even for unweighted bipartite graphs. In a circular convex (convex, respectively) bipartite graph, there is a circular (linear, respectively) ordering defined on one class of vertices, such that for every vertex in another class, the neighborhood of this vertex is a circular arc (an interval, respectively). The minimum weighted feedback vertex set problem is shown tractable for circular convex bipartite graphs in this paper, by making a Cook reduction (i.e. polynomial time Turing reduction) for this problem from circular convex bipartite graphs to convex bipartite graphs.
For the entire collection see [Zbl 1276.68032].

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
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] Bao, F.S., Zhang, Y.: A review of tree convex sets test. Computational Intelligence 28(3), 358–372 (2012); Previous version: A survey of tree convex sets test. arXiv.0906.0205 (2009) · Zbl 1251.91034
[2] Becker, A., Bar-Yehuda, R., Geiger, D.: Randomized Algorithms for the Loop Cutset Problem. J. Artif. Intell. Res. 12, 219–234 (2000) · Zbl 0947.68138
[3] Brandstad, A., Le, V.B., Spinrad, J.P.: Graph Classes - A Survey. Society for Industrial and Applied Mathematics, Philadelphia (1999) · Zbl 0919.05001 · doi:10.1137/1.9780898719796
[4] 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) · Zbl 1285.68061 · doi:10.1007/978-3-642-13731-0_10
[5] Dom, M.: Algorithmic aspects of the consecutive ones property. Bulletin of the EATCS 98, 27–59 (2009) · Zbl 1179.05071
[6] Damaschke, P., Muller, H., Kratsch, D.: Domination in Convex and Chordal Bipartite Graphs. Inform. Proc. Lett. 36, 231–236 (1990) · Zbl 0706.68055 · doi:10.1016/0020-0190(90)90147-P
[7] 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) · Zbl 1170.68029 · doi:10.1007/s00453-007-9152-0
[8] Festa, P., Pardalos, P.M., Resende, M.G.C.: Feedback set problems. In: Handbook of Combinatorial Optimization, (suppl. vol. A), pp. 209–258. Kluwer Academic Publishers (1999) · Zbl 1253.90193 · doi:10.1007/978-1-4757-3023-4_4
[9] Fomin, F.V., Villanger, Y.: Finding Induced Subgraphs via Minimal Triangulations. In: Proc. of STACS, pp. 383–394 (2010) · Zbl 1230.68108
[10] Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company (1979) · Zbl 0411.68039
[11] Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980) · Zbl 0541.05054
[12] Golumbic, M.C., Goss, C.F.: Perfect elimination and chordal bipartite graphs. J. Graph Theory. 2, 155–163 (1978) · Zbl 0411.05060 · doi:10.1002/jgt.3190020209
[13] Grover, F.: Maximum matching in a convex bipartite graph. Nav. Res. Logist. Q. 14, 313–316 (1967) · Zbl 0183.24501 · doi:10.1002/nav.3800140304
[14] Guo, J.: Undirected feedback vertex set. Encyclopedia of Algorithms, 995–996 (2008) · doi:10.1007/978-0-387-30162-4_450
[15] Hung, R.-W.: Linear-time algorithm for the paired-domination problem in convex bipartite graphs. Theory Comput. Syst. 50, 721–738 (2012) · Zbl 1253.68175 · doi:10.1007/s00224-011-9378-8
[16] Jiang, W., Liu, T., Ren, T., Xu, K.: Two hardness results on feedback vertex sets. In: Atallah, M., Li, X.-Y., Zhu, B. (eds.) FAW-AAIM 2011. LNCS, vol. 6681, pp. 233–243. Springer, Heidelberg (2011) · Zbl 1329.68125 · doi:10.1007/978-3-642-21204-8_26
[17] Jiang, W., Liu, T., Wang, C., Xu, K.: Feedback vertex sets on restricted bipartite graphs. Theor. Comput. Sci. (in press, 2013), doi: 10.1016/j.tcs.2012.12.021 · Zbl 1302.05191 · doi:10.1016/j.tcs.2012.12.021
[18] Jiang, W., Liu, T., Xu, K.: Tractable feedback vertex sets in restricted bipartite graphs. In: Wang, W., Zhu, X., Du, D.-Z. (eds.) COCOA 2011. LNCS, vol. 6831, pp. 424–434. Springer, Heidelberg (2011) · Zbl 1342.05121 · doi:10.1007/978-3-642-22616-8_33
[19] Karp, R.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972) · doi:10.1007/978-1-4684-2001-2_9
[20] Kloks, T., Liu, C.H., Pon, S.H.: Feedback vertex set on chordal bipartite graphs. arXiv:1104.3915 (2011)
[21] Kloks, T., Wang, Y.L.: Advances in graph algorithms. Manuscipt of a book (2013)
[22] Liang, Y.D., Blum, N.: Circular convex bipartite graphs: maximum matching and Hamiltonian circuits. Inf. Process. Lett. 56, 215–219 (1995) · Zbl 0875.68698 · doi:10.1016/0020-0190(95)00145-3
[23] Liang, Y.D., Chang, M.S.: Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs. Acta Informatica 34, 337–346 (1997) · doi:10.1007/s002360050088
[24] Lu, M., Liu, T., Xu, K.: Independent Domination: Reductions from Circular- and Triad-Convex Bipartite Graphs to Convex Bipartite Graphs. In: Fellows, M., Tan, X., Zhu, B. (eds.) FAW-AAIM 2013. LNCS, vol. 7924, pp. 142–152. Springer, Heidelberg (2013) · Zbl 1303.05142 · doi:10.1007/978-3-642-38756-2_16
[25] Lu, Z., Liu, T., Xu, K.: Tractable Connected Domination for Restricted Bipartite Graphs (Extended Abstract). In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol. 7936, pp. 721–728. Springer, Heidelberg (2013) · Zbl 1382.68118 · doi:10.1007/978-3-642-38768-5_65
[26] 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) · Zbl 1154.05055 · doi:10.1016/j.disc.2007.08.007
[27] Song, Y., Liu, T., Xu, K.: Independent domination on tree convex bipartite graphs. In: Snoeyink, J., Lu, P., Su, K., Wang, L. (eds.) AAIM 2012 and FAW 2012. LNCS, vol. 7285, pp. 129–138. Springer, Heidelberg (2012) · Zbl 1304.68064 · doi:10.1007/978-3-642-29700-7_12
[28] Wang, C., Liu, T., Jiang, W., Xu, K.: Feedback vertex sets on tree convex bipartite graphs. In: Lin, G. (ed.) COCOA 2012. LNCS, vol. 7402, pp. 95–102. Springer, Heidelberg (2012) · Zbl 1301.05343 · doi:10.1007/978-3-642-31770-5_9
[29] Wang, F.H., Wang, Y.L., Chang, J.M.: Feedback vertex sets in star graphs. Inform. Process. Lett. 89(4), 203–208 (2004) · Zbl 1176.05081 · doi:10.1016/j.ipl.2003.11.001
[30] Yannakakis, M.: Node-deletion problem on bipartite graphs. SIAM J. Comput. 10, 310–327 (1981) · Zbl 0468.05044 · doi:10.1137/0210022
[31] Zhou, H.: The feedback vertex set problem: a spin glass approach. arXiv:1307.6948 (2013)
[32] Van Zuylen, A.: Linear programming based approximation algorithms for feedback set problems in bipartite tournaments. Theor. Comput. Sci. (in press) · Zbl 1241.68133 · doi:10.1007/978-3-642-02017-9_39
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.