關於有唯一禁子圖的改邊問題的多項式核心無H加/删/加删邊問題求是否可能加/删/加删至多k條邊於一圖使其無任何與H同構的誘導子圖。此乃計算機科學基本問題之一，其研究廣泛。此題對任意固定H為NP完全且固定參數可解。本文研究無H改邊問題之多項式核心；其存在視H之結構而定。之分類在當H為一圈，路徑或三聯通圖時則完全，當H為删一邊於完全圖之結果時則近完全，當H為樹時則部分此結果加強對無H改邊問題之認識。本文的思路與工具益未來研究，或有助於無H改邊問題多項式核心存在二分定理之發現。 / The H-free edge completion (deletion, editing) problem asks whether it is possible to add to (delete from, add to and delete from) a graph at most k edges so that no induced sub graph isomorphic to H remains. These problems are fundamental in computer science and were studied extensively. They are NP-complete and fixed-parameter tractable for every fixed H. / In this thesis, we study polynomial kernels for H-free edge modification problems, as their existence depends on the structure of H. We characterise their existence completely when H is a path, cycle or 3-connected graph, almost completely when H is one edge short of a complete graph, and partially when H is a tree. / These results enhance our understanding of H-free edge modification problems significantly. Our ideas and tools can be useful to future studies and may lead eventually to a dichotomy theorem on the existence of polynomial kernels for H-free edge modification problems. / Detailed summary in vernacular field only. / Cai, Yufei. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 97-99). / 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 --- Preliminaries --- p.1 / Chapter 1.1 --- Edge modification problems and kernelisation --- p.2 / Chapter 1.2 --- Main results --- p.4 / Chapter 1.3 --- The lack of polynomial kernels --- p.5 / Chapter 1.4 --- Conventions and organisation --- p.8 / Chapter 2 --- Component Design --- p.11 / Chapter 2.1 --- Weighted satisficability on selective formulas --- p.12 / Chapter 2.2 --- 4-cycle --- p.15 / Chapter 2.3 --- The general scheme of component design --- p.20 / Chapter 2.4 --- Applications --- p.26 / Chapter 3 --- Local Alteration --- p.31 / Chapter 3.1 --- Bigger forbidden subgraphs from smaller ones --- p.32 / Chapter 3.2 --- Lifting the quarantine --- p.37 / Chapter 4 --- Circuit Implementation --- p.43 / Chapter 4.1 --- Monotone circuits --- p.44 / Chapter 4.2 --- Centralisation --- p.45 / Chapter 4.3 --- Implementation --- p.48 / Chapter 5 --- Kernel for Diamond-Free Edge Deletion --- p.55 / Chapter 5.1 --- Diamond-graphs --- p.56 / Chapter 5.2 --- The invariant things --- p.59 / Chapter 5.3 --- Correctness --- p.61 / Chapter 5.4 --- Lockets --- p.64 / Chapter 5.5 --- Representative systems of diamonds --- p.68 / Chapter 5.6 --- Kernel size --- p.70 / Chapter 6 --- Conclusions --- p.73 / Chapter 6.1 --- 3-connected forbidden subgraphs --- p.74 / Chapter 6.2 --- Cycles, paths and nearly complete graphs --- p.76 / Chapter 6.3 --- Trees --- p.77 / Chapter 6.4 --- Open problems --- p.79 / Chapter A --- List of Trees --- p.81 / Chapter B --- List of Problems --- p.83 / Chapter C --- Glossary --- p.87 / Chapter D --- Bibliography --- p.96
| Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_328005 |
| Date | January 2012 |
| Contributors | Cai, Yufei., 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 (iv, iv, 99 leaves) : ill. |
| 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.0026 seconds