論文の概要: Reducibility among NP-Hard graph problems and boundary classes
- arxiv url: http://arxiv.org/abs/2411.14553v1
- Date: Thu, 21 Nov 2024 19:49:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-28 17:07:50.010612
- Title: Reducibility among NP-Hard graph problems and boundary classes
- Title（参考訳）: NP-Hardグラフ問題と境界クラス間の還元可能性
- Authors: Syed Mujtaba Hassan, Shahid Hussain, Abdul Samad,
- Abstract要約: 多くのNPハードグラフ問題はグラフのクラスでは容易になり、例えば色付けは二部グラフでは容易であるが、一般にNPハードである。
問題が残る最小限のサブ構造は何か。
このような問題の研究には境界クラスの概念を用いる。
- 参考スコア（独自算出の注目度）: 0.8031975687812146
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Many NP-hard graph problems become easy for some classes of graphs, such as coloring is easy for bipartite graphs, but NP-hard in general. So we can ask question like when does a hard problem become easy? What is the minimum substructure for which the problem remains hard? We use the notion of boundary classes to study such questions. In this paper, we introduce a method for transforming the boundary class of one NP-hard graph problem into a boundary class for another problem. If $\Pi$ and $\Gamma$ are two NP-hard graph problems where $\Pi$ is reducible to $\Gamma$, we transform a boundary class of $\Pi$ into a boundary class of $\Gamma$. More formally if $\Pi$ is reducible to $\Gamma$, where the reduction is bijective and it maps hereditary classes of graphs to hereditary classes of graphs, then $X$ is a boundary class of $\Pi$ if and only if the image of $X$ under the reduction is a boundary class of $\Gamma$. This gives us a relationship between boundary classes and reducibility among several NP-hard problems. To show the strength of our main result, we apply our theorem to obtain some previously unknown boundary classes for a few graph problems namely; vertex-cover, clique, traveling-salesperson, bounded-degree-spanning-tree, subgraph-isomorphism and clique-cover.
- Abstract（参考訳）: 多くのNPハードグラフ問題はグラフのクラスでは容易になり、例えば色付けは二部グラフでは容易であるが、一般にNPハードである。
では、難しい問題がいつ容易になるのか、という疑問を問うことができます。
問題が残る最小限のサブ構造は何か。
このような問題の研究には境界クラスの概念を用いる。
本稿では,NP-hardグラフ問題の境界クラスを別の問題に対する境界クラスに変換する手法を提案する。
もし$\Pi$と$\Gamma$が2つのNPハードグラフ問題であり、$\Pi$が$\Gamma$に還元可能であるなら、$\Pi$の境界クラスを$\Gamma$の境界クラスに変換する。
より正式には、$\Pi$ が $\Gamma$ に還元可能であり、グラフの遺伝クラスをグラフの遺伝クラスにマッピングするならば、$X$ は $\Pi$ の境界クラスであり、その還元の下での$X$ の像が $\Gamma$ の境界クラスである場合に限り、$X$ は $\Pi$ の境界クラスである。
これにより、いくつかのNPハード問題の間の境界クラスと再現性の間に関係が生じる。
主な結果の強みを示すために、我々の定理を適用して、いくつかのグラフ問題、すなわち、頂点被覆、斜め、走行セール人、有界次数拡大木、部分グラフ同型および斜め被覆の既知境界クラスを得る。
関連論文リスト
- Minimizing the number of edges in LC-equivalent graph states [0.0]
あるグラフ状態を別のグラフにマッピングする局所クリフォード演算は、エッジの数の変更を含む対応するグラフの構造を変更することができる。
ここでは、与えられたグラフのLC等価クラスにおいて、最小限のエッジ数を持つグラフを見つけるという、関連するエッジ最小化問題に取り組む。
論文 参考訳（メタデータ） (2025-05-30T22:49:45Z) - Exponential speedup of quantum algorithms for the pathfinding problem [5.260626311429307]
溶接木に基づいてグラフ$G$を構築し、隣接リスト oracle $O$ でパスフィニング問題を定義する。
古典的なアルゴリズムが確率の高い指数時間で$x$-$y$パスを見つけることはできないことを証明している。
我々の発見は、量子アルゴリズムがパスフィニング問題を解決するために、より多くの種類のグラフに利点をもたらす可能性があることを示唆している。
論文 参考訳（メタデータ） (2023-07-24T02:50:34Z) - Quantum computing algorithms for inverse problems on graphs and an
NP-complete inverse problem [2.107421958337625]
有限グラフ $(X,E)$ に対する逆問題を考える。
この問題には特定の条件下でのユニークな解法があることを示し、量子計算法を開発した。
論文 参考訳（メタデータ） (2023-06-08T14:48:48Z) - Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。
複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
論文 参考訳（メタデータ） (2023-06-05T15:35:00Z) - One-step Bipartite Graph Cut: A Normalized Formulation and Its
Application to Scalable Subspace Clustering [56.81492360414741]
両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。
本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。
このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
論文 参考訳（メタデータ） (2023-05-12T11:27:20Z) - 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) - Planted Bipartite Graph Detection [13.95780443241133]
ランダムグラフに隠れた二部グラフを検出するタスクについて検討する。
ヌル仮説の下では、このグラフは、エッジ密度$q$の$n$上のアードホスラーイランダムグラフの実現である。
k_mathsfR times k_mathsfL$ bipartite subgraph with edge density $p>q$。
論文 参考訳（メタデータ） (2023-02-07T18:18:17Z) - Discrete Bulk Reconstruction [4.467248776406005]
ブラックホールの内部などの領域を再構築したい場合,AdS/CFTは指数関数的に複雑であることを示す。
また,複数の1次元境界がワームホールを介して接続される場合にも,初期進行が見られた。
論文 参考訳（メタデータ） (2022-10-27T16:39:29Z) - Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
我々は、Ksubseteq G$ の部分群に基づく境界の体系的な扱いを、バルクの Kokuev 量子倍 D(G)$ モデルで提供する。
境界サイトは$*$-subalgebra $Xisubseteq D(G)$の表現であり、その構造を強い$*$-準ホップ代数として説明する。
治療の応用として、水平方向の$K=G$と垂直方向の$K=e$に基づく境界付きパッチを調査し、量子コンピュータでどのように使用できるかを示す。
論文 参考訳（メタデータ） (2022-08-12T15:05:07Z) - Zero Pixel Directional Boundary by Vector Transform [77.63061686394038]
我々は境界を1次元曲面として再解釈し、1対1のベクトル変換関数を定式化し、クラス不均衡問題を完全に回避する境界予測の訓練を可能にする。
我々の問題定式化は、境界の方向推定だけでなく、よりリッチなコンテキスト情報もたらし、もし望めば、訓練時にもゼロピクセルの薄い境界が利用可能となる。
論文 参考訳（メタデータ） (2022-03-16T17:55:31Z) - Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm
and Application to 3D Multi-Shape Analysis [69.08838724594584]
グラフ内の最短経路を見つけることは、コンピュータビジョンやグラフィックスにおける多くの問題に関係している。
本稿では,行列値のエッジを持つグラフにおいて,最短経路のグラフ理論を新たに導入する。
論文 参考訳（メタデータ） (2021-12-08T08:23:37Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Inferring Hidden Structures in Random Graphs [13.031167737538881]
本研究では,ランダムなグラフ上に植えられた群集群集の検出と復元の2つの推論問題について検討する。
我々は、パラメータ $(n,k,q)$ や $Gamma_k$ の特定の性質の観点から、構造を検出・復元するための下限を導出し、これらの下限を達成するための計算学的に最適なアルゴリズムを示す。
論文 参考訳（メタデータ） (2021-10-05T09:39:51Z) - Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov
Random Fields [51.07460861448716]
本稿では,データから学ぶための凸解析フレームワークを提案する。
三角凸分解はその上部に対応する変換によって保証されることを示す。
論文 参考訳（メタデータ） (2021-09-17T17:46:12Z) - Impossibility of Partial Recovery in the Graph Alignment Problem [3.5880535198436156]
我々は、よく知られたNPハードグラフ同型問題の平均ケースとノイズバージョンを示す。
相関式 Erd"os-R'enyi モデルでは、スパース状態における部分的回復の不可能な結果が証明される。
我々の境界はノイズのない場合(グラフ同型問題)において厳密であり、まだノイズに密接であると予想する。
論文 参考訳（メタデータ） (2021-02-04T15:26:48Z) - Partial Recovery in the Graph Alignment Problem [0.0]
エッジオーバーラップを最大化するノード間の1対1のマッピングである2つのグラフが与えられた場合、回復する問題を考察する。
この問題は、よく知られたグラフ同型問題のノイズバージョンと見なすことができる。
我々は、ある追加仮定の下で$nqs=Theta(1)$ regimeで部分的回復を達成することができることを示す。
論文 参考訳（メタデータ） (2020-07-01T14:57:53Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文 参考訳（メタデータ） (2020-06-18T20:09:53Z) - On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
論文 参考訳（メタデータ） (2019-06-02T03:03:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。