K3 Edge Cover Problem in a Wide Sense

• Item type: Journal(1)
• 公開日: 2020-12-15
• タイトル: K3 Edge Cover Problem in a Wide Sense
• タイトル / 言語: en
• タイトル: K3 Edge Cover Problem in a Wide Sense
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [特集：離散と計算の幾何・グラフ・ゲーム] graphs, clique, edge cover, spilling-out, NP-complete, FPT, tree-width
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: School of Informatics and Engineering, The University of Electro-Communications (UEC)
• 著者所属: School of Informatics and Engineering, The University of Electro-Communications (UEC)
• 著者所属: School of Informatics and Engineering, The University of Electro-Communications (UEC)
• 著者所属: Université Paris-Dauphine, PSL University, CNRS, LAMSADE
• 著者所属: Faculty of Core Research Natural Science Division Ochanomizu University
• 著者所属: Graduate School of Informatics, Nagoya University
• 著者所属(英): en
• 著者所属(英): School of Informatics and Engineering, The University of Electro-Communications (UEC)
• 著者所属(英): en
• 著者所属(英): School of Informatics and Engineering, The University of Electro-Communications (UEC)
• 著者所属(英): en
• 著者所属(英): School of Informatics and Engineering, The University of Electro-Communications (UEC)
• 著者所属(英): en
• 著者所属(英): Université Paris-Dauphine, PSL University, CNRS, LAMSADE
• 著者所属(英): en
• 著者所属(英): Faculty of Core Research Natural Science Division Ochanomizu University
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Nagoya University
• 著者名: Kyohei, Chiba; Réemy, Belmonte; Hiro, Ito; Michael, Lampis; Atsuki, Nagao; Yota, Otachi
• 著者名(英): Kyohei, Chiba; Réemy, Belmonte; Hiro, Ito; Michael, Lampis; Atsuki, Nagao; Yota, Otachi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: In this study, we consider a problem, for a given graph G = (V, E), of finding the minimum number of 3-cliques (K3s) that cover all edges of G. Multiple covering or covering one edge by more than one 3-clique is allowed. Moreover, in this problem, we allow “spilling-out,” i.e., a set of three vertices {x, y, z} can be covered by a 3-clique even if the induced subgraph by them is not a clique. We call this problem K3 edge cover problem in a wide sense. This problem is a kind of extension of the schoolgirl problem and finite projective planes, and it has applications on experimental designs. Allowing spilling-out is useful for some applications: E.g., when we want to compare n items through some tries of experiments, in which at most three items can be compared simultaneously, and pairs of items that must be compared are given by a graph, finding the minimum number of tries is formalized as this problem. In the known literature, there are many results that considered problems for covering vertices or edges by the minimum number of cliques. However, there is no theoretical result that considers spilling-out. We obtain the following results: (1) The problem is NP-hard even if graphs are restricted to planar, cubic, and C4, C5-free in a sense of subgraphs (i.e., not restricted to induced ones). (2) For the problem with a parameter k, which is the number of 3-cliques in G, there is an O(mn + 2km)-time algorithm. (3) If a tree-decomposition of tree-width t is given, there is an O(22(t+1)(t+2)t2n)-time algorithm.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.28(2020) (online); DOI http://dx.doi.org/10.2197/ipsjjip.28.849; ------------------------------
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this study, we consider a problem, for a given graph G = (V, E), of finding the minimum number of 3-cliques (K3s) that cover all edges of G. Multiple covering or covering one edge by more than one 3-clique is allowed. Moreover, in this problem, we allow “spilling-out,” i.e., a set of three vertices {x, y, z} can be covered by a 3-clique even if the induced subgraph by them is not a clique. We call this problem K3 edge cover problem in a wide sense. This problem is a kind of extension of the schoolgirl problem and finite projective planes, and it has applications on experimental designs. Allowing spilling-out is useful for some applications: E.g., when we want to compare n items through some tries of experiments, in which at most three items can be compared simultaneously, and pairs of items that must be compared are given by a graph, finding the minimum number of tries is formalized as this problem. In the known literature, there are many results that considered problems for covering vertices or edges by the minimum number of cliques. However, there is no theoretical result that considers spilling-out. We obtain the following results: (1) The problem is NP-hard even if graphs are restricted to planar, cubic, and C4, C5-free in a sense of subgraphs (i.e., not restricted to induced ones). (2) For the problem with a parameter k, which is the number of 3-cliques in G, there is an O(mn + 2km)-time algorithm. (3) If a tree-decomposition of tree-width t is given, there is an O(22(t+1)(t+2)t2n)-time algorithm.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.28(2020) (online); DOI http://dx.doi.org/10.2197/ipsjjip.28.849; ------------------------------
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 61, 号 12, 発行日 2020-12-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764