The Black-and-White Coloring (BWC) problem seeks to find a partial vertex coloring of a graph (or hypergraph) that maximizes the number of white vertices for each number of black vertices, such that no black and white vertices are adjacent. This problem is NP-complete in general. In this paper, we present a polynomial-time algorithm to solve the BWC problem on a family of sparse hypergraphs whose hyperedge intersection graph forms a tree.
The Black-and-White Coloring (BWC) problem on a graph is defined as follows. Given a finite connected undirected graph and a positive integer , find a partial coloring of with exactly black vertices and with white vertices, where is as large as possible and with the restriction that the black and white vertices are not adjacent. The hypergraph version of BWC is defined analogously: Given a hypergraph and a positive integer , find a partial coloring of with exactly black vertices and with white vertices, where is as large as possible and with the restriction that no hyperedge in contains black and white vertices. The remaining vertices are left uncolored. Note that once the set of black vertices is ifxed, the white vertices are determined, and the resulting coloring is deemed optimal. In this context, a solution is fully characterized by its set of black vertices.
The BWC problem has several practical applications. An example arises in chemical storage, where storage locations are represented by vertices and each hyperedge corresponds to a group of locations that must store mutually compatible chemicals. In this context, colors represent chemical types: A black vertex might indicate a location storing a reactive chemical, while a white vertex indicates a location with a nonreactive (safe) chemical. The BWC constraint ensures that no hyperedge (i.e., group of storage locations) contains incompatible chemicals, thereby enabling safe and eficient use of storage space. Another example arises in social network analysis, where individuals must be assigned to groups in a way that avoids conflicts of interest. For example, one group may represent members who support a particular initiative, while another group represents those who oppose it. The BWC model ensures that no individual in favor (black) is placed in direct interaction with an opponent (white), while neutral or undecided individuals can remain uncolored. This abstraction allows analysts to identify stable partitions of the network that minimize tension and highlight potential zones of agreement or conflict. For additional applications, see [1].
The problem was originated by Berge, who raised the following instance [6]. Given positive integers and ≤ 2, place black and white queens on an × chessboard, so that no black queen and white queen attack each other and with as large as possible. Hansen et al. [10] formalized the general BWC problem and proved its NP-completeness while providing an (3) algorithm for trees. Berend and Zucker later improved this runtime to (2 lg3 ) for trees [2]. Related anticoloring problems based on rook placements [14] and king placements [1] have also been studied.
The Black-and-White Coloring problem can be naturally extended to settings involving more than two colors. This leads to the notion of an anticoloring, which is a partial vertex coloring of a graph with two or more colors such that no edge connects vertices of diferent colors. Formally, in the general anticoloring problem, we are given an undirected graph and integers 1, . . . , , and the task is to decide whether there exists a coloring in which exactly vertices are assigned color (for each = 1, . . . , ), while all other vertices may remain uncolored. Such a coloring is referred to as a (1, . . . , )-anticoloring. It was observed by [14] that this formulation can be conveniently expressed as an integer linear program. Heuristic methods, including tabu search [4] and a greedy probabilistic approach [5], have been proposed to solve the problem. In [16], the BWC problem was solved for chordal graphs. In addition, a two-approximation algorithm was presented in [15] to minimize erroneous edges in the full-coloring version (in which every vertex is colored black or white, while minimizing the number of edges connecting diferently colored vertices).
A problem closely related to BWC is the separation problem. Here, one is given an -vertex graph and a constant < 1, and the goal is to partition the vertices of into three sets , , with the following properties: (i) no edge has one endpoint in and the other in , (ii) both and contain at most vertices, for < (iii) the set is relatively small. 1, and The set functions as a separator of , since deleting it divides the graph into two subgraphs of bounded size. Using the vertices of as black, those of as white, and leaving uncolored, one obtains a BWC of the graph (not necessarily an optimal one).
Typically, the separation problem is studied within specific graph classes that are closed under taking subgraphs. An ()-separator theorem for (see, e.g., [11]) asserts that every graph ∈ admits such a partition with || ≤ ().
In this paper, we extend the study of the BWC problem to hypergraphs. A hypergraph = (, ) generalizes a graph by allowing each hyperedge ∈ to be a subset of . In the hypergraph version of the BWC problem, the restriction is that no hyperedge may contain both black and white vertices simultaneously. Our focus on sparse hypergraphs, where the weighted line graph forms a tree, allows us to leverage the tree structure for an eficient dynamic programming solution. Compared to previous work on trees, which achieved the complexities of time (3) [10] and (2 lg3 ) [2], our algorithm runs in (3), remarkably eficient given the increased complexity of hypergraphs compared to graphs. Note that such hypergraphs possess a small separator, similarly to trees and chordal graphs, facilitating eficient decomposition and dynamic programming. Our algorithm computes all pairs (, ) representing optimal BWC’s for a given hypergraph, providing a comprehensive solution for the optimization variant of the problem.
The remainder of the paper is organized as follows. In Section 2 we present some basic notions. Section 3 gives the main results. Section 4 details the proofs and describes the algorithm. Finally, Section 5 describes future research directions.
We begin by recalling the notion of a (, )-coloring for the BWC problem. A (, )-coloring of a graph (or hypergraph) is a feasible partial coloring with exactly black and white vertices, where the constraints of the BWC problem are respected. A pair (, ) is said to be non-dominated if there is no other feasible BWC solution that simultaneously uses at least black vertices and at least white vertices, while having a strictly larger total number of colored vertices. Any (, )-coloring corresponding to a non-dominated pair is termed an optimal BWC.
Our algorithm computes the set of all non-dominated pairs simultaneously. We will show how to use it to find the required BWC. The main result is summarized in Theorem 3.1.
Hypergraphs and the Weighted Line Tree. A hypergraph = (, ) is defined as usual, with each hyperedge ∈ being a subset of .
We construct the weighted line graph () = ( , ) as follows: 1. Each vertex ℎ ∈ corresponds to a hyperedge ℎ ∈ and is assigned the weight (ℎ) = |ℎ|. 2. Two vertices ℎ and ℎ′ in () are adjacent (that is, (ℎ, ℎ′) ∈ ) if and only if ℎ ∩ ℎ′ ̸= ∅. The edge (ℎ, ℎ′) is assigned the weight (ℎ, ℎ′) = |ℎ ∩ ℎ′ |.
Under the restriction that the hyperedge intersection pattern forms a tree, () is a tree and we refer to it as weighted line tree. Our approach first solves a modified full-coloring problem on this tree (in which every vertex is colored either black or white,) and then derives a feasible BWC for . As usual, denote | | = , || = . Note that if a vertex ∈ is in three hyperedges 1, 2, 3, then 1 ∩ 2 ̸= ∅, 2 ∩ 3 ̸= ∅, 1 ∩ 3 ̸= ∅, which forms a triangle in (). Since () is a tree, this is impossible in our case, and therefore each vertex of is contained in at most two hyperedges and therefore ≤ 2.
Weighted Functions. For clarity, the weight functions of the vertices and edges of are defined by:
(ℎ) = |ℎ|, ℎ ∈ , ℎ ∈ ,
(ℎ, ℎ′) = |ℎ ∩ ℎ′ |, (ℎ, ℎ′) ∈ , ℎ, ℎ′ ∈
(
For each vertex ℎ in the weighted line tree , we store a field ℎ.cList, which is a dictionary with two keys: black and white. The value ℎ.cList[black] is the list ℎ, containing non-dominated pairs (, ) for the subtree rooted at ℎ with ℎ colored black, and ℎ.cList[white] is the list ℎ, containing non-dominated pairs (, ) for the subtree rooted at ℎ with ℎ colored white. The content of this field for the root of gives the desired non-dominated pairs for the hypergraph.
Figure 1 illustrates an example where a BWC with 6 black and 9 white vertices of a hypergraph is derived from a corresponding full-coloring of its weighted line tree. The numbers written inside each vertex ℎ of the weighted line tree demonstrate the value (ℎ) = ||. The weights of each edge (ℎ, ℎ ) demonstrate the value (ℎ, ℎ ) = | ∩ |.
Theorem 3.1. Algorithm 1 computes the complete list of non-dominated pairs for any hypergraph =
(, ) whose hyperedge intersection pattern forms a tree structure. The algorithm runs in (| |3) time.
fullColorLineTree(, )
Input: A hypergraph and its weighted line tree (with weight functions and defined in (
Algorithm 1: Compute all non-dominated pairs for a weighted line tree
Once the list of all non-dominated pairs is obtained, the maximal number of white vertices corresponding to any prescribed number of black vertices can be determined by scanning for the pair (′, ) with minimal ′ ≥ . We later discuss how to recover the actual BWC from the computed information.
Assume that is arbitrarily rooted. For each vertex ℎ of , the two lists ℎ and ℎ are computed recursively. Algorithm 1 initializes these lists for the leaves and then invokes the recursive procedure in Algorithm 2 to compute the lists for the internal vertices. Two auxiliary routines, extension (Algorithm 3) and merge (Algorithm 4), are used to extend the lists when adding a new parent and to merge lists from diferent subtrees, respectively. Eventually, the algorithm uses the procedure contract, which gets a list and deletes all dominated pairs (as well as repeated occurrences of pairs). This procedure uses the bucket-sort algorithm (cf. [7]).
In this section, we describe the algorithm in detail and prove its correctness. Throughout, = (, ) denotes a hypergraph and = () = ( , ) its weighted line tree. There is a natural correspondence between subtrees of and subhypergraphs of ; that is, for a subtree ′ with vertices corresponding to the hyperedges 1, . . . , , the associated subhypergraph is induced by 1 ∪ · · · ∪ .
Although a full-coloring does not necessarily respect any BWC constraints of , it provides the basis from which a feasible BWC is derived. For each vertex ∈ , if all hyperedges containing receive the same color, then is colored accordingly; otherwise, is left uncolored. This procedure guarantees that no hyperedge contains both black and white vertices.
Let and denote the total number of black and white vertices in the resulting BWC. A full-coloring that produces the pair (, ) will be called a (, )-full-coloring of .
We will show later how to find a (, )-full-coloring of from the output of Algorithm 1.
Assume that is arbitrarily rooted. For each vertex ℎ of , we maintain two lists, ℎ and ℎ, as explained before. These lists are stored in the field ℎ.cList.
Algorithm 1 initializes the process and, after executing Algorithm 2, compiles the final list of nondominated pairs. Algorithm 2 recursively computes this list. For each internal vertex with children 1, 2, . . . , , it first obtains the lists for each child (using a post-order traversal), then calls the extension procedure (Algorithm 3) to update the lists by adding the parent as the new root of the corresponding subtree, and finally merges these updated lists using the merge procedure (Algorithm 4). solveLineTree(, ) Input: A hypergraph and a root of its weighted line tree Output: .cList if is a leaf
return .cList 1, 2, . . . , ← all children of for ← 1 to .cList ← list ←
solveLineTree(, ) extension(, .cList[black], (.cList[white], ) // Extend ℎ by adding as a parent for ← 2 to
list1 ← merge(, list1[black], list[black], list1[white], list[white]) .cList ← list1 return .cList
extension(, , , ) Input: A hypergraph ; the lists , for = root of a subtree; and the new parent Output: The updated lists , for the subtree with root , whose only child is r , ← empty list for each (, ) ∈ append(, ( + () − (, ), )) append(, ( − (, ), + () − (, ))) for each (, ) ∈ append(, (, + () − (, ))) append(, ( + () − (, ), − (, ))) contract() // Remove dominated pairs contract() return ,
The extension procedure (Algorithm 3) takes as input the lists for the root of a subtree and ‘lifts’ the solution by introducing a new root (which becomes the parent). The merge procedure (Algorithm 4) then combines the lists of two subtrees with the same new root.
The Contract function (Algorithm 5) removes dominated pairs to maintain only non-dominated pairs: This procedure uses the bucket-sort algorithm (cf. [7]).
Example 4.1. Tables 1–6 show the performance of the algorithm on the weighted line tree of Figure 1.
Table 1 gives the initial lists for the leaves ℎ1, ℎ4 and ℎ6. For example, ℎ1 corresponds to a hyperedge of size
3, so ℎ1 = (
append(, (1 + 2 − (), 1 + 2)) contract() //delete dominated pairs for each (1, 1) ∈ 1 for each (2, 2) ∈ 2
append(, (1 + 2, 1 + 2 − ())) contract() //delete dominated pairs return ,
contract() Input: List of (, ) pairs Output: List ′ containing only non-dominated pairs from if || ≤ 1
return Sort by (, ) lexicographically //sort by black count, then by white count ′ ← ∅ maxWhite ← − 1 for (, ) ∈ in sorted order //process in order to increase black count if > maxWhite ′ ← ′ ∪ {(, )} maxWhite ← return ′
in the black list by adding (ℎ2) − (ℎ2, ℎ1) = 3 − 1 = 2 black vertices to (
Lists before deleting dominated pairs
ℎ2 (
We now briefly outline the proofs that establish the correctness of the algorithm.
Lemma 4.1. The lists produced by Algorithm 3 on .cList contain all non-dominated pairs for the subtree extended by the new root .
Proof: Consider a subtree rooted at with lists and , which, by induction, contain all nondominated pairs for . When extending to a new root , we consider two cases for ’s color.
Case 1: is colored black.
• If is also colored black, for each pair (, ) ∈ , the extended pair becomes ( + () − (, ), ). This is because the vertices in ∖ are newly colored black, adding () − (, ) black vertices, while the vertices in ∩ remain black. • If is colored white, for each pair (, ) ∈ , the extended pair becomes (+ ()− (, ), − (, )). Here, vertices in ∖ are colored black, but vertices in ∩ must be uncolored since is white and is black, so we subtract (, ) from the white count.
Case 2: is colored white.
• If is also colored white, for each pair (, ) ∈ , the extended pair becomes (, + () − (, )), as vertices in ∖ are newly colored white. • If is colored black, for each pair (, ) ∈ , the extended pair becomes ( − (, ), + () − (, )). Vertices in ∩ must be uncolored due to conflicting colors (black in , white in ), so we subtract (, ) from the black count and add () − (, ) white vertices.
These updates ensure that all possible colorings of the extended subtree are considered, and the contract procedure removes any dominated pairs, leaving only the non-dominated ones. Lemma 4.2. If the lists for two subtrees rooted at 1 and 2 contain all non-dominated pairs for their respective subtrees, then Algorithm 4 produces the correct lists for their merge at .
Proof: Since 1 and 2 are copies of , they correspond to the same hyperedge . Therefore, the algorithm merges lists of the same color:
Case 1: Merging black lists 1 and 2 . For pairs (1, 1) ∈ 1 and (2, 2) ∈ 2 , the merged pair is (1 + 2 − (), 1 + 2). The number () that is subtracted from the counting of black vertices represents the vertices belonging to the hyperedge . Obviously, some of these vertices should be colored black in the BWC, but some of them should be left uncolored, as they belong to ∩ ℎ, for some hyperedge ℎ that is colored white in the full-coloring of (). For each vertex in that should be colored black in the corresponding BWC of the subhypergraphs associated with both trees rooted at 1 and 2, we need to subtract it to prevent double counting. We also need to subtract all the vertices in that should be black only in the tree rooted at 1 and not in the tree rooted at 2 (or vice versa), as they should be left uncolored in the merged subtree. Note that since each ∈ belongs to at most two hyperedges, the case that is supposed to be left uncolored in both subtrees rooted at 1 and 2 is not possible. Together we subtract () vertices.
Case 2: Merging white lists 1 and 2 . Similarly, for pairs (1, 1) ∈ 1 and (2, 2) ∈ 2 , the merged pair is (1 + 2, 1 + 2 − ()), adjusting for overlapping white vertices in and for vertices which are colored white in only one of the subtrees and uncolored in the second.
The algorithm does not merge across diferent colors (e.g., black and white lists), ensuring consistency in the color assignment to . The contract procedure removes any dominated pairs from the merged lists.
Lemma 4.3. For each vertex ℎ of , the calculated ℎ.cList contains all non-dominated pairs corresponding to the subhypergraph induced by the subtree ℎ.
Proof: The proof is by induction on the height of the subtree ℎ. For a leaf ℎ, the initialization yields the correct lists. Assuming the correctness for all subtrees of height less than , by Lemmas 4.1 and 4.2, Algorithm 3 and Algorithm 4 guarantee that the lists for a subtree of height are correct.
In order to find a (, )-full-coloring of for a pair (, ), we need to save some extra data during the running of Algorithms 3 and 4. For each pair computed by Algorithm 3, performed on the subtree rooted at ℎ, we will record that ℎ is colored black (white, respectively) if this pair was computed in ℎ (ℎ, respectively). For each pair computed using Algorithm 4, performed on the subtree rooted at ℎ, we will record a link to the two pairs from which it was computed.
Algorithm 6 recovers the full-coloring itself, using backtracking and traversing the weighted line tree top-down, starting from the root. Each vertex ℎ will be colored with the color (black or white) chosen for it when computing the pair (, ) in ℎ.cList by Algorithm 3.
The second part of Algorithm 6 finds the BWC for . For each ∈ , it checks the colors of all hyperedges containing : if all are black, it colors black; if all are white, the algorithm colors it white; otherwise, it leaves uncolored.
The construction of the weighted line tree takes (2 · ), where = || is the number of hyperedges and is the maximum size of a hyperedge [12]. Since ≤ 2 and ≤ , this construction takes (3).
The initialization of the leaves in Algorithm 1 takes () = (). recoverFullColoring(, , (, )) Input: A hypergraph , its weighted line tree , and a target pair (, ) Output: A full BWC coloring of function backtrack(ℎ, (, )) if (, ) ∈ ℎ
color[ℎ] ← black else if (, ) ∈ ℎ
color[ℎ] ← white else (1, 1), (2, 2) ← for each child of ℎ
backtrack(, (, )) end function source pairs from fusion used to get (, )
// use the matching pair for each child ← root( ) backtrack(, (, )) // start from root and recover hyperedge colors in for each vertex ∈ () // find the BWC for if all hyperedges containing are black
color[] ← black else if all hyperedges containing are white
color[] ← white else color[] ← uncolored return color
Algorithm 6: Recover a full-coloring from stored dynamic programming tables
Algorithm 2 calls Algorithm 3 and Algorithm 4 for each of the vertices of , which is () since
≤ 2. In algorithm 3, the input lists , each have a maximum size (), since , ≤ ,
and the dominated pairs are removed. Each iteration processes a pair in (
Algorithm 4 iterates over pairs in 1 , 2 (or 1 , 2 ), which is (2), since each list has size (). The contract procedure here takes ( + ) time with = (2), so (2), and the total per call is (2).
Algorithm 2 makes () calls to Algorithm 3, totaling (2), and () calls to Algorithm 4 across all merges (since has − 1 = () edges), totaling (3). Combining construction ((3)) and initialization (()), the overall runtime is (3).
Note that this runtime is for finding the list of all non-dominated pairs.
In order to find a full-coloring (and after that the required BWC), we need to save data during computations as explained in Section 4.4. Algorithm 6, which performs that, works on each vertex of in a constant time. Recall that each vertex of the hypergraph is contained in at most two hyperedges, therefore, the second part of the algorithm is also linear. We find that the runtime of the algorithm is still (3).
Our algorithm can be applied in scenarios like network partitioning, where hyperedges represent groups of nodes that must be uniformly colored (e.g., assigning servers to compatible tasks). Future work could implement and test the algorithm on real-world datasets, such as chemical storage hypergraphs from compatibility databases or social network group structures, to evaluate its practical performance and scalability.
Future research may extend our results to more general hypergraph classes such as Berge-acyclic hypergraphs and other forms of hypertrees. Note that the weighted line graph of a Berge-acyclic hypergraph is not necessarily a tree, so diferent techniques will be required. In addition, further work may focus on improving the runtime of the algorithm (e.g., similarly to what was suggested in [2]) and exploring practical heuristics for larger instances.
During the preparation of this work, the author(s) used ChatGPT, Gemini, and overleaf in order to grammar and spelling check, paraphrase and reword. After using these tools, the author(s) reviewed and edited the content as needed and assume(s) full responsibility for the content of the publication.