Answer: —
Theorem 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe number of messages and memory required by ODPOP is O(dw). PROOF. By construction, all messages in ODPOP are linear in size. Regarding the number of messages: 1. the DFS construction phase produces a linear number of messages: 2 × m messages (m is the number of edges); 2. the ASK/GOOD phase is the analogue of the UTIL phase in DPOP. The worst case behavior of ODPOP is to send sequentially the contents of the UTIL messages from DPOP, thus generating at most dw ASK/GOOD message pairs between any parent/child node (d is the maximal domain size, and w is the induced width of the problem graph).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(q\) meetings with finite timeslot domains, a support list of \(\tau\) employee types with rational masses \(\mu_t\) summing to one, each type’s attended meetings \(M_t\) and utility tables \(u_{t,e}(s)\), and the induced pairwise non-overlap constraints, compute a feasible schedule \(z\) maximizing \(U_\mu(z)=\sum_t \mu_t\sum_{e\in M_t}u_{t,e}(z_e)\); determine exact distributed message and memory bounds in terms of \(q,d,w,\tau,L\).
A society is given by its support: the list of the \(\tau\) employee types with positive binary-rational masses \(\mu_t\), with \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m=q\geq1\) meetings, each occupying one common timeslot, with explicitly listed nonempty domains \(D_e\) and \(d=\max_e|D_e|\). Type \(t\) attends \(M_t\subseteq\{1,\ldots,q\}\); every meeting has an attendee, and each table entry \(u_{t,e}(s)\) is a signed binary rational.
A schedule assigns one shared time \(z_e\in D_e\) to every meeting; feasibility requires \(z_e\neq z_f\) whenever distinct meetings \(e,f\) belong to some \(M_t\). Meetings cannot be cancelled, and masses do not permit splitting meetings or relaxing conflicts.
The optimization problem is to maximize \(U_\mu(z)=\sum_t\mu_t\sum_{e\in M_t}u_{t,e}(z_e)\), or report infeasibility; its decision version asks whether a feasible schedule has \(U_\mu(z)\geq B\), for a binary-rational threshold \(B\). Any maximizing schedule is acceptable when utilities tie.
For distributed execution, use one virtual agent with variable \(x_{t,e}\) for each attendance pair, holding its weighted unary table \(\mu_tu_{t,e}\). Hard constraints impose inequality within each type and equality between all copies of the same meeting.
Let \(G\) be this virtual-variable constraint graph, \(N=\sum_t|M_t|\), and \(a=|E(G)|\). A supplied rooted DFS forest defines \(\operatorname{Sep}(v)\) as the ancestors adjacent to \(v\) or its descendants, and \(w=\max_v|\operatorname{Sep}(v)|\).
Agents initially know their domains, incident hard constraints, and forest labels; communication uses reliable point-to-point messages along \(G\). Count messages, message bits, and peak local and aggregate memory bits, including local input and stored messages. Let \(L\) be the total binary input length; state running times and resource bounds in \(m=q,\tau,L,d,w\).
Is the decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
If it is \(\mathrm{NP}\)-hard, is the mass version FPT parameterized by \(w\), with \(d\) unrestricted?
What tight worst-case message-count, message-bit-size, and local and aggregate memory bounds can exact distributed algorithms achieve in this model?
Known discrete results: [ODPOP](https://jmvidal.cse.sc.edu/library/petcu06a.pdf) gives width-dependent bounds, with its proof counting \(O(a+Nd^w)\) messages and reporting \(O(d^w)\) stored-entry memory; these are not polynomial bounds for unrestricted \(w\). [Distributed multi-event scheduling](https://www.cs.cmu.edu/~mberna/mrrg/papers/RealWorldDCOP.pdf) is stated to be \(\mathrm{NP}\)-hard.
Related [List Coloring](https://sites.cs.ucsb.edu/~daniello/papers/EqColoring.pdf) is \(\mathrm{W}[1]\)-hard parameterized by treewidth; that parameter is distinct from the supplied DFS separator width \(w\). No result explicitly treating this normalized mass input and distributed bit-cost model was located.
The decision problem is $\mathrm{NP}$-complete, already with $d=3$ and zero utilities. Under the pairwise equality graph specified below, exact optimization is FPT parameterized by $w$, even when $d$ is unrestricted.
For distributed execution, I prove explicit upper bounds, repair the serialization accounting, and establish matching worst-case bounds for several resources. In particular, total communication can be bounded by $O(\min(m,\tau)I)$ bits, where $I$ is the actual distributed input size, and this dependence is attained on a family with $w=1$ and $d=2$.
The complete joint resource tradeoff remains open. Accordingly, the overall result is partial.
I interpret “equality between all copies of the same meeting” as including an equality edge between every pair of copies. Thus both the variables belonging to one type and the copies of one meeting form cliques. All claims involving $w$ use this graph representation.
Write
$$
h_t=|M_t|,
\qquad
k_e=|\{t:e\in M_t\}|,
\qquad
N=\sum_t h_t.
$$
Every meeting has an attendee, so
$$
m\leq N\leq m\tau.
$$
All arithmetic below is exact. Let $Q$ be the product of the denominators of the input masses, utility entries, and threshold. Its binary length is $O(L)$. The denominator of each weighted utility $\mu_tu_{t,e}(s)$ divides $Q$. Consequently, every schedule utility, and every partial sum of its weighted utilities, has a reduced numerator and denominator of length
$$
b=O(L+\log(N+1)).
$$
Indeed, conversion to denominator $Q$ produces numerators with $O(L)$ bits, and summing at most $N$ terms adds at most $O(\log(N+1))$ bits. Time labels and identifiers also have length $O(b)$.
This establishes polynomial bit complexity for the verification and preprocessing operations used below.
A certificate specifies one explicitly listed domain entry for every meeting.
The verifier checks domain membership, checks that the assigned times are distinct within every $M_t$, and computes the utility exactly before comparing it with $B$. The certificate length and these operations are polynomial in $L$, by the arithmetic bounds above.
The source problem is proper three-colorability of finite simple undirected graphs, which is $\mathrm{NP}$-complete. This is the graph three-colorability result established by [Garey, Johnson, and Stockmeyer](https://doi.org/10.1016/0304-3975%2876%2990059-1).
Given a nonempty graph $H=(V,E)$, construct:
Every meeting has an attendee. The attendance sets are distinct.
Let $\tau$ be the resulting number of types and let
$$
r=\lceil\log_2\tau\rceil.
$$
Give the first $\tau-1$ types mass $2^{-r}$ and the last type mass
$$
\frac{2^r-\tau+1}{2^r}.
$$
These masses are positive dyadic rationals and sum to one. The formula also works for $\tau=1$. Their total encoding length is $O(\tau\log(\tau+1))$.
Two meetings conflict exactly when their vertices are adjacent in $H$. Hence a feasible schedule exists exactly when $H$ is three-colorable. Every feasible schedule has utility zero, so feasibility is equivalent to the constructed decision question.
The society, virtual graph, and a DFS forest can all be constructed in polynomial time.
Therefore the decision problem is $\mathrm{NP}$-complete. Membership in $\mathrm{P}$ would imply $\mathrm{P}=\mathrm{NP}$.
The key point is that the virtual graph bounds both attendance sizes and the number of copies of each meeting.
Lemma 1. Every clique of $G$ has at most $w+1$ vertices.
Proof. In an undirected DFS forest, the endpoints of every edge are comparable in the ancestor order. Thus the vertices of a clique lie on one ancestor chain.
Let $v$ be its deepest vertex. Every other clique vertex is an ancestor adjacent to $v$, and therefore belongs to $\operatorname{Sep}(v)$. The clique has at most $w+1$ vertices. $\square$
Applying the lemma to the two kinds of cliques gives
$$
h_t\leq w+1,
\qquad
k_e\leq w+1.
$$
The inequality and equality neighbors of $x_{t,e}$ are disjoint, so
$$
\deg_G(x_{t,e})=h_t+k_e-2\leq 2w,
\qquad
a\leq Nw.
$$
Let $H_{\mathrm{meet}}$ be the graph on meetings in which two meetings are adjacent exactly when they occur together in some attendance set. Write $\delta_e$ for its degree at $e$. Then
$$
\delta_e
\leq \sum_{t:e\in M_t}(h_t-1)
\leq k_ew
\leq w(w+1).
$$
Repeated counting of a conflicting meeting only enlarges this upper bound.
Define the aggregate unary utility
$$
F_e(s)=\sum_{t:e\in M_t}\mu_tu_{t,e}(s).
$$
Then
$$
U_\mu(z)=\sum_e F_e(z_e).
$$
For each meeting $e$, retain the
$$
\min\{|D_e|,\delta_e+1\}
$$
times with highest $F_e(s)$, breaking ties arbitrarily. Denote the retained domain by $D'_e$.
Lemma 2. The reduced instance preserves feasibility and the optimum value.
Proof. Start with any feasible schedule. If meeting $e$ uses a discarded time, its retained domain has exactly $\delta_e+1$ values.
Its neighbors use at most $\delta_e$ distinct times. Therefore some retained time is unused by every neighbor. Replacing $e$'s current time by that time preserves feasibility. Its utility does not decrease because every retained value has utility at least that of every discarded value.
Process the meetings using discarded values successively. Every replacement preserves feasibility and does not decrease total utility. It also places that meeting permanently within its retained domain.
Thus every original feasible schedule can be converted into a reduced-domain feasible schedule of at least equal utility. Conversely, every reduced-domain schedule is an original schedule. These observations prove both feasibility preservation and equality of optimum values. $\square$
After polynomial-time preprocessing, every domain therefore has size at most
$$
r=\min\{d,w(w+1)+1\}.
$$
Signed utilities and utility ties cause no difficulty in this argument.
For a virtual variable $v$, write $S_v=\operatorname{Sep}(v)$ and let $C(v)$ be its children. Its unary utility is denoted by $f_v$.
Two DFS properties are used:
$$ S_c\subseteq S_v\cup\{v\}. $$
For the second property, an ancestor of $c$ adjacent to its subtree is either $v$, or an ancestor of $v$ adjacent to a descendant of $v$.
For an assignment $\alpha$ to $S_v$, let $T_v(\alpha)$ be the maximum unary utility in $v$'s subtree, subject to $\alpha$ and all hard constraints having at least one endpoint in that subtree. Infeasibility is represented by a separate flag, written as $-\infty$ in the recurrence:
$$
T_v(\alpha)=
\max_{\substack{s\in D'_v\\
s\text{ satisfies all constraints}\\
\text{from }v\text{ to its ancestors}}}
\left[
f_v(s)+
\sum_{c\in C(v)}
T_c\!\left(
(\alpha\cup\{v\mapsto s\})|_{S_c}
\right)
\right].
$$
An empty maximum, or a sum containing an infeasible child entry, is infeasible.
Correctness. Once $\alpha$ and $v=s$ are fixed, distinct child subtrees have no constraints between them. Their optima therefore add. Constraints from $v$ to ancestors are checked explicitly, and each remaining hard edge is checked at its deeper endpoint in a child subproblem. Induction from the leaves establishes the stated table semantics.
At each root the separator is empty, so its table gives its component optimum. Storing a maximizing value for each feasible entry permits reconstruction in a downward pass. Equality constraints ensure that the reconstructed copies agree on each meeting's time.
If domains have size at most $K$, a table has at most $K^w$ entries. A conservative bit-time bound, including projections onto child separators and exact rational arithmetic, is
$$
O\!\left((N+a)(w+1)K^{w+1}b^3\right),
$$
apart from polynomial preprocessing.
With $K=r$ and $a\leq Nw$, this gives
$$
\operatorname{poly}(L)+
O\!\left(
m\tau(w+1)^2
[w(w+1)+1]^{w+1}b^3
\right).
$$
Thus both optimization and decision are FPT parameterized by $w$, with unrestricted $d$.
For $w=0$, every virtual vertex is isolated. Each meeting has one copy, and choosing its best time solves the instance without communication.
The related [List Coloring hardness theorem](https://sites.cs.ucsb.edu/~daniello/papers/EqColoring.pdf) concerns treewidth of the coloring graph. Here the additional equality cliques bound meeting degrees and enable Lemma 2.
The following conventions make the resource statements precise.
Let $I_v$ be the initial input bits at agent $v$, including its weighted unary table, domain, incident constraints, and forest labels. Define
$$
I=\sum_v I_v,
\qquad
I_{\max}=\max_v I_v.
$$
These quantities include duplication across agents.
For numerical bounds, use fixed-width identifiers and a compact forest record containing the agent's parent, ordered children, depth, root identifier, and the depths of its incident neighbors. Because endpoints of a DFS edge are ancestor-comparable, comparing depths identifies ancestor neighbors.
With explicitly recorded incident constraints, this representation satisfies
$$
I_{\max}=O((d+w+1)b),
\qquad
I=O(N(d+w+1)b)
=O(m\tau(d+w+1)b).
$$
If neighbor depths are initially unavailable, exchanging them adds $O(a)$ messages and $O(a\log(N+1))$ bits. The separator-protocol message counts below assume they are supplied.
The gathering protocols only require the parent and child lists.
The communication lower bounds apply to deterministic, event-driven protocols that terminate under arbitrary reliable message delays.
Charge the complete self-delimiting packet encoding: payload, length information, and control fields. Every packet has positive charged length, including a packet with an empty payload. Delays and silence convey no information. Stored packets count toward memory.
This convention is necessary: with uncharged empty packets, packet counts could encode information while consuming zero charged payload bits.
Each agent outputs its assigned value, and each component root reports its optimum score or infeasibility. A passive external readout combines component results and compares their summed score with $B$.
A designated agent cannot report the global decision using only communication along a disconnected $G$. For example, take two isolated meetings, each with a singleton domain and one attending type of mass $1/2$. Keep the first utility zero and change the second utility between $2$ and $-2$. At threshold zero, the global answer changes while the first agent's entire history remains unchanged.
Thus a single global report requires an external readout or communication between components.
For domain bound $K$, put
$$
R_K=K^w+wK.
$$
Use four passes along the supplied forest:
If the forest has $c$ components, the bounds are:
| Resource | Upper bound |
|---|---:|
| Packet count | $O(N-c)$ |
| Maximum packet bits | $O(R_Kb)$ |
| Total transmitted bits | $O((N-c)R_Kb)$ |
| Peak local memory bits | $O(I_{\max}+((2w+1)K^w+wK)b)$ |
| Peak aggregate memory bits | $O(I+NR_Kb)$ |
Each agent has at most $2w$ children, explaining the local child-table term. Globally, each table is retained at its originating agent and at most once at its parent. Separator-domain dictionaries contribute $O(NwKb)$ bits.
Take $K=d$ for execution without domain reduction.
For each meeting, choose its smallest-identifier copy as leader. Its equality clique provides direct communication with every other copy.
The leader solicits copies one at a time. A solicited copy returns:
The leader adds the vector to its aggregate and inserts the neighbor identifiers into a set. It requests the next vector only after processing the current reply. Finally it computes and broadcasts $D'_e$.
This uses $O(N-m)$ requests, replies, and broadcasts. The solicitation rule ensures that only one incoming vector per leader can be outstanding.
The preprocessing bounds are
$$
O(N)\text{ packets},
\qquad
O(N(d+w)b)\text{ transmitted bits},
$$
and peak local working memory
$$
O(I_{\max}+(d+w^2)b).
$$
The vector accumulator has $d$ entries, and the conflict set has at most $w(w+1)$ identifiers.
Combining preprocessing with separator tables on the reduced domains gives:
| Resource | FPT protocol upper bound |
|---|---:|
| Packet count | $O(N)$ |
| Maximum packet bits | $O((d+w+R_r)b)$ |
| Total transmitted bits | $O(N(d+w+R_r)b)$ |
| Peak local memory bits | $O(I_{\max}+(d+w^2+(2w+1)r^w+wr)b)$ |
| Peak aggregate memory bits | $O(I+N(d+w+R_r)b)$ |
Substitution of $N\leq m\tau$ gives bounds in the requested parameters. Its computation time has the FPT bound proved in Section 3.
Sending an explicit separator assignment with every table row can add a factor of $w$ to total bits. The following encoding avoids that cost.
Sender and receiver first agree on the separator order and canonical domain orders. They enumerate rows lexicographically. The sender transmits one utility or infeasibility entry and waits for an acknowledgment before transmitting the next. The receiver maintains the row counter locally, so row assignments and row indices need not be transmitted.
Separator metadata, domain values, and reconstruction contexts are likewise sent item by item.
The resulting bounds are
$$
O((N-c)R_K)\text{ packets},
\qquad
O(b)\text{ maximum packet bits},
$$
and
$$
O((N-c)R_Kb)\text{ total transmitted bits}.
$$
Memory remains within the batched bounds. Stop-and-wait flow control preserves the agreed order even if the underlying transport may reorder messages.
The [ODPOP proof](https://jmvidal.cse.sc.edu/library/petcu06a.pdf) counts $O(a+Nd^w)$ messages and discusses memory in stored entries. Such entry counts require additional accounting for rational values, assignments, dictionaries, and initial input before becoming bit bounds.
Solicit and gather each component's input at its root along the supplied forest. The root enumerates meeting schedules, computes an optimum, and distributes the assignments.
A constant number of packets traverses each forest edge, yielding
$$
O(N-c)\text{ packets}.
$$
Serial solicitation and deletion of temporary packets after forwarding keep only a constant number of temporary copies of each input record. Root enumeration stores the input, a current schedule, a best schedule, and exact arithmetic workspace, all within $O(I)$ aggregate memory.
The bounds are
$$
O(I)\text{ maximum packet bits},
\qquad
O(NI)\text{ total transmitted bits},
$$
and
$$
O(I)\text{ peak local and aggregate memory bits}.
$$
Enumeration takes
$$
d^m\operatorname{poly}(I)
=
d^m\operatorname{poly}(m,\tau,L)
$$
bit operations. There is no finite elapsed-time bound under arbitrarily delayed reliable delivery.
Since the initial input alone occupies $I$ bits, the optimal unrestricted-computation aggregate-memory bound is $\Theta(I)$.
Let $J$ be the bipartite incidence graph with type vertices, meeting vertices, and one edge for every attendance pair. Then
$$
G=\operatorname{Line}(J).
$$
Indeed, two attendance pairs are adjacent in $G$ exactly when they share a type or a meeting.
Put
$$
h=\min(m,\tau).
$$
Lemma 3. Every component of $G$ has diameter at most $2h$.
Proof. Consider two attendance edges in one component of $J$. Choose the type endpoint of the first and the meeting endpoint of the second.
A simple path between these endpoints alternates between the two sides of $J$. Its length is odd and at most $2h-1$. Prepending the first attendance edge and appending the second gives a walk in the line graph of length at most $2h$. Repeated consecutive edges can be deleted. Hence the line-graph distance is at most $2h$. $\square$
A BFS tree can be constructed using logical rounds synchronized over the supplied forest. In each round:
If the component diameter is $D$, distances stabilize within $D$ rounds; one additional round detects stability. Registration and acknowledgments establish the BFS child lists.
This uses
$$
O((D+1)(N+a))
$$
packets of $O(\log(N+1))$ bits. Under the explicit fixed-width input representation, these construction bits are $O((D+1)I)$.
Now gather and distribute over the BFS tree. Each input or output record traverses at most $D$ edges. Therefore the combined protocol achieves
| Resource | BFS gathering upper bound |
|---|---:|
| Packet count | $O(h(N+a))$ |
| Maximum packet bits | $O(I)$ |
| Total transmitted bits | $O(hI)$ |
| Peak local memory bits | $O(I)$ |
| Peak aggregate memory bits | $\Theta(I)$ |
Using $a\leq Nw$, the packet count is $O(hm\tau(w+1))$. The total-bit bound in the requested parameters is
$$
O\!\left(
\min(m,\tau)\,m\tau(d+w+1)b
\right).
$$
Computation still takes $d^m\operatorname{poly}(m,\tau,L)$ bit operations.
The gathering protocol proves an $O(N)$ upper bound. The following family establishes an $\Omega(N)$ lower bound and also repairs the dependence on $m\tau$.
Take $m=\tau\geq3$. Type $t$ attends every meeting except $t$. All domains are $\{1,\ldots,m\}$, all utilities are zero, and use the positive normalized masses from Section 2.
Attendance sets are distinct, and
$$
N=m(m-1)=\Theta(m\tau).
$$
Every pair of meetings conflicts: for distinct meetings $e,f$, some type excludes neither. Thus feasible schedules are precisely permutations of the $m$ times.
Fix a terminating execution and an agent's irrevocable output for meeting $e_0$. Suppose another agent $v$, representing meeting $e$, has been incident to no packet before this output.
Change only $v$'s unary utility to give a positive bonus at:
Every optimum of the modified instance assigns $e$ its bonus time. Hence every optimum changes $e_0$'s original output.
Delay all new packets incident to $v$ until after that output. Because the original prefix had no packets incident to $v$, every other agent can retain its original history. The output is therefore unchanged and incorrect, contradicting exactness.
Consequently, all $N-1$ other agents must have been incident to a packet. Each packet involves at most two agents, so at least $(N-1)/2$ packets are necessary.
Thus:
These are worst-case statements; isolated components require no communication.
Let $\tau=2^r$ with $r\geq1$, and take meetings
$$
e_0,e_1,\ldots,e_\tau.
$$
For each $i$, type $i$ attends exactly $e_{i-1}$ and $e_i$ and has mass $1/\tau$. All domains are $\{0,1\}$.
The virtual graph is a path: inequality edges join the two variables of each type, and equality edges join the two copies of each internal meeting. Therefore
$$
N=2\tau,
\qquad
w=1,
\qquad
d=2.
$$
There are exactly two feasible schedules:
$$
A:\ z_{e_j}=j\bmod 2,
\qquad
C:\ z_{e_j}=1-(j\bmod 2).
$$
Let privately held integers $X,Y$ satisfy
$$
2^{\beta-1}\leq X,Y<2^\beta.
$$
All utility entries are zero except at the two endpoint agents. At the first endpoint, set its utilities at the values used by $A$ and $C$ to $\tau X$ and $-\tau/2$, respectively. At the last endpoint, set the corresponding utilities to $-\tau Y$ and $0$.
Then
$$
U_\mu(A)=X-Y,
\qquad
U_\mu(C)=-\frac12.
$$
Since $X-Y$ is an integer, the optimum is unique: it is $A$ exactly when $X\geq Y$. The decision answer at threshold zero has the same condition.
For completeness, the argument must use one input distribution for all cuts. Summing worst-case bounds attained on different inputs would not suffice.
Choose $X=Y$ uniformly from the $2^{\beta-1}$ allowed values. For each such input, fix a terminating execution with FIFO delivery in each direction. These executions are permitted by reliable delivery.
Fix a path cut. Its two sides contain $X$ and $Y$, respectively. Record, separately on each side, the sequence of sends and receives across the cut, including full framed packet contents. Both records together have an injective binary encoding of length at most a constant times the charged cut communication plus a constant: each packet is recorded twice, and send/receive markers have constant size.
The diagonal inputs have distinct boundary records. Suppose $(X,X)$ and $(Y,Y)$, with $X<Y$, had the same records. Combine the left-side local execution from $(X,X)$ with the right-side local execution from $(Y,Y)$.
Their boundary actions match. FIFO pairing and the local action orders give the same acyclic boundary dependencies as the original execution, so the combined local executions form an admissible execution on $(X,Y)$. No clock or delay information is used.
The left endpoint reproduces its diagonal output, selecting schedule $A$. But $(X,Y)$ uniquely requires $C$. This contradiction proves distinctness.
For $2^{\beta-1}$ distinct binary strings, at least a constant fraction have length proportional to $\beta$: there are fewer than $2^{\beta-2}$ strings of length less than $\beta-2$. Consequently, expected charged communication across this cut is $\Omega(\beta)$.
The same diagonal distribution applies to every cut. If $C_j$ denotes communication across cut $j$, linearity of expectation gives
$$
\mathbb E\!\left[\sum_{j=1}^{N-1}C_j\right]
=
\sum_{j=1}^{N-1}\mathbb E[C_j]
=
\Omega(N\beta).
$$
Every packet on the path crosses exactly one cut. Hence some single diagonal input and its fixed execution require
$$
\Omega(N\beta)
$$
total transmitted bits.
In this family,
$$
L=\Theta(\beta+N\log(N+1)),
\qquad
I=\Theta(\beta+N\log(N+1)).
$$
Taking $\beta\geq N\log(N+1)$ yields
$$
\Omega(NL)=\Omega(NI)
$$
total communication, already with $w=1$ and $d=2$.
Furthermore,
$$
h=\min(m,\tau)=\tau=N/2.
$$
Thus the BFS upper bound $O(hI)$ has a matching $\Omega(hI)$ family. This establishes tightness as a uniform worst-case bound in $h$ and $I$.
Suppose a protocol uses at most $CN$ packets on every input. On the hard execution just proved, its total communication is $\Omega(NI)$. Some packet must therefore have $\Omega(I)$ bits.
Gathering achieves $O(N)$ packets with maximum size $O(I)$. Hence under an $O(N)$ packet budget, the worst-case maximum packet size is $\Theta(I)$.
Without a packet-count restriction, constant-size packets suffice. Serialize any self-delimiting logical packet into fixed-size bit packets, using acknowledgments to preserve order. This increases packet count proportionally to transmitted bits and changes total bits only by a constant factor.
Thus the unrestricted minimum worst-case maximum packet size is $\Theta(1)$ under the charged-framing convention.
The results establish the following, for the stated deterministic framed model and componentwise output convention:
| Resource | Proven conclusion |
|---|---|
| Packet count, unrestricted packet size | Worst-case $\Theta(N)$; dependence $\Theta(m\tau)$ is attained |
| Maximum packet size, unrestricted count | $\Theta(1)$ |
| Maximum packet size with $O(N)$ packets | Worst-case $\Theta(I)$ |
| Total transmitted bits | $O(\min(m,\tau)I)$, with a matching family |
| Peak aggregate memory | $\Theta(I)$ with unrestricted computation |
| Peak local memory | Lower bound $I_{\max}$; gathering upper bound $O(I)$; separator bounds in Section 5 |
The FPT protocol supplies additional guarantees on computation and communication as functions of $w$. The input-proportional gathering protocols show that exponential separator-table storage is not a universal memory lower bound for exact algorithms.
What remains unresolved is the optimal simultaneous resource tradeoff, particularly peak local memory for a prescribed input placement and the cost of simultaneously imposing small packet counts, small packets, and FPT computation. The matching families above establish several worst-case optima, but do not determine the full dependence for every fixed tuple $(m,\tau,L,d,w)$.
⟨structured verdict parsed — rendered above⟩
The output establishes the decision problem’s $\mathrm{NP}$-completeness and an FPT algorithm parameterized by $w$, under its explicitly stated equality-clique interpretation. Its distributed results provide substantial upper bounds and several matching worst-case families. However, it does not finish the requested tight resource classification, particularly for peak local memory and dependence on the requested parameters. The appropriate overall status is partial.
I found no false central step in the complexity proofs or the communication lower-bound constructions.
1. Exact arithmetic and input size
The arithmetic argument in Section 1 is sound.
The product $Q$ includes the denominators of both each mass and each utility entry. Consequently, the denominator of their product divides $Q$, including when the two denominators share factors. Since the sum of the input denominators’ binary lengths is bounded by $L$, the binary length of $Q$ is $O(L)$.
Converting a weighted utility to denominator $Q$ requires a numerator of $O(L)$ bits. Summing at most $N$ such terms increases this bound by $O(\log(N+1))$. Thus the stated bound
$$
b=O(L+\log(N+1))
$$
is valid for finite table values and schedule utilities. The separate infeasibility flag avoids treating $-\infty$ as an ordinary rational.
No sign restriction is used, so signed utilities are handled correctly.
2. Membership in $\mathrm{NP}$
The certificate and verification procedure are sufficient:
The verifier checks the actual shared meeting choices, so it does not inadvertently allow independently scheduled copies or mass splitting.
3. Hardness reduction
The reduction in Section 2.2 is correct.
An edge-attendance type imposes exactly the corresponding graph-coloring inequality. Singleton types ensure that isolated vertices also have attendees without introducing conflicts. Distinct edges of a simple graph give distinct attendance sets, and the singleton sets do not duplicate the edge sets.
The masses satisfy all required conditions. With
$$
r=\lceil\log_2\tau\rceil,
$$
the last numerator satisfies
$$
2^r-\tau+1\geq1,
$$
and the numerators sum to $2^r$. For $\tau=1$, the construction gives the single mass $1$. Their encoding length is polynomial.
Zero utilities and $B=0$ make the decision answer equivalent to feasibility. Domain size is exactly $3$. The society and its virtual graph have polynomial size, and a DFS forest can be supplied in polynomial time.
The cited source supports the required graph three-colorability hardness result. [Garey, Johnson, and Stockmeyer](https://www.sciencedirect.com/science/article/pii/0304397576900591)
Conclusion: the claimed $\mathrm{NP}$-completeness is established.
4. Graph interpretation and structural bounds
The FPT proof explicitly assumes an equality edge between every pair of copies of a meeting. Its conclusions about $w$ are conditional on that representation.
Under this interpretation, Lemma 1 is correct: adjacent vertices in an undirected DFS forest are ancestor-comparable, so a clique lies on a single ancestor chain. Every other clique vertex belongs to the deepest vertex’s separator.
Therefore
$$
h_t\leq w+1,\qquad k_e\leq w+1.
$$
The two neighbor sets of $x_{t,e}$ are disjoint, yielding
$$
\deg_G(x_{t,e})=h_t+k_e-2\leq2w.
$$
The edge bound $a\leq Nw$ follows by summing degrees.
The meeting-conflict degree bound
$$
\delta_e\leq\sum_{t:e\in M_t}(h_t-1)\leq w(w+1)
$$
is also correct. Repeated conflicts only cause overcounting.
These deductions would require reconsideration for a sparse equality representation, but the prover does not claim otherwise. This is an explicit scope condition, not a hidden hypothesis.
5. Optimum-preserving domain reduction
Lemma 2 is correct.
If a schedule uses a discarded value at meeting $e$, then its retained domain contains exactly $\delta_e+1$ values. At most $\delta_e$ values are blocked by neighboring meetings. An available retained value therefore exists.
Its aggregate utility is at least that of the discarded value. Replacing the meeting preserves every conflict constraint and does not decrease the objective. Later replacements do not remove earlier meetings from their retained domains.
The two directions needed for optimum preservation are both supplied: original schedules can be converted without loss, and every reduced schedule remains an original schedule. The argument also preserves infeasibility and handles ties and signed utilities.
Thus the reduced domain bound
$$
r=\min\{d,w(w+1)+1\}
$$
is justified.
6. Separator dynamic programming and FPT running time
The recurrence has the stated semantics.
There are no edges between distinct DFS child subtrees. Moreover,
$$
S_c\subseteq S_v\cup\{v\}
$$
ensures that each child boundary assignment is available when evaluating the parent entry.
The recurrence checks constraints from $v$ to its ancestors. Constraints internal to child subtrees or from those subtrees to their ancestors are accounted for in the child tables. Constraints entirely outside the subtree are appropriately excluded.
The infeasibility convention, root evaluation, and reconstruction are consistent. Equality edges ensure agreement among meeting copies.
The time bound is conservative enough to cover table enumeration, child projections, constraint checks, and exact arithmetic. After domain reduction, the exponential factor depends only on $w$, while the remaining dependence is polynomial in the input size.
The separately discussed case $w=0$ is correct: there are no virtual edges, so each meeting has one copy and can be optimized independently.
The cited List Coloring result concerns treewidth of the coloring graph; it does not contradict this proof using additional structural restrictions on the virtual graph. [List Coloring source](https://sites.cs.ucsb.edu/~daniello/papers/EqColoring.pdf)
Conclusion: the FPT claim is established under the stated graph representation.
7. Distributed conventions and upper bounds
The accounting conventions are explicit and internally consistent:
The disconnected-graph example correctly shows why a designated agent cannot infer the global decision using only communication within its component. The external readout is an output convention; its cost is outside the reported communication along $G$.
The compact-label input bounds are valid for the representation the prover specifies. They should not be read as bounds for arbitrary, unnecessarily verbose forest labels.
The four separator passes justify linear packet count when tables are batched. Table sizes, separator-domain dictionaries, retained child tables, and reconstruction information are accounted for in the stated bounds.
The domain-reduction protocol correctly aggregates weighted utility vectors and conflict identifiers. Soliciting one copy at a time prevents an uncontrolled collection of large incoming vectors at a leader.
Lexicographic serialization with acknowledgments avoids transmitting a boundary assignment with every row. Its ordering argument also handles transport that does not preserve message order.
The distinction between stored-entry bounds and bit-memory bounds in the ODPOP discussion is appropriate. The cited paper does discuss width-dependent message and storage complexity. [ODPOP](https://jmvidal.cse.sc.edu/library/petcu06a.pdf)
8. Gathering and BFS gathering
The gathering bounds are justified with unrestricted local computation.
Serial subtree gathering can use a constant number of packets per forest edge while retaining only a constant number of temporary copies of input records. Exhaustive schedule enumeration requires input storage, current and best schedules, and exact arithmetic workspace; the claimed $O(I)$ aggregate memory is consistent with these requirements.
Since initial distributed input already occupies $I$ bits, the aggregate-memory conclusion $\Theta(I)$ follows.
The line-graph identity
$$
G=\operatorname{Line}(J)
$$
is valid under the equality-clique interpretation. The diameter proof correctly bounds an alternating simple path in $J$ and converts it to a walk in $G$.
The synchronized distance-label protocol supplies a BFS tree with the claimed round and communication bounds. Gathering over that tree charges each record at most the tree depth, yielding the upper bound
$$
O(\min(m,\tau)I)
$$
on total transmitted bits.
The absence of a finite elapsed-time guarantee under arbitrary reliable delays is correctly acknowledged.
9. Communication lower bounds
The linear packet-count construction is valid for exact optimization.
For $m=\tau\geq3$, every meeting pair conflicts, and feasible schedules are permutations. If another agent has not been incident to a packet before the selected agent’s irrevocable output, changing that agent’s unary utility can force a different optimal output at the selected meeting. Delaying communication incident to the changed agent preserves the other agents’ histories through that output. This contradicts exactness.
The resulting $\Omega(N)$ bound matches the unrestricted-packet-size gathering upper bound in the stated worst-case sense.
The path construction is also correct. It has
$$
N=2\tau,\qquad w=1,\qquad d=2,
$$
and exactly two feasible schedules. The endpoint utility calculation gives
$$
U_\mu(A)=X-Y,\qquad U_\mu(C)=-\frac12.
$$
Since $X-Y$ is integral, the optimum is unique and selects $A$ precisely when $X\geq Y$.
The boundary-record argument uses both sides’ ordered sends and receives, not merely an unordered packet transcript. Identical records permit the stated execution splice; the resulting mixed input contradicts the left endpoint’s reproduced output.
The same diagonal distribution is used for every cut. Therefore summing expected cut costs is legitimate and avoids the invalid operation of summing unrelated worst-case inputs.
For sufficiently large $\beta$, the encoding estimates give
$$
I=\Theta(L)=\Theta(\beta),
$$
so the resulting lower bound is $\Omega(NI)$ and hence $\Omega(\min(m,\tau)I)$ on this family.
The packet-size conclusion under an $O(N)$ packet budget follows by averaging. Constant-size serialization without a packet-count budget is also consistent with the stated framing convention.
These are valid matching families, not matching bounds for every fixed parameter tuple.
10. Blocking issue and minimum required completion
Major — Sections 7 and the concluding open points: the requested tight resource classification remains incomplete.
For peak local memory, the output gives the lower bound $I_{\max}$ and the gathering upper bound $O(I)$, without stating a matching characterization under a precise worst-case quantification. Its matching communication families likewise do not establish tight dependence on every requested parameter combination.
This is an acknowledged omission, not a refutation of the established results. An entire simultaneous tradeoff frontier need not be demanded merely because the prover mentions it. However, the requested individual tight resource bounds still need a clearly delimited final answer.
Minimum required completion:
The direction is promising: the complexity questions are resolved, and the distributed results constitute substantial genuine progress.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.