Minimizing a Vertex Set Satisfying Specific Graph Properties

• Item type: SIG Technical Reports(1)
• 公開日: 2020-11-18
• タイトル: Minimizing a Vertex Set Satisfying Specific Graph Properties
• タイトル / 言語: en
• タイトル: Minimizing a Vertex Set Satisfying Specific Graph Properties
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Graduate School of Information Sciences, Tohoku University
• 著者所属: Graduate School of Information Sciences, Tohoku University
• 著者所属: Graduate School of Information Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University
• 著者名: Yuma, Tamura; Takehiro, Ito; Xiao, Zhou
• 著者名(英): Yuma, Tamura; Takehiro, Ito; Xiao, Zhou
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Let Π1, Π2, ...,Πc be graph properties for a fixed integer c. Then, (Π1, Π2, ...,Πc)-Partition is the problem of asking whether the vertex set of a given graph can be partitioned into c subsets V1, V2, ...,Vc such that the subgraph induced by Vi satisfies the graph property Πi for every i ∈ {1, 2, ...,c}. Minimization and parameterized variants of (Π1, Π2, ...,Πc)-Partition have been studied for several specific graph properties, where the size of the vertex subset V1 satisfying Π1 is minimized or taken as a parameter. In this paper, we first show that the minimization variant is hard to approximate for any nontrivial additive hereditary graph properties, unless c = 2 and both Π1 and Π2 are classes of edgeless graphs. We then give FPT algorithms for the parameterized variant when restricted to the case where c = 2, Π1 is a hereditary graph property, and Π2 is the class of acyclic graphs.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Let Π1, Π2, ...,Πc be graph properties for a fixed integer c. Then, (Π1, Π2, ...,Πc)-Partition is the problem of asking whether the vertex set of a given graph can be partitioned into c subsets V1, V2, ...,Vc such that the subgraph induced by Vi satisfies the graph property Πi for every i ∈ {1, 2, ...,c}. Minimization and parameterized variants of (Π1, Π2, ...,Πc)-Partition have been studied for several specific graph properties, where the size of the vertex subset V1 satisfying Π1 is minimized or taken as a parameter. In this paper, we first show that the minimization variant is hard to approximate for any nontrivial additive hereditary graph properties, unless c = 2 and both Π1 and Π2 are classes of edgeless graphs. We then give FPT algorithms for the parameterized variant when restricted to the case where c = 2, Π1 is a hereditary graph property, and Π2 is the class of acyclic graphs.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2020-AL-180, 号 4, p. 1-7, 発行日 2020-11-18
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会