論文の概要: 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-25 18:36:24.528102
- 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:
- 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ハード問題の間の境界クラスと再現性の間に関係が生じる。
主な結果の強みを示すために、我々の定理を適用して、いくつかのグラフ問題、すなわち、頂点被覆、斜め、走行セール人、有界次数拡大木、部分グラフ同型および斜め被覆の既知境界クラスを得る。
関連論文リスト
- 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) - 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) - 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) - Partial Recovery in the Graph Alignment Problem [0.0]
エッジオーバーラップを最大化するノード間の1対1のマッピングである2つのグラフが与えられた場合、回復する問題を考察する。
この問題は、よく知られたグラフ同型問題のノイズバージョンと見なすことができる。
我々は、ある追加仮定の下で$nqs=Theta(1)$ regimeで部分的回復を達成することができることを示す。
論文 参考訳（メタデータ） (2020-07-01T14:57:53Z) - On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
論文 参考訳（メタデータ） (2019-06-02T03:03:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。