Efficient Algorithms for Partial Constraint Satisfaction Problems over Control-flow Graphs

• URL: http://arxiv.org/abs/2602.03588v1
• Date: Tue, 03 Feb 2026 14:38:10 GMT
• Title: Efficient Algorithms for Partial Constraint Satisfaction Problems over Control-flow Graphs
• Authors: Xuran Cai, Amir Goharshady,
• Abstract summary: We focus on the Partial Constraint Satisfaction Problem (PCSP) over control-flow graphs (CFGs) of programs.<n>PCSP serves as a generalization of the well-known Constraint Satisfaction Problem (CSP)<n>Our main contribution is a general algorithm for PCSPs over SPL graphs with a time complexity of (O(|G| cdot |D|6), where (|G|) represents the size of the control-flow graph.
• Score: 0.21485350418225244
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we focus on the Partial Constraint Satisfaction Problem (PCSP) over control-flow graphs (CFGs) of programs. PCSP serves as a generalization of the well-known Constraint Satisfaction Problem (CSP). In the CSP framework, we define a set of variables, a set of constraints, and a finite domain $D$ that encompasses all possible values for each variable. The objective is to assign a value to each variable in such a way that all constraints are satisfied. In the graph variant of CSP, an underlying graph is considered and we have one variable corresponding to each vertex of the graph and one or several constraints corresponding to each edge. In PCSPs, we allow for certain constraints to be violated at a specified cost, aiming to find a solution that minimizes the total cost. Numerous classical compiler optimization tasks can be framed as PCSPs over control-flow graphs. Examples include Register Allocation, Lifetime-optimal Speculative Partial Redundancy Elimination (LOSPRE), and Optimal Placement of Bank Selection Instructions. On the other hand, it is well-known that control-flow graphs of structured programs are sparse and decomposable in a variety of ways. In this work, we rely on the Series-Parallel-Loop (SPL) decompositions as introduced by~\cite{RegisterAllocation}. Our main contribution is a general algorithm for PCSPs over SPL graphs with a time complexity of \(O(|G| \cdot |D|^6)\), where \(|G|\) represents the size of the control-flow graph. Note that for any fixed domain $D,$ this yields a linear-time solution. Our algorithm can be seen as a generalization and unification of previous SPL-based approaches for register allocation and LOSPRE. In addition, we provide experimental results over another classical PCSP task, i.e. Optimal Bank Selection, achieving runtimes four times better than the previous state of the art.

Related papers

• Optimal Abstractions for Verifying Properties of Kolmogorov-Arnold Networks (KANs) [8.114307305249929]
  We present a novel approach for verifying properties of Kolmogorov-Arnold Networks (KANs)<n>Our key contribution is a systematic framework that exploits KAN structure to find optimal abstractions.<n>This approach determines the optimal approximation strategy for each unit while maintaining overall accuracy requirements.
  arXiv  Detail & Related papers  (2026-02-06T14:33:41Z)
• Inexact Column Generation for Bayesian Network Structure Learning via Difference-of-Submodular Optimization [8.09615396808421]
  State-of-the-art BNSL IP formulations suffer from the exponentially large number of variables and constraints.<n>A standard approach in IP to address such challenges is to employ row and column generation techniques.<n>We show that our row and column generation approach yields solutions with higher quality than state-of-the-art score-based approaches.
  arXiv  Detail & Related papers  (2025-05-16T10:23:19Z)
• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  We present a $textbfMA-OSMA$ algorithm to transfer the discrete submodular problem into a continuous optimization.<n>We also introduce a projection-free $textbfMA-OSEA$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution.<n>Our algorithms significantly improve the $(frac11+c)$-approximation provided by the state-of-the-art OSG algorithm.
  arXiv  Detail & Related papers  (2025-02-07T15:57:56Z)
• A Greedy Strategy for Graph Cut [95.2841574410968]
  We propose a greedy strategy to solve the problem of Graph Cut, called GGC.<n>It starts from the state where each data sample is regarded as a cluster and dynamically merges the two clusters.<n>GGC has a nearly linear computational complexity with respect to the number of samples.
  arXiv  Detail & Related papers  (2024-12-28T05:49:42Z)
• User-Level Differential Privacy With Few Examples Per User [73.81862394073308]
  We consider the example-scarce regime, where each user has only a few examples, and obtain the following results. For approximate-DP, we give a generic transformation of any item-level DP algorithm to a user-level DP algorithm. We present a simple technique for adapting the exponential mechanism [McSherry, Talwar FOCS 2007] to the user-level setting.
  arXiv  Detail & Related papers  (2023-09-21T21:51:55Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  Combinatorial optimization (CO) problems are often NP-hard and out of reach for exact algorithms. GFlowNets have emerged as a powerful machinery to efficiently sample from composite unnormalized densities sequentially. In this paper, we design Markov decision processes (MDPs) for different problems and propose to train conditional GFlowNets to sample from the solution space.
  arXiv  Detail & Related papers  (2023-05-26T15:13:09Z)
• Functional Constrained Optimization for Risk Aversion and Sparsity Control [7.561780884831967]
  Risk and sparsity requirements need to be enforced simultaneously in many applications, e.g., in portfolio optimization, assortment planning, and radiation planning. We propose a Level Conditional Gradient (LCG) method, which generates a convex or sparse trajectory for these challenges. We show that the method achieves a level single-set projection of the optimal value an inner conditional approximation (CGO) for solving mini-max sub gradient.
  arXiv  Detail & Related papers  (2022-10-11T02:51:51Z)
• A Deep Reinforcement Learning Framework For Column Generation [13.767526395378638]
  Column Generation (CG) is an iterative algorithm for solving linear programs with an extremely large number of variables (columns) We propose RLCG, the first Reinforcement Learning (RL) approach for CG. Unlike typical column selection rules which myopically select a column based on local information at each iteration, we treat CG as a sequential decision-making problem.
  arXiv  Detail & Related papers  (2022-06-03T03:58:54Z)
• COPS: Controlled Pruning Before Training Starts [68.8204255655161]
  State-of-the-art deep neural network (DNN) pruning techniques, applied one-shot before training starts, evaluate sparse architectures with the help of a single criterion -- called pruning score. In this work we do not concentrate on a single pruning criterion, but provide a framework for combining arbitrary GSSs to create more powerful pruning strategies.
  arXiv  Detail & Related papers  (2021-07-27T08:48:01Z)
• Generating Target Graph Couplings for QAOA from Native Quantum Hardware Couplings [3.2622301272834524]
  We present methods for constructing any target coupling graph using limited global controls in an Ising-like quantum spin system. Our approach is motivated by implementing the quantum approximate optimization algorithm (QAOA) on trapped ion quantum hardware. Noisy simulations of Max-Cut QAOA show that our implementation is less susceptible to noise than the standard gate-based compilation.
  arXiv  Detail & Related papers  (2020-11-16T18:43:09Z)
• Multiagent Rollout and Policy Iteration for POMDP with Application to Multi-Robot Repair Problems [1.6939372704265414]
  We consider infinite horizon discounted dynamic programming problems with finite state and control spaces, partial state observations, and a multiagent structure. Our methods specifically address the computational challenges of partially observable multiagent problems.
  arXiv  Detail & Related papers  (2020-11-09T06:51:50Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.