1 Introduction↩︎

Graph partitioning problems are a fundamental class of optimization problems. A classic example is the problem ( for short), which asks for a partition of the nodes of a graph into up to \(k\) subsets, maximizing the sum of weights of edges whose endpoints lie in different sets. An example is illustrated in Figure 1. The problem is \(\mathcal{N}\mathcal{P}\)-hard, which can be shown with a reduction from the related \(k\)-Colouring problem, one of Karp’s 21 \(\mathcal{N}\mathcal{P}\)-complete problems [1].

Research into has been motivated by its various applications, e.g., in computing relaxations of frequency assignment problems [2], chip load balancing [3], [4], and image reconstruction [5]. Special attention has been placed on the case \(k = 2\), called Maximum Cut (MaxCut for short). Recent research has shown that preprocessing can significantly reduce the size of real world instances for MaxCut by locating substructures for which the behaviour of the optimum solution can be determined ahead of time [6]–[9]. This preprocessing enables exact solvers to tackle significantly larger instances, sometimes even solving instances to optimality purely during preprocessing. The only published work on preprocessing for that we know of is [10]. However, in their computational experiments their technique only had an effect for \(k = 2\). The success of preprocessing for MaxCut suggests that could still benefit from sophisticated preprocessing.

Our Contribution↩︎

We extensively study optimality-preserving preprocessing techniques for the problem. In detail:

• We introduce structured cut sets, a new data separation rule particularly effective for \(k\ge 3\). The rule relies on novel criteria under which the problem reduces to independently solving the connected components obtained by deleting a cut set.

• Moreover, we generalize several of the MaxCut preprocessing rules from [6]–[9].

• In order to prove that preprocessing rules for are optimality-preserving, we introduce a new proof framework based on the addition of weighted graphs.

• We propose a preprocessing algorithm based on our theoretical findings, equipped with a framework for reconstructing optimal solutions.

• Our computational study shows that instances preprocessed by our algorithm are typically significantly smaller. When integrated into an exact solver, our preprocessing algorithm leads to substantial speed-ups and more instances solved to optimality.²

2 Preliminaries↩︎

We consider weighted, undirected graphs \(G = (V, E, w)\) with a set of vertices \(V, |V| = n\), edges \(E \subseteq \binom{V}{2}, |E| = m\) and weights \(w: E \rightarrow \mathbb{R}\). We denote by \(\delta_G(v), N_G(v)\) and \(d_G(v)\) the incident edges, neighbourhood and degree of \(v \in V\) in \(G\), by \(w(S) = \sum_{e \in S} w(e)\) the weight of a set \(S \subseteq E\) of edges and by \(\delta_G(S) = \left\{\left\{s, t\right\} \mid s \in S, t \not \in S\right\}, N_G(S) = \bigcup_{v \in S} N(v) \setminus S\) the cut set and neighbourhood of \(S \subseteq V\). If the graph is clear from context, we omit the subscript.

We denote by \(G[V'] = \left(V', \left\{e \in E \mid e \subseteq V'\right\}, w\right)\) the induced subgraph of a vertex set \(V' \subseteq V\) and by \(G[S] = \left(\bigcup_{e \in S} e, S, w\right)\) the induced subgraph of an edge set \(S \subseteq E\). For \(V' \subseteq V\) we denote by \(\partial_G(V') = \left\{v \in V' \mid \exists w \in V \setminus V': \left\{v, w\right\} \in E\right\}\) the boundary of \(V'\).

We refer to \(\left\{1,...,k\right\}\) as colours and to \(p(v)\) as the colour assigned to \(v\) by \(p\).

Partial permutations of partitions will play a major role later, as permuting the partition of a subset \(S \subseteq V\) of the nodes only changes how our \(k\)-cut behaves on \(\delta(S)\).

Now that we have formally defined partitions we can define \(k\)-cuts and the considered problem in this work:

Equivalent to is the Minimum \(k\)-Partition problem, in which we minimize the weight of edges for which both endpoints have the same colour.

2.1 Related Work↩︎

As previously mentioned, on general graphs is \(\mathcal{N}\mathcal{P}\)-hard. Even though can likely not be solved in polynomial time, various approaches that can solve real world instances to optimality in reasonable time have been proposed over the years. These are usually based on ILP formalisms [11], [12]. Different techniques to solve the ILP models have been proposed. The orbital fixing algorithm by Kaibel et. al [13] efficiently prunes symmetries in the assignment formulation. To obtain better dual bounds, both cutting planes [11], [14], and semidefinite relaxations [15]–[20] have been employed. For a recent study on exact solvers, we refer to Rodrigues de Sousa et. al [20].

Several different approaches for preprocessing MaxCut have been developed. Lange et al. [9] introduced criteria that show that certain edges with high weight are cut and certain edges with high negative weight are not cut in an optimum solution. They exploited this knowledge to then contract the endpoints. Rules that enable removing or simplifying substructures, such as unit weight cliques with a small boundary and induced \(3\)-paths, were developed by Ferizovic et al. [6]. Recently, Charfreitag et al. [8] developed a framework than enables exploiting \(2\) and \(3\) separators in preprocessing. To our knowledge the only theoretical work on preprocessing for is by Fakhimi et al. [10]. They introduce a folding techniques that allows contracting vertices under certain circumstances. However in their computational experiments their preprocessing only had an effect for \(k = 2\) and could not reduce any instance for \(k > 2\) beyond what trivial preprocessing could already accomplish.

3 Data Reduction for↩︎

Data reduction for MaxCut and is based on two central components: Data transformations and data separations:

Our definitions build on the notion of data transformations introduced in [8]. However, their definitions require that data transformations produce an offset \(\beta\) between the optimum objective values of \(G\) and \(G'\). We decided to instead require a reconstruction algorithm, as we want to obtain not just the optimum solution value, but also a corresponding \(k\)-partition. Still, all data transformations/separations discussed in this paper also yield a constant offset. This enables computing lower and upper bounds for the original instance from lower and upper bounds of the reduced instance. For an overview of the offsets see Appendix 8.1.

Since our goal is to compute optimum solutions for , all data separations and transformations we consider are optimality-preserving. To reduce the verbosity we will omit specifying that a data separation/reduction rule is optimality-preserving outside of theorems.

3.1 The Data Reduction Framework↩︎

Previous research on MaxCut preprocessing concerned itself with reducing the instances and obtaining the optimum solution value [6]–[9]. While the preprocessing rules discussed allow for reconstruction of an optimum solution for the original graph, the presented frameworks do not describe how to perform this reconstruction, nor is it clear how new preprocessing rules would be added to the reconstruction.

To this end, we introduce a new preprocessing framework that collects reconstruction algorithms during preprocessing. Our data reduction framework relies on repeatedly applying data transformation/separation rules until we can no longer reduce the graph. For reconstruction, we build a reconstruction rule tree: When applying a data reduction/separation rule to \(G'\), we add its reconstruction algorithm as a child to the reconstruction algorithm of the rule that created \(G'\). Once we cannot reduce anything any more, we solve the remaining graphs using some exact solver. We then apply the reconstruction rules in reverse DFS order, so whenever a reconstruction rule is called we have access to optimum solutions for all graphs that it depends on. A visualization of this can be seen in Figure 2.

3.2 Criteria for Preserving Optimality↩︎

As many of the following proofs will use similar techniques, we establish some notation and results that provide a general framework for our later proofs to use.

We note that if we consider graphs that can be transformed into each other only by adding/deleting weight \(0\) edges and degree \(0\) vertices, this notion of \(+\) forms a group. With this, we can now establish an optimality criterion via the addition of weighted graphs.

We note that in general the optimum solution \(p\) for \(G\) is not optimum for \(G_1\) or \(G_2\). However, given optimum solutions \(p', p''\) for \(G_1, G_2\) with \(p'^{\ifthenelse{\equal{}{}}{}{}}_{\ifthenelse{\equal{V_1 \cap V_2}{}}{}{|V_1 \cap V_2}} \cong p''^{\ifthenelse{\equal{}{}}{}{}}_{\ifthenelse{\equal{V_2 \cap V_2}{}}{}{|V_2 \cap V_2}}\) we can efficiently combine these into an optimum solution for \(G\):

4 Optimality-Preserving Data Reduction↩︎

In this section we extend several known data reduction rules from MaxCut to .

Before we get to the more advanced rules, we briefly discuss a simple rule: We can remove any vertex \(v \in V\) with \(d(v) < k\) and only positive weight incident edges. In the reconstruction we colour \(v\) with a colour not used in \(N(v)\), of which there must be at least one.

4.1 Cliques with a small Neighbourhood↩︎

Cliques are interesting in the context of -preprocessing. For a clique \(C\) with positive unit weight edges, any \(k\)-partition \(p\) with \(\forall i: \left\lceil \frac{|C|}{k}\right\rceil \geq |V_{p = i}| \geq \left\lfloor \frac{|C|}{k}\right\rfloor\) is an optimum solution. Let \(G = (V, E, w)\) be a graph that is the sum of a unit weight clique \(C = (V_C, E_C, w_C)\) and \(G' = (V', E', w')\). If the intersection \(V_C \cap V'\) is small enough, we can solve \(G'\) to optimality and then colour the remaining vertices in \(V_C\) such that our partition is also optimum for \(C\). This idea has been employed for MaxCut in [6] and was then generalised in [8]. Their results extend to very naturally.

The proof for is analogous to the proof for MaxCut in [8]. While finding maximal cliques in general is difficult, cliques with a small neighbourhood can be located efficiently as noted in [6].

4.2 Triconnected Components and 2-Vertex-Separators↩︎

MaxCut can be solved efficiently on graphs with no \(K_{3, 3}\)-minor by exploiting \(2\)-vertex-separators, that is sets of two vertices such that their removal disconnects the graph [21]. These ideas were adapted for MaxCut preprocessing in [8]. They generalise to :

To efficiently identify 2-vertex separators suitable for this reduction, we make use of the decomposition of G into its triconnected components [22], and then attempt to remove the leaves in the resulting tree structure as suggested in [8]. While [8] removed such components only if they contained \(\leq 21\) vertices, we noticed that branch-and-bound could frequently find the optimum solution for larger graphs as well. Due to this we instead opted to run an exact solver with a time limit of \(1\) second. [8] employed similar techniques with \(3\)-vertex-separators. A brief discussion why this is not possible for can be found in Appendix 9.2.

4.3 Negative Weight Dominating Edges↩︎

Another class of data reduction rules are dominating edges introduced by Lange et. al [9]. The key idea is that any edge that is not cut in an optimum solution can be safely contracted without affecting optimality.

Unfortunately, most other dominating edge rules in [7], [9] and [8] rely on specific properties of \(k = 2\). A weaker version of the triangle rule by [6] and a discussion why the other rules do not generalise can be found in Appendix 9.3.

5 Optimality-Preserving Data Separation↩︎

We now move on to data separations. For these, we describe conditions under which we can solve several subgraphs independent of each other, instead of solving the whole graph.

5.1 Separating (Bi)connected Components↩︎

Separating graphs into their (bi)connected components is a well known data separation technique [23] and a standard preprocessing step for MaxCut [7], [8]. We briefly motivate why separating (bi)connected components is optimality-preserving for . As different (bi)connected components \(C_1, C_2\) intersect in at most one vertex, optimum solutions \(p', p''\) of \(C_1, C_2\), respectively, have \(p'^{\ifthenelse{\equal{}{}}{}{}}_{\ifthenelse{\equal{C_1 \cap C_2}{}}{}{|C_1 \cap C_2}} \cong p''^{\ifthenelse{\equal{}{}}{}{}}_{\ifthenelse{\equal{C_1 \cap C_2}{}}{}{|C_1 \cap C_2}}\). Therefore \(p', p''\) can be combined into a \(k\)-partition \(p\) of \(V\) using Lemma 1. By Theorem 1 \(p\) is optimum for \(G\).

5.2 Structured Cut Sets↩︎

Here, we introduce a new separation rule called structured cut sets, which makes use of the combinatorial benefits of larger values of \(k\).

By definition, deleting the edges of a cut set \(C \subseteq E\) from \(G\) decomposes it into at least two disjoint components. In this section we assume w.l.o.g. that deleting the cut set splits \(G\) into exactly two connected components, \(G_1 = \left(V_1, E_1, w_1\right)\) and \(G_2 = \left(V_2, E_2, w_2\right)\). We also consider only cut sets in which all edges have positive edge weights (called positive cut sets). For a discussion why cut sets containing negative edges are disregarded, see Appendix 10.5. Given optimum solutions \(p', p''\) for \(G_1, G_2\), we combine them into a \(k\)-partition \(p\) of \(V\) with \(\forall v \in V_1: p(v) = p'(v)\) and \(\forall v \in V_2: p(v) = p''(v)\). We now want to permute the colours on \(V_2\) such that all edges in \(C\) are cut by \(p\). If this is possible, \(p\) is optimum for \(G\), as it is optimum for \(G_1, G_2\) and \(G[C]\) and \(G = G_1 + G_2 + G[C]\). See Figure 3 for an example.

We develop criteria to decide whether such a colour permutation exists, independent of the optimal solutions for \(G_1\) and \(G_2\). This allows us to solve \(G_1\) and \(G_2\) independently, as we can be certain that all edges in \(C\) can be cut. As our criteria work by showing that reconstruction is possible, we first introduce our reconstruction algorithm.

5.2.1 Reconstruction for Structured Cut Sets↩︎

In order to compute an optimum solution \(p\) of \(G\) from partitions \(p'\) and \(p''\) of \(G_1\) and \(G_2\), we introduce the notion of a complement that preserves the bipartition of a graph:

The central idea of our algorithm is to construct a colour relation graph \(G_{CR}\), which has \(2k\) vertices. We have one vertex for every colour \(i \in \left\{1,...,k\right\}\) and each side \(L, R\). Two vertices \((i, L), (j, R)\) are connected in \(G_{CR}\) iff an edge \(\{v, w\} \in C, v \in V_1, w \in V_2\) connects vertices with \(p(v) = i, p(w) = j\). An example can be seen in Figure 4. These edges in \(G_{CR}\) encode that we are not allowed to map \(j\) to \(i\) when permuting the colours on \(V_2\). Correspondingly, edges in the bipartite complement of \(G_{CR}\) encode how we are allowed to permute \(p\) on \(V_2\). Any perfect matching will give us a valid permutation \(\pi\). If we permute \(p\) with \(\pi\) on \(V_2\), all edges in \(C\) will be cut. Correspondingly, given a solution \(p\) for \(G\) with \(p^{\ifthenelse{\equal{}{}}{}{}}_{\ifthenelse{\equal{V_1}{}}{}{|V_1}} \cong p', p^{\ifthenelse{\equal{}{}}{}{}}_{\ifthenelse{\equal{V_2}{}}{}{|V_2}} \cong p''\) that cuts all edges in \(C\), we can derive a perfect matching in the colour relation graph. We do this by determining a permutation \(\pi\) that maps \(p''\) into \(p^{\ifthenelse{\equal{}{}}{}{}}_{\ifthenelse{\equal{V_2}{}}{}{|V_2}}\).

From this idea we can derive the following reconstruction algorithm:

The proof follows the previous outline and can be found in full in Appendix 10.1. By applying Theorem 1 we obtain the following result:

We now know how to efficiently reconstruct a cut set, provided that reconstruction is possible. However, as seen in Figure 6, there are cut sets for which reconstruction is not guaranteed to succeed.

Therefore, before splitting \(G\) at a positive cut set, we must make sure that ReconstructSCS finds a partition. We present some efficiently checkable criteria that assure that we can reconstruct a solution or prove that this is not possible. They make no assumptions about \(p'\) and \(p''\), and therefore work regardless of the partitions provided for \(V_1\) and \(V_2\).

5.2.2 Criteria for Removing Structured Cut Sets↩︎

We first introduce two criteria showing that sufficiently small cut sets can always be removed.

Both of these criteria can be checked efficiently. However, as we can see in Figure 7, there are cut sets that we can split that satisfy neither criterion.

A naive approach to solve this issue would be to simply enumerate all colourings of \(\partial_G(V_1), \partial_G(V_2)\) and check if we can reconstruct. However, this would be very time consuming, even for small \(k\). Instead we present another criterion that can be applied to larger separators and takes their combinatorial structure into account:

This criterion can be checked efficiently in time \(\mathcal{O}(|C| + k^{2.5})\) using the algorithm by [24]. Further, if the cut set contains at most \(k\) vertices, we only require \(|M| \geq 0\). Therefore, this criterion implies the first criterion from Theorem 6. Note that this criterion is sufficient, but for \(k > 3\) it is not necessary. For \(k = 4\) an example of a graph for which the criterion does not hold, but that is valid to separate, can be seen in Figure 9.

To complement the criteria showing that reconstruction is possible, we also show a simple criterion that shows reconstruction is not guaranteed to be possible:

This implies that for \(k = 2\) we can only remove cut sets containing one edge, which are already covered by splitting biconnected components.

5.3 Criteria where one Solution is Known↩︎

So far we assumed that the solutions for \(G_1\) and \(G_2\) are unknown. If we know the optimum solution for w.l.o.g. \(G_2\), we can contract all vertices in \(V_2\) that share a colour. If any criterion from Theorems 6 or 7 is fulfilled, we can delete all vertices in \(V_2\). Knowing the solution for \(G_2\) also enables a new criterion: Let \(v_1,...,v_r\) be the boundary of the contracted \(G_2\). If \(d_{G[C]}(v_i) \leq k - i\), we can delete all vertices in \(V_2\). During reconstruction we permute \(p\) on \(V_2\) such that \(v_i\) gets a colour not used by any vertex in \(N_{G[C]}(v_i)\) or \(v_1,...,v_{i - 1}\).

Given a positive cut set \(C\) we can not split with Theorems 6 or 7. If \(|V_2| \leq 20\) we solve \(G_2\) to optimality and check the criteria above.

5.4 Finding Structured Cut Sets↩︎

As we do not have a nice “if and only if” characterisation of which cut sets we can split, designing an efficient algorithm to find them is difficult. Theorem 8 implies that we can only split structured cut sets with at most \((k-1)^2\) many edges. We therefore propose to find structured cut sets by identifying small cut sets, checking our criteria, and solving one side to optimality if it is sufficiently small. For this we employ a heuristic based on the randomized MinimumCut algorithm FastCut by Karger and Stein [25]. FastCut works by randomly contracting edges to generate large numbers of small cuts, which we take as candidates.

6 Computational Experiments↩︎

For our experiments, we implemented the assignment model for by [11]. To strengthen the model we employ greedy heuristics to separate cycle, general clique, wheel and bicycle wheel inequalities from [11] and \(1, -1\) hypermetric inequalities from [14]. The solver serves both as a baseline to compare against and as the solver for the kernel graphs left over by our preprocessor. To provide a warm start for the solver we implemented a local search algorithm with tabu search based on [26]. We also used this heuristic for experiments on very large instances.

For the order of data separation and reduction rules we chose to first employ rules that maintain local positivity and unit weight of edges, to ensure that rules requiring this can still be applied later. This lead us to the following order:

1. Remove low degree vertices and split (bi)connected components

2. Locate and remove structured cut sets using FastCut and Theorems 6 and 7.

3. Remove unit weight cliques with a small neighbourhood (Theorem 2).

4. Contract negative-weight dominating edges.

5. Find two vertex separators yielding at least one small component and apply Theorem 3.

6. Find cut sets where one side is small, solve it and check if it can be removed.

If any rule successfully reduces the graph, we restart at the top. We use queues and flags to keep track of which vertices are promising candidates for the various rules and to make sure we do not run expensive rules too often. Similar techniques are used in [6], [8]. We decided to forego the preprocessing rule by [10], as they reported no reduction for \(k > 2\).

6.1 Setup↩︎

We implemented everything in C++ 20. For a graph class and fundamental algorithms we relied on NetworKit [27]. To locate biconnectors we use the SPQR-tree implementation of [28] in the Open Graph Drawing Framework [29]. We compiled the code using gcc 14.3.0 with the “-O3” flag. All experiments were run on a machine with 2 Intel Xeon “Sapphire Rapids” 48-core CPUs and 1024 GB RAM running AlmaLinux 9.6. To solve ILPs we used the state of the art solver Gurobi 13 [30] and set it to use as many threads as needed. We also employed parallelism to collect small cuts for separating structured cut setsand in our local search heuristic.

6.2 Instance Selection↩︎

We used the instances by [8], which is the most recent study on MaxCut-preprocessing. These are separated into four sets: easy, medium, big and torus. The first three sets contain instances from image segmentation and VLSI-chip design problems from [31] and biological, co-author and social networks from [32]³. The instances are split into easy, medium and hard based on how challanging they are for MaxCut. As the difficulty for varies strongly depending on \(k\) we decided to keep the grouping of [8]. The torus instances contain \(2\) and \(3\)d toroid grids from statistical physics from [33], originally generated by [34]. We also relaxed the CELAR, GRAPH and DUTtest1 sets of frequency assignment problems from [35], referred to as fap instances. These were originally provided by the CALMA project and [36]. See Appendix 11.2 for more detail on our instance sets.

6.3 Running an Experiment↩︎

We compare runs with no preprocessing, naive preprocessing (only low degree vertex removal and splitting (bi)connected components), and our preprocessing. We evaluate the \(k\)-values \(\left\{3,\ldots,8,10,12\right\}\). On the easy, medium, fap and torus datasets we employ Gurobi with a \(30\) minute time limit to solve the instances to optimality. For the big data set we run a local search heuristic with a two hour time limit. Preprocessing is included in the time limit and reported runtime. To account for variances, we run \(5\) seeds for Gurobi and \(3\) for the heuristic.

Given a combination of instance and \(k\), we determine a winner: The winner is the configuration that found the optimum solution on the largest number of seeded runs. In case of a tie, we first break by the average dual bound on the solutions not solved to optimality and then by runtime on the solved instances.

6.4 Computational Results↩︎

Figure 10 shows the number of optimum solutions found for the instances from [8] and the fap instance set. We observe significant improvements for the challenging fap data set, with the exception for \(k=5\). For \(k = 7\) we solve three additional instances and for \(k = 8\) we solve five more instances. In both cases the additional instances solved are from the real world CELAR data set, while our performance on the synthetic GRAPH and DUTtest1 instances is the same as both naive and no preprocessing. The improvements for larger values of \(k\) are due to the increased effectiveness of our structured cut sets. With increasing \(k\), many of the subgraphs split by our preprocessing are easy to solve, since they can be \(k\)-coloured easily. On the torus instances, the number of solved instances decreases with increasing \(k\), as the size of the search space grows significantly, while the grid structure means very few cutting planes are applicable. Most easy and medium instances can be routinely solved, both with and without preprocessing. Since solution times for the easy instances are below one second even with the naive preprocessing, we do not discuss them further here (see Appendix 11.3).

We now take a closer look into the medium dataset. Table ¿tbl:tab:benchmark95medium? shows the number of wins, the runtimes, and the sizes of the remaining graphs after preprocessing. We observe significant gains over naive preprocessing. Across all \(k\), the average graph kernels remaining after our preprocessing are significantly smaller than those from naive preprocessing. This leads to our preprocessing achieving more wins and lower average runtime for most \(k\). This is especially visible for \(k \geq 8\) where Gurobi with our preprocessing beats pure Gurobi by an order of magnitude and naive preprocessing by a factor of \(6\). The most challenging instances in the medium data set are network instances. These frequently contain small, dense subgraphs that are only sparsely connected to the remaining graph. Our preprocessing splits these off or removes them with the clique, structured cut sets and biconnector rules, making the kernels much easier to solve.

On the fap dataset, preprocessing removes significantly less than on the previous data sets (see Table ¿tbl:tab:benchmark95fap?). This is primarily caused by fap instances being denser than the previous network instances. Still, our preprocessing is able to separate or remove dense subgraphs that are only sparsely connected to the remaining graph. Due to this, we observe more wins and faster runtimes on average, in addition to solving more instances to optimality.

The torus instances differ in their structure significantly from the other data sets as their grid structure and the large number of negative edge weights makes almost all our preprocessing rules not applicable. In Table ¿tbl:tab:benchmark95physics? we see that naive preprocessing is able to remove almost nothing, even for higher values of \(k\). Our preprocessing is able to remove significantly more, as contracting negative-weight dominating edges breaks up the grid like structure, enabling other preprocessing rules.

On the big data set we observe more mixed results. As seen in Table ¿tbl:tab:benchmark95big?, for most instances our preprocessing does not achieve significantly greater reductions than naive preprocessing, while taking much longer. A notable exception is the web-it-2004 instance, on which our preprocessing removes almost 90% of nodes and 65% of edges for all \(k\), while naive preprocessing can not remove more than 12% of nodes and 2% of edges, even for \(k = 10\). Unfortunately our preprocessing usually does not lead to better heuristic values. A significant amount of time is spend to ensure everything is optimality-preserving. This conflicts with finding the best solution within the time limit, as the objective value on the kernels has the greatest impact on the objective for the whole graph.

6.5 Ablation Study↩︎

To evaluate the impact of our different preprocessing rules, we benchmarked how the performance changes when a rule is disabled. Table ¿tbl:tab:ablation? shows the results. Across all values of \(k\), disabling the dominating edge rules leads to the largest kernels on the torus set. However, disabling the biconnector, SCS or SCSS rule has a stronger impact on the number of wins. This suggests that these rules remove data that the solver would usually struggle with. On the medium instances, disabling the clique and dominating edge rule causes the greatest loss in the number of removed edges. This is different on the fap instances, where disabling the biconnector and the SCSS rules lead to the lowest number of removed edges. However, on the medium and fap set, none of clique, biconnector or SCS cause significantly fewer wins when removed. This suggests that these rules have comparable impacts on our ability to solve instances to optimality.

7 Conclusion and Outlook↩︎

We introduced new optimality-preserving data reduction and data separation rules for . In particular, we proposed structured cut sets, a new data separation rule that is especially effective for \(k\ge 3\). Our experimental results show that structured cut sets enables the removal of many cut sets, particularly for larger \(k\). Combined with generalisations of MaxCut-preprocessing rules, this allows us to solve significantly more instances than using an exact solver with naive preprocessing only. This holds for instances from different real-world applications and across different values of \(k\).

Future work includes developing additional criteria for cut sets whose removal preserves optimality. It would also be interesting to investigate whether structured cut setscan be used for problems related to . Furthermore, it would be interesting to engineer a preprocessing framework especially suited for running heuristics on very large instances.

8 Preprocessing Framework↩︎

8.1 Offsets↩︎

The constant offsets of the discussed rules are as follows:

• Low degree: \(\sum_{e \in \delta(v)} w(e)\)

• Cliques with a small neighbourhood: Let \(c\) be the unit edge weight of \(C\) and \(F = N(V_C) \cup V_C\). Then the offset is \[\begin{align} \frac{c}{2} \cdot \left( |F|^2 - (k - (|F| \mod k)) \cdot \left\lfloor \frac{|F|}{k} \right\rfloor^2 - (|F| \mod k) \cdot \left\lceil \frac{|F|}{k} \right\rceil^2 \right) \end{align}\]

• \(2\)-Vertex Separators: \(w(p')\)

• Negative Dominating Edges: \(0\)

• Negative Dominating Triangles (see Appendix 9.3): \(0\)

• (Bi)connected Components: \(0\)

• Structured Cut Sets: \(\sum_{e \in C} w(e)\)

  • If the optimum solution \(p\) for w.l.o.g. \(G_2\) is known, then \(w(p) + \sum_{e \in C} w(e)\).

8.2 Combining Partitions↩︎

Proof of Lemma 1:

9 Data Reduction Rules↩︎

9.1 Proof of Theorem 3↩︎

9.2 Larger Vertex Separators↩︎

A natural question that arises is whether or not we can also use \(3\) vertex separators or even larger separators for a similar preprocessing strategy. Our clique based rules work on larger separators, but rely on a very special structure of the graphs on the other side that we can not hope for in general. In [8] the usage of \(3\) vertex cuts was employed for MaxCut. Unfortunately, this can not be generalised to higher values of \(k\).

For MaxCut, given a \(3\) vertex separator \(u, v, w\), the weights of \(\{u, v\},\{u, w\}\) and \(\{v, w\}\) could be modified. Together with the offset, this gives \(4\) degrees of freedom to encode the differences in objective values for the \(4\) different optimum values for “\(u, v, w\) are in the same group”, “\(u, v\) are in the same group, \(w\) is in the other group”, “\(u, w\) are in the same group, \(v\) is in the other group” and “\(v, w\) are in the same group, \(u\) is in the other group”. For with \(k \geq 3\) we would have to encode a fifth optimum value for the case “\(u, v, w\) are all in different groups”, which makes using \(3\) vertex cuts in general not possible.

9.3 Dominating Edges and Triangles↩︎

In MaxCut preprocessing, Lange et. al [9] discussed that an edge \(e = \left\{u, v\right\}\) can be contracted if we know that there is an optimum solution that cuts \(e\). This is achieved by multiplying the edge weights of edges incident to \(u\) before contracting \(u\) into \(v\). This means if \(x\) and \(v\) are on different sides of the cut in the reduced graph, we take a penalty of \(w(\left\{x, u\right\})\), as \(x\) and \(u\) are on the same side after reconstruction. If \(x\) and \(v\) are on the same side, then \(x\) and \(u\) are on different sides after reconstruction and we take no penalty.

For for \(k \geq 3\) this unfortunately does not work, as there is also the configuration \(x, u\) and \(v\) all have different colours. The same issue was noted by Lange et. al [9] with their preprocessing for MultiCut.

9.3.1 Dominating Triangles↩︎

For the proof we refer to [9]. Unfortunately the rule does not immediately extend to . Luckily we can show that a stricter version the rule still holds for .

10 Proofs and Further Notes for Structured Cut Sets↩︎

10.1 Proof of Theorem 5↩︎

10.2 Proof of Theorem 8↩︎

10.3 Proof of Theorem 6↩︎

10.4 Proof of Theorem 7↩︎

10.5 Further Notes on Structured Cut Sets↩︎

A natural question is if we can also split structured cut setsthat contain negative weight edges. Unfortunately that is not the case. Given a cut set \(C \subseteq E\) and \(\{u, v\} = e \in C\) with \(w(e) < 0\), we distinguish two cases:

Case 1: \(|C| = 1\). In this case either the connected component containing \(e\) contains only two vertices, or at least one endpoint of \(e\) is a separating vertex and we can simply apply the rule for splitting biconnected components. Therefore, there is no need to consider the algorithms we developed around structured cut sets.

Case 2: \(|C| \geq 2\). In this case let \(\{u', v'\} = e' \in C, e \not = e'\) and we assume that w.l.o.g. \(u \not = u'\), \(u, u'\) are on one side of the cut set and \(v, v'\) are on the other. If \(w(e') < 0\), then if our solutions for \(G_1, G_2\) require that \(p(u) \not = p(u')\) and \(p(v) = p(v')\), we must cut one of \(e\) and \(e'\). If instead the solutions require \(p(u) = p(u')\) and \(p(v) = p(v')\) it is possible to cut neither.

As such we would somehow have to encode the trade off between cutting neither of \(e, e'\) and performing better on \(G_1\) and \(G_2\), which makes the techniques we developed unusable. If \(w(e') > 0\) a similar argument can be made.

11 Computational Experiments↩︎

11.1 Detailed Overview of our Preprocessing Order↩︎

We chose the order, in which the rules are applied, based on the following criteria:

• Does a rule require and/or maintain local positivity and/or unit weight?

• Can applicability of the rule be checked locally around a single vertex or do we have to observe the whole graph?

• How fast is it to check and apply a rule?

Our core idea is that all rules that require local unit weight and positivity should be applied to exhaustion before any rules that may break either property. We then run rules that may break local unit weight, but not local positivity and finally we run all remaining rules. This is to ensure that no rule causes problems with the prerequisites of another rule.

Within each group of rules, we first applied those that can be checked locally. For each such rule, we maintain a queue of candidate vertices where the rule may be applicable. If, for a vertex \(v\), an incident edge changes, we add \(v\) back to the queues for locally checkable rules again. For rules that run on the whole graph, once applied once, we mark them as blocked and only unblock them once all other rules have run to exhaustion. The only exception to this is the separator rules, which we unblock before moving from unit weight relying rules to rules that break unit weight and again when moving from rules that require local positivity to rules that break local positivity.

After some experimenting, we arrived at this order for the data separation/reduction rules:

1. Splitting into connected and biconnected components

2. Removal of locally positive low degree nodes

3. Splitting at structured cut sets(see Section 5.2)

4. When reaching this point for the first time, reactivate all data separation rules and start from the top

5. Removing unit weight cliques (see Theorem 2)

6. Rules requiring and maintaining local positivity

   1. Contracting negative dominating edges (see Theorem 4)

   2. Contracting negative triangles (see Theorem 10)

7. When reaching this point for the first time, reactivate all data separation rules and start from the top

8. Remaining rules

   1. Removing small leafs of SPQR-trees (see Theorem 3)

   2. Split SCSs where one side is small and can be solved during preprocessing.

9. When reaching this point for the first time, reactivate all rules and start from the top

Any time a rule shrinks or splits the graph, we start again from the top.

11.2 Instance Selection↩︎

See Table 1 for on overview over all instances.

For the frequency assignment instances we removed the frequency constraints on the nodes and relaxed all edge constraints to “the endpoints must have different colours”. If the instances came with costs for breaking an edge constraint, we used that as the edge weight. Otherwise we set all edge weights to \(0\). The instances that come with their own costs assign one of \(4\) levels of importance to the edges. These correspond with costs \(1, 10, 100, 10.00\), \(1, 100, 10.000, 1.000.000\) or \(1, 1.000, 1.000.000, 1.000.000.000\), depending on the instance.

11.3 Results on the Easy Instance Set↩︎

See Table ¿tbl:tab:benchmark95easy?.

11.4 Heuristic Experiments↩︎

See Table ¿tbl:tab:benchmark95big95full?.

11.5 Ablation Experiments↩︎

See Table ¿tbl:tab:ablation95full?.

References↩︎

---

1. Corresponding author↩︎

2. The code is publicly available under https://github.com/mkaibel/MaxKCutPreprocessing↩︎

3. We removed the web-google instance used in [8], as it no longer appears to be on the network repository. We instead added a larger instance called web-google to the big set.↩︎