論文の概要: A Customized SAT-based Solver for Graph Coloring

• arxiv url: http://arxiv.org/abs/2504.04821v1
• Date: Mon, 07 Apr 2025 08:22:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-08 14:09:25.031676
• Title: A Customized SAT-based Solver for Graph Coloring
• Title（参考訳）: グラフカラー化のためのSAT-based Solverのカスタマイズ
• Authors: Timo Brand, Daniel Faber, Stephan Held, Petra Mutzel,
• Abstract要約: 本稿では,ZykovColorという新しいSATベースのアルゴリズムを導入し,グラフの着色問題を解く。 H'ebrard と Katsirelos (2020) のアプローチに基づく。 SATソルバの基盤となる利点を生かした新機能を提案する。
• 参考スコア（独自算出の注目度）: 4.214684816231388
• License:
• Abstract: We introduce ZykovColor, a novel SAT-based algorithm to solve the graph coloring problem working on top of an encoding that mimics the Zykov tree. Our method is based on an approach of H\'ebrard and Katsirelos (2020) that employs a propagator to enforce transitivity constraints, incorporate lower bounds for search tree pruning, and enable inferred propagations. We leverage the recently introduced IPASIR-UP interface for CaDiCal to implement these techniques with a SAT solver. Furthermore, we propose new features that take advantage of the underlying SAT solver. These include modifying the integrated decision strategy with vertex domination hints and using incremental bottom-up search that allows to reuse learned clauses from previous calls. Additionally, we integrate a more efficient clique computation to improve the lower bounds during the search. We validate the effectiveness of each new feature through an experimental analysis. ZykovColor outperforms other state-of-the-art graph coloring implementations on the DIMACS benchmark set. Further experiments on random Erd\H{o}s-R\'enyi graphs show that our new approach dominates state-of-the-art SAT-based methods for both very sparse and highly dense graphs.
• Abstract（参考訳）: そこで我々はZykovColorという新しいSATベースのアルゴリズムを導入し,Zykovツリーを模倣するエンコーディング上のグラフカラー化問題を解く。 提案手法はH'ebrard and Katsirelos (2020) のアプローチに基づいており、この手法は伝達制約を強制し、探索木刈りの下位境界を組み込み、推定伝搬を可能にするプロパゲータを用いている。 我々は最近導入されたCaDiCalのIPASIR-UPインタフェースを活用し、SATソルバを用いてこれらの手法を実装した。 さらに,その基盤となるSATソルバを利用する新機能を提案する。 これには、頂点支配ヒントによる統合決定戦略の変更や、前回の呼び出しから学んだ節を再利用可能なインクリメンタルボトムアップ検索の使用が含まれる。 さらに,探索時の下界を改善するために,より効率的な斜め計算を統合する。 実験により,各新機能の有効性を検証した。 ZykovColorは、DIMACSベンチマークセットの他の最先端グラフカラー実装よりも優れています。 ランダムな Erd\H{o}s-R\'enyi グラフに関するさらなる実験は、我々の新しいアプローチが非常にスパースグラフと高密度グラフの両方に対して最先端のSATベースの手法を支配していることを示している。

関連論文リスト

• Smart Cubing for Graph Search: A Comparative Study [15.989407883187962]
  立方体とコンカヤによる並列解法はSATソルバをハードインスタンスに拡張するための重要な方法である。 キューブ・アンド・コンカーは純粋なSAT問題に対して成功したが、SATソルバへの応用はプロパゲータによって拡張され、ユニークな課題が提示される。 本研究では, SATモジュロ対称性(SMS)を用いて, 対称性を破るプロパゲータが等方性グラフを除去する制約を学習することで探索空間を減少させる問題について検討する。
  論文  参考訳（メタデータ） (2025-01-27T22:15:54Z)
• GraSS: Combining Graph Neural Networks with Expert Knowledge for SAT Solver Selection [45.222591894755105]
  インスタンスの3部グラフ表現に基づくSATソルバ自動選択のための新しいアプローチであるGraSSを提案する。 我々は、新しいノードの特徴設計のようなドメイン固有の決定でグラフ表現を豊かにします。 生の表現とドメイン固有の選択の組み合わせが実行時の改善につながることを実証する。
  論文  参考訳（メタデータ） (2024-05-17T18:00:50Z)
• SAT Encoding of Partial Ordering Models for Graph Coloring Problems [4.816747047269009]
  グラフ着色問題と帯域幅着色問題に対する部分順序付けベースLPモデルの新たなSAT符号化を提案する。 広く研究されているGCPでは、新しいSATエンコーディングとDIMACSベンチマークセットの最先端アプローチを実験的に比較する。 理論解析により,部分順序付きSATとILPの定式化は古典的代入ベースモデルよりも大幅に小さいことがわかった。
  論文  参考訳（メタデータ） (2024-03-23T23:48:41Z)
• torchmSAT: A GPU-Accelerated Approximation To The Maximum Satisfiability Problem [1.5850859526672516]
  最大満足度問題(MaxSAT)の解を近似できる単一の微分可能関数を導出する。 我々は,我々の微分可能な関数をモデル化する新しいニューラルネットワークアーキテクチャを提案し,バックプロパゲーションを用いてMaxSATを段階的に解く。
  論文  参考訳（メタデータ） (2024-02-06T02:33:00Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。 提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
  論文  参考訳（メタデータ） (2022-01-05T13:37:27Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  本稿では,データから学ぶための凸解析フレームワークを提案する。 三角凸分解はその上部に対応する変換によって保証されることを示す。
  論文  参考訳（メタデータ） (2021-09-17T17:46:12Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• Propositional Encodings of Acyclicity and Reachability by using Vertex Elimination [5.482532589225551]
  本稿では,非巡回性およびs-t-到達可能性制約を基礎となる有向グラフを持つ命題公式に対して符号化する新しい手法を提案する。 提案手法はこれらの制約を標準命題節として符号化し,SATソルバに直接適用する。
  論文  参考訳（メタデータ） (2021-05-27T01:57:53Z)
• Sequential Graph Convolutional Network for Active Learning [53.99104862192055]
  逐次グラフ畳み込みネットワーク(GCN)を用いた新しいプールベースアクティブラーニングフレームワークを提案する。 少数のランダムなサンプル画像がシードラベル付き例であるので、グラフのパラメータを学習してラベル付きノードと非ラベル付きノードを区別する。 我々はGCNの特性を利用してラベル付けされたものと十分に異なる未ラベルの例を選択する。
  論文  参考訳（メタデータ） (2020-06-18T00:55:10Z)
• Heuristic Semi-Supervised Learning for Graph Generation Inspired by Electoral College [80.67842220664231]
  本稿では,新たなノードやエッジを自動的に拡張して,高密度サブグラフ内のラベル類似性を向上する,新しい前処理手法であるElectoral College(ELCO)を提案する。 テストされたすべての設定において、我々の手法はベースモデルの平均スコアを4.7ポイントの広いマージンで引き上げるとともに、常に最先端のモデルよりも優れています。
  論文  参考訳（メタデータ） (2020-06-10T14:48:48Z)

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

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