Faster Exponential Algorithms for Cut Problems via Geometric Data Structures

In this paper, we mainly consider cut problems in graphs, with certain natural restrictions on how vertices may interact with the cut. We focus on decision problems (whether a cut of the required form exists); in all cases, an actual cut can be constructed with minimal overhead.

Our first problem is $d$-Cut: given an undirected graph $G=(V,E)$ and an integer $d$, find a bipartition $V=V_L\cup V_R$, where $V_L,V_R$ are nonempty disjoint sets, so that each vertex $v\in V$ has at most $d$ neighbors on the other side of the partition. Precisely, denoting by $N(v)$ the (open) set of neighbors of $v$, we require $|N(v)\cap V_R|\le d$ for all $v\in V_L$ and $|N(v)\cap V_L|\le d$ for all $v\in V_R$. The value $d$ is arbitrary, in particular, it may depend on $n$.

The problem can be seen as a natural min-max variant of the famous Min Cut problem. While Min Cut is polynomial time solvable, $d$-Cut is NP-hard, even for $d=1$ [9].

The $d$-Cut problem was studied by Gomes and Sau [12] as a natural generalization of the well-known Matching Cut problem (the case $d=1$). Graphs admitting a matching cut are known as decomposable and have been extensively studied, e.g., see Graham [17], Chvátal [9], and Bonsma [5]. For Matching Cut, Komusiewicz, Kratsch, and Le [20] give an $O({1.3071}^n)$ time algorithm, using a reduction to CNF SAT. For the general $d$-Cut problem, Gomes and Sau obtain a runtime of the form $O(c_d^n)$ where $c_d$ grows at least as ${(2^d-1)}^{\frac{1}{d}}$. As such, the base is smaller than $2$ for fixed $d$, but cannot, in general, be bounded away from $2$; the existence of an algorithm with runtime $O({(2-\epsilon )}^n)$ for $\epsilon >0$ was left open by Gomes and Sau. In fact, the SAT-based algorithm of Komusiewicz also applies to $d$-Cut, resulting in a polynomial number of $(d+2)$-CNF SAT instances with $n$ variables. Under the SETH conjecture [19], the running time of this approach also cannot be bounded as $O({(2-\epsilon )}^n)$.

We note that the related Max Cut problem can be solved in time $O({1.73}^n)$ by reduction to fast matrix multiplication [33], this technique however, seems not to extend to $d$-Cut.

A second general cut problem we consider is $(\mathrm{\alpha },\mathrm{\beta })$-Domination. Here, we seek a bipartition $V=V_L\cup V_R$, where $|N(v)\cap V_L|\in \mathrm{\alpha }$ for all $v\in V_L$ and $|N(v)\cap V_L|\in \mathrm{\beta }$ for all $v\in V_R$. Note that $\mathrm{\alpha }$ and $\mathrm{\beta }$ are subsets of the set $\{0,1,\mathrm{\dots },n\}$.

This formulation, introduced by Telle [31], generalizes many natural structures and problems in graphs, such as Independent Set, Dominating Set, Induced Matching, etc., by setting $\mathrm{\alpha }$ and $\mathrm{\beta }$ to particular values (we refer to [31, 14] for a list of special cases). While the fully general case seems hopeless, it is perhaps most natural to require $\mathrm{\alpha }$ and $\mathrm{\beta }$ to be intervals, i.e., of the form $\mathrm{\alpha }=[{\mathrm{\alpha }}^{\prime },{\mathrm{\alpha }}^{\prime \prime }],\mathrm{\beta }=[{\mathrm{\beta }}^{\prime },{\mathrm{\beta }}^{\prime \prime }]$. This already captures most, if not all of the interesting special cases. Notice, however, that the problem does not strictly generalize $d$-Cut; while setting $\mathrm{\beta }=[0,d]$ enforces the degree constraint on $V_R$, the admissible degrees for vertices in $V_L$ depend on their original degrees in $G$.

The problem was studied from the point of view of exponential algorithmics by Fomin, Golovach, Kratochvíl, Kratsch, and Liedloff [14]. They obtain algorithms with runtime $c^n$ for in the special case $|\mathrm{\alpha }|=|\mathrm{\beta }|=1$, as well as in some cases where $\mathrm{\alpha }$ and $\mathrm{\beta }$ are not necessarily intervals, e.g., when $|\mathrm{\alpha }|+|\mathrm{\beta }|=3$ or when $\mathrm{\alpha }$ and $\mathrm{\beta }$ are generated by arithmetic sequences; these latter cases fall outside of our definition. The same authors, in a different paper [15] also consider other special cases. These require some combination of $\alpha$ and $\beta$ being disjoint, finite, or successor-free (i.e., not containing consecutive integers). As such, the conditions are not comparable with our requirement for $\alpha$ and $\mathrm{\beta }$ to be intervals; in our case, $\mathrm{\alpha }$ and $\mathrm{\beta }$ may overlap arbitrarily, may be infinite, but cannot have gaps.

The third problem we consider is Internal Partition. Here, we seek a bipartition $V=V_L\cup V_R$, where $V_L$ and $V_R$ are nonempty and every vertex has at least half of its neighbors on its own side of the partition. Formally, for all $v\in V_L$ we have $|N(v)\cap V_L|\ge |N(v)\cap V_R|$, and for all $v\in V_R$ we have $|N(v)\cap V_L|\le |N(v)\cap V_R|$.

Such a partition, called an internal partition, arises in many settings (in the literature the terms friendly-, cohesive-, or satisfactory- partition are also used). Determining whether a graph admits an internal partition is NP-hard [3]; this is in contrast to external partitions (where every vertex has at least half of its neighbors on the other side), which always exist. Research has mostly focused on conditions that guarantee the existence of an internal partition, e.g., see Thomassen [32], Stiebitz [29], and the survey of Bazgan, Tuza, and Vanderpooten [3]. A long-standing conjecture is that every sufficiently large $r$-regular graph has an internal partition; e.g., see Ban and Linial [2] and Linial and Louis [22] for recent partial results. We are not aware of algorithms with runtime of the form $O({(2-\epsilon )}^n)$ for deciding the existence of an internal partition.

All three problems can trivially be solved in time $2^n\cdot n^{O(1)}$. Our main result improves this for all three problems.

While we state our results for the decision problems (does a bipartition with the given property exist?), we can also easily extend them to the optimization versions of the problems (maximize or minimize the left side $|V_L|$ of the cut while satisfying the constraint), and to the counting versions (count the number of cuts with the given property). The optimization view is most natural for $(\mathrm{\alpha },\mathrm{\beta })$-Domination, where special cases include the task of finding e.g., a maximum independent set, a minimum dominating set, etc. (of course, for some of the well-known special cases faster algorithms already exist).

Additional constraints on the cuts (e.g., requiring $V_L$ to be of a certain size, say $|V_L|=n/2$), or making the edges directed (and extending the conditions accordingly to in- or out-neighborhoods) can easily be accommodated, as will be clear later.

Our algorithms also extend naturally to more fine-grained, vertex-specific conditions. For $d$-Cut, this could mean setting an upper bound $d_v$ for each vertex $v$ on the number of neighbors across the cut, and possibly, a vertex-specific lower bound on the same quantity. For $(\mathrm{\alpha },\mathrm{\beta })$-Domination, we could set specific intervals $[{\mathrm{\alpha }}_v,{\mathrm{\beta }}_v]$ for each vertex $v$; these may even depend on the degree of $v$ in the input, or on other properties of the graph.

In spite of the unwieldy bound on the running time, our approach is conceptually exceedingly simple, and all three problems are tackled in essentially the same way.

Our starting point is the split and list technique originally used by Horowitz and Sahni [18] for Subset Sum: Given a set $X=\{x_1,\mathrm{\dots },x_n\}$, find a subset of $X$ whose elements add up to a given value $t$.

The technique works by splitting $X$ into $X_A=\{x_1,\mathrm{\dots },x_{\lfloor n/2\rfloor }\}$ and $X_B=X\setminus X_A$. Then, the sets ${𝒮}_A$, resp., ${𝒮}_B$ of the possible sums given by subsets of $X_A$, resp., $X_B$ are computed. The problem now amounts to searching, for all $x\in {𝒮}_A$, for a matching pair $t-x\in {𝒮}_B$. This can be solved in time $O(n)$ by binary search if ${𝒮}_B$ is sorted, which can be achieved by an $O(n{2}^{n/2})$ time preprocessing. An overall runtime of $O(n{2}^{n/2})$ results.

We can view the sorting/searching part of the algorithm as storing ${𝒮}_B$ in an efficient comparison-based dictionary (say, a balanced binary search tree). Our extension of the technique amounts to replacing this dictionary with a more sophisticated multidimensional search structure.

In particular, we use the orthogonal range search data structure of Chan [7]. Such a data structure stores a set of $N$ vectors from ${ℝ}^d$. A dominance range query $q\in {ℝ}^d$ returns the number (or the list) of vectors stored that are upper bounded by $q$ on every coordinate. Precisely, a stored vector $y=(y_1,\mathrm{\dots },y_d)$ is reported for query vector $q=(q_1,\mathrm{\dots },q_d)$ if $y_i\le q_i$ for all $i\in \{1,\mathrm{\dots },d\}$.

In most applications of range searching, the dimension $d$ is assumed constant, however, Chan’s data structure allows for $d$ that is polylogarithmic in $N$. As we only need $d\in O(\log N)$, we state the result in this form. Note that dominance range queries can be reduced to orthogonal range queries, where each query is specified by an axis-parallel hypercube (box), and vice versa (by doubling the number of dimensions). In our application, we always formulate our queries as dominance range queries.

A small remark on the computational model is in order. While the data structure is defined for vectors in ${ℝ}^d$, assuming a real RAM with constant time operations, in our application all vector coordinates are integers in $\{-2n,\mathrm{\dots },2n\}$, our results thus hold in more realistic models such as the word RAM, or even if we account for the number of bit-operations.

The result we rely on takes the following form.

We use this geometric data structure to solve the mentioned graph cut problems similarly to the split and list technique sketched above. We split the set of vertices in two equal parts, and form all possible bipartitions of both parts. Combining two such bipartitions into one requires checking whether they are “compatible”, i.e., whether their union satisfies the degree constraints. This can, in all three cases, be verified with dominance range queries on appropriately preprocessed degree vectors. We precisely state and prove our results in Section 2.

In Section 3 we derive an exact constant ${\epsilon }_c$ for Lemma 2 in our setting; this is not easy to read off directly from previous work, as results are stated in asymptotic notation, e.g., ${\epsilon }_c\in 1/O(\log c)$ where $c$ is allowed to be (slightly) superconstant. In our application, as we will show, $c=16$ and ${\epsilon }_c\ge 3\cdot {10}^{-6}$ are feasible, which for $N=2^{n/2}$ yield the stated runtime.

Chan [7] gives several different implementations that result in a bound of the form given in Lemma 2. We work out the constant in the exponent for the variant that appears the simplest [7, § 2.1]. It is a randomized, “purely combinatorial” implementation, i.e., not using fast matrix multiplication or other algebraic tools. The data structure allows for an online sequence of queries. As in our setting the queries are offline (i.e., known upfront), we could use one of the more efficient offline, as well as deterministic versions from [7], to obtain a similar, possibly better constant; we refrain from this to keep the presentation simple.

While the use of a geometric data structure may seem surprising in a graph theoretic context (its implementation involves an intricate lopsided recursion reminiscent of k-d-trees), Chan’s technique did have previous graph-applications, although mostly in the polynomial-time regime, e.g., for the all pairs shortest paths problem [7]. For a different flavor of applying orthogonal range searching (in constant dimensions) to graph algorithms, see [6].

After presenting our results (Section 2) and deriving a precise constant bound for the base of the running time (Section 3), in Section 4 we give some final thoughts.