Solving Subgraph Extraction Problems Using $Δ$Search

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Solving Subgraph Extraction Problems Using $Δ$Search

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cloud distributedcomputing parallelcomputing

distributed computing, parallel computing, cloud

Solving Subgraph Extraction Problems Using ΔSearch

arXiv:2606.13834v1 [cs.PF] 11 Jun 2026

REBIN SILVA VALAN ARASU, University of California Riverside, USA RAJIV GUPTA, University of California Riverside, USA Many NP-hard graph problems can be modeled as optimal subgraph extraction problems with feasibility constraints. From Network Design to Facility Location, from Robotics to Graph Drawing, the subgraph extraction pattern emerges across diverse domains. Despite this commonality, these problems are typically solved with domain-specific heuristics. Usually, these problems balance competing objectives such as maximizing coverage or minimizing cost while satisfying structural constraints such as connectivity, planarity and reachability. In this work, we introduce ΔSearch, a general and fast heuristic framework that exploits the insight of RewardPenalty optimization for solving a large class of subgraph extraction problems. The framework is easy to use as it only requires feasibility constraints and optimality criteria to be provided by the user to express the subgraph extraction problem. We also show how exact methods can be augmented with ΔSearch to improve their performance by aggressive pruning of the search space. We evaluate our framework on monotone graph problems such as Maximum Planar Subgraph (MPS) and Minimum Connected Dominating Set, Weighted Monotone problems such as Maximum Weighted Independent Set and Minimum Weighted Steiner Tree, and non-monotone graph problems such as Prize Collecting Vertex Cover (PCVC) and Uncapacitated Facility Location Problem (UFLP). Our results show that ΔSearch matches or surpasses state of the art heuristics for MPS, UFLP and PCVC problems with similar runtime. For the remaining problems, ΔSearch achieves approximately 89% of the solution quality of the state-of-the-art algorithms without any problem-specific tuning. CCS Concepts: • Theory of computation → Graph algorithms analysis; Facility location and clustering; Approximation algorithms analysis; Optimization with randomized search heuristics; Parallel algorithms; Backtracking; Random search heuristics; • Computing methodologies → Parallel algorithms. Additional Key Words and Phrases: Hereditary Graph Problems, Subgraph extraction, Combinatorial optimization, Heuristic Search, NP-hard problems, Delta Debugging, N-way parallelism ACM Reference Format: Rebin Silva Valan Arasu and Rajiv Gupta. 2026. Solving Subgraph Extraction Problems Using ΔSearch. In Proceedings of conference title (Conference ’XX). ACM, New York, NY, USA, 27 pages. https://doi.org/XXXXXXX. XXXXXXX

Introduction

NP-hard subgraph extraction problems are abundant in computer science with applications across multiple domains such as Bioinformatics [3, 95], Network Design [10, 29, 94], Robotics [54], Logistics [24, 92] and other domains. Thus, there is a need for a general framework that domain experts can use without needing expertise in graph algorithms. A graph framework that only requires what makes a good solution and not how to search for it would be ideal. Therefore, the goal of this paper Authors’ Contact Information: Rebin Silva Valan Arasu, University of California Riverside, Riverside, California, USA, [email protected]; Rajiv Gupta, University of California Riverside, Riverside, California, USA, rajivg@ ucr.edu. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. Conference ’XX, Woodstock, NY © 2026 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-1-4503-XXXX-X/2026/10 https://doi.org/XXXXXXX.XXXXXXX

, Vol. 1, No. 1, Article . Publication date: June 2026.

R.S. Valan Arasu et al.

is to present a novel and efficient way of solving this broad class of subgraph extraction problems with just the problem statement and without any problem-specific tuning or implementation. Current graph frameworks are either exact algorithms with exponential worst-case runtime that require minimal user effort [2, 79, 89] or approximate heuristics that are scalable but require extensive problem-specific tuning [44, 46, 83, 84, 100]. Numerous heuristics and metaheuristics have been developed to tackle the intractability of graph problems. Heuristics lack generality as they are tailored to individual problems. Although metaheuristics are designed to solve a large class of problems, encoding these problems into a form suitable for these metaheuristics is non-trivial [44]. The user must perform these complex problem encodings to use these metaheuristics, and thus metaheuristics achieve generality and practical runtime at the cost of increased user effort for each new problem instance. Multiple exact works have also been proposed. Constraint Programming (CP) [16, 33, 79] and Mixed Integer Linear Programming (MILP) [2, 4, 36] are two general exact exponential frameworks that can solve multiple graph problems including Facility Location, Graph Partitioning and Subgraph selection. But exactness comes at the cost of performance. These exact frameworks can typically scale only to graphs with 100 to 200 edges [21, 25]. Thus, these frameworks are slow and graph-structure unaware, and they require problem-specific tuning to achieve good performance. The framework that is closest to achieving generality is Local Ratio [7], an approximate algorithm that can be applied to multiple graph problems. Local Ratio achieves this by a user-provided approximate algorithm for simpler instances of the problem, which is then repeatedly applied to the given graph to achieve the same approximation ratio as the simpler instance. Although this approach achieves generality, it requires the presence of a problem-specific approximate algorithm for simpler instances and user effort to generate this approximate algorithm. From the above works, we can conclude that although ease of use and generality are known to be important for subgraph extraction frameworks, most frameworks sacrifice either one or both for computational efficiency. This relentless pursuit of computational runtime has also resulted in most of the frameworks being heavily tailored to the problem instances, limiting their generality. In this paper, we introduce ΔSearch, a subgraph extraction framework that only takes graph feasibility constraints and objective functions and produces good heuristic solutions for a large class of graph problems with solution quality competitive with tailored heuristics. Since both of these functions are usually part of the problem statement itself, the burden on the user is greatly reduced. Through its simpler unified interface, ΔSearch sidesteps the issues faced by heuristics and metaheuristics. Although general approximation ratios cannot be given for all the problems solvable by ΔSearch, it achieves approximations comparable to the greedy algorithm, since both the algorithms will always find maximal or minimal solutions. For example, ΔSearch inherits the 1/3-approximation of the greedy algorithm [20] for the Maximum Planar Subgraph problem [56]. Most optimal subgraph extraction problems require both balancing competing objectives such as maximizing coverage or minimizing costs and satisfying structural constraints such as connectivity, planarity, and reachability. Thus, the central idea of ΔSearch is that many subgraph extraction problems can be expressed as finding a subset of graph elements such as vertices or edges that maximizes the difference between reward and penalty functions. We refer to this Reward-Penalty decomposition, which we introduce, as the Difference of Monotone (DoM) formulation. This formulation is expressive enough to subsume existing frameworks such as Hereditary graph problems [15], Ancestral graph problems [73] and also cover other graph problems (Prize Collecting Arc Routing problem [5], Uncapacitated Facility Location Problem [24]). Formulating graph problems as Difference of Monotone (DoM) subgraph optimization problems is compelling for several reasons. First, it aligns closely with real world problem objectives such as cohesion, coverage, and structural feasibility, which typically increases or decreases monotonically , Vol. 1, No. 1, Article . Publication date: June 2026.

Solving Subgraph Extraction Problems Using ΔSearch

Fig. 1. Exact algorithm augmented with the ΔSearch Framework.

as graph elements are added. Second, the Reward-Penalty idea of DoM formulation is simpler and intuitive than more complicated submodularity or convexity assumptions. Third, the DoM formulation covers a wide range of problems as can be seen from Table 1, enabling the development of general-purpose frameworks and solvers that apply broadly across graph domains. ΔSearch performs a binary search-like exploration in the DoM search space. This simplicity in the core algorithm is what allows ΔSearch to be both efficient and general. Just as Fuzz Testing [98] generates many simple test cases rather than computing highly complex ones, we realized that running a simpler algorithm like ΔSearch multiple times usually outperforms designing a single highly engineered algorithm. Thus, we designed ΔSearch which runs the scoring (optimality) function at most quadratic times to the number of graph elements. To further demonstrate the usefulness of ΔSearch, we show how it can augment exact methods, such as the Russian Doll Search [89] method, to help prune the exponential search space (see Figure 1). The augmented exact method works by mutually sharing solutions between the exact and heuristic ΔSearch, thereby pruning the search in each and accelerating them both. By sharing the solutions, ΔSearch is directed toward regions not yet explored by the exact algorithm, and the exact algorithm prunes its explorations based on solutions found by the faster ΔSearch. Although exponential time algorithms such as Branch and Bound [70] can be applied to multiple problems, by combining these exact algorithms with the fast ΔSearch heuristic, we accelerate their search by aggressive pruning. While problem-specific pruning heuristics exist, to the best of our knowledge, this work is the first to accelerate an exact algorithm using a general heuristic. Even though problems like the shortest path problem can be converted into a hereditary problem and then expressed in our framework, the benefit of using our framework for the shortest path is limited since our framework cannot compete with exact linear time algorithms tailored for shortest path. The ΔSearch framework is best suited for NP-hard graph problems whose objective function can be expressed as a DoM function. However, expressing the objective function as a DoM function may not always be possible. If the objective function cannot be expressed as a DoM function, but can still be approximated by one, ΔSearch can still be employed. In summary, this paper makes the following contributions: (1) We introduce a new formulation for graph problems called Difference of Monotone (DoM) that encompasses a large class of graph problems including ancestral (e.g., Minimum Connected Dominating Set [29], Minimum Steiner Tree [60]), hereditary (e.g., Maximum Planar Subgraph Problem [56], Maximum Weighted Independent set [88]), and some other non-monotone graph problems (e.g., Prize Collecting Vertex Cover problem [57], Uncapacitated Facility Location Problem [24]). This new formulation generalizes the monotone graph problem class such as Hereditary and Ancestral graph problem classes while preserving the opportunities for efficient search space pruning explored in previous works [89]. (2) We introduce ΔSearch, which can find approximate solutions for DoM subgraph optimization problems with 𝑂 (𝑛 2 ) calls to the scoring function. ΔSearch also provides a simple interface where the user only needs to supply the scoring functions to the framework. Thus, the user , Vol. 1, No. 1, Article . Publication date: June 2026.

R.S. Valan Arasu et al.

can rapidly find solutions to wide variety of graph problems easily with only at most 𝑂 (𝑛 2 ) calls to the scoring functions. (3) We evaluate our framework on six subgraph selection problems: Maximum Planar Subgraph (MPS), Minimum Weighted Steiner Tree (MST), Maximum Weighted Independent Set (MWIS), Minimum Connected Dominating Set (MCDS), Prize Collecting Vertex Cover (PCVC) and Uncapacitated Facility Location Problem (UFLP). Experimental evaluations showed that ΔSearch matches or surpasses existing algorithms for MPS, UFLP and PCVC problems and also achieves approximately 89% of the best known solution quality for other problems. (4) We demonstrate the efficiency of ΔSearch as a heuristic bound that accelerates exact frameworks. We integrate ΔSearch into an exact framework to reduce the search space of the exact algorithm by pruning search directions leading to inferior solutions. Our experiments show that the ΔSearch augmented exact algorithm achieves a 2.639× speedup over the exact algorithm for the Maximum Planar Subgraph problem. The remainder of this paper is organised as follows. Section 2 presents the DoM formulation and its applications. Section 3 describes the ΔSearch algorithm and its complexity. Section 4 presents our system design and explains how the interface works. Section 5 reports the experimental results of ΔSearch across six graph problems and Section 5.3 explains how ΔSearch can be combined with exact algorithms to accelerate the exact search. Section 6 surveys prior work on general graph optimization frameworks. Finally, Section 7 concludes the paper. 2

Difference of Monotone (DoM) Framework

Most real world subgraph extraction problems involve optimizing an objective function while minimizing cost. Examples of such problems include facility location problems where the goal is to maximize service coverage while minimizing facility setup and operational costs, or vehicle routing problems where the goal is to maximize the number of deliveries while minimizing time or fuel spent. These problems can be naturally modeled as the difference between a monotonically increasing reward function and a penalty function. The monotonicity is important as it captures the intuition that adding elements to a subgraph should not decrease the reward or penalty, and it also enables efficient search strategies. In simpler terms, the Difference of Monotone (DoM) optimization function is a function that can be expressed as the difference between a reward and a penalty function i.e., a function that can be expressed as 𝑅(𝑆𝐺) − 𝑃 (𝑆𝐺) where the reward function 𝑅 and the penalty function 𝑃 are monotonically increasing functions. In mathematical terms, any problem of the following form can be solved using this framework: Find 𝑆𝐺 ⊆ 𝐺 that maximizes 𝑅(𝑆𝐺) − 𝑃 (𝑆𝐺), where 𝑅 and 𝑃 are monotone non-decreasing functions. Examples of problems with DoM functions can be seen in Table 1. Additionally, Figures 2 and 3 show the behavior of these problems when their respective graph elements are added in some random order. The plots illustrate that the difference of the reward and penalty usually rises initially with graph element additions but later falls down due to the high penalty. Figure 3 also shows that there might be multiple maxima for the difference between reward and penalty. Finally, note that these maxima pertain to this particular order of addition of graph elements; the global maximum might not be present in one of these maxima and a different ordering might be able to produce the global maximum for these problems. As we shall see in this subsection, the DoM framework naturally generalizes Hereditary [93] and Ancestral [73] graph problems that have been studied in prior works. It also covers graph problems such as Prize Collecting Vertex cover (PCVC) and Uncapacitated Facility Location (UFLP) problems that are neither hereditary nor ancestral. Table. 1 lists multiple graph problems that can be formulated as DoM problems and its subclasses Hereditary and Ancestral problems. Note , Vol. 1, No. 1, Article . Publication date: June 2026.

Solving Subgraph Extraction Problems Using ΔSearch

Table 1. 𝐶𝑃 ⊃ 𝑀𝐼𝐿𝑃 ⊃ 𝐷𝑜𝑀 ⊃ (𝐻𝑒𝑟𝑒𝑑𝑖𝑡𝑎𝑟𝑦 ∪ 𝐴𝑛𝑐𝑒𝑠𝑡𝑟𝑎𝑙) & 𝐻𝑒𝑟𝑒𝑑𝑖𝑡𝑎𝑟𝑦 ∩ 𝐴𝑛𝑐𝑒𝑠𝑡𝑟𝑎𝑙 = ∅. Note that 𝐶𝑃, 𝑀𝐼𝐿𝑃 and Hereditary are all NP-hard problems. Class of Problems Graph Problems Constraint Optimization Problems (COP) Mixed Integer Linear Programming (MILP)

Difference of Monotone (DoM) Monotone - Hereditary

Monotone - Ancestral

Graph coloring [51], Traveling Salesman [90], Balanced Graph Partitioning, Subgraph Isomorphism [96] Capacitated Facility Location [91], Minimum Flow Decomposition [35], Graph Edit Distance [31], Crossing Number Problem [23], Minimum Chordal Completion [9], Capacitated Minimum Spanning Tree [45], Clique Partitoning Problem [59] Uncapacitated Facility Location [24], Prize Collecting Steiner Tree [10], Prize Collecting Arc Routing [5], Prize Collecting Vertex Cover [57], Budgeted Weighted Steiner Tree [71] Maximum Planar Subgraph [56], Maximum Independent Set [88], Maximum Agreement Subtree [3], Maximum k-defective clique [95], Maximum s-plex problem [74], Maximum Matching [42], Maximum s-bundle graph [64], Maximum s-club problem [81], Maximum Bipartite subgraph, Maximum k-Vertex Cover [67], Maximum Degree-Bounded Connected Subgraph [66] Minimum Constraint Removal [54], Minimum Steiner Tree [60], Minimum Connected Dominating Set [29], Capacitated Vertex Cover [52], Minimum Feedback Arc Set [6], Minimum Equivalent Digraph [72]

that the class of Constraint Optimization Problems (COP) and Mixed Integer Linear Programming (MILP) problems is much more general than the DoM framework. Thus, DoM framework achieves a balance between generality and structure for efficient search. 2.1

Monotone Problems

The largest class of graph problems under DoM subgraph optimization problems is the weighted hereditary graph problems. A constraint function is said to be hereditary if all subgraphs of the graph satisfy the constraint given that the graph itself satisfies the constraint. Given a set of positive weighted graph elements, the weighted hereditary problem is to find the subgraph with the maximum total weight that satisfies the given constraint. The weight function of hereditary problems can be made into a DoM objective function by defining the reward function as the sum of the weights of the candidates and the penalty function as 0 if it satisfies the hereditary constraint and ∞ otherwise. For example, Hereditary problems such as Maximum Planar Subgraph problems can be solved by ΔSearch with the reward function equal to the number of edges and the penalty function 0 when the subgraph is planar and ∞ when the graph is not planar. ( 0 if S is planar 𝑆𝑐𝑜𝑟𝑒 (𝑆𝐺) = 𝑅(𝑆𝐺) − 𝑃 (𝑆𝐺) = |𝐸 (𝑆𝐺)| − ∞ else Clearly, the above function is a DoM function. As graph elements are added, both the reward and penalty functions increase monotonically. The reward function increases with the number of edges and the penalty function increases monotonically since subgraphs of planar graphs are planar and supergraphs of non-planar graphs are non-planar. The penalty function can be constructed using a linear time Left-Right planarity test [32]. Consider another hereditary problem: Maximum Weighted Independent Set, where the objective is to find the maximum weight set of vertices that are not adjacent to each other. Unlike the Maximum Planar Subgraph problem, this is an induced subgraph problem (vertex selection) and it , Vol. 1, No. 1, Article . Publication date: June 2026.

R.S. Valan Arasu et al.

Graph element

Hereditary

Ancestral

Maximum Planar Subgraph Problem

Minimum (weighted) Steiner Tree Problem

Maximum Weighted Independent Set

Minimum Connected Dominating Set

Edge

Vertex Fig. 2. The behavior of rewards, negative penalties and total scores of various monotone graph problems with insertion of graph elements in a random ordering.

is also a weighted problem rather than just selection. This problem can be modeled using DoM as follows: ( 0 if |𝐸𝐺 (𝑆𝐺)| = 0 𝑆𝑐𝑜𝑟𝑒 (𝑆𝐺) = 𝑅(𝑆𝐺) − 𝑃 (𝑆𝐺) = Σ𝑣 ∈𝑉𝐺 (𝑆𝐺 ) 𝑤 (𝑣) − ∞ else Ancestral problems which are defined similarly to Hereditary problems can also be formulated easily. A constraint function is said to be ancestral if all super-graphs of a graph satisfy the constraint given that the graph itself satisfies the constraint. For example, the score function of the Minimum (weighted) Steiner tree problem over vertex set 𝐴 ⊆ 𝑉 (𝐺) can be defined as follows: ( 0 if SG spans over all terminals 𝑆𝑐𝑜𝑟𝑒 (𝑆𝐺) = 𝑅(𝑆𝐺) − 𝑃 (𝑆𝐺) = − Σ𝑒 ∈ |𝐸 (𝐺 ) | 𝑤 (𝑒) −∞ else In the above Minimum Steiner Tree formulation, the penalty is the total weight of edges since the objective is to find a minimum tree and the reward is −∞ when the subgraph doesn’t span over all terminals. Note that there is no constraint to make sure that the resulting graph is a tree because any minimal solution will always be a tree. Like hereditary problems, induced ancestral subgraph problems can also be formulated in DoM formulation. For example, the Minimum Connected Dominating Set problem can be formulated as: ( 0 if 𝑉𝐺 (𝑆𝐺) is a connected dominating set 𝑆𝑐𝑜𝑟𝑒 (𝑆𝐺) = 𝑅(𝑆𝐺) − 𝑃 (𝑆𝐺) = − |𝑉𝐺 (𝑆𝐺)| −∞ else , Vol. 1, No. 1, Article . Publication date: June 2026.

Solving Subgraph Extraction Problems Using ΔSearch

The Hereditary and Ancestral graph problems are together known as the Monotone graph problems. Thus, DoM formulation allows the user to formulate any monotone, weighted or unweighted, subgraph or induced-subgraph problems easily with reward and penalty functions. As we have seen, the DoM framework is based on the idea that adding graph elements may improve one criterion to be covered while inducing another penalty to be paid. This Reward-Penalty standoff is the basis of the DoM framework. Note that any linear combination of monotone objective functions can be translated into a DoM function by grouping the monotonically increasing functions as the reward function and grouping the monotonically decreasing functions as the penalty function. This can be seen by considering the following linear combination of monotonically increasing 𝐼𝑖 s and monotonically decreasing 𝐷𝑖 s: 𝑜𝑏 𝑗 (𝑆𝐺) = Σ𝛼𝑖 𝐼𝑖 (𝑆𝐺) + Σ𝛽𝑖 𝐷𝑖 (𝑆𝐺) + Σ𝑖 𝛾𝑖 = (Σ𝛼𝑖 ≥0𝛼𝑖 𝐼𝑖 + Σ𝛽𝑖 <0 𝛽𝑖 𝐷𝑖 ) (𝑆𝐺) − ( −Σ𝛼𝑖 <0𝛼𝑖 𝐼𝑖 − Σ𝛽𝑖 ≥0 𝛽𝑖 𝐷𝑖 ) (𝑆𝐺) + | {z } | {z } Monotonically Increasing Reward

Monotonically Increasing Penalty

Σ𝑖 𝛾𝑖 |{z} Constants that can be ignored

= 𝑅(𝑆𝐺) − 𝑃 (𝑆𝐺) (1) The above proof hinges on the two facts that (i) Monotone functions are closed under addition and positive scalar multiplication and (ii) The negation of a monotonically decreasing function is a monotonically increasing function and vice versa. Thus, our formulation can work even in the presence of multiple objective functions, given that all of them are monotone. Given multiple objective functions, the above proof also provides a way to formulate it as a DoM objective function. 2.2

Non-monotone Problems

Apart from monotone problems such as Hereditary and Ancestral problems, other intricately scored problems such as Uncapacitated Facility Location Problem (UFLP), Prize Collecting Vertex Cover (PCVC), etc., as can be seen from Table 1, can also be modeled by our formulation. In Prize Collecting Vertex Cover Problem, one must find a set of vertices that covers all edges except for the edges that one is willing to be penalized for. Thus, in PCVC, the objective is to find the vertex set with minimum sum of vertex weights and penalized edges. 𝑆𝑐𝑜𝑟𝑒 (𝑆𝐺) = −Σ𝑒 ∈𝐸𝐺 (𝐺\𝑆𝐺 ) 𝑤 𝐸 (𝑒) − Σ𝑣 ∈𝑉𝐺 (𝑆𝐺 ) 𝑤𝑉 (𝑣) = (−Σ𝑒 ∈𝐸𝐺 (𝐺\𝑆𝐺 ) 𝑤 𝐸 (𝑒)) − (Σ𝑣 ∈𝑉𝐺 (𝑆𝐺 ) 𝑤𝑉 (𝑣)) = 𝑅(𝑆𝐺) − 𝑃 (𝑆𝐺) As explained, PCVC deals with minimizing the sum of weights of the vertices chosen and the sum of weights of the edges not covered by those vertices. We first convert this to a maximization problem by introducing a negative sign. Then, we apply the formula above to obtain the reward and the penalty functions. In certain cases, the optimization objective cannot be computed accurately in polynomial time or is not a DoM. In such cases, the objective can be approximated by a DoM function. The performance of an algorithm that relies on this approach will depend on the nature of the approximation. NP-hard problems whose solutions can be verified or scored easily are the best candidates for our approach. 3

ΔSearch Algorithm

Next, we present ΔSearch, a heuristic algorithm that can quickly find good solutions for problems that satisfy the DoM formulation. The algorithm only runs the reward and penalty functions at most 𝑂 (𝑛 2 ) times, which is much less than many other heuristics. The number of calls to reward , Vol. 1, No. 1, Article . Publication date: June 2026.

R.S. Valan Arasu et al.

Uncapacitated Facility Location

Prize-Collecting Vertex Cover

Fig. 3. The behavior of rewards, negation of penalties and total scores of non-monotone DoM graph problems with insertion of vertices in a random ordering.

and penalty functions reduces to 𝑂 (𝑛) for monotone graph problems. If needed, this algorithm can be run multiple times with different random seeds to obtain better and diverse solutions. The diversity of the solutions is due to the fixed exploration method of ΔSearch which allows it to find different solutions for different orderings of the candidates. This diversity is useful when combined with the exact algorithm to generate multiple diverse solutions for pruning. Next we describe the two key characteristics of ΔSearch that allow it to be efficient and general. Efficiency. To address the efficiency of subgraph extraction problems in DoM formulation, we draw inspiration from another high-complexity extraction problem that has achieved remarkable success, namely delta debugging [97, 99]. Given a large failure-inducing input, delta debugging extracts a smaller failure-inducing input to facilitate and simplify debugging by the programmer. Although the number of smaller inputs is exponential, delta debugging employs a binary search-like systematic search strategy that examines a linear [43] or quadratic [97, 99] number of smaller inputs and, in practice, delivers impressive results; however, in general, these are suboptimal results. Table 2. DoM functions for several Subgraph Extraction Problems and Greedy Action to improve solutions. Graph Problem Reward(SG) Penalty(SG) Action ( 0 if 𝑆𝐺 is planar Maximum Planar Edge =|𝐸𝐺 (𝑆𝐺)| = Subgraph Addition ∞ otherwise Minimum Steiner Tree Problem

   −∞   0 

if terminals are not connected in 𝑆𝐺 otherwise

= Σ𝑒 ∈ |𝐸𝐺 (𝑆𝐺 ) | 𝑤 (𝑒) (

Maximum Weighted Independent Set

= Σ𝑣 ∈𝑉𝐺 (𝑆𝐺 ) w(v)

Minimum Connected Dominating Set

 if 𝑉𝐺 (𝑆𝐺) is not a   −∞  connected dominating set =  0 otherwise 

= |𝑉𝐺 (𝑆𝐺)|

Uncapacitated Facility Location Problem Prize Collecting Vertex Cover

= − min𝑥𝑖 𝑗 Σ 𝑗 Σ𝑖 𝑐𝑖 𝑗 𝑥𝑖 𝑗

0 ∞

if |𝐸 (𝑆𝐺)| = 0 otherwise

= Σ𝑖 𝑓𝑖 𝑦𝑖

where 𝑦𝑖 = 1 if 𝑦𝑖 ∈ 𝑉 (𝑆𝐺); 0 otherwise; 𝑥𝑖 𝑗 ∈ {0, 1} st 𝑥𝑖 𝑗 ≤ 𝑦𝑖 & Σ 𝑗 𝑥𝑖 𝑗 = 1 = −Σ𝑒 ∈𝐸𝐺 (𝐺\𝑆𝐺 ) 𝑤 𝐸 (𝑒)

, Vol. 1, No. 1, Article . Publication date: June 2026.

= Σ𝑣 ∈𝑉𝐺 (𝑆𝐺 ) 𝑤𝑉 (𝑣)

Edge Deletion Vertex Addition Vertex Deletion Vertex Addition & Deletion Vertex Addition & Deletion

Solving Subgraph Extraction Problems Using ΔSearch

Moreover, it is a black-box technique (i.e., it is not program-specific) that simply runs the program on smaller inputs to find one that is both small and reproduces the failure encountered during the execution on the large input. Thus, delta debugging has similarities to solving non-weighted hereditary problems that are a small subset of DoM problems. We extend both the formulation and the algorithm to bring the benefits of a black-box framework to the wide range of DoM problems. Generality. Due to the monotone nature of the hereditary graph problems, greedy solutions [11, 22] were heavily explored by prior works. However, a binary search-like approach would achieve a much faster runtime. This observation is the cornerstone for delta debugging, and is what inspired ΔSearch. ΔSearch also achieves better solution quality than greedy algorithms on average due to its dynamic granularity reduction rather than one-by-one addition of candidates performed by the greedy algorithms. Greedy heuristics for hereditary problems can be easily developed by repeatedly adding maximum reward graph elements (i.e., vertices or edges) to an empty graph. Similarly, greedy heuristics for ancestral problems can be developed by repeatedly deleting maximum penalty graph elements (i.e., vertices or edges) from the original graph. These actions for various problems are shown in the last column of Table 2. The idea of greedily adding or deleting graph elements for hereditary and ancestral problems respectively motivates our heuristic for DoM to do a search prioritizing the reward for additions and penalties for deletions to achieve a good solution. We call such a heuristic bidirectional as it uses both additions and deletions. As a bidirectional search algorithm, it not only generalizes solving hereditary and ancestral graph problems but it is also able to solve other non-monotone DoM problems. Algorithm Details. The algorithm for ΔSearch is shown in Algorithm 1. Before the search begins, the user provides the graph elements (edges, vertices, or something else) to be operated on as candidates (line. 1). The search begins with the entire graph or the entire set of graph elements as the current solution and deletion of all the graph elements from the current solution as the only modification in priority queue. The priority queue always contains modifications (addition or deletion of graph elements) for the current solution ordered by priority. During any iteration, the highest priority modification is chosen to be applied to the current solution (line 14). If the solution improves, the modified solution becomes the current solution (lines 19- 21), and the undo of the modification is split and added back to the priority queue to allow for finer search. If the solution doesn’t improve, the modification is split and added back to the priority queue for finer search. In either case, if the modification is of only one graph element, then the modification is not split but added directly to the next priority queue (line 27), since we know that both the modification and its undo have already been tested and therefore cannot improve the current solution. The priority of the modifications is defined as the potential incremental benefit brought by the action without its cost. That is, for addition, the priority is the potential increase in reward, whereas for deletion, the priority is the potential decrease in penalty as can be seen from Algorithm 2. In the algorithm, the potential incremental benefit of a modification is the reward or penalty change of its parent modification and not the modification itself. Since computing scores is computationally expensive, we reuse the score computation of the parent modification to set priorities for the split modifications. Because applying a modification may or may not improve current solution, the search will either split the undo of the modification or the modification itself into two. Thus, priority is computed for both of these cases on Line 20 and Line 15 respectively in Algorithm 1. Note that in Line 20, the positions of 𝑡𝑒𝑠𝑡_𝑔𝑟𝑎𝑝ℎ and 𝑐𝑢𝑟 _𝑔𝑟𝑎𝑝ℎ are swapped. This is because the modification converted 𝑐𝑢𝑟 _𝑔𝑟𝑎𝑝ℎ to 𝑡𝑒𝑠𝑡_𝑔𝑟𝑎𝑝ℎ and therefore, the undo will convert 𝑡𝑒𝑠𝑡_𝑔𝑟𝑎𝑝ℎ (the next 𝑐𝑢𝑟 _𝑔𝑟𝑎𝑝ℎ) to 𝑐𝑢𝑟 _𝑔𝑟𝑎𝑝ℎ. Algorithm 1 also uses a pruning strategy on Lines 8-12. As can be seen from the implementation in Algorithm 2, if the current solution has the same reward as the entire graph, then no addition , Vol. 1, No. 1, Article . Publication date: June 2026.

R.S. Valan Arasu et al.

Algorithm 1 ΔSearch. 1: procedure ΔSearch ( graph, candidates ) 2: 𝑝𝑞 ← 𝑀𝑎𝑥𝑃𝑟𝑖𝑜𝑟𝑖𝑡𝑦𝑄𝑢𝑒𝑢𝑒 () 3: 𝑛𝑒𝑥𝑡_𝑝𝑞 ← 𝑀𝑎𝑥𝑃𝑟𝑖𝑜𝑟𝑖𝑡𝑦𝑄𝑢𝑒𝑢𝑒 () 4: 𝑐𝑢𝑟 _𝑔𝑟𝑎𝑝ℎ ← 𝑔𝑟𝑎𝑝ℎ 5: 𝑝𝑞.𝑖𝑛𝑠𝑒𝑟𝑡 ( (𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠, 𝐷𝐸𝐿, 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 = 0) ) 6: 7: 8: 9: 10: 11: 12:

⊲ Priority-based Worklist ⊲ Holds subsets that cannot improve cur_graph ⊲ Current solution

while ¬𝑝𝑞.𝑒𝑚𝑝𝑡𝑦 () do (𝑠𝑢𝑏𝑠𝑒𝑡, 𝑎𝑐𝑡𝑖𝑜𝑛, 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦) ← 𝑝𝑞.𝑒𝑥𝑡𝑟𝑎𝑐𝑡_𝑚𝑎𝑥 () ⊲ Prune subset check if possible if PruneCondition (action, cur_graph, graph) then 𝑛𝑒𝑥𝑡_𝑝𝑞.𝑖𝑛𝑠𝑒𝑟𝑡 ( (𝑠𝑢𝑏𝑠𝑒𝑡, 𝑎𝑐𝑡𝑖𝑜𝑛, 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦) ) continue end if

13: 14: 15:

⊲ Create test_graph to check score 𝑡𝑒𝑠𝑡_𝑔𝑟𝑎𝑝ℎ ← 𝑔𝑟𝑎𝑝ℎ.𝑎𝑝𝑝𝑙𝑦 ( (𝑠𝑢𝑏𝑠𝑒𝑡, 𝑎𝑐𝑡𝑖𝑜𝑛) ) ⊲ Add or Delete graph elements 𝑠𝑢𝑏𝑠𝑒𝑡_𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 ← Priority (𝑡𝑒𝑠𝑡_𝑔𝑟𝑎𝑝ℎ, 𝑎𝑐𝑡𝑖𝑜𝑛, 𝑐𝑢𝑟 _𝑔𝑟𝑎𝑝ℎ) ⊲ For splitting

16: 17: 18: 19: 20: 21: 22: 23: 24:

⊲ Change cur_graph if necessary 𝑠𝑐𝑜𝑟𝑒_𝑡𝑒𝑠𝑡_𝑔𝑟𝑎𝑝ℎ = 𝑟𝑒𝑤𝑎𝑟𝑑 (𝑡𝑒𝑠𝑡_𝑔𝑟𝑎𝑝ℎ) − 𝑝𝑒𝑛𝑎𝑙𝑡𝑦 (𝑡𝑒𝑠𝑡_𝑔𝑟𝑎𝑝ℎ) 𝑠𝑐𝑜𝑟𝑒_𝑐𝑢𝑟 _𝑔𝑟𝑎𝑝ℎ = 𝑟𝑒𝑤𝑎𝑟𝑑 (𝑐𝑢𝑟 _𝑔𝑟𝑎𝑝ℎ) − 𝑝𝑒𝑛𝑎𝑙𝑡𝑦 (𝑐𝑢𝑟 _𝑔𝑟𝑎𝑝ℎ) if 𝑠𝑐𝑜𝑟𝑒_𝑡𝑒𝑠𝑡_𝑔𝑟𝑎𝑝ℎ > 𝑠𝑐𝑜𝑟𝑒_𝑐𝑢𝑟 _𝑔𝑟𝑎𝑝ℎ then 𝑠𝑢𝑏𝑠𝑒𝑡_𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 ← Priority (𝑐𝑢𝑟 _𝑔𝑟𝑎𝑝ℎ, ¬𝑎𝑐𝑡𝑖𝑜𝑛, 𝑡𝑒𝑠𝑡_𝑔𝑟𝑎𝑝ℎ) ⊲ Priority to undo 𝑐𝑢𝑟 _𝑔𝑟𝑎𝑝ℎ ← 𝑡𝑒𝑠𝑡_𝑔𝑟𝑎𝑝ℎ 𝑝𝑞 = 𝑝𝑞 ∪ 𝑛𝑒𝑥𝑡_𝑝𝑞 ⊲ Current solution changed; validate subsets from next_pq 𝑛𝑒𝑥𝑡_𝑝𝑞 ← ∅ end if

25: 26: 27: 28: 29: 30: 31:

⊲ Split subset into two subsets if possible if 𝑙𝑒𝑛(𝑠𝑢𝑏𝑠𝑒𝑡) == 1 then ⊲ Thus subset cannot improve cur_graph 𝑛𝑒𝑥𝑡_𝑝𝑞.𝑖𝑛𝑠𝑒𝑟𝑡 ( (𝑠𝑢𝑏𝑠𝑒𝑡, 𝑎𝑐𝑡𝑖𝑜𝑛, 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 = 𝑠𝑢𝑏𝑠𝑒𝑡_𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦) ) else 𝑝𝑞.𝑖𝑛𝑠𝑒𝑟𝑡 ( (𝑠𝑢𝑏𝑠𝑒𝑡 [: ⌈𝑙𝑒𝑛(𝑠𝑢𝑏𝑠𝑒𝑡)/2⌉], 𝑎𝑐𝑡𝑖𝑜𝑛, 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 = 𝑠𝑢𝑏𝑠𝑒𝑡_𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦) ) 𝑝𝑞.𝑖𝑛𝑠𝑒𝑟𝑡 ( (𝑠𝑢𝑏𝑠𝑒𝑡 [⌈𝑙𝑒𝑛(𝑠𝑢𝑏𝑠𝑒𝑡)/2⌉ :], 𝑎𝑐𝑡𝑖𝑜𝑛, 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 = 𝑠𝑢𝑏𝑠𝑒𝑡_𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦) ) end if

32: 33: 34:

end while return 𝑐𝑢𝑟 _𝑔𝑟𝑎𝑝ℎ end procedure

of graph elements can improve the reward of the current solution and we also know that penalty only increases with graph element additions. Thus, any addition of graph elements can be pruned away when the current solution and the entire graph have the same reward. Similarly, any deletion of graph elements can be pruned away when the penalty of current solution is equal to the penalty of the empty graph. Although this pruning strategy is usually of little benefit to non-monotone problems like PCVC and UFLP, monotone problems can exploit this pruning strategy and nonweighted monotone problems especially can achieve a better complexity of 𝑂 (𝑛) calls to scoring functions instead of the 𝑂 (𝑛 2 ) calls in the general case. The priority and pruning define the action space used by ΔSearch. As we observed in the previous section and in Table 2, both addition and deletion may not always be needed. It is enough to use , Vol. 1, No. 1, Article . Publication date: June 2026.

Solving Subgraph Extraction Problems Using ΔSearch

Algorithm 2 Pruning and Priority. 35: procedure Priority ( test_graph, action, cur_graph ) 36: if 𝑎𝑐𝑡𝑖𝑜𝑛 == 𝐷𝐸𝐿 then return penalty(cur_graph) - penalty(test_graph) 37: else if 𝑎𝑐𝑡𝑖𝑜𝑛 == 𝐴𝐷𝐷 then return reward(test_graph) - reward(cur_graph) 38: end if 39: end procedure 40: procedure PruneCondition(action, cur_graph, graph) 41: if 𝑎𝑐𝑡𝑖𝑜𝑛 == 𝐷𝐸𝐿 then 42: if 𝑝𝑒𝑛𝑎𝑙𝑡𝑦 (𝑒𝑚𝑝𝑡𝑦_𝑔𝑟𝑎𝑝ℎ) == 𝑝𝑒𝑛𝑎𝑙𝑡𝑦 (𝑐𝑢𝑟 _𝑔𝑟𝑎𝑝ℎ) then return True 43: end if 44: else if 𝑎𝑐𝑡𝑖𝑜𝑛 == 𝐴𝐷𝐷 then 45: if 𝑟𝑒𝑤𝑎𝑟𝑑 (𝑔𝑟𝑎𝑝ℎ) == 𝑟𝑒𝑤𝑎𝑟𝑑 (𝑐𝑢𝑟 _𝑔𝑟𝑎𝑝ℎ) then return True 46: end if 47: end if 48: return False 49: end procedure

4 5

3 10

1 10

Fig. 4. An example of Prize Collecting Vertex Cover with cost of all vertices equal to 10 and edge penalties shown as edge weights.

only addition for Maximum Planar Subgraph and Maximum Weighted Independent set. Similarly, it is enough to use only deletion for Ancestral Problems. Thus, in monotone problems, pruning removes unnecessary actions. But problems that are not monotone typically require both additions and deletions. An Example. An illustration of how ΔSearch works is shown in Table 3. The example problem is an instance of the PCVC problem with the graph and edge penalties shown in Figure 4. For ease of understanding, let the vertex penalty for all vertices be 10. Note that ΔSearch can work with arbitrary edge and vertex penalties and not just a constant vertex penalty. The search in Table 3 begins with the entire graph as usual. The entire graph has score −25 and the first modification, deletion of all graph elements from the current solution, achieves a score 0 which is better than current solution. Thus, the current solution is set as the empty graph and the addition of all graph elements, which is the undo of deletion of all graph elements, is split into two: Addition of first half of graph elements {𝐴, 𝐵, 𝐶} and Addition of second half of the graph elements {𝐶, 𝐷, 𝐸}. These two modifications are then added back into the Priority Queue. The addition of graph elements {𝐴, 𝐵, 𝐶} does not achieve a score better than empty graph, hence the modification itself is split into two: Addition of graph element {𝐴} and Addition of graph elements {𝐵, 𝐶}. The addition of graph element {𝐴} achieves a better solution and hence current solution (empty graph) with {𝐴} is set as the current solution. Note that the undo of addition of {𝐴} to the current graph is not added back to the priority queue since we have already tested the empty graph and , Vol. 1, No. 1, Article . Publication date: June 2026.

R.S. Valan Arasu et al.

know that it is inferior to the current solution. Thus, the undo of this modification, the Deletion of {𝐴} is only added to the 𝑛𝑒𝑥𝑡_𝑝𝑞. The 𝑛𝑒𝑥𝑡_𝑝𝑞 containing Deletion of {𝐴} merges with the priority queue only after the current solution changes in iteration 8. Table 3 only shows the search up to 9 iterations. After this, the search proceeds with testing each of the modification in the priority queue which only produces inferior solutions, adding nothing back to the priority queue. The priority queue thus becomes empty and the search terminates with {𝐴, 𝐷 } as the solution. Complexity. Let us now analyze the time complexity of ΔSearch in terms of the number of calls to the scoring functions. Let us first look at the number of modifications that will be considered during the run of ΔSearch. Since an 𝑛 element list can only be split into two 𝑛 − 1 times, the number of modifications considered by the algorithm is at most 𝑂 (𝑛), where 𝑛 is the number of graph elements. Therefore, at any instant during the ΔSearch, the priority queue will only have at most 𝑂 (𝑛) elements. The algorithm terminates if there is no element in priority queue. Thus, the current solution must change every 𝑂 (𝑛) iterations to refill the priority queue or it terminates. Since every current solution change invalidates at least one modification, the number of times current solution changes is at most 𝑂 (𝑛). Since there are at most 𝑂 (𝑛) current solution changes and since there are at most 𝑂 (𝑛) calls to scoring functions between each current solution change, the total number of calls to the scoring functions during the runtime of the algorithm is at most 𝑂 (𝑛 2 ). This analysis is less tight for monotone problems as these problems work with only one action due to pruning. Here, all modifications can only be applied once or forever be discarded. Thus, hereditary and ancestral problems call the scoring functions at most 𝑂 (𝑛) times. Table 3. Illustration of Space Exploration by ΔSearch for the Prize-Collecting Vertex Cover Problem with weight of every vertex equal to 10. The elements in the priority queue are of the form (subset, action, priority). Solution Test Action Test Graph R(SG) Score Worklist cur_graph subset test_graph -P(SG) pq 4

B 3

{A, B, C, D, E, F}

DEL

{}

{A,B,C}

8 4

{A}

ADD

8 4

-3

{ ({A}, ADD, 27), ({B, C}, ADD, 27), ({D, E, F}, ADD, 0)}

12 - 10

{ ({B, C}, ADD, 27), ({D, E, F}, ADD, 0)}

D B 3

F 5

, Vol. 1, No. 1, Article . Publication date: June 2026.

27 - 30

{({A,B,C},ADD,-35), ({D, E, F},ADD,-35)}

3 E

{}

0-0

{({A, B, C, D, E, F}, DEL, 0) }

ADD

-25

35 - 60

Solving Subgraph Extraction Problems Using ΔSearch

13 4

B 3

{A}

{B, C}

ADD

{A}

{B}

ADD

{C}

ADD

8 4

{D, E, F}

ADD

{D}

ADD

8 4

.. . 4

.. .

28 - 20

{ ({E, F}, ADD, 23), ({A}, DEL, 10), ({D}, DEL, 10), ({C}, ADD, 9), ({B}, ADD, 6) }

35 - 40

-5

{ ({A}, DEL, 10), ({D}, DEL, 10), ({C}, ADD, 9), ({E}, ADD, 7), ({F}, ADD, 7), ({B}, ADD, 6) }

F 5

B 3

F 5

1 C

{ ({D}, ADD, 23), ({E, F}, ADD, 23) }

3 E

-5

ADD

F 5

{E, F}

35 - 40

B 3

{A, D}

{ ({D,E,F}, ADD, 0) }

{A}

21 - 20

{ ({C}, ADD, 15), ({D, E, F}, ADD, 0)}

3 E

-2

{A}

18 - 20

{ ({B}, ADD, 15), ({C}, ADD, 15), ({D, E, F}, ADD, 0)}

{A}

-3

27 - 30

.. .

Implementation and Programming Interface

ΔSearch is implemented as a Python library around three input components: (i) Graph - the graph whose subgraph is to be extracted; (ii) Graph element (Vertex or Edge) - which defines the changes allowed to the graph; and (iii) Score functions (Reward and Penalty). The mutual independence among these three components allows their reuse for different problems. Graph Elements. The graph elements represent the smallest changes that can be made to the graph. Examples of graph elements include vertices for induced subgraph problems and edges for subgraph problems. Since vertices and edges are the most common graph element types, they are implemented in the library. The user is also allowed to create custom graph elements. For example, let us consider the Minimum Constraint Removal (MCR) Problem. In the MCR problem, given a graph, a start vertex, an end vertex and a list of subsets of the vertex set called obstacles, one must , Vol. 1, No. 1, Article . Publication date: June 2026.

R.S. Valan Arasu et al.

Fig. 5. The ΔSearch architecture.

find the path between the start and end vertex that minimizes the number of obstacles it intersects. In this problem, the graph element is the obstacles (subsets of vertex sets) and with it, ΔSearch will search the smallest set of obstacles to delete that still retains reachability between start and end vertex. To write custom graph elements, the user only has to define the number of graph elements and how to add and remove them. Scoring Functions. The ΔSearch framework accepts an array of functions that sum up to the optimization objective (Reward functions and negation of Penalty functions). These functions are assigned as reward or penalty automatically by ΔSearch using the logic presented in Equation 1. Since ΔSearch calls these functions multiple times, it is important to optimize these functions well. In fact, optimizing the scoring functions is the only tuning left to the user. This is in contrast with various other meta-heuristics where the user is supposed to tune the hyper-parameters based on the user’s understanding of the algorithm. On the other hand, in ΔSearch, the user only has to implement highly optimized scoring functions. In addition to the three inputs, the ΔSearch framework consists of two modules. The first one is the DSObject - a wrapper around the inputs and the second one is the core algorithm. DSObject. The DSObject is a wrapper around all three inputs. The DSObject provides methods to add and remove subset modifications and to compute reward and penalty. The core search algorithm of ΔSearch calls these methods during its search. Although we have shown the modification and scoring done directly on the graph in Algorithm 1, the actual implementation uses the DSObject abstraction so that any data structure can be used with ΔSearch. The DSObject abstractions also allow for better optimizations such as incremental scoring (to avoid computing the scores from scratch every time), caching of scores for reuse and sharing of computation between reward and penalty functions. However, it may also introduce dependence between the scoring functions and graph elements (such as a scoring function constrained to work with only one type of graph element). Thus, users should avoid directly using the DSObject interface unless necessary. More details on the uses and implementation can be found in our code repository. The Core Algorithm. As can be seen from Figure 5, the core algorithm controls DSObject by assigning the modification to apply next and the DSObject applies the modification and computes the score after the modification has been applied. The main reason for the separation of DSObject and the core algorithm is to ensure that the core algorithm remains graph-agnostic so that it could even be applied to other problems. 5

Experimental Evaluation

We evaluate the effectiveness of ΔSearch by solving multiple graph problems and comparing its solution quality and execution time against problem-specific heuristic baselines on standard graph datasets, as shown in Table 4. We use an AMD EPYC 7713 processor with a memory limit of 50 , Vol. 1, No. 1, Article . Publication date: June 2026.

Solving Subgraph Extraction Problems Using ΔSearch

GB. ΔSearch is implemented in Python 3.10 with the networkx 2.8.8 library. Heathcliff [78] (MST), MMWIS [47] (MWIS), GuMWIS [49] (MWIS), BinCSA [85] (UFLP), and APBEA [39] (UFLP) use their original C++ implementations and were compiled with gcc 12.3.0 with -O3 optimization flag. All remaining baselines are implemented in Python 3.10. Table 4. Baseline algorithms and Datasets for evaluation of different DoM problem instances. Problem Baselines Graph Datasets Maximum Planar Subgraph Minimum Steiner Tree Problem Maximum Weighted Independent Set Minimum Connected Dominating Set Uncapacitated Facility Location Prize Collecting Vertex Cover

5.1

Naive, Cactus+ [20] TM heuristic [87], Heathcliff [14] GWMIN, GWMAX, GWMIN2 [80] MMWIS [46], GUMWIS [50], Local Ratio (LR), Fractional LR [7] GR_CDS, GR_CDS_pruned [40], IC_MIS_ST [86] BinCSA [83], APBEA [84] Local Ratio [7]

North [34], Steinlib [58] Steinlib [58] VR [37]

LPNMR [55] ORLIB [8], M* [61] Synthetic [69]

Case Studies

5.1.1 Maximum Planar Subgraph. Given a graph 𝐺 = (𝑉 , 𝐸), the Maximum Planar Subgraph (MPS) problem is to find the largest edge subset 𝐹 ⊆ 𝐸 such that 𝑆𝐺, the graph induced by 𝐹 , is planar. The MPS problem is NP-hard [19], which led to the rise in popularity of heuristic algorithms for MPS. Approximate algorithms for Maximum Planar Subgraph Problem have applications in graph drawing. The Planarization method [20], one of the strongest heuristics to draw a graph with fewest crossings starts with a planar subgraph and adds other edges incrementally. Multiple heuristics have been developed for the Maximum Planar Subgraph Problem. [22] presents a list of heuristics: Boyer and Myrvold method (BM), Cactus Algorithm (C) and the Naive method (Ni) developed for finding large planar subgraphs and evaluates them against each other. The simplest of the methods, Naive, adds edges one by one to find a maximal planar subgraph. To ensure that these methods find maximal and not just large ones, we can postprocess the other algorithms using the Naive method to achieve maximality (BM+, Cactus+) as done in [22]. Since [22] shows that BM, BM+ and Cactus are inferior to Cactus+ in solution quality, we remove them from our evaluations. The cactus algorithm is a 7/18-approximation algorithm whereas our ΔSearch and the Naive algorithm are both 1/3-approximation algorithms. However in experiments, both ΔSearch and the Naive algorithm outperform the cactus algorithm in almost all graphs. Cactus+, on the other hand, is competitive with ΔSearch and the naive algorithm. We use the non-planar graphs of the established real-world datasets from North [34] (423 instances) and SteinLib [58] (586 instances). Figure 6 shows the solution and time performance of Naive, Cactus+ and ΔSearch for the graph instances, and Table 5 shows the average improvement in solution quality and average runtime speedup of ΔSearch with respect to Naive and Cactus+ for the North and Steinlib datasets. Since the combined number of graph instances is 1009, as shown in Figure 6, we bucket the graph instances into 40 buckets based on the number of edges. We can see that on average, ΔSearch produces better solutions than the Naive greedy algorithm with 0.54% improvement. ΔSearch is also competitive against the Cactus+ algorithm in solution quality and runtime performance. Thus, ΔSearch is Table 5. MPS - ΔSearch vs. Naive and Cactus+ algorithms [20]. ↑ is better for quality and time. Improvement for North [34] Improvement for Steinlib [58] Algorithm Avg Quality Avg Time Avg Quality Avg Time Naive +0.54% -22.03% +0.53% -20.56% Cactus+ -0.18% -2.17% -0.35% -1.27%

, Vol. 1, No. 1, Article . Publication date: June 2026.

R.S. Valan Arasu et al.

Fig. 6. Maximum Planar Subgraph - ΔSearch vs. Cactus and Cactus+ baselines for the North [34] dataset. Table 6. MST - ΔSearch vs. TM and Heathcliff algorithms.↑ is better for quality and time. Improvement for Steinlib [58] Algorithm Avg Quality Avg Time TM Heuristic -36.58% -90.98% Heathcliff -31.11% +170796.17%

Fig. 7. Minimum Steiner Tree - ΔSearch vs. TM [87] and Heathcliff [14] baselines on Steinlib [58] dataset.

competitive against the algorithms developed for the Maximum Planar Subgraph despite being a general framework. 5.1.2 Minimum Steiner Tree Problem. The Minimum (Weighted) Steiner Tree problem is another important NP-hard problem in combinatorial optimization. It plays a central role in integrated circuit design, network design and facility location [65]. Given a graph 𝐺 and a subset of vertices called terminals 𝐴 ⊆ 𝑉 (𝐺), the Minimum Weighted Steiner Tree problem is to find the subgraph with minimum weighted set of edges such that all the terminals are reachable to each other in the subgraph. Multiple works have been developed to solve the Steiner Tree problem. [65] presents a survey on the recent advances in solving Steiner trees. We compare our ΔSearch framework with the winner of the PACE 2018 Track C challenge [14] on the Steiner Tree problem, which we will refer to as Heathcliff. Note that we use the original implementation of Heathcliff in C++ from [78]. We also compare our work against a heuristic algorithm named TM-heuristic [87] which achieves an approximation ratio of 2 − 2/|𝐴| of the minimum solution. We use Steinlib [58], an established real-world benchmark for the Steiner tree problem, for our evaluations. Since Heathcliff’s runtime is much higher than TM-heuristic and ΔSearch, we limit its runtime to 300 seconds for all the Steiner tree experiments. Figure 7 shows the cost of the solutions returned by ΔSearch, TM Heuristic and Heathcliff normalized by the best solution produced and the runtimes of all three algorithms. Figure 7 and Table 6 show that unlike Maximum Planar Subgraph Problem, ΔSearch performs poorly in solution quality compared to both the algorithms. This is not unexpected as both of these algorithms were developed for the Steiner problem. Interestingly, Heathcliff performs worse than TM Heuristic even with its huge runtime. A bigger time limit might be beneficial for Heathcliff. The poorer runtime performance of ΔSearch with respect to TM heuristic is mainly due to the fact that TM heuristic is constructive in nature. That is, unlike ΔSearch which checks the validity of subsets multiple times, , Vol. 1, No. 1, Article . Publication date: June 2026.

Solving Subgraph Extraction Problems Using ΔSearch

Table 7. MWIS - ΔSearch vs. other MWIS algorithms [7, 47, 49, 80]. ↑ is better for quality and time. Improvement for VR [37] Algorithm Avg Quality Avg Time GWMIN -10.10% -83.97% GWMAX -9.15% +204.76% GWMIN2 -9.75% +47.26% Local Ratio -5.38% -92.6% Fractional Local Ratio -8.15% -75.63% GUMWIS -10.12% -95.63% MMWIS -12.39% +2718.00%

Fig. 8. Maximum Weight Independent Set - ΔSearch vs. various baselines for VR [37] graph instances.

TM heuristic produces a valid Steiner tree by construction. Hence, it is much faster than ΔSearch. On the other hand, Heathcliff uses an evolutionary algorithm which is much slower than ΔSearch. Though ΔSearch is not comparable to TM heuristic, it could still be competitive with Heathcliff if run multiple times to match the runtime. The mechanism of running ΔSearch multiple times and the effectiveness of this approach is shown in Section 5.2. 5.1.3 Maximum Weighted Independent Set. The Maximum Weighted Independent Set (MWIS) problem is yet another NP-hard problem which deals with finding a set of vertices that are not adjacent and whose total weight is maximum. Maximum Weighted Independent Set problem has applications in image segmentation [18] and multi-object tracking [17] in Computer Vision and transmission scheduling in networks. Multiple greedy [80] (GWMIN, GWMAX and GWMIN2) heuristics and other heuristics [50] (GUMWIS) and metaheuristic [46] (MMWIS) works have been developed for computing Maximum Weighted Independent Set. We use all the above works as baseline for ΔSearch for Maximum Weighted Independent Set Problem. Note that the original C++ implementation of gumwis and mmwis from [49] and [47] are used for comparison. We also compare our work against general frameworks Local Ratio and Fractional Local Ratio as they too can work with this problem. A significant amount of research has been devoted to reduction techniques for the Weighted Independent Set problem. [48] presents a survey on multiple reduction techniques developed and used by prior work on Weighted Independent Set problems. Since gumwis uses multiple reduction techniques internally, to keep comparisons fair, we apply reductions to all graphs before running the baseline algorithms. For datasets, we use the dataset VR instances [37] from Vehicle Routing application. Figure 8 illustrates the sum of edge weight of solutions computed by the MWIS algorithms normalized by the best found solution and the runtime of the MWIS algorithms. Table 7 shows the ratio of solution produced and runtime by ΔSearch compared to the other MWIS algorithms. GWMIN, Local Ratio and Fractional Local Ratio are faster than the ΔSearch algorithm due to being construction-based algorithms. Although ΔSearch is comparable to Local Ratio, due to its user provided algorithm for solving smaller instances, it is able to achieve better solution quality , Vol. 1, No. 1, Article . Publication date: June 2026.

R.S. Valan Arasu et al.

Table 8. MCDS - ΔSearch vs. other MCDS algorithms.↑ is better for quality and time. Improvement for LPNMR [55] Algorithm Avg Quality Avg Time GR_CDS -21.62% -99.13% GR_CDS_pruned -22.27% -99.13% IC_MIS_ST +44.90% -61.51%

Fig. 9. Minimum Connected Dominating Set - ΔSearch vs. other MCDS baselines for the LPNMR [55] dataset.

compared to Local Ratio. ΔSearch achieves around 90% of the solution quality of the custom algorithms despite not having any user-provided guidance. 5.1.4 Minimum Connected Dominating Set. The Minimum Connected Dominating Set (MCDS) is an NP-hard problem with applications in constructing backbones in ad hoc and wireless networks [40, 86]. We use the prior works ICIK and ICML from [86] and GR_CDS from [40] as baselines for this experiment. For dataset, we use the instances from Tenth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’09) [55]. Figure 9 gives the number of edges in the solutions for GR_CDS, GR_CDS_pruned, IC_MIS_ST and ΔSearch and their runtimes and Table 8 shows the improvement of ΔSearch over the MCDS baselines. From the figure, we observe that ΔSearch achieves better solution than IC_MIS_ST, albeit being slower than the latter. But again, ΔSearch falls behind in runtime as all the baselines are constructive. However, it is still noteworthy that it achieved around 80% of the solution of the best custom algorithms GR_CDS and GR_CDS_pruned and also being able to perform better than one existing custom algorithm IC_MIS_ST. Table 9. UFLP - Non-optimal solutions found by the UFLP algorithms for ORLIB and M* datasets. * indicates crashes of the publicly available baseline implementations of APBEA[39] and BinCSA[85] on larger instances. Instance BinCSA APBEA ΔSearch MO3 1521.473 1516.773 1516.773 MR1 2609.08 2608.148 2608.148329 MR3 2788.25 2788.25 2793.324183 MS1 ∗ ∗ 5283.757394 MT1 ∗ ∗ 10069.802769

Fig. 10. Uncapacitated Facility Location - ΔSearch vs. APBEA [84] and BinCSA [83] baselines for ORLIB [8] and M* [61] datasets. The solution costs are normalized using the optimal solution cost. , Vol. 1, No. 1, Article . Publication date: June 2026.

Solving Subgraph Extraction Problems Using ΔSearch

5.1.5 Uncapacitated Facility Location Problem. UFLP is one of the most famous NP-hard problems [28] with a wide range of applications from resource allocation, network architecture and computer vision to infrastructure construction of schools, hospitals, warehouses etc [100]. An UFLP problem deals with finding a set of locations to setup factories to minimize total cost. A UFLP instance consists of a set of consumer locations and a set of locations where factories can be set up. There exists two costs in an UFLP instance: (i) Transportation cost for delivering services to the customers from any of the factory locations and (ii) Set up cost for setting up factories in a location. There is no limit on how many customers a factory can serve but all the customers must be served. The objective of an UFLP instance is to minimize the total cost or sum of transportation cost and the setup cost. Mathematically, given 𝑛 factory locations and 𝑚 customers, the UFLP instance can be described as follows: min Σ 𝑗 Σ𝑖 𝑐𝑖 𝑗 𝑥𝑖 𝑗 + Σ𝑖 𝑓𝑖 𝑦𝑖

𝑥𝑖 𝑗 ,𝑦𝑖

where Σ𝑖 𝑥𝑖 𝑗 = 1,

∀𝑗 = 1, 2, · · · 𝑚

𝑥𝑖 𝑗 ≤ 𝑦𝑖 ,

∀𝑖 = 1, 2, · · · 𝑛, ∀𝑗 = 1, 2, · · · 𝑚

𝑥𝑖 𝑗 , 𝑦𝑖 ∈ {0, 1},

∀𝑖 = 1, 2, · · · 𝑛, ∀𝑗 = 1, 2, · · · 𝑚

where 𝑐𝑖 𝑗 is the transportation cost of service from factory 𝑖 to customer 𝑗, 𝑓𝑖 is the set up cost for setting up a factory at location 𝑖. In ΔSearch, we model this problem as a selection problem where the locations where the factories need to be setup are selected. The assignment of factories to customers is then done by the reward function by assigning the closest factory to any customer. The scoring functions can be seen in Table 2. Due to its high popularity, various heuristics and meta-heuristics have been constructed for the UFLP problem. In this work, for UFLP, we compared ΔSearch against the greedy algorithm from [53] and metaheuristics APBEA, EGTOA and BinCSA from [83, 84, 100]. APBEA is considered the state of the art algorithm for UFLP. Figure 10 shows the performance of ΔSearch compared against APBEA and BinCSA. The greedy algorithm and EGTOA algorithm were removed from the figure as they produced multiple non-optimal results. Since the time taken by APBEA and BinCSA were very high compared to ΔSearch, to make comparisons fair, we ran ΔSearch 100 times and chose the best result. Details of how running ΔSearch multiple times results in better solution is explained in the next subsection. The original C++ implementation of APBEA and BinCSA from [39] and [85] respectively are used for comparison. For datasets, we use ORlib [8], the most well known dataset in this area with 15 instances and M* [61], another UFLP dataset with 22 instances. Figure 10 illustrates the cost of solution computed by and runtime of BinCSA, APBEA and ΔSearch algorithms. From Figure 10, we can see that all the algorithms achieve the optimal solution. Table 9 shows the instances where the three algorithms fail to achieve optimal solutions. ΔSearch fails to achieve optimal solution only for one instance whereas BinCSA fails to achieve optimal solution for two instances. Moreover, both BinCSA and APBEA suffer from a segfault when ran on MS1 and MT1 as they store the computational data on the stack which causes a stack overflow for larger instances. Thus, ΔSearch is superior in performance to both BinCSA and APBEA. Figure 10 also shows that ΔSearch is faster than both APBEA and BinCSA even though APBEA and BinCSA were implemented in C++ while ΔSearch is implemented in Python. Thus, ΔSearch is on par in quality and runtime with the state of the art algorithm APBEA even with a slower implementation. 5.1.6 Prize Collecting Vertex Cover. Prize Collecting Vertex Cover (PCVC) is another example of a non-monotone subgraph problem which is NP-hard. It was first introduced in [57]. Although it does not have many applications by itself, many of its variants are well researched [63, 68, 101]. The main reason we chose PCVC to evaluate our framework is because it is a non-monotone graph problem and that PCVC can be solved using Local Ratio. Hence, Local Ratio will be the only baseline , Vol. 1, No. 1, Article . Publication date: June 2026.

R.S. Valan Arasu et al.

Table 10. PCVC - ΔSearch vs. Local Ratio for the synthetic dataset [69].↑ is better for quality and time. Ratio for Synthetic [69] dataset Algorithm Avg Quality Avg Time Local Ratio +38.19% -75.78%

Fig. 11. Prize Collecting Vertex Cover - ΔSearch vs. Local Ratio baselines for synthetic dataset [69].

for this experiment. For benchmark, we use the instance generation algorithm [69] from the related generalized vertex cover problem. Figure 11 illustrates the cost of solutions and runtimes of Local Ratio and ΔSearch algorithms. Table 10 shows the total average ratio of the PCVC cost and runtimes between ΔSearch and Local Ratio. As can be seen from Figure 11 and Table 10, ΔSearch achieves better solution quality compared to Local Ratio. On the other hand, Local Ratio achieves a better runtime than ΔSearch. Local Ratio is a constructive algorithm which only generates solutions that improve the overall solution. On the other hand, ΔSearch runs the scoring function multiple times which slows down the ΔSearch algorithm. Yet despite guidance from the user, Local Ratio fails to find a better solution than ΔSearch. 5.2

Multi-Start ΔSearch

ΔSearch is a deterministic algorithm that returns the same solution when provided the same initial candidates for the graph elements. But ΔSearch is indeed sensitive to the ordering of the graph elements. This sensitivity can be exploited by running the algorithm multiple times with different orderings. Each repeat of the algorithm will change the search space of the algorithm, improving the chances of achieving a better solution at least in one of the repeats. This is a common technique in combinatorial optimization problems known as Multi-start. Figure 12 shows the improvement in solution quality with an increasing number of repeats. Figure 12 shows that the quality of the solution improves with the number of repeats. The improvement in solution quality usually decreases with the number of repeats and eventually converges to a steady state. There exists a sweet spot that balances the solution quality and the runtime that depends on the nature of the problem and the size of the instance. 5.3

Accelerating Exact Search using ΔSearch

In [89], an exact exponential algorithm, Russian Doll Search (RDS), was introduced to solve weighted hereditary problems. The main motivation was the pruning mechanisms that hereditary problems allowed for when searching via RDS. This modified RDS uses bounds generated by its previous searches to prune its future searches. We integrate ΔSearch into this algorithm, as shown in Figure 1, to improve the bounds so that the modified RDS prunes more search space thereby achieving a good speedup. Inspired by n-way parallelism [26], we run 3 threads of ΔSearch in parallel to generate bounds for the modified RDS. The ΔSearch threads run based on the exploration done by the exact algorithm. That is, the ΔSearch threads will only search for solutions that the exact algorithm has not explored. Figure 13 shows the runtime of the modified RDS for the unweighted hereditary problem of Maximum Planar Subgraph on the North [34] graph dataset. From the figure, we can see that , Vol. 1, No. 1, Article . Publication date: June 2026.

Solving Subgraph Extraction Problems Using ΔSearch

Fig. 12. Improvement in solution quality for different problems with increasing number of repeats.

Fig. 13. Improving the runtime of exact algorithm using ΔSearch for the MPS problem on North [34] dataset.

in most graph instances, ΔSearch provides a massive speedup to the modified RDS, achieving a median speedup of 2.639×. The reason why ΔSearch slows down the search for some instances is that aggressive pruning might eliminate searches that could eventually yield a better bound. Although pruning will never prune an optimal solution, it might prune a solution that could serve as a better bound for future pruning. However, as can be seen from the figure, for most of the graph instances, ΔSearch accelerates the exact algorithm. 6

Related Work

A significant amount of prior work has been done to unify optimization problem under general frameworks such as Constraint Programming (CP), Integer Linear Programming (ILP), generic branch and bound methods, meta-heuristic methods and, most recently, learning based approaches. Focus specifically on Graph Optimization Problems has been low but still existent such as the Hereditary Graph formulation and some learning based approaches. Most of these frameworks emphasize high generality and expressiveness, thus incurring significant scalability challenges or requiring problem-specific modeling and tuning. This gap motivates the need for a framework such as ΔSearch, whose formulation covers a large class of problems with similar underlying structure which also enables it to exploit the structure to enable efficient execution. ΔSearch also requires only a simpler underlying structure, making it more intuitive to formulate the graph problem in its domain. , Vol. 1, No. 1, Article . Publication date: June 2026.

R.S. Valan Arasu et al.

Constraint Optimization Problems (COP) provide a highly expressive framework in which problems can be encoded as variables with domains and constraints governing the feasible assignment of variables. COP can naturally capture a wide range of graph problems [79] including selection problems (Maximum Independent Set, Maximum Vertex Cover, etc), labeling problems (Graph coloring), and assignment based problems such as Vehicle Routing Problem (VRP) and Facility location problems [16]. COP allows constraints to be stated in an intuitive and flexible manner. Advances in Constraint Programming (methodology for solving COP) has brought multiple strategies [33] to improve performance such as look ahead strategies, domain filtering and clever backtracking. Despite these advances, Constraint Programming often suffers from poor scalability due to the large number of structural constraints inherent in large graphs which make constraint generation, propagation and repeated feasibility checks limit the performance. Practical success of COP in graph problems have usually been due to solver specific heuristic or extensive problem tuning. Integer Linear Programming (ILP) and Mixed Integer Linear Programming (MILP) formulation allows graph problems to be encoded as linear constraints over integer variables. Although more restricted than COP, a large class of graph problems [2, 4, 36] including minimum cut variants, facility location, routing, matching and partitioning problems have been successfully solved using ILP and MILP formulations. The success of ILP and MILP formulations is mainly due to the solvers which have been heavily researched and experimented. Translating graph problems into linear constraints and optimization functions introduces a significant abstraction burden which cannot be automated. This has resulted in no single general ILP/MILP framework for graph algorithms and the prior works have always manually abstracted the graph problems and then used the solvers. Translating graph problems into linear constraints also introduces a large number of variables and constraints as these formulations cannot naturally handle graph structures. These issues usually result in reduced performance from these solvers. When compared to COP, [30] noted that ILP/MILP formulations usually tend to do well when the search space is large with few constraints whereas COP formulations do well when the search space is highly constrained. In light of this, [1, 12, 77] have tried combining both COP and MILP together to achieve better performance. Hereditary graphs properties are those properties that are closed under vertex or edge deletions. Hereditary properties serve as a unification of multiple graph optimization problems where the goal is to find the maximum weighted subgraph. Many classical NP graph problems such as Maximum Clique, Maximum Independent Set Feedback Vertex Set problems fall into this category. Hereditary property problems are well-studied theoretically [13, 15, 82] and it also provides a more intuitive formulation than CSP or MILP formulations. While the underlying assumptions leads to more efficient exact algorithms [27, 89] than naive search albeit still being exponential, it is highly restricted compared to CSP or ILP/MILP. Branch and Bound frameworks can broadly be applied to Graph optimization algorithms. Branchand-bound (BnB) [41] systematically explores the solution space while pruning regions using upper and lower bounds on the objective. In principle, BnB can solve arbitrary combinatorial graph optimization problems. But the bounds always need to be problem-specific and even with the bounds, BnB frameworks tend to perform poorly without domain-tailored optimizations. [70] presents a survey on how to implement BnB algorithms in multiple ways depending on the problem at hand. Meta-heuristics [44] such as Tabu Search, Greedy randomized adaptive search procedure (GRASP), Ant Colony Optimization, Evolutionary Algorithms, and Very-Large Scale Neighborhood Search provide general search templates that explore the solution space heuristically. These methods have been applied to a wide range of graph problems, including routing, clustering, partitioning, and scheduling. Meta-heuristics can scale to large instances and often produce high-quality solutions in practice despite the absence of optimality guarantees. But the scaling and performance are , Vol. 1, No. 1, Article . Publication date: June 2026.

Solving Subgraph Extraction Problems Using ΔSearch

highly dependent on not just problem-specific tuning but also problem-specific implementation changes, which make it impossible for them to be treated as a black box for solving various graph problems. Metaheuristics also require heavy experimentation, as it is hard to know in advance which metaheuristic and which parameter configuration would work well for a problem [76]. They also cannot be applied indiscriminately to all problems as they require problem-specific implementation for most of the problems. Even a single metaheuristic will have variances in performance even for a single problem instance due to its stochastic nature. Local Ratio [7] is an approximation algorithm designed for optimization problems. Local Ratio works by breaking a given weight function 𝑤 into multiple simpler weight functions 𝑤 1, 𝑤 2, · · · , 𝑤𝑘 where Σ𝑖 𝑤𝑖 = 𝑤 and using a user-provided r-approximation algorithm for simpler weight functions to obtain an r-approximate solution for the general problem. Local ratio can be used to solve covering problems (e.g., Partial Vertex Cover, Feedback Vertex Set, Steiner Tree) and Packing problems (e.g., Independent Set, Interval Scheduling). Local Ratio achieves approximation guarantees, scalability and also applies to a large class of problems. But it is more complicated to use as the user has to provide a r-approximation algorithm for a simpler weighted instance. This puts the burden on the user to find simpler weight functions and algorithms to solve them. Learning based approaches [38, 62, 75] have focused on creating unified architectures capable of solving multiple graph optimization problems by changing optimization function or training signal. These frameworks have been applied to graph optimization problems such as Minimum Spanning Tree, Traveling Salesman Problem, Vehicle Routing, Balanced Graph Partitioning and Maximum Independent Set. Unlike some of the previous formulations, learning-based approaches are graph-aware and can exploit the structural patterns across graph problems. But these approaches lack typical formal guarantees, are sensitive to training distribution and are often evaluated on a narrow set of problems and graph sizes and distributions. This makes their performance on out-of-distribution instances unpredictable. In contrast to the above approaches, the ΔSearch framework targets a middle ground between expressiveness and efficiency while still providing an intuitive abstraction for any graph problem. Rather than relying on highly generic solvers or problem-specific algorithms, ΔSearch imposes a slightly restrictive assumption which still covers a large class of problems and which can be exploited to gain efficiency. This design allows ΔSearch to scale beyond traditional exact frameworks while retaining formal correctness guarantees, thereby addressing key limitations of existing unified graph optimization frameworks. 7

Conclusions and Future Work

In this paper, we introduced the Difference of Monotone formulation as a general reward-penalty decomposition that unifies Hereditary, Ancestral and other graph problems. We also presented ΔSearch, a heuristic that solves DoM problems with at most 𝑂 (𝑛 2 ) calls to the scoring functions. We evaluated ΔSearch for a wide range of graph problems in which it surpassed the state of the art for UFLP and PCVC, remained competitive for MPS and achieved about 80-90% of the solution quality for the remaining problems without any problem-specific tuning. We further demonstrated its effectiveness in pruning the search spaces for exact algorithms achieving around 2.6× speedup for MPS. In future work, we plan to further improve ΔSearch, derive formal approximation guarantees and develop adaptive ordering strategies to improve solutions. Data Availability Statement The experimental graph datasets, code for ΔSearch and all baseline implementations used are available at <Anonymous Github link>. , Vol. 1, No. 1, Article . Publication date: June 2026.

R.S. Valan Arasu et al.

References [1] Tobias Achterberg, Timo Berthold, Thorsten Koch, and Kati Wolter. 2008. Constraint integer programming: A new approach to integrate CP and MIP. In International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming. Springer, 6–20. [2] HA Almohamad and Salih O Duffuaa. 2002. A linear programming approach for the weighted graph matching problem. IEEE Transactions on pattern analysis and machine intelligence 15, 5 (2002), 522–525. [3] Amihood Amir and Dmitry Keselman. 1997. Maximum agreement subtree in a set of evolutionary trees: Metrics and efficient algorithms. SIAM J. Comput. 26, 6 (1997), 1656–1669. [4] Yash P Aneja. 1980. An integer linear programming approach to the Steiner problem in graphs. Networks 10, 2 (1980), 167–178. [5] Julián Aráoz, Elena Fernández, and Carles Franquesa. 2009. The clustered prize-collecting arc routing problem. Transportation Science 43, 3 (2009), 287–300. [6] Ali Baharev, Hermann Schichl, Arnold Neumaier, and Tobias Achterberg. 2021. An exact method for the minimum feedback arc set problem. Journal of Experimental Algorithmics (JEA) 26 (2021), 1–28. [7] Reuven Bar-Yehuda, Keren Bendel, Ari Freund, and Dror Rawitz. 2004. Local ratio: A unified framework for approximation algorithms. in memoriam: Shimon even 1935-2004. ACM Computing Surveys (CSUR) 36, 4 (2004), 422–463. [8] John E Beasley. 1990. OR-Library: distributing test problems by electronic mail. Journal of the operational research society 41, 11 (1990), 1069–1072. [9] David Bergman and Arvind U Raghunathan. 2015. A Benders approach to the minimum chordal completion problem. In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Springer, 47–64. [10] Bibek Bhattarai and Howie Huang. 2022. SteinerLog: Prize collecting the audit logs for threat hunting on enterprise network. In Proceedings of the 2022 ACM on Asia Conference on Computer and Communications Security. 97–108. [11] Guy E Blelloch, Jeremy T Fineman, and Julian Shun. 2012. Greedy sequential maximal independent set and matching are parallel on average. In Proceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures. 308–317. [12] Alexander Bockmayr and Thomas Kasper. 1998. Branch and infer: A unifying framework for integer and finite domain constraint programming. INFORMS Journal on Computing 10, 3 (1998), 287–300. [13] Béla Bollobás and Andrew Thomason. 1997. Hereditary and monotone properties of graphs. In The Mathematics of Paul Erdös II. Springer, 70–78. [14] Édouard Bonnet and Florian Sikora. 2018. The PACE 2018 parameterized algorithms and computational experiments challenge: The third iteration. In IPEC 2018. [15] Mieczysław Borowiecki, Izak Broere, Marietjie Frick, Peter Mihok, and Gabriel Semanišin. 1997. A survey of hereditary properties of graphs. Discussiones Mathematicae Graph Theory 17, 1 (1997), 5–50. [16] Sally C Brailsford, Chris N Potts, and Barbara M Smith. 1999. Constraint satisfaction problems: Algorithms and applications. European journal of operational research 119, 3 (1999), 557–581. [17] William Brendel, Mohamed Amer, and Sinisa Todorovic. 2011. Multiobject tracking as maximum weight independent set. In CVPR 2011. IEEE, 1273–1280. [18] William Brendel and Sinisa Todorovic. 2010. Segmentation as maximum-weight independent set. Advances in neural information processing systems 23 (2010). [19] Gruia Călinescu, Cristina G Fernandes, Ulrich Finkler, and Howard Karloff. 1998. A better approximation algorithm for finding planar subgraphs. Journal of Algorithms 27, 2 (1998), 269–302. [20] Markus Chimani and Carsten Gutwenger. 2009. Non-planar core reduction of graphs. Discrete Mathematics 309, 7 (2009), 1838–1855. [21] Markus Chimani, Ivo Hedtke, and Tilo Wiedera. 2019. Exact algorithms for the maximum planar subgraph problem: New models and experiments. Journal of Experimental Algorithmics (JEA) 24 (2019), 1–21. [22] Markus Chimani, Karsten Klein, and Tilo Wiedera. 2016. A note on the practicality of maximal planar subgraph algorithms. In International Symposium on Graph Drawing and Network Visualization. Springer, 357–364. [23] Markus Chimani and Tilo Wiedera. 2016. An ILP-based proof system for the crossing number problem. In 24th annual European symposium on algorithms (ESA 2016). Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 29–1. [24] Fabián A Chudak and David B Shmoys. 2003. Improved approximation algorithms for the uncapacitated facility location problem. SIAM J. Comput. 33, 1 (2003), 1–25. [25] Robert J Cimikowski. 1994. Branch-and-bound techniques for the maximum planar subgraph problem. International journal of computer mathematics 53, 3-4 (1994), 135–147. [26] Romain E Cledat, Tushar Kumar, and Santosh Pande. 2011. Efficiently speeding up sequential computation through the n-way programming model. In Proceedings of the 2011 ACM international conference on Object oriented programming , Vol. 1, No. 1, Article . Publication date: June 2026.

Solving Subgraph Extraction Problems Using ΔSearch

systems languages and applications. 537–554. [27] Sara Cohen, Benny Kimelfeld, and Yehoshua Sagiv. 2008. Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties. J. Comput. System Sci. 74, 7 (2008), 1147–1159. [28] Gérard Cornuéjols, George Nemhauser, and Laurence Wolsey. 1983. The uncapicitated facility location problem. Technical Report. Cornell University Operations Research and Industrial Engineering. [29] Fei Dai and Jie Wu. 2004. An extended localized algorithm for connected dominating set formation in ad hoc wireless networks. IEEE transactions on parallel and distributed systems 15, 10 (2004), 908–920. [30] Ken Darby-Dowman and James Little. 1998. Properties of some combinatorial optimization problems and their effect on the performance of integer programming and constraint logic programming. INFORMS Journal on Computing 10, 3 (1998), 276–286. [31] Andrea D’ascenzo, Julian Meffert, Petra Mutzel, and Fabrizio Rossi. 2025. Enhancing Graph Edit Distance Computation: Stronger and Orientation-based ILP Formulations. Proceedings of the VLDB Endowment 18, 11 (2025), 4737–4749. [32] Hubert de Fraysseix and Patrice Ossona de Mendez. 2012. Trémaux trees and planarity. European Journal of Combinatorics 33, 3 (2012), 279–293. [33] Rina Dechter. 2003. Constraint processing. Elsevier. [34] Giuseppe Di Battista, Ashim Garg, Giuseppe Liotta, Armando Parise, Roberto Tamassia, Emanuele Tassinari, Francesco Vargiu, and Luca Vismara. 2000. Drawing directed acyclic graphs: An experimental study. International Journal of Computational Geometry & Applications 10, 06 (2000), 623–648. [35] Fernando HC Dias, Lucia Williams, Brendan Mumey, and Alexandru I Tomescu. 2022. Fast, flexible, and exact minimum flow decompositions via ILP. In International Conference on Research in Computational Molecular Biology. Springer, 230–245. [36] Fernando HC Dias, Lucia Williams, Brendan Mumey, and Alexandru I Tomescu. 2025. Minimum flow decomposition in graphs with cycles using integer linear programming. Journal of Global Optimization (2025), 1–32. [37] Yuanyuan Dong, Andrew V Goldberg, Alexander Noe, Nikos Parotsidis, Mauricio GC Resende, and Quico Spaen. 2021. New instances for maximum weight independent set from a vehicle routing application. In Operations Research Forum, Vol. 2. Springer, 48. [38] Iddo Drori, Anant Kharkar, William R Sickinger, Brandon Kates, Qiang Ma, Suwen Ge, Eden Dolev, Brenda Dietrich, David P Williamson, and Madeleine Udell. 2020. Learning to solve combinatorial optimization problems on real-world graphs in linear time. In 2020 19th IEEE International Conference on Machine Learning and Applications (ICMLA). IEEE, 19–24. [39] Ender Özcan Emrullah Sonuç. [n. d.]. APBEA. https://github.com/3mrullah/ABPEA Accessed: 2026-03-17. [40] Deqian Fu, Lihua Han, Zifen Yang, and Seong Tae Jhang. 2016. A greedy algorithm on constructing the minimum connected dominating set in wireless network. International Journal of Distributed Sensor Networks 12, 7 (2016), 1703201. [41] François Galea and Bertrand Le Cun. 2007. Bob++: a framework for exact combinatorial optimization methods on parallel machines. In International Conference High Performance Computing & Simulation. 779–785. [42] Zvi Galil. 1986. Efficient algorithms for finding maximum matching in graphs. ACM Computing Surveys (CSUR) 18, 1 (1986), 23–38. [43] Golnaz Gharachorlu and Nick Sumner. 2018. Avoiding the familiar to speed up test case reduction. In 2018 IEEE International Conference on Software Quality, Reliability and Security (QRS). IEEE, 426–437. [44] Teofilo F Gonzalez. 2007. Handbook of approximation algorithms and metaheuristics. Chapman and Hall/CRC. [45] Luis Gouveia. 1995. A 2n constraint formulation for the capacitated minimal spanning tree problem. Operations research 43, 1 (1995), 130–141. [46] Ernestine Großmann, Sebastian Lamm, Christian Schulz, and Darren Strash. 2023. Finding near-optimal weight independent sets at scale. In Proceedings of the Genetic and Evolutionary Computation Conference. 293–302. [47] Ernestine Großmann, Kenneth Langedal, and Christian Schulz. [n. d.]. MMWIS. https://github.com/KarlsruheMIS/ KaMIS Accessed: 2026-03-17. [48] Ernestine Großmann, Kenneth Langedal, and Christian Schulz. 2024. A comprehensive survey of data reduction rules for the maximum weighted independent set problem. arXiv preprint arXiv:2412.09303 (2024). [49] Jiewei Gu. [n. d.]. GuMWIS. https://github.com/mwis-abc/mwis-source-code Accessed: 2026-03-17. [50] Jiewei Gu, Weiguo Zheng, Yuzheng Cai, and Peng Peng. 2021. Towards computing a near-maximum weighted independent set on massive graphs. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 467–477. [51] Stefano Gualandi and Federico Malucelli. 2012. Exact solution of graph coloring problems via constraint programming and column generation. INFORMS Journal on Computing 24, 1 (2012), 81–100. [52] Sudipto Guha, Refael Hassin, Samir Khuller, and Einat Or. 2003. Capacitated vertex covering. Journal of Algorithms 48, 1 (2003), 257–270.

, Vol. 1, No. 1, Article . Publication date: June 2026.

R.S. Valan Arasu et al.

[53] Sudipto Guha and Samir Khuller. 1999. Greedy strikes back: Improved facility location algorithms. Journal of algorithms 31, 1 (1999), 228–248. [54] Kris Hauser. 2014. The minimum constraint removal problem with three robotics applications. The International Journal of Robotics Research 33, 1 (2014), 5–17. [55] Raka Jovanovic and Milan Tuba. 2013. Ant colony optimization algorithm with pheromone correction strategy for the minimum connected dominating set problem. Computer Science and Information Systems 10, 1 (2013), 133–149. [56] Michael Jünger and Petra Mutzel. 1994. The polyhedral approach to the maximum planar subgraph problem: New chances for related problems. In International Symposium on Graph Drawing. Springer, 119–130. [57] Richard M Karp. 2009. Reducibility among combinatorial problems. In 50 Years of Integer Programming 1958-2008: from the Early Years to the State-of-the-Art. Springer, 219–241. [58] Thorsten Koch, Alexander Martin, and Stefan Voß. 2001. SteinLib: An updated library on Steiner tree problems in graphs. In Steiner trees in industry. Springer, 285–325. [59] Miyuki Koshimura, Emi Watanabe, Yuko Sakurai, and Makoto Yokoo. 2022. Concise integer linear programming formulation for clique partitioning problems. Constraints 27, 1 (2022), 99–115. [60] Lawrence Kou, George Markowsky, and Leonard Berman. 1981. A fast algorithm for Steiner trees. Acta informatica 15, 2 (1981), 141–145. [61] Jozef Kratica, Dušan Tošic, Vladimir Filipović, and Ivana Ljubić. 2001. Solving the simple plant location problem by genetic algorithm. RAIRO-Operations Research 35, 1 (2001), 127–142. [62] Chuan Liu, Jingwei Wang, Yunkang Cao, Min Liu, and Weiming Shen. 2022. GON: End-to-end optimization framework for constraint graph optimization problems. Knowledge-Based Systems 254 (2022), 109697. [63] Xiaofei Liu, Weidong Li, and Jinhua Yang. 2023. A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties. Frontiers of Computer Science 17, 3 (2023), 173404. [64] Yang Liu, Hejiao Huang, Kaiqiang Yu, Shengxin Liu, and Cheng Long. 2025. Efficient maximum s-bundle search via local vertex connectivity. Proceedings of the ACM on Management of Data 3, 1 (2025), 1–27. [65] Ivana Ljubić. 2021. Solving Steiner trees: Recent advances, challenges, and perspectives. Networks 77, 2 (2021), 177–204. [66] Zoran Maksimović. 2016. A new mixed integer linear programming formulation for the maximum degree bounded connected subgraph problem. Publications de l’Institut Mathematique 99, 113 (2016), 99–108. [67] Pasin Manurangsi. 2018. A Note on Max 𝑘-Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation. arXiv preprint arXiv:1810.03792 (2018). [68] Christine Markarian and Abdul Nasser El-Kassar. 2021. Algorithmic View of Online Prize-collecting Optimization Problems.. In ICEIS (1). 744–751. [69] Marija Milanović. 2010. Solving the generalized vertex cover problem by genetic algorithm. Computing and Informatics 29, 6+ (2010), 1251–1265. [70] David R Morrison, Sheldon H Jacobson, Jason J Sauppe, and Edward C Sewell. 2016. Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discrete Optimization 19 (2016), 79–102. [71] Anna Moss and Yuval Rabani. 2007. Approximation algorithms for constrained node weighted steiner tree problems. SIAM J. Comput. 37, 2 (2007), 460–481. [72] Dennis M Moyles and Gerald L Thompson. 1969. An algorithm for finding a minimum equivalent graph of a digraph. Journal of the ACM (JACM) 16, 3 (1969), 455–460. [73] Assaf Natanzon, Ron Shamir, and Roded Sharan. 2001. Complexity classification of some edge modification problems. Discrete Applied Mathematics 113, 1 (2001), 109–128. [74] Bruno Nogueira and Rian GS Pinheiro. 2020. A GPU based local search algorithm for the unweighted and weighted maximum s-plex problems. Annals of Operations Research 284, 1 (2020), 367–400. [75] Yun Peng, Byron Choi, and Jianliang Xu. 2021. Graph learning for combinatorial optimization: a survey of state-ofthe-art. Data Science and Engineering 6, 2 (2021), 119–141. [76] Fernando Peres and Mauro Castelli. 2021. Combinatorial optimization problems and metaheuristics: Review, challenges, design, and development. Applied sciences 11, 14 (2021), 6449. [77] Robert Rodosek, Mark G Wallace, and Mozafar T Hajian. 1999. A new approach to integrating mixed integer programming and constraint logicprogramming. Annals of Operations research 86, 0 (1999), 63–87. [78] Emmanuel Romero Ruiz, Emmanuel Antonio Cuevas, Irwin Enrique, Villalobos López, , and Carlos Segura Gonzále. [n. d.]. HeathcliffAC. https://github.com/HeathcliffAC/SteinerTreeProblem Accessed: 2026-03-17. [79] Stuart Russell and Peter Norvig. 2020. Artificial Intelligence: A Modern Approach, 4th US ed. Artificial Intelligence. Prentice-Hall, Egnlewood Cliffs (2020), 180–204. [80] Shuichi Sakai, Mitsunori Togasaki, and Koichi Yamazaki. 2003. A note on greedy algorithms for the maximum weighted independent set problem. Discrete applied mathematics 126, 2-3 (2003), 313–322.

, Vol. 1, No. 1, Article . Publication date: June 2026.

Solving Subgraph Extraction Problems Using ΔSearch

[81] Alexander Schäfer. 2009. Exact algorithms for s-club finding and related problems. Ph. D. Dissertation. FriedrichSchiller-University Jena. [82] Edward R Scheinerman and Jennifer Zito. 1994. On the size of hereditary classes of graphs. Journal of Combinatorial Theory, Series B 61, 1 (1994), 16–39. [83] Emrullah Sonuç. 2021. Binary crow search algorithm for the uncapacitated facility location problem. Neural Computing and Applications 33, 21 (2021), 14669–14685. [84] Emrullah Sonuç and Ender Özcan. 2023. An adaptive parallel evolutionary algorithm for solving the uncapacitated facility location problem. Expert Systems with Applications 224 (2023), 119956. [85] Emrullah Sonuç. [n. d.]. BinCSA. https://github.com/3mrullah/BinCSA Accessed: 2026-03-17. [86] Xuemei Sun, Yongxin Yang, and Maode Ma. 2019. Minimum connected dominating set algorithms for ad hoc sensor networks. Sensors 19, 8 (2019), 1919. [87] Hiromitsu Takahashi. 1980. An approximate solution for steiner problem in graphs. Math. Japonica 24, 6 (1980), 573–577. [88] Robert Endre Tarjan and Anthony E Trojanowski. 1977. Finding a maximum independent set. SIAM J. Comput. 6, 3 (1977), 537–546. [89] Svyatoslav Trukhanov, Chitra Balasubramaniam, Balabhaskar Balasundaram, and Sergiy Butenko. 2013. Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations. Computational Optimization and Applications 56, 1 (2013), 113–130. [90] Masoumeh Vali and Khodakaram Salimifard. 2017. A constraint programming approach for solving multiple traveling salesman problem. In The sixteenth international workshop on constraint modelling and reformulation. 1–17. [91] Ling-Yun Wu, Xiang-Sun Zhang, and Ju-Liang Zhang. 2006. Capacitated facility location problem with general setup cost. Computers & Operations Research 33, 5 (2006), 1226–1241. [92] Wenzheng Xu, Weifa Liang, Zichuan Xu, Jian Peng, Dezhong Peng, Tang Liu, Xiaohua Jia, and Sajal K Das. 2020. Approximation algorithms for the generalized team orienteering problem and its applications. IEEE/ACM Transactions on Networking 29, 1 (2020), 176–189. [93] Mihalis Yannakakis. 1978. Node-and edge-deletion NP-complete problems. In Proceedings of the tenth annual ACM symposium on Theory of computing. 253–264. [94] Yasin Yigit, Zuleyha Akusta Dagdeviren, Orhan Dagdeviren, and Moharram Challenger. 2021. Performance evaluation of capacitated vertex cover algorithms for security applications in wireless sensor networks. In 2021 7th International Conference on Electrical, Electronics and Information Engineering (ICEEIE). Ieee, 619–624. [95] Haiyuan Yu, Alberto Paccanaro, Valery Trifonov, and Mark Gerstein. 2006. Predicting interactions in protein networks by completing defective cliques. Bioinformatics 22, 7 (2006), 823–829. [96] Stéphane Zampelli, Yves Deville, and Christine Solnon. 2010. Solving subgraph isomorphism problems with constraint programming. Constraints 15, 3 (2010), 327–353. [97] Andreas Zeller. 1999. Yesterday, my program worked. Today, it does not. Why? ACM SIGSOFT Software engineering notes 24, 6 (1999), 253–267. [98] Andreas Zeller, Rahul Gopinath, Marcel Böhme, Gordon Fraser, and Christian Holler. 2024. The Fuzzing Book. CISPA Helmholtz Center for Information Security. https://www.fuzzingbook.org/ Retrieved 2024-07-01 16:50:18+02:00. [99] Andreas Zeller and Ralf Hildebrandt. 2025. Simplifying and Isolating Failure-Inducing Input: A Retrospective on Delta Debugging. IEEE Trans. Softw. Eng. 51, 3 (March 2025), 820–824. doi:10.1109/TSE.2025.3537167 [100] Fazhan Zhang, Yichao He, Haibin Ouyang, and Wenben Li. 2023. A fast and efficient discrete evolutionary algorithm for the uncapacitated facility location problem. Expert Systems with Applications 213 (2023), 118978. [101] Mingchao Zhou, Zhao Zhang, and Ding-Zhu Du. 2024. Approximation algorithm for prize-collecting vertex cover with fairness constraints. Journal of Combinatorial Optimization 48, 3 (2024), 20.

Received 17 March 2026

, Vol. 1, No. 1, Article . Publication date: June 2026.

Record · ID 271785 · SHA-256 23f2b809b1ba99d6
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.