{"id":"8d178b1a-7c3a-4a55-a12f-1020dd765133","arxiv_id":"2411.15687","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper proves the symmetric offloading problem is NP-hard and claims a polynomial-time submodular-minimization solution under a communication-cost assumption, but the proof of the algorithmic claim is flawed.","lead":"This paper studies how to split computing tasks between nearby edge servers and distant cloud servers to minimize communication and computation costs. It proves the general version is NP-hard and claims that a natural cost assumption makes the problem easy, but that claim does not hold as stated.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 7 relies on an unstated condition l2 >= l1; Eq. (18)'s second term is l2 - l1, which the communication assumption does not constrain, so F can be non-submodular under the paper's stated assumptions.","rationale":"The reader's weakest-assumption analysis identifies exactly the load-bearing gap: Eq. (18) contains two nonnegativity claims, and only the first follows from the communication assumption. I verified the algebra: the second term is l2_{m,j} − l1_{m,j}, not something controlled by l4 ≤ l2, l3. A two-task counterexample satisfies the paper's assumption and violates the submodularity inequality, so Theorem 7 is demonstrably false. Because the polynomial-time result is the paper's main claimed contribution, the rejection is appropriate. The NP-hardness reduction appears mathematically sound and could stand as a separate contribution, but as presented the paper's central dichotomy is unsupported. The experiments are not decisive because they rely on SFO, which assumes submodularity; running SFO on a non-submodular function does not establish optimality. No alternative reading of Definition 1 or Eq. (18) repairs the gap: the proof simply needs a condition like l2 ≥ l1 for every edge, which appears nowhere in the model. I agree with the reader's verdict and see no reason to adjust it.","tokens_in":17549,"tokens_out":3622,"duration_ms":32081,"concrete_test":"Independently re-derive Eq. (18) and evaluate submodularity on the explicit two-task instance: T = ∅, zero node weights, one directed edge vm→vj with (l1,l2,l3,l4) = (100,1,1,0). Compute F(X) = C_total(V\\X,X) − C_total(V,∅) for X = ∅, {vm}, {vj}, {vm,vj}. Check whether F({vm}) − F(∅) ≥ F({vm,vj}) − F({vj}) holds. The values are −99 ≥ −1, which fails. If this test reproduces, Theorem 7 and Corollary 8 are false under the stated communication assumption, confirming that an additional condition such as l2 ≥ l1 would be needed for submodularity.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central algorithmic claim is that F(X) in Eq. (9) is submodular under the communication assumption, making Offloading-CommA and Offloading-LCCA polynomially solvable (Theorem 7 and Corollary 8). The proof derives Eq. (18): (F(A∪{vm})−F(A)) − (F(B∪{vm})−F(B)) equals a sum over j∈B\\A of [l(vm,vj)|_{Vcld=A∪{vm}} − l(vm,vj)|_{Vcld=B∪{vm}}] plus [l(vm,vj)|_{Vcld=B} − l(vm,vj)|_{Vcld=A}]. The first bracket is l3_{m,j} − l4_{m,j}, nonnegative by Definition 1. The second bracket is l2_{m,j} − l1_{m,j}; Definition 1 only requires l4 ≤ l2 and l4 ≤ l3, with no relation between l1 and l2. The proof asserts without justification that this second term is also nonnegative. The condition l2 ≥ l1 is not part of the communication assumption and is not stated anywhere. A two-task instance with no computation costs and a single directed edge (vm,vj) with (l1,l2,l3,l4) = (100,1,1,0) satisfies the communication assumption (0 ≤ 1, 1). For X⊆{vm,vj}, F({vm})−F(∅) = 1−100 = −99, while F({vm,vj})−F({vj}) = (0−100)−(1−100) = −1. Submodularity requires −99 ≥ −1, which is false. Thus Theorem 7 is false as stated, and Corollary 8 is unsupported. The NP-hardness reduction in Section III appears sound, but it does not rescue the main polynomial-solvability claim; without submodularity, the SMA algorithm has no optimality guarantee from the theory, and the experiments comparing SMA with ILP are not a substitute for a valid proof. The paper's central dichotomy — NP-hard without the assumption, polynomial with it — collapses at the algorithmic half.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the cost-driven task offloading problem in edge-cloud environments, where each task is assigned to either an edge or a cloud server and the total cost combines computation and communication costs. It introduces a 'communication assumption' (Definition 1) requiring intra-cloud communication costs l4_ij to be no larger than inter-partition costs l2_ij and l3_ij. The paper claims two main results: (i) the symmetric offloading problem is NP-hard via a reduction from MAX-CUT (Theorem 2), and (ii) under the communication assumption, the cost-increment function F(X) = C_total(V\\X, X) − C_total(V, ∅) is submodular (Theorem 7), so the offloading problem and its latency-constrained variant are polynomially solvable by submodular function minimization (Corollary 8). The paper also reports experiments comparing the proposed submodular-minimization algorithm (SMA) with an ILP baseline and a prior heuristic (HETO).","tokens_in":18003,"tokens_out":10167,"duration_ms":78759,"significance":"The NP-hardness reduction of Section III appears sound and, if correct, closes the open question stated in [15] about the symmetric case, which is a worthwhile contribution. The experimental methodology is also a strength: the paper validates its algorithm against an independent ILP solver and reports running times on SNAP and synthetic datasets. However, the central algorithmic claim is Theorem 7, and that claim is false under the stated assumptions; the proof requires an additional condition that is neither part of Definition 1 nor stated anywhere. Since Corollary 8 and the polynomial-solvability dichotomy depend on Theorem 7, the paper's main positive result collapses. The experiments, while extensive, do not repair the missing proof and in fact include an 'adhering' cost ratio that violates the unstated condition needed by the proof.","major_comments":[{"comment":"The proof of Theorem 7 asserts that the second term of Eq. (18) is nonnegative, but that term equals l2_{m,j} − l1_{m,j} (or, in the two-sided version, l2_{m,j} + l3_{m,j} − l1_{m,j} − l4_{m,j}) for j ∈ B\\A, and Definition 1 imposes no relation between l1 and l2. A concrete counterexample satisfies every stated assumption: two tasks with a single directed edge (v_m, v_j), zero computation costs, and (l1, l2, l3, l4) = (100, 1, 1, 0). For this instance Definition 1 holds (0 ≤ 1 and 0 ≤ 1), but F({v_m}) − F(∅) = −99 while F({v_m, v_j}) − F({v_j}) = −1, so the diminishing-returns inequality of Definition 6 fails. Theorem 7 is therefore false as stated, and Corollary 8 is unsupported.","section":"Section IV.B, Theorem 7 and Eq. (18)"},{"comment":"The displayed formula for F(A∪{v_m}) − F(A) is incorrect in two respects. First, the computation-cost difference should be wcld_m − wedg_m, the negative of the expression shown, since moving v_m from the edge to the cloud changes the computation cost by that amount. Second, the communication sums include only edges of the form (v_m, v_j) and omit edges (v_j, v_m) entering v_m; those edges also change classification when v_m moves, contributing additional terms that are not constrained by Definition 1. Correcting these errors introduces exactly the l2 ≥ l1 type of condition whose absence breaks Theorem 7.","section":"Section IV.B, Eq. (16)"},{"comment":"The experimental validation does not isolate the assumption used in the proof of Theorem 7. The 'adhering' ratio (8:6:7:5) satisfies Definition 1 but violates the unstated condition l2 ≥ l1 (since 8 > 6), so the reported optimality of SMA on that ratio cannot be explained by the theorem as proven. More generally, all of the 'violating' ratios violate l2 ≥ l1 as well as Definition 1, so the experiments cannot discriminate between the paper's stated assumption and the stronger condition actually needed for submodularity. The empirical agreement with ILP is therefore not evidence for the theorem.","section":"Section V.B.3 and Fig. 7"}],"minor_comments":[{"comment":"The sentence 'For briefness, we call l1_ij and l4_ij as intra-edge and intra-cloud costs, respectively, and call l1_ij and l4_ij as inter-partition cost' should read 'l2_ij and l3_ij' in the second mention; otherwise it misidentifies which costs are inter-partition.","section":"Section II, after Eq. (2)"},{"comment":"The sentence 'This trend is attributed to the HETO’s exponential growth in runtime, which aligns with its time complexity of O(E²)' is internally inconsistent: O(E²) is polynomial, not exponential.","section":"Section V.B.2"},{"comment":"The text says 'red edges turn out to be intra-cloud communication' when describing a solution whose red nodes are executed at the edge; those edges should be called intra-edge communication.","section":"Section IV.C.2, Fig. 3 description"},{"comment":"The first paragraph of the proof states that C′ ≤ C 'apparently holds' because the offloading solution is feasible, but feasibility alone does not imply a cost bound; the argument should instead assume that a solution of cost at most C exists. Both directions of the reduction are present, but the logical structure of the lemma proof is confusing.","section":"Section III, Lemma 3 proof"}],"recommendation":"reject","confidential_remarks":"The central theorem of the paper is false as stated; the missing condition l2 ≥ l1 is not a minor fix because the communication assumption is the paper's main conceptual contribution, and without it the polynomial-solvability dichotomy collapses. The NP-hardness reduction appears sound and could form the basis of a separate short paper, but the submodularity claim and the algorithmic claims built on it require substantial reworking before the manuscript could be considered for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The NP-hardness half of this paper is worth keeping. The reduction from MAX-CUT to the symmetric offloading problem is correct, and it genuinely closes the open question left by Du et al.'s asymmetric 3SAT reduction. If the paper were only about that, it would be a clean short contribution.\n\nThe submodular half is not correct. Theorem 7 claims that the cost-increment function F(X) is submodular under the communication assumption (l4 <= l2 and l4 <= l3). The proof's decisive step is the claim that the second term in Eq. (18) is nonnegative. For an outgoing edge (m,j) with j in B\\A, that term is l2_{mj} - l1_{mj}: when Vcld = B, m is still on the edge and j is in the cloud, so the cost is l2; when Vcld = A, both are on the edge, so the cost is l1. Definition 1 says nothing about l1 versus l2 or l3. The same issue appears with incoming edges, where the term is l3 - l1. The proof hand-waves this with \"similarly,\" and the conclusion does not follow.\n\nThe failure is not a minor gap. Take two tasks and one directed edge (v1,v2) with (l1,l2,l3,l4) = (100,1,1,0). The assumption holds (0 <= 1, 1). But the marginal difference for moving v1 to the cloud is -99 when the cloud set is empty and -1 when the cloud set is {v2}, violating submodularity. So Corollary 8 is unsupported, and the claimed polynomial solvability of Offloading-CommA and Offloading-LCCA has no valid proof. The paper's central dichotomy — NP-hard without the assumption, polynomial with it — collapses on the algorithmic side.\n\nThe experiments show SMA matching the ILP benchmark under the assumption, which is decent empirical evidence that the method can work well, but it does not substitute for a proof. No code or data is provided, which limits reproducibility. The related literature is covered fairly, and the citation pattern looks normal.\n\nWho is this paper for? Someone working on the complexity of offloading problems will find the MAX-CUT reduction useful. Someone trusting the submodularity claim would be misled. The right outcome is heavy revision: state the hardness result as a standalone contribution, either fix the submodularity theorem with an explicit extra condition (e.g., l1 <= l2 and l1 <= l3) or drop the polynomial-optimality claim and reposition SMA as a heuristic. I would send it to peer review, not desk-reject, because the hardness result deserves a public record and referees should document the failure of Theorem 7. But as it stands, the main result is not acceptable.","headline":"The NP-hardness reduction is solid and new; the central submodularity theorem is false as stated, so the main polynomial-time claim collapses.","tokens_in":18506,"tokens_out":4576,"would_cite":false,"duration_ms":39303,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that edge-cloud task offloading is NP-hard without its communication assumption but becomes polynomially solvable, even with latency constraints, when the assumption holds.","keywords":["task offloading","edge-cloud computing","submodular minimization","NP-hardness","communication assumption","latency constraint","MAX-CUT reduction","cost optimization"],"falsifier":"Construct a small instance with four tasks satisfying Definition 1 but with $l^1_{ij}$ much larger than $l^2_{ij}$ and $l^3_{ij}$ (for example $l^1=10$, $l^2=l^3=1$, $l^4=0$), then exhaustively check all partitions to see whether $F(A\\cup\\{v_m\\})-F(A)\\ge F(B\\cup\\{v_m\\})-F(B)$ holds for all $A\\subseteq B$ and $v_m\\notin B$; a single violation would refute Theorem 7 as stated.","tokens_in":41,"feed_emoji":"☁️","tokens_out":6411,"duration_ms":116382,"temperature":0.7,"pith_summary":"This paper studies the task offloading problem, in which each computing task is assigned to either an edge server or a cloud server and the total computation plus communication cost is minimized. Its central claim is a dichotomy: without a 'communication assumption' the problem is NP-hard, even in the symmetric case, while with the assumption the cost function is submodular and the problem is solvable in strongly polynomial time. The assumption states that communicating between two cloud servers is no more expensive than communication crossing the edge–cloud boundary or communication between edge servers. Because submodular minimization has polynomial algorithms, the paper turns a hardness result into a tractability result under a plausible real-world cost ordering. A sympathetic reader would care because the same assumption that makes the model realistic is the one that makes optimal offloading computationally feasible.","feed_headline":"One cost rule turns task offloading from NP-hard to polynomial","feed_subtitle":"When intra-cloud communication is no costlier than other links, optimal edge-cloud offloading is computable in polynomial time.","key_machinery":"The central object is the cost-increment function $F(X)=\\Gamma(X)-\\Gamma(\\emptyset)$, which measures how the total service cost changes when the task set $X$ is executed on the cloud instead of all tasks being executed on the edge. The paper proves submodularity by expanding the difference $(F(A\\cup\\{v_m\\})-F(A))-(F(B\\cup\\{v_m\\})-F(B))$ into a sum over tasks $j\\in B\\setminus A$ of paired terms; the communication assumption makes each paired term nonnegative, because an edge that becomes intra-cloud instead of inter-partition cannot increase in cost. This pairwise nonnegativity is what carries the argument, and it is what permits the problem to be handed to existing strongly polynomial submodular-minimization algorithms.","core_discovery":"The paper's main discovery is Theorem 7: for the latency-constrained offloading problem, the cost-increment function $F(X)=C_{\\mathrm{total}}(V\\setminus X,X)-C_{\\mathrm{total}}(V,\\emptyset)$ is submodular whenever the communication assumption $l^4_{ij}\\le l^2_{ij},l^3_{ij}$ holds for every edge. Submodularity means the marginal cost of moving a task to the cloud decreases as the set of cloud-assigned tasks grows, which is exactly the diminishing-returns behavior needed for polynomial minimization. With this in hand, Offloading-CommA and Offloading-LCCA can be solved optimally in strongly polynomial time by minimizing $F$ over all $X\\subseteq V\\setminus T$. Complementing this, the paper proves that without the assumption the offloading problem is NP-hard even when computation costs are zero and communication costs are symmetric, via a reduction from MAX-CUT. Taken together, the paper argues that the communication assumption is the dividing line that separates polynomial solvability from NP-hardness.","pith_inferences":["If the missing pairwise ordering is genuinely required, the true picture may be finer than a simple dichotomy: instances satisfying the full pairwise ordering are polynomial, while instances satisfying only the stated assumption may still be hard, and a cleaner sufficient condition would be $l^1_{ij}+l^4_{ij}\\le l^2_{ij}+l^3_{ij}$ for every edge.","The same cost-increment trick could be applied to other two-sided assignment problems with asymmetric communication costs, as long as a pairwise ordering makes every marginal difference nonnegative.","A testable engineering consequence is that exact optimal offloading is feasible when intra-cloud bandwidth is cheap but edge-to-cloud links are slow, whereas systems with cheap edge-to-edge links may still need heuristics.","If the missing condition is added to the model, the dichotomy result would become a practical diagnostic: check the four communication costs on each link, and the complexity class is decided by a simple inequality."],"forward_implications":["Under the communication assumption, Offloading-CommA is solvable optimally in strongly polynomial time.","The latency-constrained version Offloading-LCCA remains polynomially solvable when some tasks must stay on edge servers.","Without the assumption, the offloading problem is NP-hard even with zero computation costs and symmetric communication costs.","The communication assumption, not symmetry or computation costs, is the key factor separating NP-hardness from polynomial solvability in this model.","Experiments on real-world and synthetic graphs show the submodular-minimization algorithm matches the ILP optimum and runs faster than the previous HETO heuristic."],"supporting_citations":[{"why":"Supplies the heterogeneous cost model with four communication costs per edge, the previous NP-hardness proof for the asymmetric case, and the HETO baseline that the paper extends and compares against.","marker":"[15]"},{"why":"Provides the combinatorial strongly polynomial algorithm for submodular minimization that the paper invokes to solve Offloading-CommA and Offloading-LCCA.","marker":"[34]"},{"why":"Establishes MAX-CUT as NP-hard, the source problem for the paper's reduction proving NP-hardness of symmetric offloading.","marker":"[39]"},{"why":"Gives the first polynomial algorithm for submodular minimization, used to justify polynomial solvability in general.","marker":"[32]"},{"why":"Provides another combinatorial strongly polynomial algorithm for submodular minimization, cited as an available tool for the transformed problem.","marker":"[33]"}],"fun_headline_variants":["One cost rule flips offloading from NP-hard to polynomial","Edge-cloud offloading: submodular when links are cheap","Cheap cloud links make task offloading polytime","Communication assumption: the offloading complexity switch","Submodularity solves offloading when intra-cloud costs are low"],"cache_read_input_tokens":20480,"weakest_assumption_plain":"The whole polynomial-time result depends on a cost-ordering condition that the paper never states: the proof needs the edge-cost savings from moving a task to the cloud to be nonnegative in both directions, which fails when communication between two edge servers is much more expensive than communication across the edge–cloud boundary.","fun_headline_variants_meta":{"raw":{"variants":["One cost rule flips offloading from NP-hard to polynomial","Edge-cloud offloading: submodular when links are cheap","Cheap cloud links make task offloading polytime","Communication assumption: the offloading complexity switch","Submodularity solves offloading when intra-cloud costs are low"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000226,"raw_usage":{"total_tokens":1501,"prompt_tokens":1011,"completion_tokens":490,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":627,"completion_tokens_details":{"reasoning_tokens":408}},"tokens_in":627,"tokens_out":490,"duration_ms":5470,"temperature":1.0,"reasoning_tokens":408,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:01:35.316097+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a small instance with four tasks satisfying Definition 1 but with $l^1_{ij}$ much larger than $l^2_{ij}$ and $l^3_{ij}$ (for example $l^1=10$, $l^2=l^3=1$, $l^4=0$), then exhaustively check all partitions to see whether $F(A\\cup\\{v_m\\})-F(A)\\ge F(B\\cup\\{v_m\\})-F(B)$ holds for all $A\\subseteq B$ and $v_m\\notin B$; a single violation would refute Theorem 7 as stated.","supporting_citations":[{"cited_title":"Algorithmics of cost-driven com- putation offloading in the edge-cloud environment,","cited_arxiv_id":null,"evidence_quote":"Supplies the heterogeneous cost model with four communication costs per edge, the previous NP-hardness proof for the asymmetric case, and the HETO baseline that the paper extends and compares against."},{"cited_title":"A combinatorial strongly polynomial algorithm for minimizing submodular functions,","cited_arxiv_id":null,"evidence_quote":"Provides the combinatorial strongly polynomial algorithm for submodular minimization that the paper invokes to solve Offloading-CommA and Offloading-LCCA."},{"cited_title":"Some simplified np- complete problems,","cited_arxiv_id":null,"evidence_quote":"Establishes MAX-CUT as NP-hard, the source problem for the paper's reduction proving NP-hardness of symmetric offloading."},{"cited_title":"The ellipsoid method and its consequences in combinatorial optimization,","cited_arxiv_id":null,"evidence_quote":"Gives the first polynomial algorithm for submodular minimization, used to justify polynomial solvability in general."},{"cited_title":"On submodular function minimization,","cited_arxiv_id":null,"evidence_quote":"Provides another combinatorial strongly polynomial algorithm for submodular minimization, cited as an available tool for the transformed problem."}],"review_version":1}