在給定圖類II的II收縮問題中，對于任意的輸入圖G和參數k，該問題詢問能否收縮G中的至多k條邊使得到的新圖屬于類II。此問題與諸多圖算法問題相關聯，且在之前的文獻中有較多研究成果。 / 在本文中我們將研究圖收縮問題對于不同的類II的參數化復雜度。我們首先給出完全圖收縮問題的FPT算法。并且相較于另兩個已知的FPT問題：弦圖删邊問題及弦圖增邊問題，我們證明弦圖收縮問題是W[2]難問題。我們還將說明當H為一個特定的圈、路、星圖時，無H收縮問題是W[2]難問題，并且給出對所有連通度至少為3的圖H，無H收縮問題之參數化復雜度的一個完備界定。此外，我們證明了任意的無完全圖收縮問題、完全二分圖收縮問題以及分裂圖收縮問題都是FPT時間可解決，并且這些問題都不大可能包含多項式核心。 / 除此之外，我們將研究諸如點染色問題及支配集問題等經典NP難問題在一類特殊參數化圖上的參數化復雜度。 / 我們相信本文對于圖收縮問題的研究有著重要的貢獻，同時文中的一些思想和方法也將有助于對此問題進一步的研究。 / The II-Contraction problem is to determine whether an input graph G can be modified into a graph belonging to a desired class II by contracting at most k edges. It is closely related to graph minors and graph modification problems, and has been studied in the literature for several classes II. / In this thesis, we study parameterized complexity of II-Contraction problems in terms of graph classes II. We present FPT algorithms for Clique Contraction, which is the dual of a well-known FPT problem: Maximum Clique Minor. In contrast to FPT of Chordal Deletion and Chordal Completion, we prove the W[2]-hardness of Chordal Contraction. We also show that H-Free Contraction is W[2]-hard whenever H is a fixed graph that is a cycle C₁ for l≥4, an odd path P₁ for l≥5, a star K₁,[subscript r] for r≥4 or a diamond, and completely characterize the parameterized complexity of H-Free Contraction for every fixed 3-connected H. Moreover, we prove that K[subscript t]-free Contraction for every fixed t≥3, Biclique Contraction and Split Contraction are FPT but have no polynomial kernels unless NP ⊆ coNP/poly. / Furthermore, we study the parameterized complexity of some NP-complete classical problems such as Vertex Coloring and Dominating Set on F↑ke graphs, which are graphs that can be made into F-graphs by contracting at most k edges. / We believe that the thesis has made an important contribution to the study of graph contraction problems, and our ideas and techniques will be useful to future studies of graph contraction problems. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Guo, Chengwei. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 109-117). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Background --- p.3 / Chapter 1.1.1 --- Graph minors --- p.3 / Chapter 1.1.2 --- Graph modification problems --- p.4 / Chapter 1.1.3 --- Previous results for edge contraction --- p.5 / Chapter 1.2 --- Organization of the thesis --- p.6 / Chapter 2 --- Notation and definitions --- p.9 / Chapter 2.1 --- Basic notations on graphs --- p.9 / Chapter 2.2 --- Parameterized complexity --- p.12 / Chapter 3 --- FPT algorithms for -Contraction --- p.16 / Chapter 3.1 --- General results --- p.17 / Chapter 3.1.1 --- FPT algorithm for bounded-degree graphs --- p.17 / Chapter 3.1.2 --- Kernelization of special graph families --- p.18 / Chapter 3.1.3 --- Component theorem for H-Free Contraction . --- p.19 / Chapter 3.2 --- Contraction to clique-free graphs --- p.21 / Chapter 3.3 --- Contraction to cliques --- p.23 / Chapter 3.3.1 --- FPT algorithm for Clique Contraction --- p.24 / Chapter 3.3.2 --- Kernelization of Clique Contraction --- p.29 / Chapter 3.4 --- Contraction to bicliques --- p.32 / Chapter 3.4.1 --- Kernelization of Biclique Contraction --- p.33 / Chapter 3.5 --- Contraction to split graphs --- p.34 / Chapter 3.5.1 --- FPT algorithm for Split Contraction --- p.35 / Chapter 4 --- Hardness of H-Free Contraction --- p.40 / Chapter 4.1 --- Contraction to cycle-free graphs --- p.42 / Chapter 4.1.1 --- Cl-Free Contraction --- p.42 / Chapter 4.1.2 --- Chordal Contraction --- p.44 / Chapter 4.2 --- Contraction to path-free graphs --- p.45 / Chapter 4.2.1 --- Odd path --- p.45 / Chapter 4.2.2 --- Even path --- p.47 / Chapter 4.3 --- Contraction to star-free graphs --- p.49 / Chapter 4.4 --- Contraction to diamond-free graphs --- p.54 / Chapter 4.5 --- 3-connected H --- p.56 / Chapter 5 --- Incompressibility --- p.62 / Chapter 5.1 --- General techniques --- p.63 / Chapter 5.2 --- Incompressibility of clique-free contraction problems --- p.64 / Chapter 5.3 --- Incompressible of other -Contraction problems --- p.72 / Chapter 5.4 --- Conjecture for Clique Contraction --- p.77 / Chapter 6 --- Parameterized graph families --- p.81 / Chapter 6.1 --- Background and general results --- p.82 / Chapter 6.2 --- Clique ↑ ke graphs --- p.84 / Chapter 6.3 --- Other graph classes --- p.89 / Chapter 7 --- Concluding remarks --- p.93 / Chapter 7.1 --- Summary --- p.93 / Chapter 7.2 --- Open problems on edge contraction --- p.95 / Chapter 7.3 --- Related graph operations --- p.97 / Chapter 7.3.1 --- Vertex merging --- p.97 / Chapter 7.3.2 --- Neighborhood contraction --- p.99 / Chapter A --- Graph classes --- p.102 / Bibliography --- p.109
| Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_328193 |
| Date | January 2013 |
| Contributors | Guo, Chengwei, Chinese University of Hong Kong Graduate School. Division of Computer Science and Engineering. |
| Source Sets | The Chinese University of Hong Kong |
| Language | English, Chinese |
| Detected Language | English |
| Type | Text, bibliography |
| Format | electronic resource, electronic resource, remote, 1 online resource (x, 117 leaves) : ill. (some col.) |
| Rights | Use of this resource is governed by the terms and conditions of the Creative Commons “Attribution-NonCommercial-NoDerivatives 4.0 International” License (http://creativecommons.org/licenses/by-nc-nd/4.0/) |
Page generated in 0.0046 seconds