Fast Proxy Experiment Design for Causal Effect Identification

We address limitation 1 and the minor comments below.

Limitations

L1:

Note that our reformulations allow for solving the MCID problem exactly. Given that the MCID problem is NP-hard, the best achievable solution for an exact algorithm is to provide a faster reformulation of another NP-hard problem, which is precisely what we have accomplished. In addition to vastly better performance in practice, our reformulations offer significant theoretical speedups for multiple-district graphs. Specifically, our algorithm operates quadratically in the number of districts, whereas the original approach is exponential. Thus, while the MCID problem is NP-hard, we have managed to solve it exactly by multiple orders of magnitude faster than the previous approach, as well as providing theoretical guarantees for a polynomial-time complexity in terms of the number of districts.

Minor comment:

W7:

Yes, the sentence should read "... a specific class of causal effects in which the effect..." We apologize for the oversight.

We sincerely thank the reviewer for their thorough reading of our paper and their detailed feedback. We have addressed each comment and question below.

Weaknesses:

W1:

We acknowledge this comment. We have made our statements more precise to clarify that data fusion for causal identification goes way back (as we ourselves build upon a follow-up to Bareinboim and Pearl, 2012, namely Lee et al., 2020), and we are revising our manuscript to include a comprehensive literature review on this; but that the idea of surrogate experiment design for causal identification was put forward by Akbari et al., 2022.

W2:

We indeed slightly diverged from the original definitions of hedge and district, particularly by not imposing maximality. This was done solely to simplify the presentation of our work and enhance readability. These adjusted definitions are what make our arguments sound. However, we acknowledge that this can be confusing for certain readers. To address this, we are updating our manuscript to use alternative names or be more explicit about the altered definitions wherever possible. We have additionally included proper citations to the relevant papers by Richardson et al. 2023 and Shpitser et al. 2008, 2012, 2014.

W3:

If $S_\ell$ is identifiable in $\mathcal{G}$, i.e., there is no hedge formed for$S_\ell$ in $\mathcal{G}$, then $H_\mathcal{G}(S_\ell) = \emptyset$. Thus, the statement for any $W$ in $H_\mathcal{G}(S_\ell)$, $\mathcal{I}_k \cap W \neq \emptyset$ is true by the concept of vacuous truth, as the antecedent (i.e., $\forall W \in H_\mathcal{G}(S_\ell)$) can never be satisfied.

As for your second example, we are not sure what you mean by "when $S_\ell$ is a hedge." By our definition of hedge (Def. 2), $S_\ell$ can never be its own hedge. If you meant that $S_\ell$ is within a hedge for another district $S_k$, then our statement is still valid. For instance, consider the graph of Fig. 2(d), where $S_2$ is involved in a hedge formed for $S_1$, and our statement is still valid with $I_k=\\{S_2\\}$.

W4:

Our Def. 3 defines the hedge hull for a (single) district. Right after this definition, we define the hedge hull of an arbitrary set $S$ as the union of the hedge hulls of each of its districts. In your specific example, $S=\\{Z,Y\\}$ consists of two districts, $S_1=\\{Z\\}$ and $S_2=\\{Y\\}$. Following Def. 3, the hedge hull of $S_1$ is $S_1$ itself, and the same goes for $S_2$. Therefore, $\mathcal{H}_{\mathcal{G}}(S)=S_1\cup S_2=S$, which indicates that $P(Y\mid do(X))$ is identifiable, as expected.

Our paper first covers the case where $S$ comprises a single district, then generalizes the results to the case of arbitrary sets (see lines 157-158,). As such, Alg. 2 is designed for single-district $S$. We have made this clearer in the revised version. In particular, we have explicitly stated that if $S$ comprises more than one district, Alg. 2 is run on each district separately to compute the hedge hull of $S$.

W5:

Due to space constraints, we had to move the details of the SAT construction to Appendix B.2. However, with the extra page allocated for the camera-ready, we are relocating these construction details to the main text. We have also provided a walkthrough of how the SAT expression can be constructed using a toy graph from Figure 2. This will clarify the SAT reformulation. We will also add the DFS encoding of a graph as a SAT problem in the appendix and reference it in the main text, aiding readers, especially those new to SAT constructions.​

We have condensed Algorithms 2 and 3, and brought them into the main text, with a brief explanation of the rationale behind them to aid the reader in understanding the work more easily.

W6:

It’s important to clarify that the MCID problem is NP-hard, as shown by Akbari et al. 2022, with the best achievable polynomial-time approximation being within a $\log(n)$ factor, where $n$ is the number of vertices. Thus, the worst-case time complexity of our reformulations is expected to be exponential in $n$.

Our reformulations not only solve the problem exactly, but also provide a significant speedup of 1,000 to 100,000,000 times for the single-district case.

Moreover, for the multiple-district case, our approach is only quadratic in the number of districts (theoretically guaranteed), unlike the previous method which required iterating over an exponential number of partition sets. This efficiency is demonstrated in Fig. 3b, showing speedups of 50 to 10,000 times for a modest number of districts.

We believe therefore the term “fast” is justified. Although the exact solution remains exponential in the worst case, our reformulations make solving these problems practically feasible and significantly more efficient, especially for large graphs.

Another significant contribution is our novel min-cost experiment design for generalized adjustment (Section 4), for which we provide a polynomial-time algorithm.

These distinctions will be more clearly presented in the revised text to accurately reflect our contributions and their practical implications.

Questions (Q1):

Yes, the condition $S \subsetneq W$ ensures that $S$ cannot form a hedge for itself, in line with Shpitser and Pearl (2006), which impose $F_1\subsetneq F_2$ for two r-rooted c-forests. Without this, $S$ would always have a trivial hedge, itself, Consequently, many of our statements and proofs would need to be modified to exclude the trivial hedge. complicating many statements and proofs. For example, "hitting all of the hedges of $S$" would need to be "hitting all of the nontrivial hedges of $S$."

Thank you for your time and detailed feedback. We are confident in the correctness of the technical statements in our paper. We appreciate your other comments, most of which are easily fixable, and will be promptly addressed in the manuscript. We kindly request that you acknowledge the soundness of our work and consider increasing your score accordingly.

The average time taken in seconds to solve one instance of the MCID problem for our SAT approach and the minimal hedge solver (MHS) of Akbari et al., 2022. The speedup factor refers to MHS time divided by SAT time.

Thank you for taking the time to read our rebuttal and engage in the discussion. Please find our responses to your comments and questions below.

W2

Our claims, including the results we reference from other works, such as Proposition 1, are valid under our own definitions. However, it would not be difficult to use the original definitions. For example, while we did not impose maximality when defining a district, we refer to $\\{S_i\\}_{i=1}^{r}$ as the ‘maximal districts’ of $\mathcal{G}[S]$ in Proposition 1, Lemma 1, and Theorem 2, aligning with the original definition. The decision not to impose maximality in our definitions was made for simplicity, as there are sections of the paper where we discuss connected components that are not necessarily ‘maximal’, such as the set $S$ itself. Based on your suggestion, we will use standard terms for non-maximal components, but please note that our claims remain valid with this renaming.

1,000 to 100,000,000 speed up

Based on the results that generated Fig. 3(a), posted below for your convenience, starting with $n$ as small as 30, we observe a speedup ratio of 1,000, which increases to 1,000,000 by $n=58$. Although we were unable to run MHS for $n$ greater than 60, we can extrapolate that for $n$ as low as 70, the speedup factor would reach at least 100,000,000.

Worst-case complexity

We discuss the reason behind this speed up to some extent in lines 162-173 and Remark 3 (lines 244-248). Specifically, the method of Akbari et al., 2022 has a two-step procedure:

1. Discover a new (minimal) hedge.
2. Solve a weighted minimum hitting set problem (WMHS) on the already discovered hedges.
3. Repeat steps 1 and 2 until the solution to the WMHS instance results in identification.

We present an example in Figure 2(c), where the number of minimal hedges is exponential in $n$. Since the WMHS problem itself is NP-hard, their approach requires running an exponential number of instances of an NP-hard problem. In comparison, our method reduces the MCID problem to a single instance of WPMAX-SAT, which has a worst-case time complexity of one WMHS problem, rather than exponentially many of them. This is why we can solve the same problem several orders of magnitude faster than the method of Akbari et al., 2022.

It is noteworthy that the size of an instance of the WMHS problem they solve (i.e., the number of sets to hit) can be exponential in $n$, whereas the size of the WPMAX-SAT problem we solve (i.e. the number of variables and clauses) remains polynomial in $n$. In summary, we solve one instead of exponentially many instances of an NP-hard problem, and our problem has a significantly smaller size.

We acknowledge this point isn’t clearly conveyed and will clarify it with a more detailed discussion.

Quadratic complexity for multi-district

We make this claim in Remark 3 of the paper. Specifically, the quadratic complexity of our method in terms of the number of districts arises from the fact that the number of variables and clauses in our SAT construction for a multi-district set $S$ with $r$ districts scales as $r^2$. The formal justification for this claim lies in Theorem 2, where we prove that MCID is equivalent to a SAT formulation with size quadratic in $r$, the number of districts.

Regarding the time complexity of the approach by Akbari et al., 2022, this is due to their method requiring the enumeration of all possible partitions of the districts, the count of which (the so-called Bell number) grows super-exponentially with the number of districts. They solve an instance of single-district MCID problem for each of these possible partitions. We mentioned this in line 171.

We recognize that this point may not be clearly communicated in the current manuscript, and as it is a significant contribution of our paper, we will revise the paper to ensure this aspect is highlighted more effectively.

Unformalized justification and fast claim

The justification for our claims is present in the paper, and we want to clarify that our response is based on information already included in the manuscript (as referenced in our responses to the formal result regarding quadratic worst-case time complexity in terms of the number of districts, discussion around how we achieve a significant speedup compared to Akbari et al., 2022, and comparison of the worst-case complexities of our method and Akbari et al., 2022). However, we acknowledge that this information may be too dispersed to effectively convey the strength of our approach. To address this, we will consolidate these justifications into a dedicated section in the revised manuscript, where we will clearly detail our contributions and demonstrate why our approach outperforms the method of Akbari et al., 2022, both theoretically and in practice.

We sincerely appreciate your thorough review of our paper and your engagement with us during the discussion period. Please let us know if you have any more questions or concerns.

Please find our modified example (regarding W5) below.

Consider a patient taking three types of medications: one for lowering blood pressure (antihypertensives), another for controlling diabetes (anti-diabetics), and a third for managing kidney function (renal function modulators). These medications interact in various ways to manage heart health. For example, antihypertensives directly lower blood pressure, which is closely linked to cardiovascular health. Anti-diabetics help reduce cardiovascular risk by controlling blood sugar levels. Renal function modulators can influence both blood pressure and kidney health. Lifestyle factors and other health conditions, such as metabolic syndrome, can affect how these medications work together. For instance, a healthy diet and regular exercise can enhance the effectiveness of these treatments. To understand the combined effect of these medications on heart disease risk, we could conduct a proxy experiment by adjusting the anti-diabetics, as this is often easier and safer to modify compared to the others. This approach allows us to infer how these medications collectively impact heart health.

We appreciate the reviewer’s comments and feedback. We respond to your individual comments below.

Weaknesses:

W1:

Based on our extensive simulations given in Section 5 and Appendix A, the WPMAX-SAT reformulation, when paired with a high-performance MAX-SAT solver like RC2, consistently outperforms other approaches in terms of speed and effectiveness. The ILP reformulation, on the other hand, provides a more straightforward and interpretable way for incorporating extra constraints, say domain expert knowledge. We have included a paragraph in Section 6 emphasizing the advantages of using each reformulation.

W2:

Thank you for pointing this out. Indeed, the time complexity of Algorithm 1 can be analyzed in a rather straightforward way. The short answer is that the worst-case complexity of the algorithm is cubic in the number of variables. In particular, the two bottle-necks are (i) the initial pre-processing of lines 2-3, which can take up to $n$ rounds of d-separation tests (each of which can be carried out using a depth-first search), and (ii) the minimum-cut instance solved at line 9, which is carried out using a min cut - max flow algorithm such as Edmonds-Karps or linear programming, for which the worst-case complexities are known; e.g., push-relabel algorithms or MKM take time at most $O(|V|^2\sqrt{|E|})$ or $O(|V|^3)$ in the worst case. We will include the rigorous analysis in the final version.

As a side note, we would like to emphasize that our Algorithm 1 serves the main purpose of solving the minimum cost generalized adjustment set, but it also can be utilized as a very perofrmant heuristic for MCID, as seen in Section 5.

W3:

We have provided a more detailed explanation in the text, given below:

We need to ensure that for each district $S_\ell$, there exists at least one intervention set $\mathcal{I_k} \in \boldsymbol{\mathcal{I}}$ such that by intervening on $\mathcal{I_k}$, $S_\ell$, becomes identifiable. However, as we do not require that all intervention sets hit the hedges formed for $S_\ell$, we introduce the boolean variable $z_{k,\ell}$, which indicates whether $I_k$ intersects (hits) the hedges formed for $S_\ell$, and we add the clause $(z_{1,\ell}\lor\cdots\lor z_{r,\ell})$ to the SAT expression to ensure at least one $z_{k,\ell}$ is $1$. Then, if $z_{k,\ell} = 1$, the solution of the $k^\text{th}$ SAT expression must hit the hedges of $S_\ell$, whereas if $𝑧_{k,\ell} = 0$, there is no such obligation. As such, the $\neg z_{k,\ell}$ term ensures that if there is no need for $\mathcal{I_k}$ to hit the hedges of $S_\ell$ (meaning that another intervention set is already hitting them), we impose no constraints on the $k$-th copy. Note that when $z_{k,\ell}=0$, or equivalently, $\neg z_{k,\ell}=1$, the $k$-th copy is already satisfied, imposing no unnecessary constraints. Note that without $𝑧_{k,\ell}$, every copy would be forced to give a solution that hits $S_\ell$, which would be undesirable.

W4:

Thank you for pointing this out. We have conducted new simulations on real-world networks, which we present and discuss in the general rebuttal.

W5:

Thank you for your valuable feedback. In response, we are revising parts of the introduction to make the concept of the MCID problem more accessible. Following your advice, we have modified the example (see the comment below) to be less technical and more straightforward.

Limitations:

L1:

In the revised version, we are providing more detail on the baseline algorithms that we compared our methods with. Below are the relevant modified paragraphs from the main text:

The baseline algorithm with which we compare our exact algorithms is Algorithm 2 of Akbari et al., 2022, referred to as Minimal Hedge Solver (MHS). MHS runs as follows. It maintains a growing list of discovered hedges, and at each iteration, solves a minimum hitting set problem for this list of hedges. If the solution to this minimum hitting set problem is sufficient to make the query identifiable, it terminates. Otherwise, it discovers a new hedge and grows the list of its discovered hedges. As there can be exponentially many minimal hedges, as shown in Fig. 2(c), the runtime of their algorithm is doubly exponential, which is corroborated by the poor performance in our simulations.

We compare our heuristic algorithm, Algorithm 1, with the two best heuristics of Akbari et al., $H_1$ and $H_2$. Both algorithms solve a weighted minimum cut problem to return a set of interventions. $H_1$ performs a minimum cut between $S$ and the parents of $S$ over the bidirected edges, while $H_2$ performs a minimum cut between $S$ and the bidirected neighbors of $S$ over the directed edges.

As for the datasets used, we explained them in lines 337-341 for the exact algorithms, and lines 356-359 for the heuristic algorithms. However, we have added more detail, as included below:

For all simulations, we used the NetworkX library in Python to generate Erdos-Renyi (ER) graphs. ER graphs were generated by creating an upper triangular $n \times n$ adjacency matrix, where $n$ is the number of vertices. Then, we permuted the rows and columns of the adjacency matrix to ensure that node indices are randomized.

To ensure reproducibility, we used a fixed random seed for graph generation. The code as well as detailed instructions, including the specific seed values and the script for graph generation, are provided in the supplementary materials.

L2:

Thank you for the feedback. We will add a detailed and intuitive explanation of the WPMAX-SAT problem, starting from the SAT problem and building up to the weighted partial MAX-SAT problem. Additionally, we will include the encoding of the depth-first traversal of a directed graph as a SAT problem. This example, being similar in spirit to our approach, is easier to follow and understand, and will help readers grasp the underlying intuition behind our reformulation more effectively.

We thank the reviewer for reading and responding to our rebuttal. We address your remaining concerns below.

Regarding limited evaluation regime

To the best of our knowledge, no publicly available dataset includes both costs and ADMGs suitable for our setup. If the reviewer is aware of such a dataset, we would greatly appreciate the suggestion.

That being said, we want to emphasize that the absence of such a dataset should not diminish the validity of our claims or the value of our contribution. First, we have proven theoretically that our approach operates quadratically in the number of districts of $S$, a significant improvement over the exponential complexity of the previous method (Remark 3). This theoretical advantage holds regardless of the specific dataset used.

Second, our extensive simulations, detailed in Section 5 and Appendix A, involve testing over 1,000,000 graphs, covering all combinations of directed and bidirected sparsity and density, and demonstrate that our SAT reformulation outperforms the previous approach by factors ranging from 1,000 to 100,000,000 in speed. This significant speed advantage makes it highly unlikely that our approach would perform worse than the previous method in any practical scenario. Additionally, our new rebuttal simulations, which evaluated our approach on DAGs from 17 distinct real-world applications, demonstrate the same performance superiority. It is important to note that although the costs are synthetically generated, our experiments in Appendix A.4 confirm that varying costs does not impact the relative performance of our method compared to the previous approach. Therefore, our rebuttal simulations provide a reliable indication of how our approach would perform on real-world problems with non-synthetic costs.

Regarding general examples

We address the problem of determining optimal proxy experiments for causal effect identification, a key issue in many decision-making contexts where direct policy implementation (i.e., intervention) is costly, risky, or time-consuming. Here are two real-world examples.

Proxy interventions for evaluating diesel vehicle bans in environmental policy​

Consider in environmental policy, where a city is considering a ban on diesel vehicles to reduce air pollution. Instead of implementing the ban outright, the city might first introduce low-emission zones or offer incentives for electric vehicle purchases in certain areas. These low-emission zones can be viewed as proxy experiments (interventions), and they allow the city to estimate the policy's effectiveness before committing to the full-scale ban [1,2].

Proxy experiments for evaluating nationwide sugary drink tax policies

Consider a scenario where a government is considering a nationwide tax on sugary drinks to reduce obesity rates. Directly implementing the tax across the country could be costly and politically challenging. Instead, the government might conduct proxy experiments by imposing the tax in selected regions or by encouraging voluntary reduction in sugary drink consumption through public campaigns in others. These proxy experiments can help estimate the potential impact of a nationwide policy without the need for immediate, large-scale implementation [3,4].

Regarding comment on rebuttal policy

We appreciate your diligence in ensuring that the rebuttal process is followed correctly. However, we believe there might be a misunderstanding. After reviewing both the guidelines on the NeurIPS website and the emails sent by program chairs regarding the rebuttal/discussion period, we found no policy that prohibits authors from adding an official comment before the reviewer’s reply.

Please let us know if there are any remaining questions. In light of this response and our rebuttal, which addressed all of your other comments and questions, we kindly ask that you reconsider your score.

References

[1]: Dey, S., Caulfield, B., & Ghosh, B. (2018). Potential health and economic benefits of banning diesel traffic in Dublin, Ireland. Journal of Transport & Health.

[2]: Pérez-Martínez, P., Andrade, M., & Miranda, R. (2017). Heavy truck restrictions and air quality implications in São Paulo, Brazil. Journal of environmental management, 202 Pt 1, 55-68.

[3]: Redondo, M., Hernández-Aguado, I., & Lumbreras, B. (2018). The impact of the tax on sweetened beverages: a systematic review. The American journal of clinical nutrition, 108 3, 548-563.

[4]: Álvarez-Sánchez, C., Contento, I., Jiménez-Aguilar, A., Koch, P., Gray, H., Guerra, L., Rivera-Dommarco, J., Uribe-Carvajal, R., & Shamah-Levy, T. (2018). Does the Mexican sugar-sweetened beverage tax have a signaling effect? ENSANUT 2016. PLoS ONE, 13.

We thank the reviewer for their comments and positive assessment. Taking your comments into account, we have rewritten and restructured the relevant sections of the paper to improve the presentation and clarity. We respond to your comments and questions below.

Weaknesses:

W1:

We acknowledge the need for improvements in how the content is conveyed. We are refining our manuscript to enhance its readability based on the feedback we received. We are undertaking another round of revision and restructuring to enhance the clarity and organization.

W2:

Please see our answer to L1.

W3:

Thank you for noticing this and bringing it to our attention. Due to space limitations, we chose to present only the two most noteworthy and practical reformulations, namely WPMAX-SAT and ILP, in the main paper. We have revised the introduction to clarify that we present and focus on these two reformulations in the main text, while the other reformulations are provided in Appendix D.

Questions:

Q1:

Costs are assigned to interventions on variables (i.e., conducting experiments). We consider heterogeneous costs, as certain experiments can be more costly to run than others. 'Cost' in this context can be in terms of:

• Financial Costs: For example, in the healthcare system, different interventions can have varying financial implications. Upgrading medical equipment might be relatively inexpensive compared to implementing a comprehensive telemedicine service or enhancing emergency response systems.
• Time Resources: Time is another critical aspect of cost. For instance, upgrading medical equipment in already existing hospitals may require significantly less time than building a new hospital from scratch.
• Other Resources: This includes human resources and other logistical considerations. For example, implementing a new healthcare protocol might require extensive training for staff, which can vary in cost depending on the complexity and scope of the training required.

Additionally, some experiments are not possible to perform as they might be unethical or have not yet recieved approval from authorities, and for these experiments, we model the cost as infinite. For example, in medical research, conducting certain experiments might require exposing patients to possibly harmful or unapproved treatments or withholding treatments currently percieved as effective, which is ethically unacceptable.

We have included these concrete examples in the revised paper to help readers better understand the practical implications of costs.

Q2:

Thank you for pointing this out. We have adapted the notation in the introduction to be more consistent with the rest of the paper.

Q3:

Thank you for thoroughly going over our examples! In Fig. 2(d), notice that $\\{S_1\\}$ and $\\{S_2\\}$ are the two unique districts of $S=\\{S_1,S_2\\}$. As they are both singletons, we use $\\{S_1\\}$ and $S_1$, and $\\{S_2\\}$ and $S_2$ interchangeably for the sake of conciseness. Note that after intervening on a variable, in the resulting graph, all the incoming edges to that variable disappear, i.e., the intervened variable has no parents.

Focusing first on $S_1$, we observe that after intervening on $S_2$, the resulting graph contains no hedges for $S_1$ by Definition 2. This is because the only sets $W \supsetneq \\{S_1\\}$ that are districts (i.e., connected via bidirected edges) and contain $S_1$ are $W= \\{S_1, X_2\\}$, $W= \\{S_1, X_4\\}$, or $W = \\{S_1, X_2, X_4\\}$, and neither of these sets satisfy condition (ii), namely that all $w \in W$ are ancestors of $S_1$ in $\mathcal{G}[W]$. Looking now at $S_2$, the only ancestor of $S_2$ is $X_3$, and following an intervention on $X_3$, it is not in the same district with $S_2$. Therefore, by Definition 2, there are no hedges remaining for $S_2$.

We have added these explanations for both figures 2(b) and 2(d) in the revised version.

Q4:

You are right that there is a discrepancy between Example 1 and what we had written between lines 152 and 155. We have fixed the example to be consistent with what is stated in lines 152-155.

Q5:

We agree with your suggestion that focusing on one reformulation would streamline the presentation, which is why we concentrated on the WPMAX-SAT and ILP formulations. These two formulations are very similar, making it sensible to present both. To clarify this better, we have added an explanation in the main text on why we chose to focus on these reformulations:

Based on our extensive simulations provided in Section 5 and Appendix A, the WPMAX-SAT reformulation, when paired with a high-performance MAX-SAT solver like RC2, consistently outperforms other approaches in terms of speed and effectiveness. Similarly, the ILP formulation aligns very closely with the structure of the WPMAX-SAT approach, thus justifying our focus on these two formulations.

Q6:

The sentence should read "... a specific class of causal effects in which the effect..." We apologize for the oversight.

Limitations:

L1:

We have added a paragraph addressing the limitations in the main text. We provide the paragraph below:

The main limitation of our reformulation is that it still involves solving an NP-hard problem, which inherently has a worst-case exponential complexity. However, it should be noted that the MCID problem itself is an NP-hard problem, meaning any reformulation will inevitably have an exponential worst-case complexity. Despite this, our WPMAX-SAT reformulation offers significant advantages over the initial formulation by expressing the problem as a single instance of a WPMAX-SAT problem. This approach allows for the use of well-studied and high-performance solvers, as demonstrated in our simulations. Moreover, our reformulation benefits from a quadratic complexity in the number of districts of $S$, compared to the exponential complexity of the initial formulation by Akbari et al., 2022.

We thank the reviewer for the review and positive comments. We respond to your question below.

Questions:

Q1:

Could the authors provide more clues about the reason that the SAT-based method performs better than the existing method?

Response:

At a high level, the previously existing method requires multiple calls to a subroutine solving an instance of the minimum hitting set problem, which is NP-hard. The number of calls to this subroutine can be exponential in the worst case, leading to solving exponentially many instances of a problem where each instance may require exponential time to solve. In contrast, our reformulation necessitates only a single call to a MAX-SAT solver. Additionally, the complexity of the previous methods grows exponentially with the number of districts of $S$, while the complexity of our method remains quadratic. This is due to the fact that the previous methods require enumerating all possible partitionings of the set of variables, whereas our SAT formulation avoids this unncessary enumeration by directly encoding the constraints into a single optimization problem, significantly reducing the computational burden.