本篇論文主要研究的問題是在雙向旋轉圖和四價凱利圖上的回饋問題(feedback problem)。回饋問題分為兩類：針對點和邊分別稱為回饋點集合(feedback vertex set)及回饋邊集合(feedback arc set)。
圖G=(V,E)的一個回饋點集合F是圖G中點集合V的一個子集合，而且當F從G中移除後，剩下的點所形成的圖形將不會有任何環路(cycle)存在；同樣的，回饋邊集合H是圖G中邊集合E的一個子集合，而且當H從G中被移除後，剩下的邊所形成圖也將不會有任何環路存在。
雙向旋轉圖(bi-rotator graph)是具有相當優良的拓樸特性的一種互連網路(interconnection network)，例如點對稱(node symmetry)、邊對稱(edge symmetry)的拓樸特性，使得在這種網路之上諸如繞徑(routing)、容錯繞徑(fault-tolerant routing) 等等的研究工作容易進行。四價凱利圖(quadrivalent cayley graph)亦是凱利圖類的圖，擁有每個節點皆為分支度(degree)為4的良好特性，比其他的凱利圖類的圖形結構來的優秀。
最後在本篇論文當中，我們提出了在雙向旋轉圖上利用維度為4的最小回饋點集合個數來推導出在高維度時的回饋點集合上界，而在四價凱利圖中的趨近最小回饋點集合演算法，我們是利用了四價凱利圖中節點的連結特性找出兩個互斥的獨立點集合，再分別討論所加入節點是否產生環路而得到趨近於最小回饋點集合演算法。

In this thesis, we address the feedback problems in bi-rotator graphs and quadrivalent cayley graphs. The feedback problem is divided into two kinds: feedback vertex set and feedback arc set.
A feedback vertex set of a graph G = (V, E) is a subset of vertices F to belong to V whose removal from G induces an acyclic graph G’= (V’, E’) with V’= V\F and E’= {(u, v) ∈ E : u,v ∈ E’}. Similary, a feedback arc set of a graph G is a subset of arcs H to belong to E whose removal from G induces an acyclic graph.
A bi-rotator graph, an interconnection network, has the excellent topological properties. For example, node symmetry and edge symmetry make those research works, routing and fault-tolerant routing on bi-rotator graphs, simple. Compared to other cayley graphs, quadrivalent cayley graphs have a good property of the constant degree 4.
In the end, we bargain that an upper bound of the feedback vertex set in the bi-rotator graphs, deduce from BR(4)(short for the size：4 in bi-rotator graph). In the quadrivalent cayley graphs, we find out the two disjoint sets by connection property. When the set accede to the graph, we are anticipate does it have any cycle, then getting an algorithm was closing with the minimal feedback vertex set algorithm.

[1] S.B. Akers and B.Krishnamurthy, A group theoretic model for symmetric interconnecton networks, IEEE Transcation on Computers, vol.38, pp. 555-566, (1989)
[2] V. Bafna, P. Berman, and T. Fujito, A 2-approximation algorithm for the undirected feedback vertex set problem, SIAM J.Discrete Math, pp.289–297 (1999).
[3] R. Bar-Yehuda, D. Geiger, J. Naor, and R.M. Roth, Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference, SIAMJ. Comput, pp. 942–959 (1998).
[4] S. Bau, L.W. Beineke, Z. Liu, G. Du, R.C. Vandell, Decycling cubes and grids, Utilitas Math. vol.59, pp.129–137 (2001).
[5] J.C. Bermond, C. Peyrat, De Bruijn and Kautz networks, a competitor for the hypercube, Hypercube and Distributed Computers, Elsevier Science Publishers, North-Holland, pp.278–293 (1989).
[6] I. Caragiannis , C. Kaklamanis, and P. Kanellopoulos, New bounds on the size of the minimum feedback vertex set in meshes and butterflies, Information Processing Letters vol.83 pp.275–280 (2002).
[7] M.R. Carey and D.S. Johnson, Computers and Intractability, Freeman, San Francisco, CA (1979).
[8] I. Caragiannis, Ch. Kaklamanis and P. Kanellopoulos, New bounds on the size of the minimum feedback vertex set in meshes and butterflies, Information Processing Letters, vol.83, no.5, pp.75–80 (2002).
[9] P. Festa, P.M. Pardalos, and M.G.C. Resende, Feedback set problems, in: D.-Z. Du, P.M. Pardalos (Eds.), Handbook of Combinatorial Optimization, Vol. A, Kluwer Academic Publisher, Dordrecht, pp.209 (1999).
[10] R. Focardi, F.L. Luccio, and D. Peleg, Feedback vertex set in hypercubes, Information Processing Letters, vol.76, pp.1–5 (2000).
[11] M.M. Flood, Exact and heuristic algorithm for the weighted feedback arc set problem: A special case of the skew-symmetric qyadratic assignment problem, Network, vol.20, pp.19-32 (1967).
[12] R. Flotd, Assigning Meaning to Programs, In Proceedings of Symposium on Applied Mathematics, vol.XIX, pp.19-32 (1967).
[13] D. Gusfield, A graph theoretic approach to statistical data security, SIAM Journal on Computing, vol.17, no.3, pp.552-571 (1998).
[14] M.R. Garey, and D.S. Johnson, Computers and Intractability, Freeman, San Francisco, CA (1979).
[15] D. Kratsch, H. Muller, and I. Todinca, feedback vertex set and longest induced path on AT-free graphs, Graph-Theoretic Conceots in Computer Science-29th International Workshop, WG 2003, pp.309-321 Springer-Verlag (2003).
[16] R. Kralovic, and P. Ruzicka, Minimum feedback vertex sets in shuffle-based interconnection networks, Information Processing Letters, vol.86, no.4, pp.191–196 (2003).
[17] J. Kleinberg, and A. Kumar, Wavelength conversion in optical networks, in: Proc. 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 99), pp.566–575 (1999).
[18] F.T. Leighton, Introduction to Parallel Algorithms and Architectures, Morgan Kaufmann, Los Altos, CA (1992).
[19] Y.D. Liang and M.S. Chang, Minimum feedback vertex set in comparability graphs and convex bipartite graphs, Acta Inform, vol.34, pp.337–346 (1997).
[20] C. Lu and C. Tang, A linear-time algorithm for the weighted feedback vertex problem on interval graphs, Information Processing Letters, vol.61, no.2, pp.107–112 (1997).
[21] F.L. Luccio, Almost exact minimum feedback vertex set in meshes and butterflies, Information Processing Letters, vol.66, pp.59–64 (1998).
[22] E.L. Llyod and M.L. Soffa, On locating minimum feedback vertex sets, J. Comput. System Sci, vol.37 pp.292-3 (1988).
[23] Y.D. Liang, On the feedback vertex set in permutation graphs, Information Processing Letters, vol.52, pp.123–129 (1994).
[24] B. Monien and R. Schultz, Four approximation algorithm for the feedback vertex set problems, 7th Conference on Graph Theoretic Concepts of Computer Science, Hanser-Verlan, Munich, pp.315-326 (1981).
[25] I. Niven and H.S. Zuckerman, An Introduction to the Theory of Number, Wiley, New York (1980).
[26] D. Peleg, Local majority voting, small coalitions and controlling monopolies in graphs: A review, in: Proc. 3rd Colloquium on Structural Information and Communication Complexity (SIROCCO 96), pp.152–169 (1996).
[27] D. Peleg, Size bounds for dynamic monopolies, in: Proc. 4th Colloquium on Structural Information and Communication Complexity, Carleton Univ. Press, Ottawa, pp.165-175 (1997).
[28] A. Shamir, A linear time algorithm for finding minimum cutsets in reducible graphs, SIAM J. Comput, vol.8, no.4 pp.645–655 (1979).
[29] G.W. Smith and R.B.Walford, The identification of a minimal feedback vertex set of a directed graph, IEEE Trans. Circuits and Systems, CAS-22, pp.9–15 (1975).
[30] O. Togni, Placement de convertisseurs de longueurs d’ondes dans les réseaux optiques, in: Proc. ALGOTEL (2000).
[31] J.D. Ullman, Computational Aspects of VLSI, Computer Science Press, Rockville, MD (1984).
[32] C. Wang, E.L. Lloyd, and M.L. Sofra, Feedback vertex sets and cyclically reducible graphs, J. ACM, vol.32, no.2, pp.296–313 (1985).
[33] J.M. Xu, Y.Z. Wu, J. Huang, and C. Yang, Feedback numbers of Kautz digraphs, Discrete Mathematics (2006).
[34] C.C. Wang, E.L. Lloyd, and M.L. Soffa, Feedback vertex sets and cyclically reducible graphs, J. Assoc. Comput, Mach. 32 pp.296–313 (1985).
[35] F.H. Wang, C.J. Hsu, and J.C. Tsai, Minimal feedback vertex sets in directed split-stars, Networks, vol.45, no.4, pp.218–223 (2005).
[36] F.H. Wang, Y.L. Wang, and J.M. Chang, Feedback vertex sets in star graphs, Information Processing Letters, vol.60,no.4,pp.203-208 (2004).
[37] J.M. Xu, Topological Structure and Analysis of Interconnection Networks, Kluwer Academic Publishers, Dordrecht/Boston/London, (2001).
[38] M. Yannakakis, Node-deletion problem on bipartite graphs, SIAM Journal on Computing, vol.10, pp.310-327 (1981).