Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
Authors: Alex Crane
Thomas Stanley
Blair D. Sullivan
Nate Veldt
Venue: ICML 2025 poster (2025)
Keywords: hypergraph clustering
edge-colored clustering
approximation algorithms
parameterized complexity
Primary area: optimization->discrete_and_combinatorial_optimization
TL;DR: We provide improved approximation algorithms and parameterized complexity results for clustering edge-colored hypergraphs

Abstract: We consider a framework for clustering edge-colored hypergraphs, where the goal is to cluster (equivalently, to *color*) objects based on the primary type of multiway interactions they participate in. One well-studied objective is to color nodes to minimize the number of *unsatisfied* hyperedges---those containing one or more nodes whose color does not match the hyperedge color. We motivate and present advances for several directions that extend beyond this minimization problem. We first provide new algorithms for maximizing *satisfied* edges, which is the same at optimality but is much more challenging to approximate, with all prior work restricted to graphs. We develop the first approximation algorithm for hypergraphs, and then refine it to improve the best-known approximation factor for graphs. We then introduce new objective functions that incorporate notions of balance and fairness, and provide new hardness results, approximations, and fixed-parameter tractability results.

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
Alex Crane' Thomas Stanley? Blair D. Sullivan
Nate Veldt
Abstract
We consider a framework for clustering edge- colored hypergraphs, where the goal is clus- ter (equivalently, color) objects based on the primary type of multiway interactions they par- ticipate in. One well-studied objective is to color nodes to minimize the number of unsatisfied hy- peredges those containing one or more nodes whose color does not match the hyperedge color. We motivate and present advances for several di- rections that extend beyond this minimization problem. We first provide new algorithms for maximizing satisfied edges, which is the same at optimality but is much more challenging to ap- proximate, with all prior work restricted to graphs. We develop the first approximation algorithm for hypergraphs, and then refine it improve the best- known approximation factor for graphs. We then introduce new objective functions that incorpo- rate notions of balance and fairesss, and provide new hardness results, approximations, and fixed- parameter tractability results.
The node coloring on the left satisfies 4 edges (2 blue, 2 red, 0 green). The coloring on the right only satisfies 3, but each color has a satisfied edge.
Figure I.
example, if nodes are researchers, edges are author lists for publications, and colors indicate publication field (computer science, biology, etc.), then ECC provides framework for inferring researchers' fields based on publications. ECC has also been used for temporal hypergraph clustering (Amburg et al., 2020), where edge colors encode time windows in which interactions occur. ECC then clusters nodes into time windows in which they are especially active. Variants of ECC have also been used for team formation (Amburg et al., 2022), in which case nodes are people, edges represent team tasks, and colors indicate task type. In this setting, ECC cor- responds to assigning tasks based on prior team experiences. Related work and research gaps. Edge-colored clustering has been well-studied in the machine learning and data min- ing literature from the perspective of approximation algo- rithms (Amburg et al., 2020; 2022; Veldt, 2023; Crane et al., 2024; Angel et al., 2016) and -ked-parameter tractability results (Kellerhals et al., 2023; Cai & Leung, 2018; Crane et al., 2024). It is also closely related to chromatic corre- lation clustering (Bonchi et al., 2012: 2015; Anava et al., 2015; Klodt al., 2021; Xiu et al., 2022), which is an edge-colored variant of correlation clustering (Bansal et al., 2004). Several variants of ECC have been encoded using different combinatorial objective functions for assigning colors to nodes. The earliest and arguably the most natural is MAXECC (Angel et al., 2016), which seeks to maxi- mize the number satisfied edges-edges in which all the nodes match the color of the edge. More recent attention has been paid MINECC (Amburg et al., 2020), where the goal is minimize the number of unsatisfied edges. The latter is the same as MAXECC at optimality but differs in terms of approximations and fixed-parameter tractabil- ity results. The approximability of MINECC is currently well-understood: recent ICML paper designed improved approximation guarantees that are tight with respect linear
1. Introduction
Edge-colored clustering (ECC) is optimization frame- work for clustering datasets characterized by categorical relationships among data points. The problem is formally encoded as an edge-colored hypergraph (Figure 1), where each edge represents an interaction between data objects (the nodes) and the color of the edge indicates the rype or cate- gory of that interaction. The goal assign colors to nodes in such way that edges of color tend include nodes of that color, by minimizing maximizing some objective function relating edge colors and node colors. ECC algo- rithms have been applied to various clustering tasks where cluster labels naturally match with interaction types. For
Kahlert School of Computing, University of Utah, Salt Lake City, USA 'Department of Computer Science and Engineering, Texas A&M University, College Station, USA. Correspondence to: Alex Crane <alex.cranc @ edu..
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
programming integrality gaps and nearly tight with respect to approximation hardness bounds (Veldt, 2023). However, existing approximations for MAXECC apply only to graph inputs, whereas nearly all algorithms for MINECC apply to hypergraphs. There is also a much larger gap between the previous best 0.3622-aprroximation algorithm (Ageev & Kononov, 2020) and the best existing upper bound, which only rules out approximation factors better than 0.972 as- suming P + NP (Alhamdan & Kononov, 2019).
2020). While the increase in approximation factor appears small at face value, this improves a long sequence of papers on MAXECC for the graph case (Angel et al., 2016; Ageev & Kononov, 2015; Alhamdan & Kononov, 2019;
Ageev & Kononov, 2020). Obtaining even a minor increase in the approximation factor is highly non-trivial and consti- tutes the most technical result of our paper.
Our contributions for balanced and fair ECC variants. Our first contribution towards balanced and fair variants of ECC is to introduce the generalized En- f--NORM MINECC objective, which uses a parameter to control balance in unsatisfied edges, and captures MINECC as a special case when p = 1. For p = DO, the objective corresponds to a new problem we call COL.OR-FAIT MINECC, where the goal is minimize the maximum number of edges of any color that are unsatisfied. We prove COLOR-FAIR MINECC is NP-hard even for k = 2 colors, even though standard MINECC is polynomial-time solvable for k = 2. We pro- vide a 2-approximation for N~NORMM MINECC for every p N 1 by rounding a convex relaxation, and give a 2 approximation for every p E (0, 1). We prove that this factor 2 for p 2 is tight in the sense that it matches an integrality gap for the p Do case. We then study COLOR- FAIR MINECC from the perspective of parameterized com- plexity, proving it is terms of the total number of unsatisfied edges, but is not FPT (under standard complexity assumptions) for many other parameters including feedback edge number, cutwidth, treewidth + maximum degree, and slim tree-cut width; this is in contrast to positive results for the standard ECC ob- jective (Kellerhals et al., 2023). We also consider a variant of COLOR- MINECC that maximizes the minimum number of satisfied edges of any one color, proving it is NP-hard to approximate to within any multiplicative factor.
Another limitation of prior work is that nearly all objec- tive functions for ECC (including MINECC and MAX- ECC) only consider the total number of edges that are (un)satisfiedd, even if it means certain colors are dispropor- tionately (un)satisfied. Figure 1 provides small example where the optimal MINECC solution satisfies four edges but only from two colors. Meanwhile, another color assign- ment satisfies only three edges but includes satisfied edge of each color. The latter choice is natural for applications where one may wish to incorporate some notion of balance or fairness in edge satisfaction. For example, if coloring nodes means assigning individuals to tasks for future team interactions, then we would like avoid situations where one type of task is assigned no workers. Balanced and fair objectives have been studied and applied for many other recent clustering frameworks, but have yet to be explored in the context of edge-colored clustering. As a key exam- ple, there have been many recent advances in algorithms for alternative objectives for correlation clustering, which is closely related to ECC. This includes results for minimizing the maximum number of edge "mistakes" incident any one node (Davies et al., 2023; Heidrich et al., 2024; Cao et al., 2025), as well as algorithms for generalized fy-norm objective (Pulco & Milenkovic, 2016; Kalhan et al., 2019:
tractable (FPT)) in
Jafarov et al., 2021; Charikar et al., 2017; Davies et al., 2024) that captures the latter mini-max objective when p = do and captures standard correlation clustering when p == 1.
We also consider scenarios in which the "importance" of the edge colors is unequal. In particular, we introduce PROTECTED- COLLOR MINECC, where we are given a spe- cial color C₁ which can be thought of as encoding a pro- tected interaction type. The goal is to color nodes to min- imize the number of unsatisfied edges subject to a strict upper bound on the number of unsatisfied edges of color C1 We give bicriteria approximation algorithms based on rounding a linear programming relaxation, meaning that our algorithm is allowed violate the upper bound for the protected color by bounded amount, in order to find solution that has a bounded number of unsatisfied edges relative to the optimal solution. Finally, although the con- tributions of our paper are primarily theoretical, we also implement our algorithms for COLOR- FAIR MINECC and
Motivated by the above, we present new contributions to ECC along two frontiers: improved MAXECC algorithms, and new frameworks for balanced and fair ECC variants.
Our contributions for MAXECC. We present the first ap- proximation algorithm for hypergraph MAXECC, which has an approximation factor of (2/e)* (r + 1)-1 where r the maximum hyperedge size. The approximation factor goes to zero as increases, but this is expected since prior hardness result rules out the possibility of constant-factor approximations that hold for arbitrarily large r (Veldt, 2023). Our result shows that non-trivial constant-factor approxima- tions can be obtained when r is a constant. We use insights from our hypergraph algorithm to obtain a new best approx- imation factor of 154/ /40 s 0.38 for the graph version of the problem, improving on the previous best 0.3622- approximation shown five years ago (Ageev & Kononov,
'A problem is FPT with respect to parameter & if it is solvable in f(k) (1)) time, where n is the instance size and f any computable function. See Appendix A for detailed introduction.
2

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
PROTECTED-COL.RR MINECC on a suite of benchmark ECC datasets. Our empirical results show that (1) our algo- rithms outperform their theoretical guarantees in practice, and (2) our balanced and fair objectives still achieve good re- sults with respect to the standard MINECC objective while better incorporating notions of balance and fairness.
do not rule out the possibility of approximating MAXECC when is constant. Indeed there many approximations for graph MAXECC (r 2) (Angel et al., 2016; Alhamdan & Kononov, 2019; Ageev & Kononov, 2015; 2020), but these require lengthy proofs, rely fundamentally on the as- sumption that the input is a graph, and do not easily extend even to the r = 3 case. Here we provide generalized approach that gives the first approximation guarantees for hypergraph MAXECC, when r is constant. Our approach also provides simplified way to approximate graph MAX- ECC, and we design refined algorithm that achieves a new best approximation factor for graph MAXECC, improving on the long line of previous algorithms for this case.
2. Improved MAXECC Algorithms
Preliminaries. For positive integer n, let [m] (1,2,...n) n]. We use bold lowercase letters to denote vec- tors, and indicate the ith of entry of a vector x E R" by z4- For a set S and a positive integer t, let (9) denote all subsets of S of size I. An instance of edge-colored clustering is given by hypergraph H = (V, E, f, {we]ee E) where V node set, E is set of hyperedges (usually just called edges), and L: E + [k] is mapping from edges to a color set [k] - (1, .k, }.. nonnegative weight associated with e, which equals 1 for all edges in the unweighted version of the problem. For a color c E [ki], let E. S E denote the edges of color c. We use r to denote the rank of H, i.e., the maximum hyperedge size.
2.1. Technical preliminaries for LP rounding algorithms
The LP relaxation for MAXECC can be obtained by relaxing the binary constraints in Binary Linear Program (1) to linear constraints 0 S 5 S 1 and 0 S ze S 1. Solving this LP gives a fractional node-color assignment xr E [0, 1]. The closer sy, is to 1, the stronger this indicates node v should be given color c. For the remainder of this section, assume { (ze, =;;= optimal set of LP variables for the relaxation. Our task is to round these variables to assign one color to each node in a way that satisfies provable approximation guarantees.
For E F., we let We 2 0 denote
E, v E V.c E [b]} specifically refers to an
The goal of ECC is to construct map A: V - [k] that associates each node with color, in order to optimize some function on edge satisfaction. Edge e E E is satisfied if f(e) = A(v) for each E e, and is otherwise unsatisfied. The two most common objectives are maximizing the to- tal weight of satisfied edges (MAXECC) or minimizing the total weight of unsatisfied edges (MINECC). Formally, MAXECC can be cast binary linear program (BIP))
Our algorithms (Algorithms and 2) are randomized. Both use the same random process to identify colors that node "wants". For each E [K] we independently generate uni- form random color threshold a. E [0, 1]. If of, > Oce, we say that node u wants color c, or equivalently that color e wants node u. Because a node may want more than one color, we use a random process to choose one color to assign, (1) informed by the colors the node wants. Our approximation proofs rely on (often subtle) arguments about events that are independent from each other. We begin by presenting sev- eral useful observations that will aid in proving our results.
max Eoer s.t. Vo V:
Σt at =1 o 2 ze VOEE Ve Mal,,VV,ee,
Vc [k], E Fe:: =n E 1)
Setting x to indicates that node u is given color e (i.e., zy to denote
A(u) = c). We use X, = [x]] x² the vector of variables for node u. For edge e E E, the con- straints are designed in such way that z = 1 if and only if is satisfied. A binary LP for MINECC can be obtained by changing the objective function to min Eoen
Our first observation is that if we can bound the expected cost of every edge in terms of the LP upper bound, it pro- vides an overall expected approximation guarantee.
Observation 1. Let A be a randomized ECC algorithm and P E [0.1] be a fixed constant. If for each e E E we have Ple is satisfied by A 2 pžc, then A is a p-approximation.
ze).
Challenges in approximating MAXECC. Although MINECC and MAXECC are equivalent at optimality, the latter is far more challenging to approximate. Due to an reduction from INDEPENDENT SET, is ha-hard to approximate MAXECC in hypergraphs of unbounded rank to within factor EE| 1-c (Veldt, 2023; Zuckerman, 2006). There also are simple instances (e.g., a triangle with 3 colors) where a simple 2-approximation of Amburg et al. (2020) for MINECC (round variables of an LP relaxation to 0 if they are strictly below 1/2, otherwise round to 1) fails to satisfy any edges. These challenges
Let X denote the event that u wants c, and Ze be the event that every node in edge e E E wants color c c= L(e.. Observation 2. For each node v E V, the events (Xe) (Xg)cet) [E[M] are independent, and [[X:]] = Plac < ag] = x. S 1.
upproximation-presse
Observation 3. P|Z.] = PP = min x = Ze.
For an edge e and color * E(e), we frequently wish to quantify the possibility that some node in e wants color i, as this opens up the possibility that e will be unsatisfied
3

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
Algorithm 1 Approximation alg. for hypergraph MAXECC
from each other and from c, the events (Au, X;: v E e) are mutually independent. Thus, using Observation 3 gives
Obtain optimal variables { for the LP relaxation T + uniform random ordering of colors [k]
For c E [b]. Oe < uniform random threshold in [0, 1]
II P[ Fe." ? #EC
TP
Ao
n
Ze
P[Z.]
for E V do
W {c [k] a < 20)
if [W] > 0 then
the joint event J = (Nuse-Ae) Ao, holds, this means every node in e wants color and at most r distinct other colors (one for each node in u E e since there is one set C. for each v E e) want one or more nodes in e. Conditioned on J, e is satisfied the color e has a higher priority (determined by TT) than the other r colors, which happens with probability 1/(r + 1). Thus,
A(e) < argmax T (c)
else
X(V) + arbitrary color
end if
end for
because some node v E e is given color Towards this goal, for each e E E and color i E [k] we identify one node in e that has the highest likelihood of wanting i. Formally, we identify some representative node v E satisfying z 2 x for every u e (breaking ties arbitrarily if multiple nodes satisfy this), and we define (i( e. The definition of ae(i) implies the following useful observation:
P[T. 2 P [J][]
Ze r r 6
(2)-
2
Comparison with prior graph MAXECC algorithms. AL- gorithm 1 achieves a 4/(3e") x 0.18 approximation factor for graph MAXECC (r = 2). This improves upon the first ever approximation factor of 1/e" x 0.135 for graph MAXECC (Angel et al., 2016), and comes with a signifi- cantly simplified proof. There are two interrelated factors driving this simplified and improved guarantee. The first is our use of Observation 4. Angel al. (2016) bound the probability of satisfying an edge v) E Ee using delicate argument about certain dependent events we can denote by B, (the event that v wants at most 1 color from = [k]] \ {c}) and B, (defined analogously for u). The algorithm of Angel et al. (2016) requires proving that P P.B, n B.] 2 IP P[B,|P[[BA even though B, and B, are dependent. The proof of this result (Proposition 1 in Angel et al. (2016)) is interesting but also lengthy. It fundamentally relies on the assumption that there are exactly two nodes in the edge, and involves several long algebraic expressions to describe probabilities for different events. In its current form the result does not apply when r >> 2. Attempting to generalize it even for r 3 leads to far more complicated algebraic expressions, and even then it is unclear if similar result can be shown. Subsequent approximation algorithms for graph MAXECC also rely on complicated variants of this proposition (Ageev & Kononov, 2015; 2020; Alhamdan & Kononov, 2019). In contrast, Theorem 2.1 deals with mutually independent events {A, : u E c). which allows us to immediately see that A,] >
Observation 4. Color i does not want any nodes in e color i does nol want v- de (i).
Variations of Observations 1-3 have often been used to prove guarantees for previous randomized ECC algorithms. How- ever, Observation 4 is new and is key to our analysis.
2.2. Hypergraph MaxECC Algorithm
In addition color thresholds {ae], our hypergraph MAX- ECC algorithm (Algorithm 1) generates uniform random permutation to define priorities for colors. A node is then assigned to the highest priority color it wants.
Theorem 2.1. Algorithm 1 is a (++ (2)) -apprxximation algorithm for MAXECC in hypergraphs with rank
Proof. Fix an arbitrary edge E and let {(e). Let T. denote the event that is satisfied. By Observation 1, it suffices to show P|Te]
2 r+1 (2)".
Let C = [k] \ (c). To partition the color set C, for each v E e we define C, = {i E C: (1) = v}. Recall that oe identifies node v E satisfying ot maxaee xng Let Ag denote the event that most one color in C, wants one or more nodes in From Observation 4, A, is equivalent to the event that wants at most 1 color in C., Thus, the probability of A, is the probability that at most one of the events {X i E C.) happens. Observation 2 gives DE_ = Σ at. 1, allowing us to repurpose supporting lemma of Angel et al. (2016) on graph MAXECC to see that [P[AA]= 2 2/e (Lemma B.I in Appendix B).
N IP[A,) for arbitrary sized hyperedges. Observation 4 provides the key insight as why it suffices to consider these events when bounding probabilities, leading to a far simpler analysis that extends easily to hypergraphs.
Our second key factor is the use of global color ordering म. Angel et al. (2016) and other results for graph MAXECC apply two-stage approach where Stage identifies which
Because color thresholds } are drawn independently for each color, and because color sets (C.: e E e) are disjoint
4

---

Theorem 2.2. For every e E E, Pfe is satisfied) 2 pže where p = 154 405 > 0.3802 when running Algorithm 2. Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
Algorithm 2 0. 0.38-approximation alg. for graph MAXECC
Algorithm 2 first checks if o wants any weak colors. If so, it assigns v the weak color of highest priority (using T) that wants. If wants no weak colors but has strong color, then v is assigned the strong color. Prioritizing weak colors in this way appears counterintuitive, since if v has a strong color it suggests that v should get color c. However, note that 5 2 2/3 still implies v will get color e with high probability, since large value for æ makes less likely u will want any weak colors. Meanwhile, prioritizing weak colors enables us to lower bound the probability that an edge = (u, v) is satisfied even if {(e) is weak for u or v. We prove the following result for an arbitrary edge e, which by Observation 1 proves our approximation guarantee.
Obtain optimal variables } for the LP relaxation T + uniform random ordering of colors [k]
For c E [b]. Oz < uniform random threshold in [0
for E V do
S, < {c [
2 2 2/3); W.
[K]] \ S.
W = {o W. ag x
if [WW) > 0 then
X(v) t argmax,ewa -()
else if 3c s.t. S, = {c} then
X(e) c
else
X(u) + arbitrary color
end if
end for
Proof sketch. Fix E = (u, v). let c = {(e). and set C = [K]] Me]. Define C. {i E C: x 2x1. and C. = -C.C As before, T. is the event that e is satisfied and X is the event that wants color i. Let Y be the event that is assigned color i by Algorithm 2, and N. be the event that v wants no colors in C. If is strong for v, event N, is equivalent to event Y Let W.; denote colors in W, that want v. Define X Yú, W and N₂ analogously for u. The proof is separated into (increasingly difficult) cases, based on how many of {u, f} have e as a strong color.
nodes "want" which colors, and Stage 2 assigns nodes to col- ors independently for each node. To illustrate the difference, consider the probability of satisfying an edge (u, v) E Eee if we condition on and both wanting e and each want- ing at most one other color. The algorithm of Angel et al. (2016) has a 1 1/4 chance of satisfying the edge (each node gets color c with probability 1/2), whereas Algorithm has a 1/3 chance (the probability that e is given higher global priority than the other two colors). This is precisely why Algorithm I 's approximation guarantee is a factor 4/3 larger than the guarantee of Angel et al. (2016).
Case 1: S. S, {c). Setting W = W., UWW we have
P
Pi & W'] = II
Pli 4 W
II
Pli $ will
=
2.3. Graph MaxECC Algorithm
IEC
iEC,
iEC
Although Algorithm 1 does not improve on the 0.3622- approximation of Ageev & Kononov (2020) for graph MAX- ECC, we can incorporate its distinguishing features (the color ordering т and Observation 4) into a refined algorithm with a 154/405 Ri 0.38 approximation factor. In order to improve on this extensively studied special case of the prob- lem, our analysis is much more involved than the proof of Theorem 2.1 and requires proving several detailed techni- cal lemmas that may be of interest in their own right. We provide an overview here and a full proof in Appendix B.
=
II (1 iEC.
x
II IEC.
(1
x
2
2
2
4
Ze.
3
3
9
The first equality holds because e is satisfied + W W = 0. The second follows from the definition of C. and C, and Observation 4. The second to last step can be shown using the constraint Σ 2y = 1 and the fact that de 2 2/3 for w E {u, ub (see Lemma B.3 Appendix B).
Case 2: S. =c),, c E W... Sttisffin e equivalent to event Y n Y,, and S, {c} implies Y; is equivalent to No. Note that Y Y n Xg- In Appendix B we combine this with Bayes" Theorem, the independence of X and Ne. and the fact that P[X
Our refined algorithm (Algorithm 2) for graphs solves the LP relaxation, generates color thresholds {aş: i E [k]], and generates a color ordering и the same way as Algorithm differs in that it partitions colors for each v into colors that are strong or weak for v, given respectively by the sets
r 2 Ze, to get
P = P n nx N.
2 P P
N. N N.XXPNNN Ze-
Similar to Case 1, we use Lemma B.3 to prove that
S. fi E [k]] a. 2 2/3} and W,, = [k] - S..-
P [NJ] II [ = II (1 x 2 3
Since Ein att = 1, we know |.o| E 13. We say color
IEC
I
i is strong for v if S. = {i). otherwise i is weak for v. Note that a color being strong or weak for u is based on a
The most difficult steps for Case 2 are the two inequalities
fixed and non non-random LP variable. This is separate from the notion of color wanting v which is a random event.
PP P|Y N. N. M PL
X 2 31/54,
5

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
where the first inequality relies on Lemma B.2 and the sec- ond on Lemma B.5, both of which require detailed proofs. Putting all these pieces together yields
entries in a per-color error vector E Z which tracks the number of unsatisfied edges of each color. Otherwise, the variables and constraints are similar to BLP (1), adapted for the minimization objective. When p 1. we recover the standard MINECC problem, i.e., the f--norm on m. We now show how to approximate the generalized 2--NORM MINECC problem. For p 2 1, if we relax the binary constraints linear constraints S d; S and 0 S % S 1, we obtain a convex programming relaxation. We can then apply convex optimization techniques to find the optimal solution to this relaxation and round the resulting fractional coloring. The rounding scheme is similar to that used for MINECC (Amburg et al., 2020). In particular, given a fractional coloring consisting of optimal variables (de), we assign color to vertex if and only if de < }.. We show that the resulting coloring is well-defined and 2- approximation the generalized objective. When 0 p we lose convexity, but we can recover approximations via reduction to SUBMODULAR VERTEX COVER.
31 2 31
IP [T.] 2 L
X [N. de
3 = 81 Ze-
54
Case 3: C E W n We. First condition on Ze = X n.x
P [[T.] = P [T. Z.] P(Z.] = [T.: Ze] Ze.
Define D W.W.W. W \ {c) to be the weak colors in that want at least one of {u, v). The proof ultimately bounds P [Te Zel, by conditioning on how many colors in D want one or both of {u, v). We partition D into D. = (i E D: x 2 x and D. = D - Du. and using the same logic as Observation 4, note that i E Du (respectively, i E D.) wants one or more nodes in {u, 3 if and only if i wants u (respectively, wants v). Let D' be the colors in Da that want and define D analogously for v. Since [Da] and [D&] are independent, we have
Theorem 3.1. l tN-NORM MINECC is approximable within factor 2 when p 2 and factor 22 when 0 p 1.
|D I P
PID
= PPID) = A 1+i+j
PfTel [z]
= Σ
As p increases, the e--nrrm on m converges to the maximum component value in m. Thus, for p - Do we recover a mini- max variant of ECC, for which the objective is to minimize the maximum number of unsatisfied edges of any color. This variant will be the focus of Section 3.2, but first pause to note that this convergence of the & objective implies that we cannot hope to obtain a better-than 2-approximation by rounding fractional solutions to Program (3).
i=0
1=0
where the fraction 1/(1 + () j) is the probability that- conditioned on i + colors in D wanting some nodes in {u, the color e will have higher priority than these i j other colors and hence e will be satisfied. Using multiple applications of Lemma B.5 to bound sums of probabilities on the right hand side of Eq. (2), we show that P[Te| Ze) > 154/405, which concludes the proof.
Theorem 3.2. As p + 30, the integrality gap of Program (3) converges to 2.
3. A Alternative ECC Objectives
3.2. Color-fair ECC variants
We now turn our attention to more general ECC objectives, as well as several which incorporate notions of balance or fairness with respect to edge colors. Given space constraints, we defer proofs to Appendices C, D, and E.
Now we focus on the mini-max case of fn-NORM MINECC given by p -> co, which refer COLOR-FAIR MINECC. In the following, M indicates the number of edges of color which are unsatisfied by a coloring X.
3.1. Generalized Norm Objective
COLOR-FAIR MINECC
Input:
A k-edge-colored hypergraph H
We begin by introducing N--NORM MINECC, which we define via the following convex program:
(V, E,E) E) and an integer 7.
Problem: Does there exist vertex coloring À of
H with ma M < <??
min
s.t.
VEEV:
Dn 15 2
Vc [k), E E : d S Te EeEe
(3)
The optimization problem asks for a coloring which min- imizes maXce[K] M.A Also of interest is the corresponding maxi-min variant COLOR- FOLOR-FAIR MAXECC, for which the question is whether there exists a coloring which satisfies at least 7 edges of every color. These problems are not equiva- lent at optimality in general, though they are when restricted to hypergraphs with an equal number of edges of every color. We begin by establishing hardness for both problems.
Vc E [k]:
mc = EeE E, Ya
dy E 10 Ac [k], V, F.
Recalling the notation of BLP (1), we think of di = 1-160 x
as encoding the "distance" of node e to color c, and % = 1- Ze as encoding whether hyperedge e is unsatisfied (7e 1)
or not (?e = 0). The variables m. can be thought of as the
6

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
Theorem 3.3. COLOR-FAIR MINECC is NP-hard even when restricted to subcubic trees with cutwidth 2, exactly 3 edges of each color, and = 2. COLOR-FAIR MAXECC is NP-hard even when restricted to paths with T = 1.
2-approximation for SPARSE VERTEX COVER would refute the unique games conjecture (Blum al., 2022).
It is also compelling to develop purely combinatorial ap- proaches, i.c., algorithms which do not rely upon convex optimization. As a first step, in Appendix D we show how to analyze an existing linear-time and purely combinato- rial ECC algorithm of Veldt (2023), proving that it yields a k-approximation the COLOR-FAIE MINECC objective.
Theorem 3.3 implies that it is NP-hard to provide any multi- plicative approximation for COI.OR-FAIR MAXECC, since it is NP-hard even to decide whether the optimum objective value is non-zero. Our reduction also rules out efficient algorithms in graphs of bounded feedback edge number, cutwidth, treewidth + max. degree, or slim tree-cut width. This highlights interesting differences between COLOR- FAIR MINECC and the standard ECC problem, which was shown be FPT in terms of all four of these struc- tural parameters (Kellerhals et al., 2023). On the positive side, we can give FPT algorithm parameterized by the total number& t of unsatisfied edges. We remark (omitting the details) that the dependence on t in the following theo- rem tight under the exponential time hypothesis (ETH). To see this, we observe that the reduction of Theorem 3.3 creates linearly many vertices and edges with respect to the BOOLEAN SATISHABILITY instance from which we reduce. In combination with similar observation regarding the reduction of Tovey (1984), we conclude that under the (nor 20(m)time) algorithm exists
3.3. Protected-color ECC
COLOR-FAIR MINECC encodes faireess by ensuring that single color is heavily "punished" (as measured by unsat- isfied hyperedges), but what if we only concerned about single color that represents a protected interaction type? It is always trivially possible to ensure that every edge of a given color e1 is satisfied by setting X(u) = e for every vertex v. This strategy, however, completely disregards all other edges. We might reasonably assume that while we are constrained by concern for a given protected color, we still wish find high-quality solution measured by the traditional clustering objective. This tension is captured in the following problem definition.
ETH no (0IIV+))))))) for COLOR-FAIEE MINECC.
PROTECTED-COLOR MINECC
Theorem 3.4. COLOR-FAIR MINECC is solvable in ((2r||El)-time
Input:
An edge-colored hypergraph H (V, E, E), two integers t, b, and a pro- tected color et.
Though Theorems 3.3 and 3.4 close the most natural param- eterized complexity questions, remains open to determine whether COLOR-FAII MINECC is hard when the number k of colors is bounded. The standard ECC objective is in P when & < 2 and NP-hard whenever k 2 3 (Amburg et al., 2020). We resolve this question via an intermediate hardness result for a VERTEX COVER variant which may be of independent interest. Specifically, Appendix we prove that given a bipartite graph G (A t B, E¹) and an integer a, it is vertex cover C' of G with max n A1, |C n BI} a. This result facilitates the resolution of our question:
Problem: Is it possible to color such that most edges are unsatisfied, of which at most b have color c₁?
When = b we recover the standard ECC problem, so POSTECTED-COLOC MINECC is NP-hard. However, by rounding fractional solutions to the following linear program we recover bicriteria (a, apprroxixiissssnnns If opt, is the minimum possible number of unsatisfied edges subject to the constraint 6, then these algorithms guarantee at most a- opt, unsatisfied edges, of which at most 3-b have color C
to determine whether there exists
Theorem 3.5. COLOR-FAIR MINECC and COLOR-FAIR MAXECC are ND-hard even in 2-regular hypergraphs with k- ==2. 2.
min Eccr %o
s.t.
V V
E 1 1
We conclude this section by pointing the interested reader toward a few additional results. In Appendix D, we prove that an alternative to the 2-approximation implied by Theo- rem 3.1 can be obtained by reducing VERTEX COVER variant called SPARSE VERTEX COVER and applying re- sult of Blum et al. (2022). A natural question is whether COLOR- MINECC is approximable below factor 2. Any such algorithm is likely to require new techniques. Theorem 3.2 implies that the first of our two strategies can- not be improved, while any improvement in the existing
We E [k], Ec:
5% Vu
(4)
EesE, Ve S
d. E [0,1]
Vee (L)
All variables have the same meaning as in Program (3), but we have added the third constraint which encodes that at most b edges of our protected color Cj may be unsatisfied. Apart from this constraint, LP (4) is identical to the canon- ical MINECC LP used to obtain ofate-of-the-an the-r-r approxima-
7

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
Table 1. We report hypergraph statistics, and compare the standard (ST) MINECC, algorithm against the COLOR-FAAI MINECC (CF)
algorithm. Runtimes are given in seconds taken to solve the IP.. Objective numbers are an upper bound on the approximation ratio, given by the objective value for the algorithm divided by the lower bound for the objective determined by the LP relaxation.
Runtime (s)
ECC Obj
CFECC Obj
Dataset
[
r
ST
CF
ST
CF
ST
CF
Brain
638
21180
2
2
0.50
1.57
1.00
1.02
1.26
1.00
Cooking
67 14
39774
65
20
46.76
52.88
1.00
1.00
1.66
1.66
DAWN
2109
87104
22
10
4.49
11.60
1.00
1.00
1.39
1.38
MAG-10
80198
51889
25
10
8.40
15.52
1.00
1.20
1.48
1.03
Clingo-Cliccout
207974
247362
85
55
116.94
129.55
1.00
1.37
1.68
1.01
Walmart-Trips
88837
65898
25
44
156.71
314.03
1.00
1.05
2.48
1.56
tions (Amburg et al., 2020; Veldt, 2023), and our algorithm can be seen as an appropriate adaption of those rounding schemes. In the following, / E (0, 21 is a parameter which allows us to tune the approximation guarantees and B.
brain regions, edges of one color indicate regions with high fMRI correlation, and edges of the other color indicate re- gions with similar activation patterns. Cooking is derived from the What's Cooking dataset (Kaggle, 2015a) nodes are food ingredients, hyperedges are ingredients encoding a recipe, and colors indicate cuisine (e.g., Indian or Ko- rean). In DAWN, nodes are drugs from the Drug Abuse Warning Network (Substance Abuse and Mental Health Ser- vices Administration.), and hyperedges are groups of drugs ingested by individual prior to trip to the emergency room. Colors indicate patient outcome (e.g.. "sent home" or "surgery"). MAG-10 is derived from publication data from the Microsoft Academic Graph (Sinha et al., 2015); nodes are academic authors, hyperedges indicate authors on publication, and hyperedge colors indicate the publication venue. Walmart-Trie Cellmart-Trips is derived from the Kaggle trip type classification data (Kaggle, 201 5b); nodes are products sold at Walmart, and hyperedges represents sets of products pur- chased in the same shopping trip. Colors are shopping trip types. Trivago-Clickoul is derived from the 2019 ACM Rec- Sys Challenge data (Knees et al., 2019); nodes are vacation rentals on Trivago, hyperedges are sets of rentals that a user "clicks out" on during the same browsing session. Colors encode the country location where the browsing session oc- curred (e.g.. Spain if the browsing happened on Trivago.es). Table provides statistics for each hypergraph.
Theorem 3.6. For every P E () there exists polynomial-time (1) r-p)) approxxiatan for PROTECTED- COLOR MINECC.
We also give a FPT algorithm.
Theorem 3.7. PROTECTED-COLOR MINECC is FPT with respect to the total number of unsatisfied edges.
Given these positive results, a natural question is whether we may efficiently solve the MINECC objective with multiple protected colors. We conclude by showing that as soon as we allow more than one protected color, it becomes hard even determine whether any solution exists.
Theorem 3.8. Given a 2-regular H = (V, E), two inte- gers b1, by, and two colors C1, it is NP- determine whether it is possible to color V such that at most by edges of color ei and at most b2 edges of color 22 are unsatisfied.
4. Experiments
While primarily focus theoretical results, we also implemented and evaluated the performance of our al- ternate objective ECC algorithms on a standard suite of benchmark hypergraphs. LP-based methods for standard ECC are known to perform far better in practice than their theoretical guarantees, often yielding optimal solu- tions (Amburg et al., 2020). Thus, our MAXECC algo- rithms should be viewed theoretical results that help bridge the theory-practice gap and are thus not the focus of our experiments. Code for our experiments can be found at https: / / thub.
Implementation. We refer to our LP algorithms for COLOR- FAIR MINECC and PROTECTED-COLOD MINECC as CF and PC respectively, and refer the standard MINECC LP rounding algorithm as ST. These were implemented in the Julia programming language and run research server running Ubuntu 20.04.1 1 with two AMD EPYC 7543 32- Core Processors and 1 TB of RAM. Our implementation of these algorithms chooses a color that has the lowest LP distance variable among all colors for each node. This ap- proach can only improve our approximation guarantees over the theoretical approach that only assigns color if there an LP variable that is less than 1/2. Our implementation for PC then performs at least well as the algorithm from
1 01 9/AltECC.
Datasets. We consider edge-colored hypergraphs from Am- burg et al. (2020) and Veldt (2023). Brain is derived from brain MRI data (Crossley et al., 2013); nodes represent
8

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
100
PCECC Approx Bound
2.00
PC Unsabstied %
1.2
ECC Apprax Bound
1.75
50-
1.50
0.9
25
1.25
0.8-
01
0.7
1.00
0
25
50
75
100
25
50
75
100
0
25
50
75
100
Protected Class Constraint
Protected Class Limit %
Protected Class Limit %
(a) Constraint Violation
(b) PROTECTED-COLOR approximation
(c) MINECC approximation
Brain Cooking
DAWN
MAG-10 X Privago-Clickoul
Walmart-Trips
Figure 2. Results for PC while varying the size of the constraint b, given a percent of the total number of protected edges. The protected color is always chosen to the color with the median number of edges among all colors in the hypergraph. Figure (a) shows the percent of protected edges left unsatisfied by PC, versus the maximum percent of edges that the constraint allows to be unsatisfied. Line y represents the constraint imposed by the problem definition, and y = 2x the theoretical limit for our bicriteria approximation. Figures (b) and (c) are upper bounds on the approximation ratio achieved by PC for the protected color objective and for MINECC respectively.
Theorem 3.6 with p 1/2, it is a (2, -aapproximation. We used Gurobi optimization software with default settings to solve LPs. The bottleneck for all algorithms is solving the LP, which takes between few seconds and a few min- utes depending on the dataset. The time to round the LP is negligible (under 0.3 seconds in the worst case).
of the total number of protected edges, achieving a 1.3- approximation better in this case (Figure 2(b)). Once b is above this 50% threshold, PC satisfies no protected edges on DAWN and Cooking. This still matches our theory: in order to guarantee (based on our theory) we do not leave all protected edges unsatisfied, b must be less than 50% of these edges. PC also does a good job of approximating the stan- dard MINECC objective (factor better, see Figure 2(c)), while incorporating this protected color constraint.
COLOR-FAIR MINECC. Table compares CF against ST. We first observe that in practice, CF achieves approximation factors that are much better than the theoretical bound of 2, and in several cases are very close to 1. Furthermore, CF even does well approximating the standard MINECC objective even though it is not directly designed for it. In the worst case, achieves a 1.37-aprrxximation, which is only 37% worse than ST, which finds an optimal solution for MINECC. By comparison, ST is up to 66% worse than CF for the color-fair objective. In fact, average among the datasets we tested, CF is only 10.66% worse than ST on the standard MINECC objective, while ST is 32.62% worse than CF on the color-fair objective. In other words, the cost of incorporating fairness into the ECC frame- work is not too high-CF maintains good performance in terms of the MINECC objective while showing significant improvements for the color-fair objective.
We note that the rightmost point in Figure 2(a) corresponds to standard MINECC as there is no bound on unsatisfied protected edges. From this, we can examine how badly ST violates protected color constraints for small b values. On MAG-10 when is 10% of the number of protected edges, ST violates the constraint by a factor of 3.60 whereas PC only violates the constraint by factor of 1.01. This gap is even more pronounced for the DAWN dataset at 10%. where ST violates the constraint by a factor of 10.3 while PC satisfies the constraint. Thus, for situations where there is a need to protect certain edge types, standard MINECC algorithms do not provide meaningful solutions.
5. Conclusions
PROTECTED-COLae MINECC. Figure 2(a) shows the constraint satisfaction for PC as b (the number of unsatisfied protected edges) varies. Again we see that our algorithm tends to far exceed theoretical guarantees. In most cases, the number of protected edges left unsatisfied by PC below the constraint b, even though the algorithm can in theory vio- late this constraint by up a factor 2. Results are especially good for Brain, MAG-IO, 10, Walmart, and Trivago- -Cinkk,, where the constraint tends to be satisfied and the objective value for CF is within a factor 1.007 of the LP lower bound (Figure 2(b)). PC also tends to satisfy the protected color constraint for DAWN and Cooking when is below 50%
We have established the first approximation algorithm for hypergraph MAXECC and improved the best known ap- proximation factor for graph MAXECC. We also introduced two ECC variants that incorporate fairness, designing new approximation algorithms which in practice far exceed their theoretical guarantees. One open direction is to try to fur- ther improve the best approximation ratio for MAXECC. This may require deviating significantly from previous LP rounding techniques, since it is currently very challenging to improve the approximation by even a small amount using this approach. Another open direction is to improve on the 2// app-appprxiiaaioon for l. NNRM MINECC when p <

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
Acknowledgements
Bansal, N., Blum, A., and Chawla, S. Correlation elustering.
Machine Learning, 56:89-1133 113, 2004.
This work was supported in part by the Gordon & Betty Moore Foundation under award GBMF4560 to Blair D. Sullivan, by the National Science Foundation under award IIS-1956286 Blair D. Sullivan, and by the Army Research Office under award W911NF-24-1-0156 to Nate Veldt.
Blum, J., Disser, Y., Feldmann, A. E., Gupta, S., and Zych- Pawlewicz, A. On sparse hitting sets: From fair vertex cover to highway dimension. In 17th International Sym- posium on Parameterized and Exact Computation, 2022.
Impact Statement
Bonchi, F., Gionis, A., Gullo, F., and Ukkonen, A. Chro- matic correlation clustering. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1321-1329, 2012.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which feel must be specifically highlighted here.
Bonchi, F., Gionis, A., Gullo, F,, Tsourakakis, C. E., and Ukkonen, A. Chromatic correlation clustering. ACM Transactions on Knowledge Discovery from Data (TKDD), 944):1224, 2015.
References
Ageev. A. and Kononov, A. Improved approximations for the max k-colored clustering problem. In Approximation and Online Algorithms: 12th International Workshop, WAOA 2014, Wroclaw, Poland, September I 1112, 2014, Revised Selected Papers, pp. 1-10. Springer, 2015.
Cai, L. and Leung, O. Y. Alternating path and coloured clustering. arXiv preprint 1xXi::807.11031. 2018.
Cao, N., Roche, S., and Su, H.-H. Min-max correlation clustering via neighborhood similarity. arXiv preprint urXiv:2502.12573 2025.
Ageev, A. and Kononov, A. A 0. 0.3622-appe appo-aaproi algo- rithm for the maximum k-edge-colored colored clustering prob- lem. In Mathematical Optimization Theory and Opera- fions Research: 19th International Conference, MOTOR 2020, Novosibirsk, Russia, July 6-10, 2020, Revised Se- lected Papers, pp. 3-15. Springer, 2020.
Charikar, M., Gupta, N., and Schwartz, Local guarantees in graph cuts and clustering. In International Conference on Integer Programming and Combinatorial Optimiza- tion, pp. 136-147. Springer, 2017.
Alhamdan, Y. M. and Kononov, A. Approximability and inapproximability for maximum k-edge-colored cluster- ing problem. Computer Science-Theory and Applica- tions: 14th International Computer Science Symposium in Russia, CSR 2019, Novosibirsk, Russia, July 1-5, 2019, Proceedings 14, pp. 1-12. Springer, 2019.
Crane, A., Lavallee, B., Sullivan, B. D., and Veldt, N. Overlapping and robust edge-colored clustering in hy- pergraphs. In Proceedings of the 2024 conference on Web Search and Data Mining, WSDM '24, 2024.
Crossley, N. A., Mechelli, A., Vértes, P. E., Winton-Brown, T. T., Patel, A. X., Ginestet, C. E., McGuire, P., and Bullmore, E. T. Cognitive relevance the community structure of the human brain functional coactivation net- work. Proceedings of the National Academy of Sciences, 110(28): 11588, 2013.
Amburg, L, Veldt, N., and Benson, A. Clustering in graphs and hypergraphs with categorical edge labels. In Proceed- ings of The Web Conference 2020, pp. 706-717. Associa- tion for Computing Machinery, 2020.
Amburg, I., Veldt, N., and Benson, A. R. Diverse and ex- perienced group discovery via hypergraph clustering. In Proceedings of the 2022 SIAM International Conference on Data Mining (SDM), pp. 145-153. SIAM, 2022.
Cygan, M., Fomin, F. V., Kowalik, E., Lokshtanov, D., Marx, D., Pilipezuk, M., Pilipezuk, M., and Saurabh, S. Param- eterized algorithms, volume 5. Springer, 2015.
Davies, S., Moseley, B., and Newman, H. Fast combi- natorial algorithms for min max correlation clustering. In International Conference on Machine Learning, pp. 7205-7230. PMLR, 2023.
Anava, Y., Aligdor- N., and Gamzu, I. Improved theoretical and practical guarantees for chromatic correla- tion clustering. In Proceedings of the 24th International Conference on World Wide Web, pp. 55-65, 2015.
Davies, S., Moseley, B., and Newman, H. Simultaneously approximating all f, no-norms in correlation clustering. In 5 International Colloquium on Automata, Languages, and Programming, pp. 52-1. Schloss Dagstuhl-Leibnizz Leibniz- Zentrum für Informatik, 2024.
Angel, E., Bampis, E., Kononov, A., Paparas, D., Poun- tourakis, E., and Zissimopoulos, V. Clustering on k- edge-colored graphs. Discrete Applied Mathematics 211: 15-22, 2016.
10

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
Heidrich, H. S., Irmai, J., and Andres, B. A 4-approximation algorithm for min max correlation clustering. In Interna- tional Conference Artificial Intelligence and Statistics, pp. 1945-1955 PMLR, 2024.
Substance Abuse and Mental Health Services Admin-
istration. Drug abuse warning network (DAWN). drug-abuss waungaaguewwaringgggu network, netrrng 2011.
Jafarov, J., Kalhan, S., Makarychev, K., and Makarychev, Y. Local correlation clustering with asymmetric classifi- cation errors. In International Conference on Machine Learning, pp. 4677-4686. PMLR, 2021.
Tovey, C. A. A simplified up-complete satisfiability problem.
Discrete applied mathematics, 8(1):85-89, 1984.
Veldt, N. Optimal Ip rounding and linear-time approxima- tion algorithms for clustering edge-colored hypergraphs. International Conference on Machine Learning, pp.
Kaggle. What's cooking? https//www.kagglee.om//wkk cooking, 2015a
34924-34951. PMLR, 2023.
Kaggle. Walmart recruiting: trip type classifica- tion. use market basket analysis to classify shopping
Xiu, Q., Han, K., Tang, J., Cui, S., and Huang. H. Chromatic correlation clustering, revisited. Advances Neural In- formation Processing Systems, 35:26 147-26159, 2022.
trips. https//wwww.kagll.comm hataggll.ooo/cvaaaarrrrttnngggn type-clasiffcation, 2015b.
Zuckerman, D. Linear degree extractors and the inapprox- imability of max clique and chromatic number. In Pro- ceedings of the thirty-eighth annual ACM symposium on Theory of computing, pp. 681-690, 2006.
Kalhan, S., Makarychev, K., and Zhou, T. Correlation clustering with local objectives. Advances in Neural Information Processing Systems, 32, 2019.
Kellerhals, L., Koana, T., Kunz, P., and Niedermeier, R. Parameterized algorithms for colored clustering. Pro- ceedings of the AAAI Conference on Artificial Intelligence (in press), AAAI 2023, 2023.
Klodt, N., Seifert, L.,, Zahn, A., Casel, K., Issac, D., and Friedrich, T. A color-blind 3-approximation for chromatic correlation clustering and improved heuristics. In Pro- ceedings of the 27th ACM SIGKDD Conference on Knowl- edge Discovery Data Mining, pp. 882-891, 2021.
Knees, P. Deldjoo, Y., Moghaddam, F. B., Adamezak, J., Leyson, G.-P., and Monreal, P. Recsys challenge 2019: Session-based hotel recommendations. In Proceedings of the 13th ACM conference on recommender systems,,,ss,stemm,, pp.
570-571, 2019.
Kuo, S.-Y. and Fuchs, W. K. Efficient spare allocation for reconfigurable arrays. IEEE Design & Test of Computers, 4(1):24-31, 1987.
Lovász, L. Submodular functions and convexity. Mathemat- ical Programming The State of the Art: Bonn I 1982, pp. 235-257, 1983.
Pulco, G. and Milenkovic, O. Correlation clustering and biclustering with locally bounded errors. In International Conference on Machine Learning, pp. 869-877, PMLR, 2016.
Sinha, A., Shen, Z., Song, Y., Ma, H., Eide, D., Hsu, B.- J., and Wang, K. An overview of microsoft academic service (mas) and applications.
Proceedings of the 24th international conference on world wide web, pp. 243-246, 2015.

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
A. Parameterized Complexity
For a complete introduction to parameterized complexity, we refer the reader to the standard text (Cygan et al., 2015). A parameterized problem is a language _ Σ", where Σ is a fixed, finite alphabet. An instance is a tuple (I, E Σ- x N. where & is the parameter. A parameterized problem is called fixed-parameter tractable (FPT) if there exists an algorithm A, computable function f: N + N and constant e such that for every instance (I, A decides whether (I, E L in time bounded by [(k) [(T, A.)1s This means the algorithm A has polynomial dependence on the instance size, while the exponential (or worse) part of the running time is dependent only on the parameter k.
The standard ECC problem is FPT with respect to both natural parameters, i.e,, the number of unsatisfied edges and the number of satisfied edges (Cai & Leung, 2018), as well as several structural parameters, notably the slim tree-cut width, feedback edge number, cutwidth, and treewidth plus maximum degree (Kellerhals et al., 2023). Meanwhile, it is (under standard complexity assumptions) not FPT with respect to vertex-cover number or treewidth (Kellerhals al., 2023).
B. MAXECC Proofs
We use the following lemma as a small step in our approximation guarantee for hypergraph MAXECC (Theorem 2.1). The result was originally used in designing a a/ee-approximation algorithm for graph MAXECC (Angel et al., 2016). A full proof can be found in the work of (Angel al., 2016).
Lemma B.1 (Lemma 4 of Angel et al. (2016)). Let (X,, X}} be set of independent events satisfying Σx P[X.) S 1, then the probability that at most one of them happens is greater than or equal to 2/e.
The remainder of our supporting lemmas are new results that we prove for our approximation algorithm for graph MAXECC. Lemma B.2. Given an edge e = (u, v) of color e with c E Wa. when running Algorithm 2 we have
PP P N2 n x 2 [ [
Proof. For a node u and color we use X to denote the event that u does not want c.
We first observe that it is sufficient show positive correlation between Ye and N,.. To see this, we use Bayes' Theorem and the independence of X and N2 to write
P PY n N n
PIN, n X
P.Y
PIN. n X P.
P Nx =
PNN. n X
P PN.
X
P
P
as well
PIX
P Y. PYY)
1.P P[X
P X
P[X]]
P
By rearranging terms, we see that our claim is equivalent to
[N n X Y =P TP
Y. 2 (N.).
We complete the proof by demonstrating the equivalent inequality P[Y No] Z P PY.] Impose an arbitrary order C1, C2 ..... Cj on the color set, and without loss of generality assume that E(e) = c = Ck. In what follows, we always write c for c& and whenever considering a subscripted color e; we assume that i E W., \ (c).
If node u has strong color, then without loss of generality we assume that the strong color is ca-1- The remainder of the proof is written for the case where S, = 0. in which case the set of weak colors (other than c) that might want node is W., \ {c} = {c1, C....., C.-1). In other words, W., is the set of colors with indices in [k 1]. If instead we had Su = [ and W. {c] = (ci, C2 Ck -2 the proof works in exactly the same way if we instead considered the set of colors associated with indices in [K- 2) instead of indices in [1-1].
Now, consider all possible subsets of [K- 1] which may define (according to our ordering) those weak colors (besides e) which are wanted by For a particular subset S C [k 11], we write X for the event that wants exactly (not considering <) the colors in S. In the following, we write w(S)) +I and call this quantity the weight of S. The events X partition the sample space, so may write
PP PY =
Σ P SCR-11
x IP [ = P[X
Σ SC
w(S) PP [X
12

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
In the above, the second equality follows from the observation that, conditioned on X for any S S [k - 1]. the event Y occurs if and only if (a) u wants and (b) preceeds each color in S in the global ordering of colors. The conditions (a) and (b) are independent, and occur with probabilities IP [X[]] and wSS), respectively, We will now make use of the independence of the X events to write P [X,]] as the product of k 1 probabilities.
[I x )
[ = P
w(S)
II [[
(5)
SC 11
VES
JES
We want to write a similar expression for P [ We begin by using similar reasoning as above to write
P P N,)
Σ P
x
N.
IP
[ No.
SC
= P|
Nol
Σ w(S) P X No]
SC[K-1]
w(S) P - No]. =[
SCIK-1]
Next, we observe that the X events remain independent even when conditioned N.- This allows write )]
P N. = P
Σ
w(S)
[I I
[I jES
X N..
SC
WES
To simplify this expression further, we claim that for every E [K 1], [
N.] P X X
This can be derived
from the observation that Ni X is independent of X when conditioned on X as well as being unconditionally independent X We then manipulate the definition of conditional probability to see that
P X
jots
No)
IP
X
X
Uu
X X
jitt'
P M+
X
X
jit
X
IP
Ni
P
X
X
IP
i X.
IP
Mites
X.
P
x
x
We write suitable counterpart to Equation (5):
x:1)
P Pl N.] = P
Σ
w(S).
X PP
(6)
SC
13

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
We will complete the proof by showing that the RHS of Equation (5) is lower bound for the RHS of Equation (6). We accomplish this in k: steps, one for each color besides c. In the first step, we begin by rearranging the terms of Equation (6) to isolate
P
X X
and P
Xx X
P P N.] = P pX
P
xa
x
Σ
w(S)
II 1ytiS
IP
x
x:]]
II JES
[x
x!]
931
+ P
x
Σ S
w(S)
X
X )
P X M
x::
NES
I#jeS
In the above, we refer to the first and second sums as the C1 c1-wanted coefficient and the 0₁ sg-not-wannin wanted coefficient, respectively, Observe that there exists natural bijection between the summands in these two coefficients. Specifically, we map the summand in the wa-ted coefficient corresponding to set S to the summand in the ci si-not-wanted coefficient corresponding to the set S' \ {1}. These two summands are identical up to the difference between w(S) and w(S \ {1}). By definition, the former weight is smaller. Hence, the C1 ei-wanted coefficient is smaller than the C1 sy-not-ward wanted coefficient.
Next, we claim that TP X a X
P [
and (equivalently)
x
X
To prove this claim, we
consider two cases.
2 I zy
then X
X
= 5 x
Otherwise,
x > xy and we have
X
x
5
1- S
I x
P
1-
We now rewrite our expression for P Y following, let S P[x]]] - P
N₂ in terms of unconditional probabilities of (not) wanting color c1. In the
x
x
P No] P[X]
(FIX0] - d)
Σ w(S)
II L
P
X
x::
II jds
[
X
x.
891
+ (IP
d)
Σ
w(S)
IP
X
x
IP
x
x
931
KiES
1
Our observation that the ei wanted coefficient is smaller than the Gj nott-waateed coefficient yields the bound we desire:
PIC N.J 2 P
Σ w())
II IyiEs
X
x
x
891
jES
X x )
PP
w())
II LiE
X
x
P
931
1
This completes the first of ls 1 steps. In the next step, begin by rearranging terms in the inequality above to isolate We then apply the same analysis, yielding another lower bound on IP [Y Ne), this
P X
and P time written in terms of unconditional probabilities of u (not) wanting colors e and 022 and conditional probabilities of (not) wanting colors c3, c... After 1 steps, our lower bound becomes identical (up to rearranging terms) the RHS of Equation 5, as desired.
14

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
Lemma B.3. Let [0, be a constant and Ry be length nonnegative vector satisfying Ei=1 3i S B, then we have 11
zz) 2 1 3.
Proof. Observe that the claim is trivially true when m = 1. We proceed via induction on m. For m > 1, we have
Em-1 I Imm, so by the inductive hypothesis
II x²) = Im)
II (1 04) 21 (1 mm)( 3 xm) = Im (B Fmm -B. tm
Before presenting next lemma we first require the following definition.
Definition B.4. Let m be nonnegative integer and be integer. Given vector E R". if 2 t 0, we define the
function Pxx, t) follows:
P(x,t) = Σ
πI iET
II (1 (1- (1-2,) jELm//
IE (mm))
and for other choices of and we define
if < <0
1(x,
if = m =t
1.)
if = < m.
To provide intuition, P(x, t) is defined to encode the probability that events from a set of m independent events happen. In more detail, consider a set of m mutually independent events X'
event happens is v; PP[ [[X:), the entry of The function X2, Xmm }. where the probability that the ith probability that exactly of the events in X happen. our proofs for MAXECC, we will apply this with representing subset of colors in the ECC instance, while the vector encodes LP variables { } for some node u and that of colors (which by Observation 2 probabilities for wanting those colors). Lemmas B.5 and B.6 will aid in bounding the probability that node is assigned certain color, conditioned on how many other colors it wants.
Definition B.4
Lemma B.S. Let > be integer and ag; 01, Om be values such that for every E [0,m m
a++1 S Ot
20,11 S + 04+2.
Let D (x 10,2/3]": E Ji 11 be the domain of a function f D + IR defined
f(x) = =xx== P(x, t).
t=0
Then is minimized (over domain D) by any vector x* with entry to 2/3, one entry set to 1/3, and every other entry set to O. Furthermore have
f(x)) = aa + 02) + 01
Proof. Let S (x E 1,,2/3]"; E x. = 1} Ç D be the of input vectors for f whose entries sum exactly 1. Let I S be the set of vectors in S with entry equal to 2/3, entry equal 1/3, and all other entries equal to 0. More formally, if E I, this means there exists two distinct indices {i,j) such that 2/3, æÿ 1/3, and k & {i,j}. Our goal is to prove there exists some x E I that minimizes f. We prove this in two steps: (1) we show that there exists a minimizer of if in S, and then (2) we show how to convert an arbitrary vector x E S into a new vector x" satisfying fx*) & f(x). Given x" E I, the value fxx) in Eq. (7) amounts to a simple function evaluation, realizing that P(x", for t 3.
0 for every
15

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
Step 1: Proving minimizers exist in S.
Let E D \ S, and let [m]] be entry such that Ty 2/3. Set ò min - i==1 r1, mng > 0 and define new vector x' E D by
Z2 if デリ y 24 8 otherwise.
2 = (1)
=
(8)
By our choice of we know that x' DD and will prove this satisfies f(x') S (x). To do so, re-write f(x in way that isolates terms involving Ty. Let My = [m]] (v)- Recall that f is linear combination of terms P(x, t), where P(x, represents the probability that exactly & events out of set of m independent events occur. Entry æ; of x is the probability that ith event occurs. We can therefore re-write:
P(x, 1) P(x ()) - -x,) P(x[My), Jdy
To explain this in more detail, use slight abuse of terminology and refer to [m] as set of events. The first term in Eq. (9) is the probability that exactly t events in My occur and that event does not occur. The second term is the probability that y does occur and exactly - events in M, occur. We therefore re-write (xx as
m
f(x)
Σ 1=0
ae P(x,
(definition of f)
(10)
41 (P(((M))))) xyy) + P(x - 1)mry)
(from Eq. (9)
(11)
a, P( () xyy) + Σ a P(x t 1)
(separating terms)
(12)
P/P(x(M,) t) x.y) +
0 0++1 P(x|M) t)
(change of variables)
(13)
0. PxP(((M ()(1 - x.y) + Σ
0++1 P(x[M
(P(x(M)),m) = P((M)) -1) = 0)
(14)
P(x[M,l.t) 1) (ae(1 - xy) + a1+1
(recombining)
(15)
Observe that if we replace the value of x.y with By + in Eq. (15) this gives the value of / (x'). We can then see that
f(x) Σ P(x[My).1) (ax(1 - -yy -) + ( + 6))
0
P(x[My).t) (a+(1 2zy) alt1 + 5(art1 -a)))
fx) +
(0+1--00
Using the constraint 0++1 < ag we notice that the last term always less that or equal to zero. Hence we have f(x) S f(x). Recall that min -im1 24, 2/3 xyy }. If 5 1 1 Σ 2y then 8 = 2/3 Zy. and Ny = 2/3. We can then apply the same exact procedure again, by increasing the value of some index x₂ (where * v). which we know satisfies xz S 1 1/3. The second application of this procedure is guaranteed to produce vector in S.
that E S and we done. Otherwise,
16

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
Step 2: Editing a vector from S to Z. The proof structure for Step 2 is very similar Step 1, but is more involved it requires working with entries of x rather than one. Let x S \ I, which means can identify two entries Ty and x; in the vector (with A z) satisfying the inequality
0 < Fy S x2 < 2/3.
(16)
Given these entries, d ( 2/3 xz} and define a new vector x' by
if $ (y, =}
5 x0()
24
if if i 2.
(17)
24
+
Observe that E S and that either siy, = or x¹= = 2/3. We will show that f(x') Σ f(x), by re-writing f(x) in a way that
isolates terms involving By and T. Let Myz = [mm]]/11 =}. Similar to the proof Step I, we can re-write P(x, 1) as
t(x.t) P(x[M t) zyy( 10--x- 22))
(18)
+ P(x[M 1- [r xx) + (1 11-xyyJa Ny)as]
(19)
+ P(x --)x,,
(20)
Line (18) captures the probability that exactly events from the set Mys happen, and that neither of the events y or happen.
Line (19) is the probability that events from Mys happen, and exactly one of the events {y. happens. Finally,
line (20) is the probability that both y and z happen, and 2 of the events in My happen. For simplicity now define
a (1 xy)(1 - xz)
8 = ry(1 xx) + (1 - xy)22
7 = Nz
so that re-write f(x) as follows:
f(x)= Σ tx)
(definition of f)
(21)
P(x[MM))) P(MM 118 P(x(M)z),1-2))
(expanding P(x, ())
(22)
4.
+
Σ a P(x
a P(xxXMyz)) 2)7
(separating three terms) (23)
m-2 2
Σ
P( M My +
95+1 Pxx
+
Σ
0x42 Dx42P(x(M,zzl1))
(change of variables)
(24)
km-2
m
Σ
a. Px +
ab+2 ax42 ())
(25)
Σ a,P(x[M,.l,))a + P((MM((( +
4k+2 Mx42P(([M,z),H)))
(26)
0
2
= Σ P(x[M (a.a + 13 +
(recombining sums). (27)
In Eq. (25) and Eq. (26) we have used the fact that = m Consider now the vector x' obtained by perturbing entries Fy and v.. and define
0
a' = (1 21) x²))
(1 (x, 0)) (z+ + 8))
= =a =a 5 xx) - 82
B' = (1- x')) + (1 2t)=''s
= =(x, - 0)(1 (x, + 6)) + (1 - (z, -x)) +8)
= =9 + 28(I, - Iyy) + 282
r = atya's
= =(x,, - 0)(x, +0)
7 - 5(I,, xx) -
17

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
In the expression for f(x) given in Eq. (27), the entries zy and xg appear only in the terms a, B, and y. Therefore, if we replace {a, with {a', 8 n'), we obtain similar expression for f(x'). We can then see that
m- 2
f()) =
Σ yl (ar(a' a) + a4+1 - 3) a(4((//71))
82) + ac+ (28(1= - Fyy) + +80) + 0++2(0(0y - -xa) 82)) p(x(M (ar(5(0y x.) -82)
pf) (a)(01 x2) - -82) 22141(6(22) - x2) - -82) + a(+2(6(1,, - xz)) - -82)
(( ((a: - 20 + ((+2) xxz)== x=2) -62)) S 0,
where in the last line we have used the fact that a; 20c+1 + ac+2 2 0 and (xy - xz)) < 0.
we start with an arbitrary vector x E S. applying one iteration of the above procedure will ensure that at least one entry of x will move to one of the endpoints (0, 2/3} of the interval [o, 2/3]. Therefore, applying this procedure m (or fewer) times an arbitrary vector x E S will produce vector x E I that satisfies f(x) S fxx.
Lemma B.6. The inequalities at 2 at+1 and at + a++2 2 20++1 hold for sequence at I+9+z where g 2 an arbitrary fixed integer. These inequalities also hold for the sequence
2 1 a 9 t+1
(28)
++3
t ++2
Proof: The first inequality (monotonicity) is easy to check for both sequences. The most involved step is checking that the second inequality holds for the sequence in (28). To show it holds, we note that the inequality + a++2 2 2a,+1 effectively corresponds to a discrete version of convexity. We first extend the definition of the sequence in (28) to all positive reals by defining the function
2
1 x +1
5
1
Mxx
x
which we can easily prove is convex over the interval [0, oo) by noting that its second derivative is
10
4
4
h (((x)
(x 2)3
(xr + 3)3
(xr 1)3
which is greater than 0 for all x 2 0. From the definition of convexity for any 3 E [0, 1] and any y 2 0 we have
h(IB + (1 - B)v) - (h(x)) + (1 -3)(())
Now if we consider the specific values = t, + 2, and 1/2 get
1
1
h
1- 11 +2+2 2) 2
2 h11) h(t + 2)
hit + 1) < / (()) + 2 hill + 2)
2h(1 + 1) < h(() + h(( + 2)
20 < 0: + 0++2-
One can use a similar approach to show (even more easily) that the sequence a. = =1/(1+ + f) also satisfies the second inequality.
18

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
Proof of main approximation guarantee. Given the above supporting lemmas, now ready to prove the approximation guarantee for graph MAXECC satisfied by Algorithm 2.
Theorem 2.2. For every E E, P/c is satisfied] 2 pte where 154/405 > 0.3802 when running Algorithm 2.
Proof of Theorem 2.2. Fix = (u, v) Eg and set C [k]][c]. As before, X is the event that wants color i. Let Y, be the event that v is assigned color i by Algorithm 2, and N2 be the event that e wants no colors in C. If c strong for event N, is equivalent to event y Define X Yu and N,, analogously for u.
break the proof up into three cases, which depend on whether 2, I, or neither of the nodes in e = (u, o) have c {(e) as strong color.
Case 1:
is strong for both and u, i..., S. = S. (c)-
Let W. denote colors in Wa that want and define W". analogously for Since c is the strong color for both and v, is satisfied if and only if W = W 0. Additionally, because nodes can only have single strong color and we know e is strong for both и and we know that all other colors must be weak for both u and v. Using the property that probabilities regarding separate colors are independent we have
TP le is satisfied =P =P(W. W 0]
P
IEC
Consider a color i E C., which by definition means x 2 x There are three options for the random threshold o;:
by S a which happens with probability at and implies that i W O O.W.
z < a < x. which happens with probability z, - x and implics E W i & W and
z < x < Cxi which happens with probability 1 - zt, and implies i & W U.!
Thus, for i C. we have Pli W. U.J (1 ax) and similarly for E Cn we have Pli E W. W.W.. = -r.)). This gives
I Pli W W REC
II (1 SEC.
2.,) II (1- (1-)))) REC.
The fact that è is strong for both u and v means - 2 2/3 and - 2 2/3. From the equality constraint in the LP we see that for w fu, w) we have Eiec xf 2/3 1/3. Applying Lemma B.3 gives
22
4 4
II (1-2) + II x 2 iEC, VEC.
2
%e.
33
9
Case 2: c strong for one of u or v. Without loss of generality we say S, = {c} and E Wu. Edge is satisfied if and only if Y Y, holds. Because is strong for v, event Ye holds if and only if N, holds. Using the fact that Y Yg n X write
P [e is satistied] Y n N.).
Using Bayes' Theorm, the fact that Xς and N, are independent?, Observation (P[X a and Lemma B.2, we see that
P F [Y
N, n X
[N,, Xi]
(Bayes" Theorem)
[Y
N, X P [N.] IP [X]] N. 5
(X: and N, are indepdendent) (Observation 1)
IP [Y;
N₂ X
P
2 P [Y;
N, X
P [2,]
(LP constraint x 2 =e)
2
X IP
[N.] Ze
(Lemma B.2).
"Independence follows from fact that X is concerned with color c, while N₂ concerned with disjoint color set = [k]]{c).
19

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
Using X, to indicate that e does not want i, we get
P [N.] =P
X
II (1 xEC
2t))
LIEC
As in Case 1, because is strong for v, we know that Eier dg S 1/3 and applying Lemma B.3 gives us that [[N.] 2 2/3.
Finally we must bound IP [Y X.]. Since e is weak for (i.e., c W.). will be convenient to consider all weak colors for u other than c, which we will denote by W., W. \ (c). We will then use W {i E W.: 04 < x to denote the set of colors in W.. that u wants. Note that X is independent of the number of colors in W., that wants.
Because of the global ordering of colors, conditioned on u wanting and wanting exactly colors in Ww, there is a 1/( +t++) 1) chance that c is chosen first by the permutation и, and is therefore assigned to u. Formally:
1 [ X (WW) = =t] ++1
Define p. = P|WW = t] to be the probability that exactly t colors from Wa are wanted by u. Using the vector x, [W.] to encode LP variables {xt,, : i W.) for node and the colors in W., we see that Pt P(x, [W.]. t). Therefore, the law of total probability (combined with the fact that X is independent from [WrD gives
W Σ t=
P P
X n (IW)) = t) PI = = Σ
1 Pt-
tt
(29)
1
t=
Eq. (29) is exactly of the form in Lemma B.5 with = 1/(t + 1). From Lemma B.6, we know this sequence {a, satisfies
the constraints needed by Lemma B.5, and applying Lemma B.5 shows [Yr X previously established bound IP [N.]] 2 2/3 gives
2 31 31/54. Combining this with the
31
2
31
154
fe satisfied] 2 P [ X.IP(N.
2e
Ze.
54
81
405
Case 3: is weak for both and v, i.e., e e W. n W.. First we condition the probability of satisfying e on the event X n X². If one of X or X does not happen, then cannot be satisfied, so we have
IP [e is satisfied] [e is satisfied X n PX X [e satisfied X X ze.
Define D = (W, OW, (.fcf to be the set of weak colors (excluding c) that want at least one of (u, v). If we condition on u and both wanting c, it is still possible that e will not be satisfied. This will happen if a weak color e wants either or u, and the permutation æ prioritizes color over c. We bound the probability of satisfying e by conditioning on the number of colors in D that want one both of {u, v).
Using the same logic as in Observation 4, we present simpler way to characterize whether a color i E D wants at least one of {u, v). Formally, we partition D into the sets:
Da (iE D: x xt) D- D.
Note that a color i D., wants one or both nodes if and only if wants u, and color i D, wants one or both nodes in if and only if wants Mirroring our previous notation, let D', denote the set of colors in Du that want node (based on the random color thresholds) and define D', analogously. The set D', U D'. is then the set of weak colors that want one or more node in e. Thus, conditioned on D' U D' = and conditioned on u and v wanting c, in order for e to be satisfied c must come before all f colors in D U D in the random permutation æ. Formally, this means
le is satisfied
X x D 0) -
T+0
20

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
Again using the law of total probability and the fact that X X is independent from D2 U D'), see
I PID
Ple is satisfied X x
(30)
Observe now that Du and D, are disjoint color sets, which implies that D2 and [D]] are independent random variables. This allows us to decouple D and D' in the above expression since PP [ a D = = IP [|P]] + = t]. We define
Ps = PI| = 2] and qi || i]
so that we can write
P PI + | = 1 Σ
Piqj = Σ
Pit-i--
t=
This allows us to re-write Eq. (30) as
D..1
Fle is satisfied
X n X
Σ
Σ
+ i Pigj.
(31)
Without loss of generality we now assume |P,]= S |Dol, and proceed case by case depending on the sizes of Da and Da.. Our goal is to show that for all cases Ple satisfied X x 2 154/405, In the cases below, we use the vector x, [D,] to encode LP variables for node u and colors in D, so that Pt P D . i), and likewise % [(x.[Do]: i), to match with notation in Definition B.4 and Lemma B.5.
Case 3a. Dul Dr 0.
No weak colors other than e want u or v, so IPfe is satisfied X n =
Case 3b. Da. and D2l Letting be the single color in D.,
1
Ple is satisfied| X n X;] = Po + 2 po91 = 90 + + = (1 -x,))=) + 2²
Because a is a weak color for we know x E (0, } and the minimum value the probability can obtain is 3 }
154 405
Case 3c. |Dal = Drr = 1.
Letting a be the color in Dy and be the color in Da.
1
Ple is satisfied
X N = Polo + (po9) + p1go) +
3 P191
= (1 - x1 (1)=)))) x + 2 ((1 - 2 + (1- - (1-) + 2.
3
Because a is weak for and b is weak for u, we know x. x E [0, 3. This gives minimum value for the probability of
13
154
27
405
Case 3d. !Dul = and [D]] > 1.
In this case pu = 1, and Eq. (31) simplifies to
D.
Ple is satisfied X X
Σ
1
93
2
31
+
54'
1=0
where we have applied Lemma B.5 with a, /
Case 3e. Daal = 1 and D+l >
Eq. (31) simplifies to
De
D+1
31
19
Peee is satisfied
X n = Po
+ P1
2
Po
+
P1
+
54
54"
コ=
1=
21

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
where we applied Lemma B.5 twice, once with aj - and once with aj has minium value of 23 54'
The right hand side of the above bound
J+2
Case 3f. Du, > and |Dl > 1. From Eq. (31) we know
I2
D2
Ple is satisfied X X
Pi
90
+ +
J=U
We then apply Lemma B.5 Dal + times, once for each choice of E {0, 1, the sequence 0z = 1424j to get
Dull The ith time we apply it, we use
Del Σ 1=0
5
1+i+J
9j
i+1
+
i i+3
+
9
i +
(32)
The right hand of (32) defines new sequence
1
5 1
a
+
(33)
i i+1
i+3
3
9
i+2)
We know from Lemma B.6 that this sequence {a,} in Eq. (33) satisfies the conditions from Lemma B.5, applying Lemma B.5 one more time and combining all steps gives
Ple is satisfied X n X
Dull Σ Ps
1
Σ j=0
Dul
Σ Pi
(2 2 (2
+
1
+
5
1111
)
1
154
9 ii+1
i+3)
9
i+
405"
Therefore, we have shown in all possible subcases of Case 3 that P [e is satisfied
X n X
154
105
Cases 1,2, and all together show that for every E we have
154
IP [e is satisfied]
405 Ze.
C. Omitted proofs from Section 3.1
Theorem 3.1. by- NORM MINECC is approximable within factor when p 1, and factor 2-/v when 0 < p 1.
Proof. We begin with the case where p 2 1. It is well known that the no-norm convex, and we observe that all of the constraints in Program (3) are linear. Thus, may in polynomial time obtain optimal fractional variables {d)), {%c), {m.} for the relaxation of Program (3).
We observe that for each vertex v, there is at most one color with the property that de < 2. Otherwise, there are two colors
C1, C2 with di d3 < 2, but then
1
d
2
2 + (k 2) k 1-1. 1.
contradicting the first constraint of Program (3).
We now propose coloring À as follows. For each color and vertex assign A(e) if d; < By the preceding observation, this procedure assigns at most one color each vertex. If for any we have that dē 2 5 for all colors c, then we set ( arbitrarily.
Now, for each hyperedge e let f%a be equal to if A(v) = f(e) for all v E e, or 1 otherwise. We claim that te 1, then Te 2 1. Otherwise, letting e = f(e). the second constraint of Program (3) implies that d; < for all v E e. Then A(v) = c for all V E e, implying that te- = 0, a contradiction. We conclude that for every hyperedge e, 9. $ 27c-
22

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
For each color e, we write me for the number of hyperedges of color which are unsatisfied by X. Equivalently,
me
Σ
Te
2 Σ > = 2m
e
cEE,
where the last equality comes from the third constraint of Program 3.
follows that for every c, m I 2 2 and thus
k
m
2
m
which in turn implies that
1/2
1/p
Σ m
2
Σ mg
so À is 2-approximate.
We now consider the case where 0 < < 1. We begin by defining, for each E [ki] a non-negative, monotone, and submodular function fc: 2 + E given by fc(S) = E. n S). If X is a vertex coloring of H and Sx S E is the set of edges unsatisfied by X, then Sc(Sx) measures the number of edges of color unsatisfied by x. Because the composition of a concave function with submodular function results in a submodular function and < p < f is non-negative, monotone, and submodular. Then the function f: _ R given by the sum
((5) Σ I!(S)
has these same properties.
Now, let A be an optimal vertex coloring of H and let Sx- be the set of hyperedges unsatisfied by X Our goal will be to compute a coloring À with f(Sx) s 2f(xx)). This would complete the proof, since then we have 2 (f(S))) = fl/p
and ff f are precisely the objective values attained by À and X", respectively. according to Program (3).
We give classic analysis based on the Lovász extension (Lovász, 1983). Some readers may find it helpful to observe that the following is conceptually equivalent to the textbook 2-approximation for SUBMODULAR VERTEX COVER², where the graph in question is the conflict graph G' of our edge-colored hypergraph H. The conflict graph G' is obtained by replacing each hyperedge in /l with a node in G, and adding an edge between two nodes in G if they correspond to overlapping hyperedges of different colors in H. The connection between vertex colorings of edge-colored hypergraphs and vertex covers of their associated conflict graphs has been observed several times in the literature (Angel al., 2016; Cai Leung, 201 8; Kellerhals al., 2023; Veldt, 2023), and also appears elsewhere in the present work, e.g., in the proofs of Theorems 3.8, D.2 and D.3.
Impose an arbitrary order on the edges of E and for each vector 7 E [0, 1||El map edges to components of according to this order. Henceforth, for a hyperedge we write Ye for the component of y corresponding to e. Moreover, for value selected uniformly at random from [0, 1]. we write (>))) = {e: 7e 2 p}. Then the Lovász extension f: [0, 1] - IR of is given by
f(>) (T))))()))]
This f is convex (Lovász, 1983), so we may efficiently optimize the following program:
min
f(7)
s.t. Ne 7y 21
for all e, f E E such that e off * 0 and f(e) + {(F)
(34)
No 1 0
for all e e E.
'Given a graph G and submodular function f. find vertex cover C minimizing f(C).
23

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
Consider the binary vector given by Je 1 if Sx. or 0 otherwise; note that this vector satisfies the constraints of Program (34). Hence, we can see that the minimum value for Program (34) provides lower bound on f(Sx.)
Let y be a minimizer of Program (34), and let
S = fo E F: de 2
11
The first constraint of Program (34) ensures that S contains at least one member of every pair of overlapping and distinctly colored hyperedges. Thus, is trivial to compute a coloring À with Sx S S. follows from monotonicity that f(Sx) - f(S), and that for each p S ((5) S ((T,(T)). Putting all together, we have
S(S) S(Sx) < 2
S² ((S) dp d J/d S(TA(T)) dp J S(T,(T)) /(7) [(Sx)),
which completes the proof.
Theorem 3.2. As p + 0o, the integrality gap of Program (3) converges to 2.
Proof. Consider a triangle three vertices 1/, 222 by with distinct edge colors C12, Cza, C13- Is not possible to satisfy more than one edge, so the optimal objective value is (1P + 12 + 0P) 22/P, Meanwhile, fractional relaxation of Program (3) can set deta = d = 12
d'g"" = de = d'gg 1.4 thus achieving (fractional) objective value ( + 2" + 27 ) 2
31/5
Thus, the ratio of the optimal integral objective to the optimal fractional objective is 2 (2) which converges to 2 as approaches cc.
D. Omitted proofs from Section 3.2
Theorem 3.3. FOLOR-FAIR MINECC is NP-hard even when restricted subcubic trees with cutwidth 2, exactly edges of each color, and T 2. COLOR-FAIR MAXECC is NP-hard even when restricted to paths with 7 = 1.
Proof. We reduce from BOOLEAN SATISFIABILITY, for which the input a formula written in conjunctive normal form, consisting of clauses C1, C2,... Cn over n. variables corresponding positive and negative literals. We make the standard assumptions that no clause contains both literals of any variable, and that every literal appears at least once. We also assume that each clause has size 2 or 3, and that each variable appears in at most three clauses (implying that each literal appears in at most two clauses); hardness is retained under these assumptions (Tovey, 1984). Given an instance of this problem, we construct an instance (G = (V, E), = 2) of COLOR-FARE FAIR MINECC. See Figure for a visual aid.
-nn For each variable 24, write x; and -w; for the
For each clause Cj. we create unique color cj. Also, if C, has size two, we create second unique color d),, and five vertices of. u3, uf, od. and uf. We call these the spare vertices associated with Cy. The reason for creating these vertices and the second color de will become apparent later. Next, for each variable H;, we create vertex uf for each (ordered) pair of clauses Cj Oz with Cj. containing the positive literal x; and Cj2 containing the negative literal -z, We call t/,,,, conflict vertex for the variable and the variable-clause pairs (Ii, Cj.) and (I,, Cj.). Observe that each variable has either one or two associated conflict vertices, as does each variable-clause pair. For each variable-clause pair (æ;, Cz) with single associated conflict vertex, we create an additional vertex of and call this the free vertex for the variable-clause pair (xz, C5).
Now we create edges. For each clause Cj. we begin by creating one edge of of color Cj for each variable x, contained in Cj. This edge contains either the two (I,, Cj) conflict vertices, or the single (I,, Cý) conflict vertex and the (I,, Cγ) free vertex. We call the edge ej a conflict edge associated both with clause Cj. and with the literal of x; which appears in Cj. Observe that every free vertex has degree one, and every conflict vertex has degree two. For clauses C, of size 3, there are exactly three edges of color cj. For clauses Cj of size 2, we have thus far created two edges of color ej. For each such clause, we the associated spare vertices to create third edge {ug, uf) of color cj. which call the spare edge associated with Cj. and three edges {of, 3 {af, ) and {u), 1. each of color dz. Observe that our constructed graph still has maximum degree three, and that there are now exactly 3 edges of every color. Finally, we set T 2.
24

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
(x1 23) A (21 V -2g V -a3) A (-01 V -x2)
Color Key:
C1
1,3
33
1
22
C3
C
1,2 1,2
2/2
U2
2
Vi
22
2,3
3,4
bj,2
62. 62.3
$,,4
65.4
03
Figure 3. The construction given by Theorem 3.3 for the CNF formula three clauses C1 (22 V V xt), C2 (21 V - V - and Cs = (-wi V -ww)). Notice that the vertices are partitioned visually into four horizontal layers. The top layer contains conflict vertices, the second from top contains free vertices. the second from bottom bridge vertices, and the bottom spure vertices. Every edge containing a conflict vertex is a conflict edge, every edge containing a bridge vertex is bridge edge, and all other edges are spare edges. The colors c 02 and ca correspond the clauses C1, C2, and Cs. The color dg is the spare color associated with Cg. The remaining colors are bridge colors. We refer to the proof of Theorem 3.3 for a formal description of the construction and the accompanying analysis.
Since free vertices have degree one, they do not participate in cycles. It is also clear from the construction that spare vertices do not participate in cycles. Thus, any cycle contains only conflict vertices. Note that if two conflict vertices share an edge, then they are associated with the same variablc-clause pair. It follows that every vertex in cycle is associated with some single variable-clause pair. However, a variable-clause pair has at most two associated conflict vertices, so we have constructed a forest.
Now we will add some gadgets turn our forest into a tree. Suppose that the graph we have constructed so far has q connected components. Impose arbitrary order on these components, and label them G1, ......, Gg. Observe that every connected component contains either only spare vertices or two free vertices. In both cases, it is possible to add two edges each with one (distinct) endpoint in G; without raising the maximum degree above three. That the endpoints are distinct will be important when we analyze the cutwidth. For each consecutive pair G;, G;- 1 of connected components, we add two bridge vertices bl, 63,441 1 and a bridge color ch, We add bridge edges (chosen so as not to violate our maximum degree constraint) from G, to 6) 1, from bi,411 to 6f,,41 and from 6,,411 to G.+1. We color each of these three edges with ch,441- Observe that the graph is now connected, but it is still acyclic since there is exactly one path between any pair of vertices which were in different connected components before the addition of our bridge gadgets.
We now claim that the constructed graph G has cutwidth 2. To this end, we will construct a ordering a: V + N of the vertices of G, where a is injective, (v)) = 1 indicates that v is the first vertex in the ordering, ou)) = [V] indicates that u is the last vertex in the ordering, and (v) < o(u) if and only if u precedes u in the ordering. We will show that for every i, there exist at most two edges wo E with the property that (u) S i and (v) > We refer to this number of edges as the width of the cut between vertices and + 1 in a. We begin by guaranteeing that, for every i, if is the associated bridge vertices, then au))= = (b),++) - 1 = (b), - (v)) 3. A consequence is that for every i, if u, v are vertices of G, then every vertex with the property that (u) < (w) < a (v) is also vertex of G. Observe that every cut between two bridge vertices has width 1, as does every cut between a bridge vertex and non-bridge vertex. We therefore need only consider cuts between pairs of vertices in the same G, If G; contains a conflict vertex, then G; is either a P3 or a Pa. The former case arises when a variable appears in exactly two clauses, so there is one associated conflict vertex adjacent to two free vertices. The latter case arises when a variable appears in exactly three clauses, so there are two associated conflict vertices. These are adjacent. Additionally, each conflict vertex is adjacent to a distinct free vertex, so we have a P4. Both the Pa and P1 have cutwidth 1, as evidenced by ordering the vertices as they appear along the path. Moreover, we may assume that the relevant bridge edges incident on the appropriate endpoints of the path, and any cut between vertices of G; has width 1. Otherwise, G; contains no conflict vertices. In this case, G, contains only the five spare vertices of. u/: uff of. and uf associated with some clause Cy, and the four edges are o9 v/, us ug ue vf. and ugug. It simple to check that this
the last vertex of G; in o, is the first vertex of G,-1 in Ø,, and 6) 1 62 1
25

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
construction has cutwidth 2, as evidenced by the ordering (uf)) ( < <v() < (vf) < <off)) Once again, we may assume that the relevant bridge edges are incident on uÿ and ug. Moreover, we can assume that at least one such G2 exists, since BOOLEAN SATISFIABILITY instances which every clause has size three and every variable appears at most three times are polynomial-tinn -tiee solvable (Tovey, 1984). Thus, G has cutwidth 2.
It remains to show that the reduction is correct. For the first direction, assume that there exists assignment e of boolean values to the variables 21,22.....; T.n which satisfies every clause. We say that the assignment & agrees with a variable- clause pair (Iz, C₃) if C3 contains the positive literal z, and (zx,) True or if Cj contains the negative literal -r; and <(x;)) = False. We color the vertices of our constructed graph as follows. To every free vertex associated with clause Cj we assign color cj. The free vertex was only in edges of color cj, so this results in zero unsatisfied edges. Next, to each bridge vertex we assign the associated bridge color. The bridge vertices were only edges of this color, so once again this results in zero unsatisfied edges. Moreover, we have now guaranteed that at least one bridge edge of every bridge color is satisfied, meaning that at most two can be dissatisfied. Henceforth, Next, for each clause C2 of size 2, we assign color c/ to every spare vertex associated with Cj. This results in exactly one unsatisfied edge of color cj, and ensures that every edge of color e, is satisfied. Finally, for each conflict vertex vf,.j. if agrees with (I:; Cj,) we assign color Cn to of Ja and otherwise we assign color C22- Observe that this coloring satisfies an edge ej if and only if e agrees with (Iz; Cÿ). Moreover, because e is satisfying, every clause Cj contains at least one variable x; such that Φ agrees with (Ii, C2). Hence, at least one edge of every color is satisfied. Because there are exactly three edges of every color, there are at most two unsatisfied edges of any color.
will not consider the remaining bridge edges.
For the other direction, assume that we have a coloring which leaves at most two edges of any color unsatisfied. We will create satisfying assignment éb. For each variable Ft, we set ((r;)) True if any conflict edge associated with the positive literal z; is satisfied, and d(x;) False otherwise. We now show that ø is satisfying. Consider any clause Cj. There are exactly three edges with color Cj. and at least one of them is satisfied. We may assume that the spare edge associated with C2 (if such an edge exists) is unsatisfied, since satisfying this edge would require three unsatisfied edges of color dy-- Thus, at least one conflict edge associated with Cj is satisfied. Let x; be the corresponding variable, so the satisfied conflict edge is ej. If C2 contains the positive literal Fi then (xx)) = True so C, is satisfied by é. Otherwise C₁ contains the negative literal - In this case, we observe that every conflict edge associated with the positive literal x; intersects with ej at a conflict vertex, and none of these edges has color ej since Cj does not contain both literals. Hence, the satisfaction of ej implies that every conflict edge ussociated with the positive literal F; is unsatisfied. It follows that Φ(x,) = False, meaning C is satisfied by Φ.
To show the claim for COLOR-FAIR MAXECC, we repeat the same construction, except that we omit all spare colors, vertices, and edges. The effect is that the constructed graph is path. The proof of correctness is conceptually unchanged. Given a satisfying assignment Φ we color vertices in the same way as before, and given a vertex coloring which satisfies at least one edge of every color, it remains the case that at least one conflict edge associated with every clause must be satisfied. The remaining analysis is similar.
Theorem 3.4. COLOR-FAIR MINECC is solvable in ((2rr(El)-time
Proof. We give a branching algorithm. Given an instance (H = E), T) of COLOR-FAIR MINECC, a conftict is a triple (v. e2) consisting of a single vertex v and a pair of distinctly colored hyperedges e1, e2 which both contain v. If H contains no conflicts, then it is possible to satisfy every edge. Otherwise, we identify a conflict in (rr time by scanning the set of hyperedges incident on each node. Once a conflict (v,e1, has been found, we branch on the two possible ways to resolve this conflict: deleting ei or deleting e2. Here, deleting a hyperedge has the same effect as "marking" it as unsatisfied and no longer considering it for the duration of the algorithm. We note that it simple check in constant time whether possible branch violates the constraint given by t; these branches can be pruned. Because each branch increases the number of unsatisfied hyperedges by 1, the search tree has depth at most t. Thus, by computing the search tree in level-order, the algorithm runs in time (2)r
FAIR BIPARTITE VERTEX COVER
Input: A bipartite graph G = (V = A U B, E) and an integer a.
Problem:
II,ICn Does there exist vertex cover C of G with max{IC n Al, [.n BI} < da?
26

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
Theorem D.1. FAIR BIPARTITE VERTEX COVER is NP-hard.
Proof. We reduce from CONSTRAINED BIPARTITE VERTEX COVER, for which the input a bipartite graph G = (AuB, E) along with two integers Ota Ob, and the question is whether there exists vertex cover C' with |CnA| 0a and [Cn B| - ab. This problem was shown to be NP-complete by Kuo & Fuchs (1987).
Given an instance (G = (A A B, E), ala as) of CONSTRAINED BIPARTITE VERTEX COVER, we construct an instance of FAIR BIPARTITE VERTEX COVER as follows. First, we observe that if Ct = og then (G,0a, is already an instance of FAIR BIPARTITE VERTEX COVER, in which case there is nothing to do. We therefore set a4 - an and assume without loss of generality that > O. We begin by copying G'. That is, for each vertex a E A we create a vertex a' E A', for each vertex b B we create vertex 6' E B', and for each edge ab E E' we create an edge a'b' E'. We call the vertices (and edges) that we have created thus far original vertices (and edges). Next, we create 3 auxiliary vertices {a: 1 S i S 3) C A', and B(os + 1) auxiliary vertices {bi 1 S i S 8, 1 S j S as + 1] C B', We also add auxiliary edges {a,biz 1 < i < B. 1 S S as + 1 C E'. Finally, we set a = ct. This concludes the construction.
(G' = (A' w B¹, F)),)) a) F''),,
Oa, 0%)
remains to show that the reduction is correct. For the first direction, assume that C C V is a vertex cover of with |C I aa and |C n B| S at. We construct vertex cover C" of G' as follows. For each vertex a E C' C'A,, we add a' to C, and for each vertex E C B, we add b' to C. We also add the auxiliary vertex a, to C, for each 1 S S B. Because C' is vertex cover of E, C" covers every original edge in E'. Because every auxiliary edge in E' is incident on some auxiliary vertex 0g, C" also covers all auxiliary edges in F'. Hence, C' is vertex cover of G'. Moreover, by construction |C" B'I S ab = a, and (C" n'I S aa + ==== =0.
For the other direction, assume that there exists a vertex cover C' of G' with |C' nAl. C" i n S a. We will construct a vertex cover C' of G. We begin by observing that C" contains every auxiliary vertex a; for S i S 3. Suppose otherwise, ie., that for some fixed we have a, & C Then each of the ag + 1 auxiliary vertices byj. for 1 S j S ag + 1, is contained in C². Since a Os, this contradicts that |C" n B'] S a. So, we conclude that a; E C" for each S i ك B. We now also assume that C" n B' consists entirely of original vertices, since the vertex set resulting from the removal of auxiliary vertex biy is still a cover, as it contains ag Now, for each b' E C", we add b to C, and for each original a' E C², we add to C. Because the auxiliary vertices of G" are not incident to any original edges, the original vertices of C" must cover all original edges. Hence, C is a vertex cover of G. Since |C' n A'I S a = Oa + B3 and C" O A' contains 3 auxiliary vertices, C" A' must contain no more than aa, original vertices. Similarly, C' n B' contains at most a = as original vertices. These properties allow us to conclude that [C CA S aa and |Cn B| S crg, as desired.
Theorem 3.5. COLOR-FAIR MINECC and COLOR-FAIR MAXECC are NP-hard even in 2-regular hypergraphs with 2
Proof. Given an instance (G = (A H B, of FAIR BIPARTITE VERTEX COVER, we construct an instance (H = (V, Ea E,), T = a:) of COLOR-FAIR MINECC with two colors (ca and cB) as follows. For each edge ab E E, we create vertex uas V. We call this vertex a conflict vertex, and we say that it is associated with A and with b E B. Next, for each vertex A, we create a hyperedge ea which contains every conflict vertex associated with a. We color this edge CA- Similarly, for each vertex b E B we create a hyperedge es of color en which contains every conflict vertex associated with b. Observe that every hyperedge is nonempty, as we may assume that G has no isolated vertices. Observe also that every vertex has degree 2. We set r = a.
To see that the reduction correct, consider first a vertex cover C of G with |C n AC, |C n B| < a. For each vertex E A \( C, we assign color Ca to every conflict vertex associated with a. Similarly, for every b e B \ C, we assign cg to every conflict vertex associated with b. We color remaining vertices arbitrarily. We claim that this is a valid coloring, i.e.. every vertex has received exactly one color. To see this, observe that every vertex Vab in V is a conflict vertex associated with exactly two vertices a, b in A l B. Since C' is vertex cover, at least one of a, is in C. Hence, Cab is assigned exactly one color. We next claim that our assignment of colors leaves at most T = a hyperedges of any single color unsatisfied. Due to our coloring scheme, if hyperedge e, (resp. 6b) associated with a vertex a E A (resp. b E B) is unsatisfied, then a (resp. b) is contained in C. Since |Cn C n Bl < a, we conclude that at most т = a hyperedges of color CA (resp. cB) are unsatisfied.
27

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
For the other direction, suppose that have a coloring A: V + {cA.Cal which leaves at most T a hyperedges of any single color unsatisfied. We construct vertex cover C of G which contains E A (resp. b B) if and only if the hyperedge associated with a (resp. b) is unsatisfied by X. It is immediate that |C AJ, |C B| S Now we claim that C is a vertex cover of G. Consider any edge ab E E. The conflict vertex dab is contained in both Ea. which has color CA. and eb, which has color en- Thus, at least one of ea, Eb is unsatisfied by X, and so C' contains at least one of o, b. Then C' is a vertex cover, as desired.
simple adjustment to our construction yields the claimed hardness result for COLOR-FAIR MAXECC. Let = -B] and assume without loss of generality that 3 2 0. If 3 = 0, then there are already an equal number of edges of colors Ca and cB, so make no adjustment to the construction. If 3 2 3, we add an additional vertices v1, ...... Ug. and an additional 3 hyperedges é1 = {vi, v2),
{u2, va....... Eg {us, e1 }. constructing cycle with 33 vertices and edges (a Cg). We assign color св to each of these hyperedges. We now observe that in the constructed hypergraph, there are an equal number of hyperedges of colors CΛ and CB. and every vertex has degree 2. Finally, if 3 E {1,2]. we add / + 6 vertices 21, 022 ... V846. With three of these vertices we form a triangle with each edge having color ca. and with the remaining g + 3 vertices we form a C3+3 with each edge having color cB- Once again, we observe that there are now an equal number of edges of colors сд and cg in the constructed hypergraph, and every vertex has degree 2. We set |A| - a if 3, or ||| + otherwise. Correctness follows from substantively identical analysis.
SPARSE VERTEX COVER
Input: A graph = (V = U UV.
Task: Find a vertex cover C C V of which minimizes max {|C V.l..
Theorem D.2. COLOR-FAIR MINECC admits a 2-approximation via reduction to SPARSE VERTEX COVER.
Proof. Let H G= = UV........ Vg E') of SPARSE VERTEX COVER. For each hyperedge of color i, we create vertex de in V/" Next, for every pair of distinctly colored hyperedges e1, E2 with e ne + 0 (a bad hyperedge pair), we create an edge Ve, Ueg- This completes the construction of G.
E E&) be an edge-colored hypergraph with i colors. We construct an instance
Now, let opta and 1 be the optimal objective values for G and H, respectively. We claim that opt. S opt Suppose that S is the set of hyperedges unsatisfied by some optimal coloring X, so max n E,| = opt,,- Because À satisfies all edges in F. 5, S must contain at least one member of every bad hyperedge pair. Hence, the set C = {v. V vertices in G corresponding to hyperedges in S is a vertex cover in G, and has the property that max4e(K] |C n V/11 = opt,, It follows that opt; < opt,-
S) of
Finally, we show how to lift a solution. Let C' C V be a vertex cover in G which is 2-approximate; such a cover can be computed in polynomial time (Blum et al., 2022). Let S = {e E E Ue E C} be the hyperedges of H corresponding to the vertices in C. Because C' is vertex cover and the edges of G correspond exactly to the bad hyperedge pairs of H, is trivial to compute a coloring X which satisfies every edge in E \ S. The objective value of À is at worst
max RE(R
IS E.J
max E R
S m V' s 2 opt S 2- o
Theorem D.3. COLOR-FAIR MINECC admits a linear-time combinatorial k-approximation.
Proof. We begin by proving that SPARSE VERTEX COVER admits polynomial-time combinatorial k-approximation when the vertex classes V1, V2..., , V are disjoint and every edge has endpoints in distinct vertex classes. Let G = (V V, U V/2 J...u w Ve, E) be an instance of SPARSE VERTEX COVER which satisfies these conditions. Let opts be the optimal objective value for SPARSE VERTEX COVER on G, M C E be a maximal matching in G, and C' C V be U.EM e. We claim that C a k-approximate solution.
28

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
Since M is maximal, C' is vertex cover of G. Because every edge has endpoints in distinct vertex classes, for each E [A] have that
C - MM).
|anv <
To obtain lower bound, we observe that because M is matching, every vertex cover of G' has cardinality at least J.M.. It follows from the pigeon-hole principle that opts 2 //k. Thus, for each E [k] we have that |C n Vil s k opt.. as desired.
The result for COLOR-FAIR MINECC now follows from the reduction of Theorem D.2. This algorithm is the same as the vertex-cover based 2-approximation for standard MINECC previously shown by Veldt (2023), with a new analysis to prove the approximation guarantee for COLOR-FAIR MINECC. The linear runtime is obtained by applying the implicit construction process of Veldt (2023).
E. Omitted proofs from Section 3.3
Theorem 3.6. For every E (0, b) there exists a polynomial-time (/. ) approximatin for PROTECTED-COLOR MINECC.
Proof. We begin by computing optimal fractional values {te}, {dg} for LP (4).
We claim that for every pair of distinctly colored overlapping hyperedges e, f. Ye + 7f 2 Otherwise, let E en Ge f(e), and ef {(f) Since " + 7f follows from the second constraint of I.P (4) that de + de < 1. Then
Σ de - k
contradicting the first constraint of (4).
Now we show how to color the nodes of our hypergraph H = (V, F)) with protected color Fj. For each hyperedge e, we set
if e E Ej and 2 1
%e =
if e & E and Ne 2 p otherwise,
0
and we construct the set S {e E: 9/ 1}.
First we observe that since
(0, 21 1-p
1
and so
p²
|
Σ
te
1
Σ
Ne + 1-p p
1
Σ
1e Σ Yes
P
P
eE
EEEVE,
eEE,
EEB
and
Σ S < 1-P
1
Ye
1
All that remains to compute a coloring À which satisfies every hyperedge in E \ S. S contains at least one member of every pair of distinctly colored overlapping hyperedges, then computing such a is trivial. We conclude the proof by showing that S has this characteristic. Let e, f E with with en f * 0 and E(e) # {(f). Assume toward a contradiction that e, f & S. Because and f are distinetly colored, at least one is in F. Fj. If both e, $ Fj, then
Te 7 7/ < 2p < 1,
but we have already shown that + + 2 1. so exactly one of or f must be in Ej. Assume without loss of generality that e E E and f E E E. Then
%e + + < - p p=p=1,
so we have contradicted that S fe,e f) = 0. as desired.
29

---

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
Theorem 3.7. PROTECTED-COLLOR MINECC is FPT with respect to the total number I of unsatisfied edges.
Proof. We give a branching algorithm which is essentially identical to that of Theorem 3.4. For completeness, we repeat the details. Given instance (H- = (V; (, of PROTECTED-COL.c MINECC, a conflict is triple (v, 61, e2) consisting of single vertex e and pair of distinctly colored hyperedges e1, eg which both contain If H contains no conflicts, then it is possible to satisfy every edge. Otherwise, we identify a conflict in O time by scanning the set of hyperedges incident on each node. Once a conflict (1) has been found, we branch on the two possible ways to resolve this conflict: deleting é1 or deleting c2- Here, deleting hyperedge has the same effect as "marking" as unsatisfied and no longer considering it for the duration of the algorithm. We note that it is simple to check in constant time whether a possible branch violates the constraints given by or b; these branches can be pruned. Because each branch increases the number of unsatisfied hyperedges by 1 and WLOG & b, the search tree has depth at most t. Thus, the algorithm runs in time ())
Theorem 3.8. Given 2-regular H (V, F,,), two integers bı, b2, and two colors C1 it is NP-hard to determine whether it is possible to color V such that at most bj edges of color e₁ and at most b2 edges of color eg are unsatisfied.
Proof. We once again reduce from CONSTRAINED BIPARTITE VERTEX COVER, for which the input is a bipartite graph G= (At B, E) along with two integers Oa. Obb, and the question is whether there exists a vertex cover C' with |CnAl S Oa and |Cn B I ag. We will construct the edge-colored hypergraph for which G is the associated conflict graph. Formally, we construct an edge-colored hypergraph H = (V, Fa It Fa, E) with two colors Ca and G as follows. For each edge e E E, we create a vertex Ue E V. For each vertex a A, we create a hyperedge ca E Es such that e, = {vee a E e). Similarly, for each vertex b E B, we create a hyperedge e, E Eg, such that es = (ve: b E e). For each 6, E E, we set E(ea) = ca. and for each e, E Eb we set E(ea) cb. Note that H is 2-regular, since each E' has cardinality 2 and thus the corresponding vertex vg is contained in 2 hyperedges. We say that our protected colors E, and Eg,, and set the associated constraints bi Ota, and b2- Olb.
Thus, if À is vertex coloring of H, Sx is the set of hyperedges unsatisfied by A, and we have that |S Eal S. b1 ag and [S Eg I b2 = (t.. then the set C = {a: ea E C} U {b: e E C} has the properties that |C A/A S aa and |C' B| S ag. Moreover, if ab = is an edge in e, then ea and e are distinctly colored, with ea Neg = (ve). Hence, S contains at least one of ea, Cb. meaning that C contains at least one of a, so C' a vertex cover.
For the other direction, assume that C' is vertex cover of G with the properties that |C' A S 02 = =b and |Cn < ag b2. so the set 5 fea: : C} U {es: b C} has the properties that |S n Eal < b1 and |S n Egl b2. Observe that, if ea and 6 are distinctly colored hyperedges which overlap, then ab E F. Thus, at least one of a, is contained in C, and so at least one of ea. e, is contained in S. Then there are no pairs of distinctly colored overlapping hyperedges in (E, W Eb) \ S. Consequently, it is trivial to compute a coloring À which satisfies every hyperedge not contained in S, meaning that it leaves most bj hyperedges of color e, unsatisfied, and at most by hyperedges of color eo unsatisfied.
30


Reviews:
[{"review_id": "PVJProDzUd", "reviewer": "Reviewer_Tzam", "summary": "This submission studies a clustering problem where one wants to cluster vertices of a hypergraph by coloring them while approximately maximizing the number of hyperedges all whose vertices get a hyperedge-specific color (those hyperedges are called satisfied). It gives the first algorithm for this problem on general hypergraphs the approximation ratio of which gets worse with increasing maximum hyperedge size but actually beats the previous best ratio for hyperedge size 2. The algorithm, like older ones for the graph setting, is based on randomized rounding of an LP solution. As is often the case, the idea behind this rounding is natural but analyzing its quality involves some carefully combined ideas.\nAdditionally, the submission proposes variants of the dual problem for minimizing the number of unsatisfied hyperedges that put hard constraints on the number of allowed unsatisfied hyperedges of a specific protected color or require that the number of unsatisfied edges of each color be balanced and devises some basic hardness results and algorithms for them. The latter are partially implemented and tested.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your feedback and questions!\n\n**Motivation for ECC variants.** We highlight 2 points we could have done better addressing in the main text.\n\n(1) Correlation Clustering variants\n\nOne key motivation for our fair/protected ECC variants is that these are directly analogous to questions that have been extensively studied for variants of the closely related correlation clustering (CC) problem. Puleo and Milenkovic (ICML 2016) considered a mini-max objective (minimize the maximum number of mistakes incident to any one node) and a more general Lp-norm variant of correlation clustering. Subsequent papers on these CC variants include:\n\nCharikar et al. (IPCO '17)\n\nKalhan et al. (Neurips '19)\n\nJafarov et al. (ICML '21)\n\nDavies et al. (ICML '23)  \n\nHeidrich et al. (AISTATS '24)\n\nDavies et al. (ICALP '24)\n\nUnlike the rich literature on correlation clustering, prior work on ECC has focused only on objectives that consider the total count of (un)satisfied edges. Our motivation is to understand whether algorithms for this simplest variant work only in this setting, or if we can identify algorithmic strategies that work (or fail) for alternative objectives. \n\n(2) Resource allocation, team formation\n\nWe are also interested in potential applications to resource allocation (motivation from the first graph ECC paper, Angel et al 2014) and team formation problems that relate to the work of Amburg et al 2022, but go beyond the explanation we provided in our introduction. For team formation, one can imagine nodes representing workers, and colors representing assignments to work teams (possibly encoding different physical work sites). An edge of a certain color is then a task that can be completed if and only if a specific set of individuals are assigned to that same group or site. In this case, a natural goal is to partition workers to balance the number of tasks that can be accomplished at different work sites. Here it’s not enough to just balance the number of workers in each group—one must consider the collection of tasks that can be completed by workers assigned to a team.\n(This motivation aligns more with Color-Fair MaxECC. However, the latter is NP-hard to even approximate. Color-Fair MinECC provides roughly the same goal if the number of edges of each type is balanced, and we show it is amenable to approximations.) \n\nWe stress that this direction of exploration is still in initial phases, which is why we did not focus on it extensively in our submission. The present paper is more directly motivated to establish better theoretical foundations of ECC algorithms for a broader class of objective functions, analogous to the rich literature on correlation clustering.\n\n**Regarding results for fair/balanced ECC.** Our goal was to get as complete an understanding as possible of (i) the approximability and (ii) parameterized complexity of our fair/balanced objectives, especially for Color-Fair ECC. We agree that there are still open questions that could be explored, but we sought to provide as full of an answer as possible.\n\nRegarding FPT results, we chose to explore the same collection of parameters considered by Kellerhals et al. (AAAI 2023), who provided a comprehensive study of the parameterized complexity for standard ECC. This uncovered fundamental differences between FPT results for standard ECC and Color-Fair ECC (see text after Theorem 3.3).\n\nNote that we did include some approximation hardness results, in that Color-Fair MaxECC is NP-hard to approximate to within any factor (see line after Theorem 3.3). We agree that approximation hardness results for Color-Fair MinECC and Protected ECC would also be interesting, but ultimately we were not able to settle all open questions in one paper. These are interesting directions for future work.\nSee also our response to Question 5 of reviewer Hv7k regarding approximation hardness and ways in which our results are tight.\n\nWe agree that there is a lot going on in the second half of the paper in various directions. We could have chosen to discard some of these results, but ultimately we felt it would be better to provide as many answers to natural questions as we could. \n\n**Related work.** The reviewer argued that “the problem seems a bit niche for the broad audience (this impression seems to also be confirmed by looking at where most closely related work was published).” However, we would like to point out that the most related papers are published at ICML or similar venues. This includes hypergraph ECC papers:\n\nVeldt (ICML '23)\n\nAmburg et al (WWW '20)\n\nAmburg et al (SIAM Data Mining '22)\n\nKellerhals et al (AAAI '23)\n\nCrane et al (WSDM '24)\n\n\nand papers on approximation algorithms for the closely related problem of correlation clustering in edge-colored graphs: Bonchi et al (KDD 2012), Anava et al (WWW 2015), Klodt et al (KDD 2021), Xiu et al (Neurips 2022)\n\nThanks finally for the additional Comments and Suggestions. We will address these in an updated version of the paper.", "claims_and_evidence": "The only content I am suspicious of is the motivation behind defining the fair variants of the problem. The described potential applications sound more like the size of the clusters should be lower bounded rather than the number of unsatisfied clusters balanced. If one were to reformulate that application as wanting each type of task to be not be doable because of a certain assignment of workers to roles one would also consider it more sensible to somehow view this relative to the number of tasks of a type there are in total. In general, I would need some more convincing arguments why the suggested fair problems are interesting, even from a theoretical standpoint.", "methods_and_evaluation_criteria": "The methods seem appropriate.", "theoretical_claims": "I read everything except the appendix.", "experimental_designs_or_analyses": "I did not check them beyond reading their description and thinking about whether they make sense on a superficial level but these are also not the core of the contributions.", "relation_to_broader_scientific_literature": "This falls into the research direction on edge-colored clustering, improves a line of results there and tries to open new research directions about the problem.", "essential_references_not_discussed": "I am not aware of any.", "other_strengths_and_weaknesses": "In terms of topic, this could be in scope for ICML but the problem seems a bit niche for the broad audience (this impression seems to also be confirmed by looking at where most closely related work was published). Apart from that, the results and included proofs are also generally well-presented.\n\nBecause I am not convinced of how relevant the general problem and even more so the introduced variants are, I am scoring this as a weak reject but am happy to discuss this assessment.", "other_comments_or_suggestions": "-L026: best known (no hyphen)\n-L058: Maybe say here what this gap is\n-L135: Maybe add r is an arbitrary constant\n-L138: line of previous research\n-At the beginning of section 2.1.: at some point you should fix z_e and such to be values of the variables in an arbitrary fixed optimal solution of the LP (otherwise z_e is not defined in the statements of the observations and such).\n-L166: Obtain optimal values for {z_e,x_v^c} in the LP relaxation.", "questions_for_authors": "Can you argue a bit more why the introduced fair variants of the problem are of interest?\n\nSimilarly, your later results seem a bit arbitrary. Can you explain why you chose to focus on those, e.g. some approximation, some approximation results and some hardness results in which you do not mention hardness of approximation? Did you try to get a comprehensive view in any of these directions?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YZ24aVaPAN", "reviewer": "Reviewer_Hv7K", "summary": "This paper studies variants of the Edge Colored Clustering problem. The input consists of a hypergraph where the hyperedges are equipped with a color each. The goal is to find a coloring of the vertices. A hyperedge e is satisfied if all its vertices have the same color as e; otherwise e is unsatisfied.\nAn important variant is MaxECC where the goal is to maximize the number of satisfied edges. The paper provides the first approximation algorithm hor hypergraph MaxECC. Morover, an improved approximation factor for the graph variant is provided. \nMoreover, also balanced and fair variants of ECC are studied and mainly approximation algorithms are provided.\nFinally, a proof-of-concept implementation is provided showing the effectiveness of the newly proposed algorithms.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the detailed review! We agree the FPT algorithms are simple, and intended only as small supporting results. Also, please see our answer below regarding ETH bounds. \nThank you also for your line-based comments and suggestions. We will revise the manuscript accordingly. We’ll focus the majority of our space on your 5 specific questions.\n\nQ1: This observation considers the probability that every node in an edge wants the edge’s color. A node wants a color if the LP variable for that node-color pair is greater than the random threshold for that color. What we are observing is that a single random threshold is used for the entire color, so in order for all nodes in an edge to want a color, it is enough for the node corresponding to the smallest LP variable to want the color. Note that the random variables in question are not independent, so we do not want to multiply the probabilities\n\nQ2: We omitted this proof, since the text preceding the theorem statement contains the main idea. However, we would be happy to add a formal proof to the appendix. All that is missing is a standard rigorous treatment of the limit analysis.\n\nQ3: This is good intuition, but reducing from 3SAT (with our construction, at least) only proves that Color-Fair MinECC is NP-hard when the rank of the hypergraph is at least 3, i.e., we would leave the graph case open. To understand why, observe that in our reduction we assume that each literal appears no more than twice. This assumption is crucial in bounding the size of constructed edges by 2 (each variable-clause pair has no more than 2 associated conflict vertices). If we instead reduce from 3SAT, then by the results of Tovey (Discrete Applied Math; 1984), we must assume that some variable appears at least 4 times, meaning that a literal may appear thrice. One might wonder whether the reduction of Tovey can be adapted to guarantee that literals appear at most twice. This may be possible, but it is not straightforward (we tried).\n\nQ4: For Color-Fair MinECC, observe that the reduction of Theorem 3.3 creates an instance with O(m) total edges, where m is the number of clauses in the SAT instance. Clearly, the parameter t is thus also in O(m). So, conditioned on an ETH-bound for the particular variant of SAT from which we reduce, we can obtain one for Color-Fair MinECC.\n\nRegarding the relevant SAT variant, at a glance it appears that the ETH excludes any 2^o(m) algorithm. To formalize this, one needs to make a few relatively simple arguments about the reduction of Tovey (Discrete Applied Math 1984). Having not worked out all of the details formally, for now we conjecture strongly that, under the ETH, Color-Fair MinECC does not admit any 2^o(t) algorithm. \n\nFor Protected-Color ECC, first observe that the problem generalizes standard ECC. We believe that no ETH bound for ECC has ever appeared in the literature. However, it is clear that one can be obtained. For example, the reduction from Vertex Cover given by Veldt 2023 excludes any 2^o(t) algorithm for ECC (each hyperedge corresponds to a unique vertex in the Vertex Cover instance). The same bound then applies to Protected-Color ECC.\n\nThe aforementioned Vertex Cover reduction creates an ECC instance with unbounded rank. It is thus open (and perhaps more interesting) to seek an ETH bound for ECC when the rank is bounded, most prominently in the graph (rank 2) case. Perhaps an ETH bound can be inferred from one of many reductions given by Kellerhals et al. (AAAI '23).\n\nQ5: For Color-Fair MinECC we are not aware of any approximation bound, though we agree that this is interesting. In particular, it is interesting to ask whether Color-Fair MinECC can be approximated as well as (or even better than) standard MinECC, for which Veldt 2023 gave a UGC-hardness bound.\n\nFurther progress beyond our given 2-approximation is likely to require a new perspective. To see why, observe that we obtain 2-approximations for Color-Fair MinECC via two distinct strategies. First, we round the LP given at the beginning of Section 3.1 (appropriately rewritten for the mini-max p → infinity case). We cannot tighten this technique, since we already match the integrality gap. Second, we obtain a 2-approximation via reduction to Sparse Vertex Cover (see line 333 column 1, and Thm C.2). Improving the bound yielded by this reduction would require a better-than-2-approximation for Sparse Vertex Cover, which would refute the UGC. We mention these points only to emphasize that, while we do not have approximation lower bounds for Color-Fair MinECC, our results are tight with respect to the techniques used. \n\nFor Protected-Color ECC, we can apply the UGC-conditioned lower bound for standard ECC from Veldt 2023. However, it is interesting and open to determine whether Protected-Color MinECC can be approximated as well as standard MinECC. Finally, we mention (line 298, column 2) that unless P = NP, no poly-time multiplicative approximation for Color-Fair MaxECC exists.", "claims_and_evidence": "For me, all claims are convincing. Also the problem and its variants have a good motivation.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I did not check all proofs in detail (especially the long proofs about the approximation guarantee), but I think I got a rough understanding of the ideas.", "experimental_designs_or_analyses": "The experiments are only a proof-of-concept implementation. But these experiments are sufficient to outline the effectiveness of the new approximation algorithms.", "relation_to_broader_scientific_literature": "In the introduction a very good overview of related papers and previously known approximation factors is provided.", "essential_references_not_discussed": "I think all relevant papers are discussed.", "other_strengths_and_weaknesses": "other strength:\nI liked that ideas from the hypergraph algorithm are adapted to the graph case and this then yields a better approximation factor than what was previously known.\n\nother weaknesses:\nThe FPT-algorithms are very simple. It would be interesting to have matching lower bounds, eg no 2^o(t) algorithms are possible.\nBut I think this is not a real weakness. I see these FPT results as a small bonus and that the main results are the approximation algorithms.", "other_comments_or_suggestions": "line 99 column 2: I think w should be part of the definition of H\n\nline 130 column 1: please provide some references\n\nline 190 column 2: Can you add a short description why the proof does not work for r>2?\n\nline 236 column 1: I got a good intuition for the used prioritization, but I didn't get an intuition for ``strong''. Please add a few lines there for more intuition.\n\nline 311 column 2: I think many more parameters are open; and an interesting one might be the max leaf number.\n\nTheorem 3.9 If I understand it correctly, I think this theorem should also hold for 2-regular graphs? If yes, please mention this in the theorem.\n\nline 411 column 1: Table 4 >> Table 1\n\nline 527 that that >> that the\n\nline 1134: the forward reference to section 3.2 is not very nice; please define it here too.\n\nline 1472: I think Protected-Color MinECC should be NP-hard for b=0. I think this should be mentioned somewhere.\n\ntable 2: explain shortly the meanings of n,m,r,k", "questions_for_authors": "Q1: I don't understand the second equation in Observation 3. I think you need to multiply the probabilities? I think it is used like this in line 196 column 1.\n\nQ2: Where is the proof of Theorem 3.2\n\nQ3: Can't you simplify the proof of Theorem 3.3 significantly, if you additionally assume that each clause has exactly 3 literals?\n\nQ4: Are you aware of any ETH lower bounds for your FPT-algorithms with respect to t?\n\nQ5: Are there any inapproximation results for the balanced and fair variants of your problem?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Lu6KCcxzbc", "reviewer": "Reviewer_qaps", "summary": "The authors study the edge-colored clustering (ECC) problem in hypergraphs. They generalize MaxECC from graphs to hypergraphs, and present an approximation algorithm of factor $(2/e)^r (r+1)^{-1}$, where $r$ is the maximum number of nodes that are allowed in a single hyperedge. A slight modification of this algorithm provides a factor of 154/404 for graph MaxECC. They also study three variants of ECC, that are, $\\ell_p$-norm ECC, color-fair ECC and protected-color ECC, and give a series of algorithmic and hardness results on them. Experimental results demonstrate that their algorithms have much better results in practice than the theoretical worst-case guarantees.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your detailed review and feedback on our manuscript. \n\nRegarding the “significance of the variant problems for ECC”, please see our response to reviewer Tzam, where we provide more details on motivation we could have been clearer about in our submission.\n\nThanks for your question about comparing our techniques to those of Veldt 2023. There are indeed strong high-level similarities (LP relaxation + global color ordering + randomized rounding), but the difference between MaxECC and MinECC is significant enough that the algorithm of Veldt 2023 can be shown to completely fail for MaxECC. Furthermore, the way to make an algorithm work for MaxECC requires quite a bit of new technical machinery, and as a result the overall techniques and proof for our algorithm substantially differ from the technical contribution Veldt 2023.\n\nTo explain this in more depth, note the following important differences between the randomized LP rounding MinECC algorithm of Veldt 2023 and our randomized LP rounding algorithm for MaxECC:\n\n(1) We have a threshold (determining how colors want nodes) for each color, while Veldt 2023’s algorithm uses a single threshold that applies to all colors at once.\n\n(2) Especially for the graph case, we have to distinguish between whether a color is “strong” or “weak” for a node\n\n(3) We draw each color threshold uniformly from [0,1]. Veldt 2023 draws the threshold within a bounded subset in the interval [0,1]: either [⅓, ½] or [1/4 , 1/2] or [⅛, ½] depending on the relationships between k and r. Note that these intervals appear at face value to be different from what is written in Veldt 2023, but that is only because Veldt was considering flipped LP variables (essentially, for our LP variables $x_{u}^c$ Veldt was working with $1-x_{u}^c$ )\n\nFocusing on difference (3), choosing a threshold that is bounded away from 0 means that Veldt could essentially ignore hyperedges where the $z_e$ variable is very small, even if $z_e > 0$. For the MinECC formulation, this means there is a variable $x_e = 1- z_e$ that is close to 1, and note that the LP relaxation for MinECC has objective min \n$\\sum_{e} x_e$. When $x_e$ is large, then we can just delete (leave unsatisfied) that edge with probability 1, and the “mistake” (for the MinECC objective) is paid for in terms of the (large) value of $x_e$ in the LP. Thus, Veldt 2023 can focus on edges e where $z_e$ is not too small (i.e., $x_e$ is not too large). This is essential for the analysis because this implies useful bounds on the number of different colors that can want each node in the hyperedge, which in turn leads to simpler bounds on the probability of making the edge unsatisfied.\n\nHowever, for MaxECC, if we choose a threshold that is bounded away from zero when deciding how nodes want colors, this means that if an edge e has an LP variable $z_e$ that is positive but close to zero, the algorithm of Veldt 2023 is guaranteed to delete it, meaning that the probability that the edge $e$ is satisfied is 0. This completely ruins the strategy of proving that for every edge e, the probability of satisfying e is at least $p z_e$ for some approximation value $p$.\n\nBecause of this, a different algorithm (with a very different proof) is necessary. First of all, we must consider thresholds that can be arbitrarily small (hence we draw them from [0,1]). This then makes the analysis much more complicated, because now we do not have any convenient bounds on the number of colors that want nodes in an edge (recall that this was crucial for the analysis of Veldt 2023). This is what leads to other needed differences in the algorithms (in particular, differences (1) and (2) listed above). In terms of the proofs themselves, our (often quite complicated) supporting lemmas (Lemmas A.2-A.6) and the ways they fit together to provide full proofs, deviate significantly from the technical details of Veldt 2023 for MinECC. (Note also that Observations 1 and 3 are simple results that are analogous to observations used by Veldt 2023, but Observations 2 and 4 are unique to our algorithm and analysis for MaxECC). \n\nIn regards to the datasets, we used a suite of datasets that have been described in detail in previous work on ECC (Amburg et al WWW 2020). Because these datasets have been described in detail previously and because of space constraints, we omitted a more detailed description. However, we understand that more details would be nice so that readers do not have to refer to other work, and we are happy to include more details in the appendix. Additionally, if the paper is accepted, that would provide us with 1 page of additional space we may be able to use. Some of this 1 page of space is also needed to expound on parameterized complexity (see response to reviewer LJar), but we may also be able use some of this space to briefly expound on the datasets even in the main text.\n\nThanks finally for noticing the typo on line 411.", "claims_and_evidence": "Yes, I think so.", "methods_and_evaluation_criteria": "Yes, except the benchmark datasets for which there is not too much information provided in the paper, e.g., what the nodes and hyperedges represent, what the colors mean, etc.", "theoretical_claims": "I have only checked the proof of Theorem 2.1 for the basic algorithm, and had a quick review for the variants. Every algorithmic result is starting from some kind of LP description of the relative problem, while LP-rounding and randomization are main techniques in analysis. All conclusions are easy to understand.", "experimental_designs_or_analyses": "No baseline method is introduced in the experiments. But I’m not sure whether there is.", "relation_to_broader_scientific_literature": "This research fits well in the study line of ECC on (hyper)graphs. It has the first approximation algorithmic result of MaxECC for the hypergraph case and improves that (even slightly) for graph case. It also complements some algorithmic and hardness results on three variants of MinECC for hypergraphs.", "essential_references_not_discussed": "Yes, several key related works have been cited properly in this paper.", "other_strengths_and_weaknesses": "S1. The theoretical analyses are solid, and the conclusions are rich.\n\nW1. I am not sure how many new technical contributions are developed, especially compared with (Veldt 2023). LP seems to be the common starting point for ECC algorithms in each prior work. Randomized rounding and global color ordering techniques have also been used. I understand that the two problems MaxECC and MinECC are different from the perspective of approximation algorithm, but I am not clear what the essential difference is when the same techniques are used for both of them.\n\nW2. I am not clear for the motivation and practical significance of the variant problems, or they are just in a mathematical sense.", "other_comments_or_suggestions": "1. It’s better to introduce more about the benchmark hypergraphs from the references (Veldt, 2023; Amburg et al., 2020), especially when they are used for the variants of the ECC, as such datasets are not very common after all. The information in Table 2 is insufficient.\n2. Line 411, Column 1, “Table 4” should be “Table 1”.", "questions_for_authors": "1. Can you give a comparison with the techniques that are used in (Veldt, 2023)? See W1 for more details on this question.\n2. Is there any practical example to demonstrate the significance of the variant problems of ECC?\n3. Can you explain more about the benchmark datasets and your manipulation on them for your experiments?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "No ethical review concern."}}, {"review_id": "Ffr6uGYqiZ", "reviewer": "Reviewer_LJar", "summary": "The submission provides a range of algorithmic and complexity-theoretic contributions to the Edge-Colored Clustering problem, which has been shown to have several applications in the general area of ML.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the helpful feedback on our manuscript. With regards to the motivation please see our response to the reviewer Tzam for details on our motivation for these variants. \n\nFurthermore, we agree that some sections are quite dense on results and sparse on details. We wished to provide more details and a less terse write-up (in particular, a more comprehensive introduction), but due to the page limit we ended up having to push many results to the appendix. We decided it is better to include all results, since there are readers who care about them (e.g., the parameterized complexity results). If the paper is accepted, we plan to use the extra 1 page of space to address these exact concerns you are raising (which we agree with). In particular, an extra page of space will allow us to provide a fuller introduction and overview of our results, provide needed background on parameterized complexity for a broad audience, and fill in some other details that are dense in the current manuscript. \n\nFinally to answer the question you posed, this is answered for Lp-norm ECC by our hardness result for the special case of Color-Fair MaxECC (see Section 3.2). One could argue that Color-Fair MaxECC is in fact more natural than Color-Fair MinECC in some settings (to answer part of your question). However, Theorem 3.3 implies that it is NP-hard to approximate this objective to within any factor even in graphs (in fact, just paths). Hence, as you wondered, “results for such a formulation are more elusive”. Regarding Protected Color ECC, we agree that a maximization variant could also be interesting and our hardness results do not rule out approximations for bounded hyperedge sizes. This is an interesting direction for future work, but as of yet we have not established any results.", "claims_and_evidence": "Yes, all claims are supported by evidence (primarily proofs), although most of this is deferred to the appendix.", "methods_and_evaluation_criteria": "The primary methods used are theoretical proofs, with some supporting implementations.", "theoretical_claims": "I did not check the details of all proofs, but those I did see seemed reasonably well-written and problem-free.", "experimental_designs_or_analyses": "The experiments only have a minor, supporting role and seemed problem-free.", "relation_to_broader_scientific_literature": "The key contributions are related to broader scientific literature.", "essential_references_not_discussed": "N/A.", "other_strengths_and_weaknesses": "While the problem studied in this submission is graph-theoretical in nature, it is well-motivated and has a sufficient footprint in the machine learning community - in fact, there are several algorithmic-theory papers on the topic that appeared in recent ICML and NeurIPS conferences. In terms of technical contribution, the submission is very strong and exceeds what I would expect from an average theoretical ICML paper. \n\nFor MaxECC, the results include the first \"general\" approximation algorithm that is a constant-factor approximation for each hyperedge size, but also an improved polynomial-time approximation algorithm for the prominent and previously studied graph variant (i.e., the case of hyperedge size 2). I believe the latter provides great \"added value\" to the paper: on its own this result might not be of sufficient interest to the ML community (or even the TCS community for that matter), but it rounds up the paper's contributions for MaxECC very nicely.\n\nIn the second part of the submission, the authors turn to MinECC. While approximation algorithms for that problem were known, the authors introduce two fair/balanced variants of that problem and provide a range of algorithmic results for these (including not only novel approximation algorithms, but also parameterized algorithms and complexity-theoretic lower bounds).\n\nIn the third part of the submission, the authors support their theoretical investigation with a range of experiments. As the authors correctly state, these are only meant to have a \"supporting role\" and should not be seen as the main results; still, I believe they form a nice touch that complements the rest of the submission.\n\nAs can be seen from the text above, overall I view the submission's contributions very positively and would be happy to support acceptance. However, there are also some weaknesses that need to be mentioned:\n1) While the motivation for MaxECC is clear, the motivation for the two new variants of MinECC is weaker - there are no references for this or similar formulations of the problem, and the variants are essentially \"made up\".\n2) The submission attempts to convey too many results, which unfortunately spreads the story too thin and  makes the writeup rather unfocused. To be clear: I personally do not think that the inclusion of more results should be seen as a drawback on its own, but the writeup needs to be very careful to still present a coherent picture that is accessible to a reasonable fraction of the ICML community. As it stands, the paper is so dense that the introduction cannot even cover all of the individual results proved or even the individual problem variants studied. This is nicely illustrated, e.g., in the following sentence near the end of the introduction:\n\"Our results also include several parameterized complexity and hardness results for COLOR-FAIR MINECC and a related maximization variant where the goal is to maximize the minimum number of edges of any one color that are satisfied.\"\n\nNote that the majority of the readers may not be aware of parameterized complexity theory, and so in its current state the submission might be fairly inaccessible to them (in fact, it does not even introduce parameterized complexity in the preliminaries). Later in the paper, the writeup even mentions significantly more advanced notions such as (slim) treecut-width or cutwidth... I understand that it makes no sense to define these just to have them briefly mentioned, but there should at least be a reference to point interested readers to some literature.\n\nOverall, I have a very high opinion of the paper's results and technical contributions, but given these weaknesses I personally see this more as a solid \"accept\" than a \"strong accept\".\n\n## Update after rebuttal\nThank you for the responses; I maintain my score.", "other_comments_or_suggestions": "N/A.", "questions_for_authors": "You introduce two novel MinECC variants that take into account fairness/balance aspects (Lp-Norm MinECC and Protected-Color MinECC) and provide some nice results for both of these. But on a higher level, I wonder why it makes sense to have the fairness part focus on MinECC even though the first part (which is better linked to previous work) focuses exclusively on MaxECC. Maybe the authors could comment on this discrepancy - is it because there's no nice \"natural\" formulation of fair MaxECC, or is it because getting results for such a formulation are more elusive?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper makes interesting progress on a clustering-like problem. Here is one basic problem that receives much attention in the paper. We are given a hypergraph H = (V, E), i.e., a set family where each member of E (i.e., each “hyperedge” or “edge”) is a subset of the set of “vertices” V; we also have a non-negative weight for each e in E (note again that e is a hyperedge). Each hyperedge is also given a “color” c from the range {1, 2, …, k}. The goal is to assign each vertex v in V a color from the same range {1, 2, …, k}, so that the weighted sum of “satisfied” hyperedges---those e in E for which each of e’s elements gets the same color as e---is maximized. Parametrizing by the “dimension”---maximum size of a hyperedge---r of H, the paper develops good approximation algorithms with approximation ratio a function of r for this problem by a novel randomized rounding scheme to the natural linear-programming relaxation of the problem. Various improvements and additional results are also developed: e.g., a related minimization problem, the useful special case r = 2 (where H is a graph), and “fair” versions. 

I know several rounding theorems and their subtleties and was surprised positively by the nice rounding scheme in the paper. It will likely have further consequences. 

The paper is in the area of “fair combinatorial optimization” and although connected to ML through clustering, the fit with ICML is not strong, and nor is the fit absent.
Decision: Accept (poster)