論文の概要: Computational Complexity of Edge Coverage Problem for Constrained Control Flow Graphs
- arxiv url: http://arxiv.org/abs/2602.18774v1
- Date: Sat, 21 Feb 2026 09:51:51 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-24 17:42:02.308401
- Title: Computational Complexity of Edge Coverage Problem for Constrained Control Flow Graphs
- Title（参考訳）: 制約付き制御フローグラフにおけるエッジ被覆問題の計算複雑性
- Authors: Jakub Ruszil, Artur Polański, Adam Roman, Jakub Zelek,
- Abstract要約: この記事では、明示的な制約で拡張された制御フローグラフのエッジカバレッジについて研究する。
この制約がエッジカバレッジの実現可能性と計算複雑性の両方にどのように影響するかを分析する。
- 参考スコア（独自算出の注目度）: 2.099922236065961
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The article studies edge coverage for control flow graphs extended with explicit constraints. Achieving a given level of white-box coverage for a given code is a classic problem in software testing. We focus on designing test sets that achieve edge coverage \textit{while respecting additional constraints} between vertices. The paper analyzes how such constraints affect both the feasibility and computational complexity of edge coverage. The paper discusses five types of constraints. POSITIVE constraints require at least one test path where a given vertex precedes another. NEGATIVE constraints forbid any such test path. ONCE constraints require exactly one test path with a single occurrence of one vertex before another. MAX ONCE constraints allow such precedence in at most one test path. ALWAYS constraints require every test path containing a given vertex to also contain another vertex later on the same path. Each type models a different test requirement, such as mandatory flows, semantic exclusions, or execution cost limits. We investigate the computational complexity of finding a test set that achieves edge coverage and respects a given set of constraints. For POSITIVE constraints, the existence of an edge covering test set is decidable in polynomial time by extending standard edge coverage constructions with additional paths for each constraint. For NEGATIVE, MAX ONCE, ONCE, and ALWAYS constraints, the decision problem is NP-complete. The proofs rely on polynomial reductions from variants of SAT. The NP-completeness results hold even for restricted graph classes, including acyclic graphs, for all these four constraints. Finally, we study the fixed-parameter tractability of the NEGATIVE constraint. Although the general problem is NP-complete, the paper presents an FPT algorithm with respect to the number of constraints.
- Abstract（参考訳）: この記事では、明示的な制約で拡張された制御フローグラフのエッジカバレッジについて研究する。
与えられたコードに対して所定のレベルのホワイトボックスカバレッジを達成することは、ソフトウェアテストにおいて古典的な問題である。
我々は,頂点間の制約を尊重するエッジカバレッジを実現するテストセットの設計に重点を置いている。
この制約がエッジカバレッジの実現可能性と計算複雑性の両方にどのように影響するかを分析する。
本稿は5種類の制約について論じる。
POSITIVE制約は、与えられた頂点が他の頂点に先行する少なくとも1つのテストパスを必要とする。
否定的な制約は、そのようなテストパスを禁止します。
ONCEの制約は、1つの頂点がもう1つ前に1つ発生した、正確に1つのテストパスを必要とする。
MAX ONCE制約は、少なくとも1つのテストパスにおいて、そのような優先順位を許す。
ALWAYSの制約は、与えられた頂点を含む全てのテストパスを、同じ経路上の他の頂点も含むように要求する。
各型は、必須フロー、セマンティック排他、実行コスト制限など、異なるテスト要件をモデル化する。
エッジカバレッジを達成し,与えられた制約を尊重するテストセットを見つけることの計算複雑性について検討する。
POSITIVE制約に対して、エッジ被覆テストセットの存在は、各制約に対して追加の経路を持つ標準エッジカバレッジ構造を拡張することで多項式時間で決定可能である。
NEGATIVE、MAX ONCE、ONCE、ALWAYSの制約に対して、決定問題はNP完全である。
証明はSATの変種からの多項式還元に依存する。
NP完全性の結果は、これらの4つの制約全てに対して非巡回グラフを含む制限グラフクラスに対しても成り立つ。
最後に, NEGative 制約の固定パラメータトラクタビリティについて検討する。
一般問題はNP完全であるが,本論文では制約数に関してFPTアルゴリズムを提案する。
関連論文リスト
- Adaptive Neighborhood-Constrained Q Learning for Offline Reinforcement Learning [52.03884701766989]
オフライン強化学習(RL)アルゴリズムは、通常、アクション選択に制約を課す。
本稿では,Bellmanターゲットにおける行動選択を,データセットアクションの近傍の結合に制限する新しい地区制約を提案する。
我々は,この制約を満たす目標動作を用いてQ学習を行うための,単純で効果的なアルゴリズムであるAdaptive Neighborhood-Constrained Q Learning(ANQ)を開発した。
論文 参考訳（メタデータ） (2025-11-04T13:42:05Z) - Cottontail: Large Language Model-Driven Concolic Execution for Highly Structured Test Input Generation [19.910389068755503]
CottontailはLLM(Large Language Model)による新しいコンコリック実行エンジンである。
より完全なプログラムパス表現であるExpressive Structure Coverage Tree (ESCT)が最初に構築され、構造を考慮したパス制約を選択する。
Solve-Complete パラダイムに基づく制約解法は、制約に適合するだけでなく、入力構文にも有効であるテスト入力を得るために、パス制約を解くように設計されている。
履歴誘導型シード取得を用いて、テスト開始前またはテストが飽和した後に、新しい高度に構造化されたテスト入力を得る。
論文 参考訳（メタデータ） (2025-04-24T13:32:20Z) - Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。
既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。
これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-04-21T17:15:48Z) - Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。
我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文 参考訳（メタデータ） (2024-08-21T20:14:54Z) - A Block Coordinate Descent Method for Nonsmooth Composite Optimization under Orthogonality Constraints [7.9047096855236125]
textbfOBCDは標準臨界点よりも高い最適性を示すことを示す。
また,textbfOBCDの非エルグ収束率を示す。
論文 参考訳（メタデータ） (2023-04-07T13:44:59Z) - Limited Query Graph Connectivity Test [14.108454811023465]
エッジが2つの可能な状態(On/Off)を持つグラフを考える。
我々は,経路(オンエッジのみの構成)とカット(オフエッジのみ構成)を識別し,s-t接続性をテストすることを目指している。
我々のモデルは主に、ネットワーク内に攻撃経路が存在するかどうかを確かめる必要があるサイバーセキュリティユースケースによって動機付けられている。
論文 参考訳（メタデータ） (2023-02-25T09:27:02Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - Gradient-Variation Bound for Online Convex Optimization with Constraints [25.002868073267464]
複数の機能的制約とユークリッド球のような比較的単純な制約セットからなる制約を持つオンライン凸最適化について検討する。
一階法は、$mathcalO(sqrtT)$ regret と $mathcalO(1)$ 制約違反を達成するが、問題の構造的情報を考慮してはならない。
本稿では,新しいオンライン原始双対ミラー-プロキシアルゴリズムによって得られる複雑な制約を伴って,オンライン凸最適化のインセンタンス依存バウンダリを提供する。
論文 参考訳（メタデータ） (2020-06-22T17:38:14Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文 参考訳（メタデータ） (2020-06-18T20:09:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。