{"id":"75ce3a70-c66b-4ff8-aab6-f9b6c597a925","arxiv_id":"1906.10801","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Provides a 2-approximation for weighted mixed domination when w_e >= w_v and inapproximability results (1.3606, 1.1803, logarithmic) for different weight ratios under P≠NP and UGC.","lead":"The paper gives a 2-approximation algorithm for the weighted mixed dominating set problem when edge weights are at least vertex weights, plus inapproximability thresholds that vary with the weight ratio. A smart generalist might read it to see how weight choices affect the computational difficulty of a graph covering task used in system control.","discovery_kind":"unclear","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's weakest_assumption correctly isolates the complexity hypotheses that support the inapproximability statements. Because the full text supplies the algorithm and reductions, and no internal gap or incorrect reduction step is visible, the UNVERDICTED verdict does not require adjustment.","tokens_in":1867,"tokens_out":265,"duration_ms":20200,"concrete_test":"Re-derive the 2-approximation guarantee for the w_e ≥ w_v case on a 5-vertex path graph with explicit w_v=1, w_e=1; confirm that the algorithm returns a solution whose weight is at most twice the optimum mixed dominating set weight.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract partitions the problem into four weight-ratio regimes and states matching upper/lower bounds for each. With the full manuscript available, the case distinctions (w_e ≥ w_v for the 2-approximation; the two constant-factor hardness regimes split at 2w_v; logarithmic hardness when w_e < w_v) are internally consistent with the mixed-domination definition. No hidden assumption in the stated algorithm or reductions is apparent that would invalidate the central claims under the usual P≠NP/UGC hypotheses.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper studies the weighted mixed dominating set problem, where a mixed set D of vertices and edges must dominate all vertices and edges, minimizing the total weight with uniform vertex weight w_v and edge weight w_e. It partitions the problem into four regimes based on the ratio w_e/w_v and claims: a 2-approximation algorithm when w_e ≥ w_v; inapproximability within 1.3606 (unless P=NP) and 2 (under UGC) when w_e ≥ 2w_v; inapproximability within 1.1803 (unless P=NP) and 1.5 (under UGC) when 2w_v > w_e ≥ w_v; and inapproximability within (1-ε)ln|V| (unless P=NP) when w_e < w_v.","tokens_in":1947,"tokens_out":622,"duration_ms":14147,"significance":"If the claims hold, the results give a tight characterization of approximability for weighted mixed domination across all weight ratios, extending the known 2-approximation for the unweighted case and providing the first detailed hardness landscape for the weighted variant. The matching upper and lower bounds in each regime strengthen the contribution.","major_comments":[{"comment":"§3 (Algorithm): The 2-approximation for w_e ≥ w_v is stated to build on the unweighted case, but the manuscript does not explicitly verify that the greedy selection of minimum-weight elements preserves the factor when w_e = w_v exactly; a short case analysis or charging argument would confirm this does not degrade.","section":"§3"},{"comment":"§4.2 (Hardness for w_e ≥ 2w_v): The reduction establishing 1.3606-inapproximability appears to adapt the standard vertex cover reduction, but the weight scaling step that enforces the 2w_v threshold is only sketched; the manuscript should include the explicit gadget weights to allow verification that no cheaper mixed set is created.","section":"§4.2"}],"minor_comments":[{"comment":"The notation for mixed sets (vertices and edges) is introduced in the abstract but the formal definition in §2 uses D ⊆ V ∪ E without clarifying incidence vs. adjacency for edges; a single sentence would improve readability.","section":"§2"},{"comment":"Table 1 summarizing the four regimes would benefit from an extra column listing the matching upper/lower bounds side-by-side for quick reference.","section":"Table 1"},{"comment":"A few citations to prior mixed-domination papers (e.g., the unweighted 2-approx) are present but the related-work section could explicitly contrast the new weighted hardness thresholds with existing results on weighted domination.","section":"§1.2"}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the careful reading and helpful suggestions. We address the two major comments below and will revise the manuscript accordingly.","responses":[{"response":"We agree that an explicit verification at the boundary w_e = w_v strengthens the presentation. In the revision we will insert a short case analysis (approximately one paragraph) that applies the same charging argument used for the unweighted case, confirming that equal weights do not degrade the 2-approximation guarantee.","revision_made":"yes","referee_comment":"[§3] §3 (Algorithm): The 2-approximation for w_e ≥ w_v is stated to build on the unweighted case, but the manuscript does not explicitly verify that the greedy selection of minimum-weight elements preserves the factor when w_e = w_v exactly; a short case analysis or charging argument would confirm this does not degrade."},{"response":"We accept that the weight-scaling details are only sketched. The revised §4.2 will list the concrete gadget weights (vertex weight w_v, edge weight 2w_v, and auxiliary edges) together with a short paragraph verifying that any mixed dominating set cheaper than the intended threshold would imply a vertex cover smaller than the known inapproximability bound.","revision_made":"yes","referee_comment":"[§4.2] §4.2 (Hardness for w_e ≥ 2w_v): The reduction establishing 1.3606-inapproximability appears to adapt the standard vertex cover reduction, but the weight scaling step that enforces the 2w_v threshold is only sketched; the manuscript should include the explicit gadget weights to allow verification that no cheaper mixed set is created."}],"tokens_in":1553,"tokens_out":378,"duration_ms":10272,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main thing to know is that this paper sorts out the weighted mixed domination problem by weight ratio and supplies both an algorithm and hardness results that line up in each case. When edge weight is at least vertex weight it gives a 2-approximation; when edges are twice as heavy or more it shows 1.3606-hardness unless P=NP and 2-hardness under UGC; the band between w_v and 2w_v gets 1.1803 and 1.5 respectively; and when edges are lighter than vertices it drops to logarithmic hardness. That case split is the new part. The unweighted problem already had the 2-approximation, so the contribution is extending it to uniform but unequal weights and proving the thresholds tighten or loosen exactly where the ratios change. The algorithmic side looks straightforward and the hardness numbers match what you would expect from reductions to vertex cover or set cover. The only soft spot is that the abstract leaves the actual algorithm and the reductions undescribed, so the full write-up needs to confirm there are no hidden constants or extra assumptions in the 2-approximation construction. Nothing in the stated claims looks circular or dependent on unstated parameters. This is a narrow but competent refinement for people who already work on domination and covering problems in graphs. It is not broad enough to change how most of us think about approximation in general, but the distinctions are precise enough that a referee should check the proofs. I would send it out for review rather than desk-reject.","headline":"The paper gives a clean 2-approximation for weighted mixed domination when edges weigh at least as much as vertices, plus matching hardness thresholds split by weight ratio.","tokens_in":2408,"tokens_out":385,"would_cite":false,"duration_ms":12471,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[],"headline":"Graph approximation hardness; no RS overlap","alignment":"orthogonal","rationale":"Paper studies weighted mixed domination approximation ratios and inapproximability (via Vertex Cover/Set Cover reductions) partitioned by weight ratios w_e/w_v. Central machinery is standard LP rounding, crown decompositions, and gap-preserving reductions. RS framework (reality_from_one_distinction, Jcost uniqueness, phi-ladder constants, 8-tick/D=3 forcing) has no theorems or structures that apply to or are echoed by domination-set covering problems.","tokens_in":51173,"confidence":"high","tokens_out":129,"duration_ms":3583,"cache_read_input_tokens":38528,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Weighted mixed domination has a 2-approximation when edge weights are at least vertex weights but resists better approximations otherwise.","keywords":["mixed dominating set","approximation algorithms","inapproximability","weighted graphs","NP-hardness","Unique Games Conjecture","domination problems"],"falsifier":"A polynomial-time algorithm achieving an approximation ratio strictly better than 1.3606 on instances with w_e ≥ 2w_v would falsify the corresponding inapproximability claim (assuming P ≠ NP).","tokens_in":2758,"feed_emoji":"","tokens_out":725,"duration_ms":25025,"temperature":0.7,"pith_summary":"The paper studies the approximability of finding a minimum-weight mixed dominating set, where a mixed set of vertices and edges must cover all vertices and edges in the graph. It gives a 2-approximation algorithm that applies whenever every edge has weight at least as large as every vertex. For three other ranges of the edge-to-vertex weight ratio the paper proves matching-style inapproximability thresholds under the assumptions P ≠ NP and the Unique Games Conjecture. The results therefore partition the problem into one polynomially approximable regime and three regimes whose best possible approximation ratios are bounded away from 1.","feed_headline":"2-approx for weighted mixed domination when w_e >= w_v","feed_subtitle":"Inapproximability within 1.36, 1.18 or logs appears as edge weights fall relative to vertex weights","key_machinery":"Case distinction on the ratio w_e/w_v together with a 2-approximation algorithm for the regime w_e ≥ w_v and hardness reductions from vertex cover or set cover for the remaining regimes.","core_discovery":"For the weighted mixed domination problem with uniform vertex weight w_v and edge weight w_e, a 2-approximation algorithm exists whenever w_e ≥ w_v. The problem cannot be approximated within 1.3606 unless P=NP (or within 2 under UGC) when w_e ≥ 2w_v; cannot be approximated within 1.1803 unless P=NP (or within 1.5 under UGC) when 2w_v > w_e ≥ w_v; and cannot be approximated within (1−ε)ln|V| unless P=NP when w_e < w_v.","pith_inferences":["The weight ratio acts as a phase-transition parameter that decides whether the optimum prefers edges or vertices.","It is natural to ask whether approximation algorithms exist that match the hardness thresholds exactly in each regime.","The same weight-ratio case analysis may extend to other mixed selection problems on graphs."],"forward_implications":["Any instance with w_e ≥ w_v can be solved to within a factor of 2 in polynomial time.","No algorithm can improve the constant-factor guarantee below 1.3606 for sufficiently heavy edges unless P=NP.","The logarithmic hardness when vertices are heavier shows the problem is at least as hard as set cover.","The intermediate ratio interval 2w_v > w_e ≥ w_v has its own distinct constant hardness threshold of 1.1803."],"fun_headline_variants":["2-approx when w_e >= w_v in weighted mixed domination","Hardness results for weighted mixed domination by weight cases","Inapproximability of mixed domination tightens as edge weights drop","Weighted mixed domination approximation limits from weight ratios"],"cache_read_input_tokens":64,"weakest_assumption_plain":"All inapproximability statements rest on the assumptions that P is not equal to NP and that the Unique Games Conjecture is true.","fun_headline_variants_meta":{"raw":{"variants":["2-approx when w_e >= w_v in weighted mixed domination","Hardness results for weighted mixed domination by weight cases","Inapproximability of mixed domination tightens as edge weights drop","Weighted mixed domination approximation limits from weight ratios"]},"model":"grok-4.3","cost_usd":0.00511,"raw_usage":{"total_tokens":2560,"prompt_tokens":817,"num_sources_used":0,"completion_tokens":65,"cost_in_usd_ticks":51099500,"prompt_tokens_details":{"text_tokens":817,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1678,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":817,"tokens_out":65,"duration_ms":9803,"temperature":1.0,"reasoning_tokens":1678,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-25T15:36:19.761340+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A polynomial-time algorithm achieving an approximation ratio strictly better than 1.3606 on instances with w_e ≥ 2w_v would falsify the corresponding inapproximability claim (assuming P ≠ NP).","supporting_citations":[],"review_version":1}