論文の概要: (1,1)-Cluster Editing is Polynomial-time Solvable

• arxiv url: http://arxiv.org/abs/2210.07722v1
• Date: Fri, 14 Oct 2022 11:40:34 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-17 18:21:26.300437
• Title: (1,1)-Cluster Editing is Polynomial-time Solvable
• Title（参考訳）: (1,1)-クラスタ編集は多項式時間可解である
• Authors: Gregory Gutin and Anders Yeo
• Abstract要約: a*: V(G)rightarrow 0,1,dots, a and $d*: V(G)rightarrow 0,1,dots, a and $d*: V(G)rightarrow 0,1,dots, a and $d*: V(G)rightarrow 0,1,dots, a and $d*: V(G)rightarrow 0,1,dots, a and $d*
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A graph $H$ is a clique graph if $H$ is a vertex-disjoin union of cliques. Abu-Khzam (2017) introduced the $(a,d)$-{Cluster Editing} problem, where for fixed natural numbers $a,d$, given a graph $G$ and vertex-weights $a^*:\ V(G)\rightarrow \{0,1,\dots, a\}$ and $d^*{}:\ V(G)\rightarrow \{0,1,\dots, d\}$, we are to decide whether $G$ can be turned into a cluster graph by deleting at most $d^*(v)$ edges incident to every $v\in V(G)$ and adding at most $a^*(v)$ edges incident to every $v\in V(G)$. Results by Komusiewicz and Uhlmann (2012) and Abu-Khzam (2017) provided a dichotomy of complexity (in P or NP-complete) of $(a,d)$-{Cluster Editing} for all pairs $a,d$ apart from $a=d=1.$ Abu-Khzam (2017) conjectured that $(1,1)$-{Cluster Editing} is in P. We resolve Abu-Khzam's conjecture in affirmative by (i) providing a serious of five polynomial-time reductions to $C_3$-free and $C_4$-free graphs of maximum degree at most 3, and (ii) designing a polynomial-time algorithm for solving $(1,1)$-{Cluster Editing} on $C_3$-free and $C_4$-free graphs of maximum degree at most 3.
• Abstract（参考訳）: グラフ $H$ がclique グラフであれば、$H$ はclique の頂点非共役和である。 abu-khzam (2017) は $(a,d)$-{cluster editing} 問題を導入し、固定自然数 $a,d$ に対して、グラフ $g$ と頂点重み $a^*:\ v(g)\rightarrow \{0,1,\dots,a\}$ と $d^*{}:\ v(g)\rightarrow \{0,1,\dots,d\}$ が与えられたとき、$g$ が $v\in v(g)$ に対して最大$d^*(v)$ edges インシデントを削除できるかどうかを判断する。 komusiewicz と uhlmann (2012) と abu-khzam (2017) による結果は、すべてのペアに対して$a,d$ と$a=d=1.$ abu-khzam (2017) から離れて$(a,d)$-{cluster editing} の複雑性(p または np完全)の二分法を提供し、$(1,1)$-{cluster editing} が p にあると推測した。 (i)最大次数3の$C_3$-freeおよび$C_4$-freeグラフに真に5つの多項式時間還元を与える。 (ii)最大次数の$c_3$-free と $c_4$-free グラフ上で$(1,1)$-{cluster editing} を解く多項式時間アルゴリズムを設計する。

関連論文リスト

• A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering [10.697784653113095]
  すべてのクラスタ$C$とすべてのグループ$i in [ell]$に対して、$C$ from group $i$のポイント数は、他のグループ$j in [ell]$のポイントの数のt倍でなければならない。 私たちは、$ell=2$が一般的な均一容量$k$-medianに匹敵する難易度である場合にも、その問題を示します。
  論文  参考訳（メタデータ） (2024-05-16T18:17:44Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。 我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。 平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
  論文  参考訳（メタデータ） (2023-04-17T10:38:08Z)
• Repeated Averages on Graphs [2.363388546004777]
  我々は$frac(1-epsilon)2log2nlog n-O(n)$が$n$ノード上のすべての連結グラフに対する一般的な下界であることを証明する。 また、星、膨張星、ダンベル、サイクルなど、いくつかの重要なグラフの族に対して、$t_epsilon,1$の急激な等級も得られる。
  論文  参考訳（メタデータ） (2022-05-09T20:18:31Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
  本稿では, ErdHos--R'enyi グラフに対するグラフマッチングやネットワークアライメントの問題を扱う。 これはグラフ同型問題のうるさい平均ケース版と見なすことができる。
  論文  参考訳（メタデータ） (2021-10-11T05:07:50Z)
• Local Correlation Clustering with Asymmetric Classification Errors [12.277755088736864]
  相関クラスタリング問題では、エッジを"similar"と"dissimilar"とラベルした完全な重み付きグラフ$G$が与えられる。 クラスタリングの$mathcalC$ of graph $G$の場合、同じエッジが$mathcalC$、エンドポイントが別のクラスタに属している場合は$mathcalC$、エンドポイントが同じクラスタに属している場合は$mathcalC$と一致しない。 我々は$pgeq 1$に対する不一致ベクトルの$ell_p$ノルムを最小化するクラスタリングを生成する。
  論文  参考訳（メタデータ） (2021-08-11T12:31:48Z)
• A common variable minimax theorem for graphs [3.0079490585515343]
  我々は、$mathcalG$の全てのグラフに対して滑らかな非定数関数が存在するかどうかを同時に理解し、それが存在するかどうかをどうやって見つけるかという問題を研究する。
  論文  参考訳（メタデータ） (2021-07-30T16:47:25Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。