The dancing links algorithm by Knuth can be used to find decompositions of a complete graph eficiently. In this paper, we generalize it to find covers of a complete graph by cliques as well. This problem arose as one step of a parallel implementation of the bounded element method when solving partial diferential equations. The modification brought up an issue of counting certain covers of multiple edges multiple times. Having solved the problem by imposing a natural order, we show the computational results achieved by the modified algorithm.
however the core memory is rather limited. While computation is cheap, memory and data transfer are expensive, therefore it is favorable to keep small.
Boundary element methods (BEM) have become a useful
tool for solving partial diferential equations. In
comparison to widely used discretization techniques, as smaller 1.1. Covering of complete graphs
systems with fewer degrees of freedom they ofer certain
advantages. However, when implementing BEM, one of In this paper, we address the hardest part of the BEM
the major dificulties lies in dense matrices. To parallelize implementation - the problem of decomposing into
the computation, a method of decomposing a dense ma- ’s where is a small integer while grows along with
trix into (dense) submatrices using cyclic decomposition the number of available cores. In general, such
decomof complete graphs into complete subgraphs position cannot be cyclic. For fixed = 3 and = 4
was introduced in [
When becomes large, the cyclic decomposition is and Mills [
To find such covers for small by brute force, we
suc23rd Conference ITAT: Workshop on the Computational Aspects of cessfully use a modification of the dancing link algorithm
Large-Scale Problems in Discrete Mathematics, September 22–26, 2023, (DLX) by Donald Knuth [
For example, the following matrix has such a set formed by the rows 2 and 3. problem. One modification is based on extending the reaches a point where all columns have been “removed”, data structure, while the other is a modification of the i.e. [ℎ] = ℎ. Then the algorithm goes back to the algorithm itself. In the forthcoming sections, we describe last level of depth and attempts to include the next row the two approaches. that covers the same column, as soon as the “removed” columns are “restored” in the matrix by the correspond1.2. Decomposition of complete graphs ing modifications of links in the function uncover_column.
The output of the algorithm would contain all feasible using the dancing links algorithm solutions to the exact cover problem, while it also makes sense to stop after finding the first solution when we are only interested in the existence of a solution. ⎛1 1 0 1 0 0 1⎞ ⎜0 1 1 0 1 1 0⎟ ⎜⎜1 0 0 1 0 0 1⎟⎟ ⎜⎜0 1 1 0 1 1 1⎟⎟ ⎜⎝1 0 1 1 1 1 0⎟⎠
1 1 1 0 0 1 0
A special data structure is suggested by Knuth to implement the algorithm, that each 1 in the matrix be represented by a data object with five fields including [], [], [], [], pointing circularly left, right, up, down to the neighbour of , as well as [] that links to the column object it belongs to. Situated in the list header, each column object has two additional fields besides those attributed to a normal data object, its size [] which counts the number of 1s in the column as well as its name [] that serves as an identifier for printing.
An additional root object ℎ is added linking all column objects circularly, i.e. [ℎ] points to the leftmost column, while [ℎ] to the rightmost one. The object ℎ does not admit the other fields, i.e. [ℎ], [ℎ], [ℎ], [ℎ] and [ℎ] are not used.
The algorithm works as follows. A depth-first search tree is set up by invoking search(0). As long as there is at least one column in the list headers, the algorithm chooses the leftmost column, and tries to form a solution by the first row that is able to cover this column.
The choice of column we made here left the field unused throughout the algorithm. Before continuing, the algorithm requires the chosen column to be “removed” by modifying the links of its neighbours in the function cover_column. Other columns covered by the same row need to be “removed” in the same way, so that the size of the data matrix will decrease. Then search(1) is invoked recursively on the shrunk matrix to include another row in the partial solution. If this partial solution turns out to be a valid solution, it is printed by the function print_solution when the corresponding search 1It is a frugal approach to the problem, albeit not polynomial. def choose_column():
return R[h] def cover_column(c):
L[R[c]] = L[c] R[L[c]] = R[c] i = D[c] while i != c: j = R[i] while j != i:
U[D[j]] = U[j] D[U[j]] = D[j] j = R[j] i = D[i] return def uncover_column(c): i = U[c] while i != c: j = L[i] while j != i:
U[D[j]] = j D[U[j]] = j j = L[j] i = U[i] L[R[c]] = c R[L[c]] = c return def print_solution(): s = [] for o in partial_solution: row = [N[C[o]]] p = R[o] while p != o: row.append(N[C[p]]) p = R[p] s.append[row] print(s) return def search(depth): if R[h] == h: print_solution() return else: c = choose_column() cover_column(c) r = D[c] while r != c: partial_solution.append(r) j = R[r] while j != r: cover_column(C[j]) j = R[j] search(depth + 1) r = partial_solution.pop() c = C[r] j = L[r] while j != r: uncover_column(C[j]) j = L[j] r = D[r] uncover_column(c) return
When the structure of 21 columns and 35 rows are inputted, the dancing links algorithm finds 30 solutions for the decomposition of 7 into 3, as expected.
The major challenge posed to the original dancing links algorithm when considering the covering rather than the decomposition of a complete graph is that a solution may contain more than one row covering the same column. This section suggests possible modifications to the original algorithm in order to overcome this issue.
The decomposition of a complete graph by copies of a smaller complete graph ( ≤ ) can be naturally modelled as an exact cover problem, in which the edges of are treated as columns and the subgraphs of isomorphic to serve as the rows: one row for every choice of vertices from the with ones denoting the edges contained in the particular choice.
For example, consider the decomposition of 7 into such as 1,2 + 1,3 + 2,3 and 4,5 + 5,6 + 4,6, must 3, where 21 columns are given, each correspond- be doubled in the data structure, resulting in 32 rows ing to an edge of 7, and there are (︀ 37)︀ = 35 rows instead of 20. that represent the 35 3-subgraphs of 7. Denote Introducing extra columns does not only bring about the vertices of 7 by 1, 2, · · · , 7, and let , := bloated data structure, but also redundant solutions. If (0, · · · , 0, edg1e-, 0, · · · , 0), then, for instance, the row some solution contains a row that has been doubled when corresponding to the triangle ∆123 has the form 1,2 + building the data structure, it would appear again as 1,3 + 2,3. Apparently, the rows 1,2 + 1,4 + 2,4, another solution including the clone of the same row. 2,3 + 2,5 + 3,5, 3,4 + 3,6 + 4,6, 4,5 + 4,7 + 5,7, For instance, solving the covering problem of 6 by 3 1,5 + 1,6 + 5,6, 2,6 + 2,7 + 6,7 and 1,7 + 1,3 + 3,7 with 3 extra columns as mentioned above using dancing constitute a solution to the exact cover problem, which links yields 16 solutions, of which only 2 are genuinely corresponds to the decomposition of the 7 into the diferent from each other. following 7 copies of 3: In graph coverings, the excess multigraph is often not determined uniquely. When the excess is fully known, it seems natural to add the edges in the excess as extra columns, so that the covering problem is transformed to a decomposition one.
For example, consider the covering of 6 by 6 copies
of 3, of which the excess is known ([
{∆124 , ∆235 , ∆346 , ∆457 , ∆156 , ∆267 , ∆137 }.
To count the number of feasible coverings from a the- Besides introducing extra columns, the algorithm can be oretical perspective, notice that fixing the triangle ∆123 steered to revisit a column as long as it is not “removed" in the solution is equivalent to choosing 3 as the last from the structure during the last visit, which motivates element in the triangle covering the edge 1-2 among 5 us to assign a multiplicity [] to each column in the options: 3, 4, 5, 6, 7; fixing also ∆145 is equivalent to original data structure that equals 1 by default. When choosing 5 as the last element in the triangle covering 1- an edge is in the excess of a covering problem, we raise 4 among 3 options: 5, 6, 7; then fixing ∆246 is equivalent the multiplicity of the corresponding column to match to choosing 6 as the last element in the triangle covering the amount it needs to be covered. The vector can be 2-4 among 2 options: 6, 7; and it is now apparent that the implemented as an additional field of the header elements. remaining part of the solution is unique: ∆167 , ∆356 , For example, when covered by triangles, if we order the ∆257 and ∆347 .
We modify the functions cover_column and uncover_column accordingly so that the multiplicity is always increased or decreased by 1 while the “removal" or “restoration" of the column only happens when its multiplicity is 1 or 0, respectively.
This approach avoids the unnecessary expansion of data structure, while continues to generate duplicate solutions. Suppose two rows cover the same column and sit in a feasible solution to a covering problem, the same solution may reappear with the two rows included in the reverse order. If the leftmost column has a high multiplicity, the algorithm yields numerous duplicate solutions; in comparison, if the column with higher multiplicity is placed further to the right in the structure, as the data matrix shrinks during the search, the algorithm tends to generate fewer duplicate solutions.
For example, consider the covering of 5 by 4 copies
of 3, of which the excess is known ([
This section evaluates the dancing links algorithm adapted to the covering problem in Section 2.2. Some improvements to eliminate multiple counts are suggested.
An apparent shortcoming of our algorithm is the redundant search of rows covering the same column with nontrivial multiplicity, which not only produces an inaccurate number of solutions, if any exist, but also harms the eficiency of the algorithm. To address the issue, when covering such a column, the rows containing it should be processed only in a certain order.
One approach is to introduce an order on the elements in each column. More specifically, we return the currently processed row in the search function, and start the next search from the next valid row once the columns concerned are properly “removed" by the cover_column function. This idea is realised by introducing the previously unused field [] to each data object : the objects in a column are assigned values 1, 2, · · · , [] from the top row to the bottom. The modified search function (see the lines 8–13 below) follows. def search(depth, prev): if R[h] == h: print_solution() return prev else: c = choose_column() cover_column(c) r = D[c] if c == C[prev]: while S[r] < S[prev]: if r == c:
break r = D[r] while r != c: partial_solution.append(r) j = R[r] while j != r: cover_column(C[j]) j = R[j] search(depth + 1, r) r = partial_solution.pop() c = C[r] j = L[r] while j != r: uncover_column(C[j]) j = L[j] r = D[r] uncover_column(c) return r obj = L[obj] if obj == L[r]:
break return
For instance, with the following lines executed, the algorithm finds only 2 decompositions of 7 into 3 containing the triangles ∆123 and ∆145 , as expected.
In addition to the redundant solutions addressed in Sec- utilise_row('1, 2, 3') tion 3.1, another factor that increases the size of output utilise_row('1, 4, 5') is that some solutions are simply a permutation of ver- search(0) tices applied to one another, such as the following two neutralise_row('1, 4, 5') decompositions of 7 into 3: neutralise_row('1, 2, 3') {∆124 , ∆235 , ∆346 , ∆457 , ∆156 , ∆267 , ∆137 }, {∆123 , ∆245 , ∆346 , ∆357 , ∆156 , ∆267 , ∆147 }.
It is worth mentioning that some solutions, even sometimes all, may be omitted when a search bears too many ifxed rows. Further research can be carried out on the maximal amount of (independent) rows one is able to fix while preventing the algorithm from missing a solution.
If we draw the vertices 1, 2, · · · , 7 of 7 cyclically, the ifrst solution above is a cyclic decomposition into 3 while the second seems not to be cyclic. However, if we swap the vertices 3 and 4, the second solution becomes 4. Computations cyclic as well, which implies that the two solutions are equivalent. To demonstrate the eficiency of the DLX algorithm for
Multiple counts of equivalent solutions appeared al- the cover problem, we summarize computation times ready in graph decompositions. Motivated by such con- for finding all solutions when covering by for siderations, we can fix certain row(s) when searching = 3, 4 along with the count of all possible covers. solutions using the dancing links algorithm to omit equiv- Confirming the existence by finding the first solution, alent solutions, provided that merely the existence of any provided it exists, for in Tables 2 through 4 took less solution interests us. The implementation follows. than 1 second in each of the cases. Table 1 compares rundef utilise_row(r): ning times of the original dancing link algorithm with partial_solution.append(r) the modified algorithm where decomposition (not cover) obj = r is possible, since the DLX algorithm does not support while True: covers. The times are essentially identical, since the modicover_column(C[obj]) ifcation did not have much influence on the performance. obj = R[obj] Tables 2 through 4 then compare running times of the if obj == r: cover problem for diferent sizes of the covered graph.
break Columns 3 and 4 give the counts and times when finding return all possible covers using the modification of the DLX algorithm described in Section 2.2, where some equivalent
After the data setup, we may execute several lines solutions are counted multiple times. Columns 5 and
of utilise_row to restrict our attention to the solutions 6 give the counts and times when finding all possible
containing certain rows, before invoking search(0). For covers eliminating multiple counts (and thus reducing
the sake of conservation of the structure, it is advisable to the number of cases to traverse) using the modification
call the following neutralise_row function in the opposite described in Section 3.1.
order after the search of solutions, when the original data Other approaches have been used to find complete
structure is properly restored. graph decompositions using a brute force search. In [
return -1 else: obj = L[r] while True:
uncover_column(C[obj])
5. Conclusion
On the other hand, the nonexistence of a 6
decomposition of 16 was shown in less than a second by UNSAT
in [
When running the DLX algorithm for = 3 and = 4 we include the positive answers only (Tables 2 and 3), since the existence is known. When covering simultanously by 3 and 4 we provide running times of the DLX algorithm even in some cases when no solution exists (e.g. with excess 2), which was demonstrated by a brute force search with negative outcome (Table 4).
This work is partially supported by Grant of SGS