{"id":"1861deae-f1e3-4c2e-83fd-e3152375ddcb","arxiv_id":"2607.01770","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Faster FPT algorithms for Telephone Broadcast achieve 2^{O(vc log vc)}, 2^{O(vi^2 log vi)}, and 2^{O(k log k)} n^{O(1)} time via reduction to b-Matching.","lead":"This paper presents faster fixed-parameter tractable algorithms for the Telephone Broadcast problem, improving the dependence on vertex cover, vertex integrity, and distance to clique via a Turing reduction to edge-weighted b-Matching. A smart generalist might read it for insights into efficient algorithm design for message dissemination in structured networks.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's weakest assumption correctly isolates the reduction as the sole unverified step. With only the abstract available, no internal inconsistency, incorrect parameter mapping, or other technical flaw can be located in the argument.","tokens_in":1867,"tokens_out":221,"duration_ms":18900,"concrete_test":"Check whether known FPT algorithms for edge-weighted b-Matching (parameterized by the relevant measure) compose with a Turing reduction that produces O(f(vc)) oracle calls on instances of size n^{O(1)} with parameter O(vc log vc) to recover exactly the claimed 2^{O(vc log vc)} n^{O(1)} bound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No load-bearing concern can be identified. The abstract states that a Turing reduction to edge-weighted b-Matching is the main ingredient enabling the improved single-exponential bounds, but the full manuscript is not available for technical inspection of the reduction's construction, parameter dependence, or correctness.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper claims improved FPT algorithms for Telephone Broadcast: 2^{O(vc log vc)} n^{O(1)} parameterized by vertex cover, 2^{O(vi^2 log vi)} n^{O(1)} by vertex integrity, and 2^{O(k log k)} n^{O(1)} by distance to clique. The central technical contribution is a Turing reduction from Telephone Broadcast to edge-weighted b-Matching that enables these single-exponential bounds, improving on prior 2^{O(vc^3)}, double-exponential, and 2^{O(k^2)} algorithms.","tokens_in":1897,"tokens_out":308,"duration_ms":16208,"significance":"If the reduction is correct and parameter-preserving, the results constitute a meaningful advance in parameterized complexity for dissemination problems, replacing higher-degree or double-exponential dependence with logarithmic factors. The Turing reduction to b-Matching is a reusable technique that could apply to related broadcast or gossiping problems on sparse graphs.","major_comments":[],"minor_comments":[{"comment":"Abstract: 'suprisingly' is a typo for 'surprisingly'.","section":null}],"recommendation":"uncertain","confidential_remarks":"The abstract states the running times and identifies the Turing reduction as the key ingredient, but supplies no proof sketch, construction details, or parameter analysis. Full verification of the reduction's correctness, running-time overhead, and how it yields the claimed single-exponential bounds requires the complete manuscript."},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their summary of our results and for noting the potential significance of the Turing reduction to b-Matching. The recommendation is listed as uncertain, but the report contains no major comments or specific technical questions. We are prepared to address any points that may arise during further review.","responses":[],"tokens_in":1370,"tokens_out":77,"duration_ms":10065,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The paper gives strictly better running times for Telephone Broadcast: 2^{O(vc log vc)}, 2^{O(vi^2 log vi)}, and 2^{O(k log k)} instead of the prior vc^3, double-exponential in vi, and k^2. The main new piece is the Turing reduction to edge-weighted b-Matching that enables these exponents.\n\nThe work is clear on what it improves and why the reduction matters. It takes parameters where FPT was already known and tightens the dependence without changing the overall approach. That is a concrete step forward for anyone tracking these specific bounds.\n\nThe reduction itself is the load-bearing claim. The abstract states it works and preserves the parameters, but the details are not visible here. If the construction holds up in the full text, the results follow; if the parameter blow-up or the Turing queries are worse than stated, the claimed times do not. No other red flags appear in the abstract or stress-test note.\n\nThis is aimed at researchers in parameterized complexity who work on dissemination problems or matching-based reductions. A reader already following FPT algorithms on graphs with small vertex cover or distance to clique will find the new times and the technique useful. It is narrow in scope but the improvement is real if the reduction checks out.\n\nThe paper deserves peer review. The claims are specific, the prior work is cited properly, and the method could transfer to related problems.","headline":"Paper improves FPT bounds for Telephone Broadcast via a Turing reduction to edge-weighted b-Matching.","tokens_in":2354,"tokens_out":359,"would_cite":false,"duration_ms":19967,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Telephone Broadcast admits faster FPT algorithms with single-exponential dependence on vertex cover via a Turing reduction to edge-weighted b-Matching.","keywords":["Telephone Broadcast","Parameterized algorithms","Fixed-parameter tractability","b-Matching","Vertex cover","Vertex integrity","Distance to clique"],"falsifier":"A concrete graph together with a source vertex where the broadcast time obtained from the b-Matching instance differs from the true minimum number of rounds needed.","tokens_in":2770,"feed_emoji":"","tokens_out":750,"duration_ms":21236,"temperature":0.7,"pith_summary":"The paper establishes improved fixed-parameter tractable algorithms for the Telephone Broadcast problem on graphs. It replaces prior running times of 2 to the O of vc cubed for vertex cover number, double-exponential for vertex integrity, and 2 to the O of k squared for distance to clique with new bounds of 2 to the O of vc log vc, 2 to the O of vi squared log vi, and 2 to the O of k log k respectively. These speedups rest on a Turing reduction that converts broadcast instances into edge-weighted b-Matching instances whose solutions recover the minimum broadcast time. A sympathetic reader would care because the new bounds make the problem computationally feasible on graphs whose vertex covers or similar measures are moderate in size. The reduction is presented as the main technical ingredient enabling the improvements.","feed_headline":"Telephone broadcast gets single-exponential FPT for vertex cover","feed_subtitle":"Turing reduction to edge-weighted b-matching improves prior cubic and quadratic exponents to O(vc log vc) and O(k log k).","key_machinery":"Turing reduction to edge-weighted b-Matching, which converts the broadcast instance so that an optimal solution to the matching problem yields the minimum number of broadcast rounds.","core_discovery":"The authors prove that Telephone Broadcast can be solved in time 2 to the O of vc log vc times n to the O of 1 when parameterized by vertex cover number vc, in time 2 to the O of vi squared log vi times n to the O of 1 when parameterized by vertex integrity vi, and in time 2 to the O of k log k times n to the O of 1 when parameterized by distance to clique k. These bounds improve the previous 2 to the O of vc cubed, double-exponential, and 2 to the O of k squared algorithms. The central mechanism is a Turing reduction to edge-weighted b-Matching that preserves the relevant parameters up to logarithmic factors.","pith_inferences":["The reduction approach may apply to other message-dissemination problems that involve choosing neighbors sequentially.","Graphs with small vertex cover could now be handled in practice for broadcast scheduling if the matching solver is efficient.","The technique suggests looking for similar Turing reductions from dissemination tasks to matching or flow problems in parameterized settings."],"forward_implications":["Telephone Broadcast becomes fixed-parameter tractable with single-exponential dependence on vertex cover number.","The same reduction technique yields the stated improved bounds for vertex integrity and distance to clique.","Any future improvement to algorithms for edge-weighted b-Matching immediately transfers to faster broadcast algorithms under these parameters.","The problem remains NP-hard on certain graphs of small pathwidth and treedepth even though it is FPT under the listed parameters."],"fun_headline_variants":["FPT for telephone broadcast improved via b-matching reduction","Single-exponential FPT for vertex cover in telephone broadcast","Turing reduction speeds telephone broadcast parameterization","Logarithmic exponents for telephone broadcast FPT algorithms"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The Turing reduction from Telephone Broadcast to edge-weighted b-Matching is correct and maps parameters to parameters of comparable size.","fun_headline_variants_meta":{"raw":{"variants":["FPT for telephone broadcast improved via b-matching reduction","Single-exponential FPT for vertex cover in telephone broadcast","Turing reduction speeds telephone broadcast parameterization","Logarithmic exponents for telephone broadcast FPT algorithms"]},"model":"grok-4.3","cost_usd":0.005967,"raw_usage":{"total_tokens":2840,"prompt_tokens":853,"num_sources_used":0,"completion_tokens":58,"cost_in_usd_ticks":59665500,"prompt_tokens_details":{"text_tokens":853,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1929,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":853,"tokens_out":58,"duration_ms":18471,"temperature":1.0,"reasoning_tokens":1929,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-03T04:20:08.414478+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A concrete graph together with a source vertex where the broadcast time obtained from the b-Matching instance differs from the true minimum number of rounds needed.","supporting_citations":[],"review_version":1}