論文の概要: On Structural Parameterizations of the Offensive Alliance Problem

• arxiv url: http://arxiv.org/abs/2110.15757v1
• Date: Fri, 29 Oct 2021 13:12:54 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-01 18:38:44.328007
• Title: On Structural Parameterizations of the Offensive Alliance Problem
• Title（参考訳）: 攻撃アライアンス問題の構造パラメータ化について
• Authors: Ajinkya Gaikwad and Soumen Maity
• Abstract要約: 攻撃アライアンス問題のパラメータ化複雑性について検討する。 目的は、最小規模の攻勢同盟を見つけることである。 この問題は、かなり制限的な構造パラメータの広い範囲でW[1]-ハードパラメータ化されていることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Offensive Alliance problem has been studied extensively during the last twenty years. A set $S\subseteq V$ of vertices is an offensive alliance in an undirected graph $G=(V,E)$ if each $v\in N(S)$ has at least as many neighbours in $S$ as it has neighbours (including itself) not in $S$. We study the parameterized complexity of the Offensive Alliance problem, where the aim is to find a minimum size offensive alliance. Our focus here lies on parameters that measure the structural properties of the input instance. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that the problem is W[1]-hard parameterized by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, treewidth, pathwidth, and treedepth of the input graph.
• Abstract（参考訳）: 攻撃同盟問題は過去20年間に広く研究されてきた。 頂点の集合 $S\subseteq V$ は無向グラフ $G=(V,E)$ における攻撃同盟であり、各$v\in N(S)$ が少なくとも$S$ の近傍を持つならば、$S$ の近傍(自身を含む)は$S$ ではない。 我々は,最小サイズの攻撃同盟を見つけることを目的とした攻撃同盟問題のパラメタライズド複雑性について検討する。 ここでの焦点は、入力インスタンスの構造特性を測定するパラメータにあります。 本稿では,入力グラフのフィードバック頂点集合数,木幅,パス幅,木深さなど,かなり制約のある構造パラメータの広い範囲で,w[1]ハードな問題であることを示すことで,パラメータ化複雑性の観点から,この問題の理解を深める。

関連論文リスト

• Reducibility among NP-Hard graph problems and boundary classes [0.8031975687812146]
  多くのNPハードグラフ問題はグラフのクラスでは容易になり、例えば色付けは二部グラフでは容易であるが、一般にNPハードである。 問題が残る最小限のサブ構造は何か。 このような問題の研究には境界クラスの概念を用いる。
  論文  参考訳（メタデータ） (2024-11-21T19:49:33Z)
• Exact Algorithms and Lowerbounds for Multiagent Pathfinding: Power of Treelike Topology [0.0]
  我々は、与えられたグラフの$G上の一組の$kエージェントの経路を効率的に見つけることに重点を置いており、各エージェントはそのソースからターゲットへの経路を求める。 解の質の重要な尺度は提案されたスケジュールの長さ$ell$、すなわち最長経路の長さである。 MAPFは$G$+$ell$に対してW[1]ハードであり、FPTは$G$+$ell$であることを示す。
  論文  参考訳（メタデータ） (2023-12-15T09:42:46Z)
• Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
  ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。 複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
  論文  参考訳（メタデータ） (2023-06-05T15:35:00Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。 低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
  論文  参考訳（メタデータ） (2023-02-13T22:51:07Z)
• The Sample Complexity of Online Contract Design [120.9833763323407]
  オンライン環境での隠れアクションの主エージェント問題について検討する。 各ラウンドにおいて、主席は、各結果に基づいてエージェントへの支払いを指定する契約を投稿する。 エージェントは、自身のユーティリティを最大化する戦略的な行動選択を行うが、プリンシパルによって直接観察できない。
  論文  参考訳（メタデータ） (2022-11-10T17:59:42Z)
• Discrete Bulk Reconstruction [4.467248776406005]
  ブラックホールの内部などの領域を再構築したい場合,AdS/CFTは指数関数的に複雑であることを示す。 また,複数の1次元境界がワームホールを介して接続される場合にも,初期進行が見られた。
  論文  参考訳（メタデータ） (2022-10-27T16:39:29Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。 グラフの構造は知られており、ノードは$N$である。 頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T16:21:31Z)
• A simple geometric proof for the benefit of depth in ReLU networks [57.815699322370826]
  本論文では, 多層フィードフォワードネットワークにおける深度の利点を, 整流活性化(深度分離)により証明する。 我々は、線形深さ($m$)と小さな定数幅($leq 4$)を持つ具体的なニューラルネットワークを示し、問題をゼロエラーで分類する。
  論文  参考訳（メタデータ） (2021-01-18T15:40:27Z)
• Intervention Efficient Algorithms for Approximate Learning of Causal Graphs [22.401163479802094]
  我々は、潜時の存在下で観察された変数の集合間の因果関係を学習する問題を研究する。 我々の目標は、介入の最小限の費用で、すべての因果関係や祖先関係の方向性を$G$で回収することです。 我々のアルゴリズムは効率的な介入設計と低コストな分離集合系の設計を組み合わせる。
  論文  参考訳（メタデータ） (2020-12-27T17:08:46Z)
• Partial Recovery in the Graph Alignment Problem [0.0]
  エッジオーバーラップを最大化するノード間の1対1のマッピングである2つのグラフが与えられた場合、回復する問題を考察する。 この問題は、よく知られたグラフ同型問題のノイズバージョンと見なすことができる。 我々は、ある追加仮定の下で$nqs=Theta(1)$ regimeで部分的回復を達成することができることを示す。
  論文  参考訳（メタデータ） (2020-07-01T14:57:53Z)
• Structured Linear Contextual Bandits: A Sharp and Geometric Smoothed Analysis [48.25118610209545]
  本稿では,ガウス雑音によって逆向きの文脈が乱されるような構造付き線形文脈帯域のスムーズな設定について考察する。 単純な欲求アルゴリズムが機能するスムーズな環境では暗黙的な探索が存在することを示す。
  論文  参考訳（メタデータ） (2020-02-26T07:29:24Z)

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

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