A widespread belief about county splits in political districting plans is wrong

Consider the task of dividing a state into k contiguous political districts whose populations must not differ by more than one person, following current practice for congressional districting in the USA. A widely held belief among districting experts is that this task requires at least k-1 county splits. This statement has appeared in expert testimony, … Read more

Political districting to optimize the Polsby-Popper compactness score

\(\)In the academic literature and in expert testimony, the Polsby-Popper score is the most popular way to measure the compactness of a political district. Given a district with area \(A\) and perimeter \(P\), its Polsby-Popper score is given by \( (4 \pi A)/P^2\). This score takes values between zero and one, with circular districts achieving … Read more

Political districting to minimize county splits

When partitioning a state into political districts, a common criterion is that political subdivisions like counties should not be split across multiple districts. This criterion is encoded into most state constitutions and is sometimes enforced quite strictly by the courts. However, map drawers, courts, and the public typically do not know what amount of splitting … Read more

Linear-size formulations for connected planar graph partitioning and political districting

Motivated by applications in political districting, we consider the task of partitioning the n vertices of a planar graph into k connected components. We propose an extended formulation that has two desirable properties: (i) it uses just O(n) variables, constraints, and nonzeros, and (ii) it is perfect. To explore its ability to solve real-world problems, … Read more

On fault-tolerant low-diameter clusters in graphs

Cliques and their generalizations are frequently used to model “tightly knit” clusters in graphs and identifying such clusters is a popular technique used in graph-based data mining. One such model is the $s$-club, which is a vertex subset that induces a subgraph of diameter at most $s$. This model has found use in a variety … Read more

Political districting to minimize cut edges

When constructing political districting plans, prominent criteria include population balance, contiguity, and compactness. The compactness of a districting plan, which is often judged by the “eyeball test,” has been quantified in many ways, e.g., Length-Width, Polsby-Popper, and Moment-of-Inertia. This paper considers the number of cut edges, which has recently gained traction in the redistricting literature … Read more

Worst-case analysis of clique MIPs

The usual integer programming formulation for the maximum clique problem has several undesirable properties, including a weak LP relaxation, a quadratic number of constraints and nonzeros when applied to sparse graphs, and poor guarantees on the number of branch-and-bound nodes needed to solve it. With this as motivation, we propose new mixed integer programs (MIPs) … Read more

Solving the distance-based critical node problem

In critical node problems, the task is identify a small subset of so-called critical nodes whose deletion maximally degrades a network’s “connectivity” (however that is measured). Problems of this type have been widely studied, e.g., for limiting the spread of infectious diseases. However, existing approaches for solving them have typically been limited to networks having … Read more

Continuous Cubic Formulations for Cluster Detection Problems in Networks

The celebrated Motzkin-Straus formulation for the maximum clique problem provides a nontrivial characterization of the clique number of a graph in terms of the maximum value of a nonconvex quadratic function over a standard simplex. It was originally developed as a way of proving Tur\'{a}n’s theorem in graph theory, but was later used to develop … Read more