zbMATH — the first resource for mathematics

Feedback vertex set in hypercubes. (English) Zbl 1338.68218
Summary: Given a graph \(G= (V, E)\), the minimum feedback vertex set \(\overline{V}\) is a subset of vertices of minimum size whose removal induces an acyclic subgraph \(G'= (V \backslash\overline{V}, E')\). The problem of finding \(\overline{V}\) is \(\operatorname{NP}\)-hard for general networks but interesting polynomial solutions have been found for particular graph classes. In this paper we find close upper and lower bounds to the size of \(\overline{V}\) in a \(k\)-dimensional hypercube.

68R10 Graph theory (including graph drawing) in computer science
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI Link
[1] Bar-Yehuda, R.; Geiger, D.; Naor, J.; Roth, R.M., Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference, SIAM J. comput., Vol. 27, 4, 942-959, (1998) · Zbl 0907.68110
[2] Festa, P.; Pardolos, P.M.; Resende, M.G.C., Feedback set problems, (1999), revised version to appear in: Encyclopedia of Optimization, Kluwer Academic Publisher, Dordrecht, Netherlands, 2000
[3] Garey, M.R.; Johnson, D.S., Computers and intractability, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[4] Johnson, D.S., Approximation algorithms for combinatorial problems, J. comput. system sci., Vol. 9, 256-278, (1974) · Zbl 0296.65036
[5] Liang, Y.D., On the feedback vertex set in permutation graphs, Inform. process. lett., Vol. 52, 3, 123-129, (1994) · Zbl 0822.68083
[6] Liang, Y.D.; Chang, M.S., Minimum feedback vertex set in cocomparability graphs and convex bipartite graphs, Acta inform., Vol. 34, 337-346, (1997)
[7] Lloyd, E.L.; Soffa, M.L., On locating minimum feedback vertex sets, J. comput. system sci., Vol. 37, 292-311, (1988) · Zbl 0661.68065
[8] Lu, C.; Tang, C., A linear-time algorithm for the weighted feedback vertex problem on interval graphs, Inform. process. lett., Vol. 61, 2, 107-112, (1997)
[9] Luccio, F.L., Exact minimum feedback vertex set in meshes and butterflies, Inform. process. lett., Vol. 66, 2, 59-64, (1998) · Zbl 0925.68196
[10] MacWilliams, F.J.; Sloane, N.J.A., The theory of error-correcting codes, (1978), North-Holland Amsterdam · Zbl 0369.94008
[11] Peleg, D., Local majority voting, small coalitions and controlling monopolies in graphs: A review, (), 152-169
[12] Peleg, D., Size bounds for dynamic monopolies, Discrete appl. math., Vol. 86, 2-3, 263-273, (1998) · Zbl 0910.90286
[13] Peterson, W.W.; Weldon, E.J., Error-correcting codes, (1972), MIT Press Cambridge, MA · Zbl 0251.94007
[14] Shamir, A., A linear time algorithm for finding minimum cutsets in reducible graphs, SIAM J. comput., Vol. 8, 4, 645-655, (1979) · Zbl 0422.05029
[15] Smith, G.W.; Walford, R.B., The identification of a minimal feedback vertex set of a directed graph, IEEE trans. circuits systems, Vol. CAS-22, 1, 9-14, (1975)
[16] Wang, C.; Lloyd, E.L.; Soffa, M.L., Feedback vertex sets and cyclically reducible graphs, J. ACM, Vol. 32, 2, 296-313, (1985) · Zbl 0633.68064
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.