{"id":"e44bac34-12cc-4fd1-9b97-0f97eedecc6e","arxiv_id":"1908.05445","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Tracking paths is NP-complete on planar graphs, admits a 4-approximation, and is linear-time solvable on bounded clique-width graphs with a given decomposition.","lead":"Placing trackers to uniquely identify paths in a planar graph is NP-complete, and the paper gives a 4-approximation algorithm for that case. This matters because planar graphs model road networks and other infrastructures where surveillance tracking is applied.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 14's upper bound is false as stated: after Reduction 1, s and t may have degree 1, so ALG ≤ 2(|F|−2) fails on a triangle with pendant s,t; the 4-approximation proof needs the corrected bound ALG ≤ 2|F|−2.","rationale":"The reader's weakest assumption identifies exactly the load-bearing flaw in the central 4-approximation claim: Lemma 14's upper bound is false as stated because degree-1 endpoints s and t are possible after Reduction 1. The counterexample with a triangle and pendant s,t shows the bound ALG ≤ 2(|F|−2) fails, so the proof of Theorem 3 is invalid as written. The correction to ALG ≤ 2|F|−2 is straightforward and preserves the approximation ratio, so the paper's main theorem is likely salvageable, but the authors must repair the lemma and its proof. I see no other issue that outweighs this one: the NP-hardness reduction and clique-width section appear structurally sound, and Lemma 6's lower bound, while informal, is not contradicted by small examples. The conditional verdict remains appropriate because the identified gap is concrete and requires author action, but it is not fatal to the paper's contributions.","tokens_in":13564,"tokens_out":14876,"duration_ms":139262,"concrete_test":"Re-derive Lemma 14 with the corrected degree sum: enumerate all reduced planar graphs on up to 8 vertices, run Algorithm A, and verify ALG ≤ 2|F|−2 for each. Then verify the implication ALG ≤ 2|F|−2 ≤ 4·OPT follows from Lemma 6 for all face counts. If any reduced graph violates the bound, the approximation lemma requires further revision beyond the corrected Euler argument.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 14 asserts that after Reduction 1 there cannot be vertices of degree 1, but s and t may have degree 1. Consider a triangle abc with pendant edges s-a and t-b. After Reduction 1, s and t have degree 1 and |F|=2. Algorithm A places one tracker on c, so ALG=1, violating the stated bound ALG ≤ 2(|F|−2)=0. The Euler-formula proof uses 2|E| ≥ 3|V≥3|+2|V2|, omitting degree-1 endpoints. Correcting the degree sum to include d1 ∈ {0,1,2} degree-1 vertices gives |F| = 2 + |V≥3|/2 − d1/2. Since the output T satisfies |T| = |V≥3| − e, where e is the number of s,t with degree ≥3, and d1 ≤ 2, we get |T| ≤ 2|F|−2. This corrected bound still implies ALG ≤ 2|F|−2 ≤ 4·OPT via Lemma 6, so the 4-approximation is repairable. However, Theorem 3 as written relies on a false lemma, so the proof has a genuine gap that must be fixed.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the tracking-paths problem on planar graphs, in which one seeks a minimum set of vertices whose intersections with every s-t path are pairwise distinct sequences. The authors claim three main results: (1) a 4-approximation algorithm for Planar-Tracking based on reductions and an Euler-formula counting argument, (2) NP-hardness of Planar-Tracking via a reduction from Planar-3-SAT, and (3) solvability of the general problem in linear time on graphs of bounded clique-width when a clique decomposition is provided, by an MSO1 formulation and Courcelle's theorem. The NP-hardness reduction is detailed and plausible, and the clique-width application is a standard, correct use of Courcelle's theorem. The main issue is in the approximation section: Lemma 14's stated upper bound is false as written because it neglects degree-1 terminals, although the argument can be repaired to yield the same 4-approximation ratio.","tokens_in":13811,"tokens_out":14536,"duration_ms":138470,"significance":"If the approximation proof is repaired, the paper makes a solid contribution: it establishes that Planar-Tracking is NP-hard and admits a constant-factor approximation, closing a natural gap left by earlier work on general graphs. The bounded-clique-width result is a clean application of Courcelle's theorem and is interesting as a theoretical algorithmic result. The NP-hardness construction is detailed and appears sound. The 4-approximation is the weakest link: the key counting lemma is false in the form stated, but the failure is local and the corrected bound ALG <= 2|F|-2 still combines with Lemma 6's lower bound OPT >= (|F|-1)/2 to give the claimed approximation ratio. Thus the central claim is defensible but the manuscript as written contains a load-bearing error that must be fixed.","major_comments":[{"comment":"Lemma 14 states ALG <= 2(|F|-2), but the proof explicitly assumes that after Reduction 1 there are no vertices of degree 1. This is false because the source s and destination t may themselves have degree 1. A concrete counterexample is a triangle with pendant edges from s to one triangle vertex and from t to another: after Reduction 1 the graph has |F|=2, and Algorithm A places one tracker (on the remaining degree-2 triangle vertex via Reduction 3, or on a degree-3 vertex after further suppression), so ALG=1, violating the claimed bound 2(|F|-2)=0. The Euler-formula argument omits the contribution of degree-1 vertices from the degree sum. Including them yields ALG <= 2|F|-2 rather than 2(|F|-2). Since Lemma 6 gives OPT >= (|F|-1)/2, the corrected bound still implies the 4-approximation in Theorem 3, but the lemma and its proof must be revised before Theorem 3 is valid as written.","section":"Section 3.2, Lemma 14"},{"comment":"Reduction 2 as stated removes an arbitrary one of two adjacent degree-2 vertices and does not exclude s and t. If a terminal has degree 2 and is adjacent to another degree-2 vertex, the algorithm can delete the source or destination, after which the output of Algorithm A is not a tracking set for the original s-t instance. The proof of Lemma 24 implicitly assumes the removed vertex is not a terminal when it argues that moving a tracker from u to u' preserves the tracking property; this argument fails when u=s or v=t. The reduction rule and its safety proof must explicitly forbid removing s and t (or otherwise handle terminal vertices), and the effect of this restriction on the degree-counting argument in Lemma 14 should be rechecked.","section":"Section 3.2, Reduction 2 and Appendix A, Lemma 24"}],"minor_comments":[{"comment":"The attribution of the origin of the tracking-paths problem is inconsistent: the abstract says it was first introduced in [3], while the introduction cites both [4] and [3]. These references should be reconciled.","section":"Abstract and Introduction"},{"comment":"The problem is stated as an optimization problem ('What is the smallest tracking set?'), but Corollary 18 claims NP-completeness. The corresponding decision version (does there exist a tracking set of size at most k?) should be stated explicitly.","section":"Section 1, problem definition"},{"comment":"Figure 3(b) is labeled as a tight example for ALG = 2(|F|-2). If Lemma 14 is corrected to ALG <= 2|F|-2, the tight-example claim and caption should be updated to match the corrected bound.","section":"Figure 3(b)"},{"comment":"Claim 7 states that a vertex on an entry-exit pair has degree greater than 2, with proof 'Trivial by Definition 1.' This is not true for s and t: a terminal of degree 2 can lie on a cycle and serve as an entry or exit vertex. The claim should be restricted to non-terminal vertices, which is all that the later reduction proofs actually need.","section":"Section 3.2, Claim 7"},{"comment":"The introduction says Tracking can be solved in cubic time for bounded clique-width, but Theorem 22 and the surrounding text state polynomial time (via Oum's cubic-time decomposition construction) and linear time only when the decomposition is given. The wording should be made consistent and precise.","section":"Section 5"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe two headline results are real: Planar-Tracking is NP-complete and there is a 4-approximation. The Planar-3-SAT reduction is detailed and plausible, and the MSO1/Courcelle result for bounded clique-width is a clean, standard application. The face-charging lower bound (Lemma 6) is the most interesting technical piece and looks sound.\n\nThe soft spot is Lemma 14. The proof states there cannot be degree-1 vertices after Reductions 1–4. That is false: s and t can have degree 1 after Reduction 1, and Reductions 2–4 leave them alone. Concretely, take a triangle with pendant s attached to one triangle vertex and pendant t attached to another; after reduction, |F|=2, and the algorithm outputs one tracker, violating the claimed ALG ≤ 2(|F|-2)=0. The fix is a correct Euler-formula count that includes the degree-1 endpoints, giving ALG ≤ 2|F|-2. Combined with Lemma 6, that still gives a 4-approximation, so the theorem survives, but the proof as written is not correct.\n\nMinor issues: the NP-hardness gadget proofs live in the appendix and rely heavily on pictures and 'by observation' statements; this is common but could be tightened. The bounded clique-width section is routine, though correctly executed. Citations to Banik et al., Lichtenstein, and Courcelle are appropriate.\n\nWho this is for: people working on tracking sets, path reconstruction, or planar graph algorithms. It is a solid contribution to a small subfield, not a broad breakthrough. I would bring it to reading group and cite it once the lemma is fixed. If I were the editor, I would send it to review—not because the paper is flawless, but because the main results are likely correct, the gap is clearly repairable, and the work deserves referee time. Ask for a corrected Lemma 14 and, ideally, a fuller write-up of the gadget arguments.","headline":"Good paper with a repairable proof gap in the 4-approximation lemma; the results stand, but the version needs a fix before citing.","tokens_in":14370,"tokens_out":5742,"would_cite":true,"duration_ms":54527,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","68Q17","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that finding the smallest tracking set in a planar graph is NP-hard, and also gives a polynomial-time 4-approximation algorithm and a linear-time exact algorithm for bounded-clique-width graphs when a decomposition is…","keywords":["approximation algorithm","tracking paths","planar graphs","NP-hardness","clique-width","monadic second-order logic","3-SAT","graph algorithms"],"falsifier":"Run Algorithm A on all small planar graphs and compare its output size to the exact minimum tracking set found by brute force; a single instance where Algorithm A returns more than four times the optimum would disprove the 4-approximation claim. More narrowly, the stated lemma $\\mathrm{ALG} \\le 2(|F|-2)$ is already falsified by a triangle with s and t attached as degree-1 leaves, for which |F|=2 and the algorithm outputs one tracker.","tokens_in":13342,"feed_emoji":"📍","tokens_out":10398,"duration_ms":92664,"temperature":0.7,"pith_summary":"The paper studies the problem of placing the fewest trackers on vertices of a graph so that every path from a source s to a destination t records a distinct sequence of visited trackers, allowing an observer to reconstruct which path was taken. It establishes two main facts for planar graphs: the problem is NP-complete, so no polynomial-time exact algorithm is expected, and yet there is a polynomial-time 4-approximation, meaning the tracker set it outputs is never more than four times larger than an optimal set. The approximation is based on the observation that every cycle in a well-reduced planar graph needs only a bounded number of trackers and that the number of faces gives a lower bound on the optimum. It also shows that if the input has bounded clique-width and a clique decomposition is supplied, the exact optimum can be computed in linear time. These results are relevant to surveillance, network monitoring, and tracing the spread of infections or misinformation, where one wants to reconstruct an unseen path from sparse observations.","feed_headline":"Planar path tracking is NP-hard yet 4-approximable","feed_subtitle":"Finding the minimum tracker set in planar graphs is NP-hard; a simple algorithm gets within a factor of 4.","key_machinery":"The load-bearing object is the entry-exit pair: for a cycle C, an ordered pair (s',t') of vertices on C such that s connects to s', t' connects to t, the two connecting paths are disjoint, and each meets C only at its endpoint. Such a pair describes two alternative s-t paths that differ only inside C, so any tracking set must put a tracker somewhere on C outside {s',t'}. The approximation algorithm is carried by a cycle-characterization lemma from earlier work, together with a planar face-charging argument: adding faces one at a time shows each optimal tracker can account for at most two faces, giving OPT≥(|F|−1)/2; a sequence of safe reductions turns the graph into one where every face is trivially tracked by at most two trackers per face, giving the upper bound. For NP-hardness, the machinery is a gadget reduction from planar 3-satisfiability in which variable gadgets have exactly two minimum tracking sets, one per truth value, and clause gadgets are satisfied exactly when their face is tracked. For bounded clique-width, the machinery is an MSO1 formula expressing that a vertex set is a tracking set, which invokes a general linear-time algorithm for MSO1-expressible optimization problems on such graphs when a clique decomposition is supplied.","core_discovery":"The paper's central claim is that Planar-Tracking, the optimization version of finding a minimum tracking set in an undirected planar graph with a source s and destination t, is NP-hard but admits a 4-approximation algorithm. The algorithm first applies safe reductions that remove vertices not on any s-t path, contract chains of degree-2 vertices, and force trackers on degree-2 vertices inside small cycles; it then outputs all remaining vertices of degree at least three except s and t. The paper proves the output is always a tracking set, proves it has size at most 2(|F|−2) on reduced graphs, and proves every tracking set has size at least (|F|−1)/2, yielding the ratio 4. The NP-hardness is shown by a polynomial reduction from planar 3-satisfiability using variable and clause gadgets whose minimum tracking sets encode truth assignments. Finally, because the property of being a tracking set is expressible in monadic second-order logic, the exact problem is solvable in linear time on graphs of bounded clique-width when a clique decomposition is given.","pith_inferences":["The face-charging lower bound likely extends to graphs on surfaces of bounded genus with a constant that grows with the genus, since Euler's formula still relates vertices, edges, and faces; the paper leaves this as an open direction.","The degree-1 endpoint oversight in the upper-bound proof is repairable: a corrected Euler count that charges the endpoints separately still preserves the 4-approximation ratio, so the theorem's conclusion is probably safe even though the stated lemma is not.","Because the MSO1 formulation is the only graph-structure requirement, exact linear-time algorithms should also hold for any graph class of bounded clique-width if one is willing to pay cubic preprocessing, and on small networks brute force can validate the approximation ratio in practice.","The gadget reduction suggests a natural testable extension: one can attempt to strengthen the inapproximability ratio beyond the factor 4 by composing the planar 3-SAT reduction with gap amplification, which the paper does not do."],"forward_implications":["Planar-Tracking is NP-complete, so unless P=NP there is no polynomial-time exact algorithm for planar instances; approximation and parameterized algorithms are the meaningful targets.","The 4-approximation is analytically tight up to constants: there are planar instances where an optimal set has |F|/2 trackers and the algorithm outputs 2(|F|−2), so the ratio cannot be improved just by tightening the two lemmas.","The reduction shows that tracking-set decisions are at least as hard as planar 3-satisfiability, placing the problem among other planar NP-hard optimization problems.","For graphs of bounded clique-width, exact tracking-set optimization is fixed-parameter tractable in the clique width: cubic time without a decomposition, linear time when a bounded-width clique decomposition is given.","The entry-exit-pair characterization means that checking whether a proposed vertex set is a tracking set can be reduced to checking every cycle, which is why the planar face structure can be exploited."],"supporting_citations":[{"why":"Supplies the lemma that a set is a tracking set iff every simple cycle has a tracker outside its entry-exit pairs, and the safety of the initial reduction that removes vertices not on any s-t path.","marker":"[3]"},{"why":"Establishes that Planar-3-SAT is NP-complete, the problem reduced from for hardness.","marker":"[21]"},{"why":"Shows every Planar-3-SAT instance can be drawn rectilinearly with variables on a line, the drawing convention the gadget construction assumes.","marker":"[20]"},{"why":"Provides the meta-theorem that MSO1-expressible graph optimization problems are linear-time solvable on bounded-clique-width graphs when a decomposition is given.","marker":"[14]"},{"why":"Gives an algorithm to construct a bounded-width clique decomposition in cubic time, making the bounded-clique-width result polynomial without a supplied decomposition.","marker":"[24]"}],"fun_headline_variants":["Planar tracking paths: NP-hard, yet 4-approximable","4-approximation for NP-hard planar tracking","Planar path tracking: NP-complete, but 4-approx","Tracking paths in planar graphs: NP-hard, 4-approx","Planar tracking: NP-hard but 4-approximable"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The upper-bound proof of the 4-approximation assumes that after the initial reduction no vertex has degree 1, but the source s and destination t may themselves have degree 1; because of that, the lemma's stated bound $\\mathrm{ALG} \\le 2(|F|-2)$ is false as written, though a corrected Euler-argument that accounts for the two endpoints still yields the 4-approximation ratio.","fun_headline_variants_meta":{"raw":{"variants":["Planar tracking paths: NP-hard, yet 4-approximable","4-approximation for NP-hard planar tracking","Planar path tracking: NP-complete, but 4-approx","Tracking paths in planar graphs: NP-hard, 4-approx","Planar tracking: NP-hard but 4-approximable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001003,"raw_usage":{"total_tokens":4202,"prompt_tokens":866,"completion_tokens":3336,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":482,"completion_tokens_details":{"reasoning_tokens":3246}},"tokens_in":482,"tokens_out":3336,"duration_ms":24163,"temperature":1.0,"reasoning_tokens":3246,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:15:00.869755+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm A on all small planar graphs and compare its output size to the exact minimum tracking set found by brute force; a single instance where Algorithm A returns more than four times the optimum would disprove the 4-approximation claim. More narrowly, the stated lemma $\\mathrm{ALG} \\le 2(|F|-2)$ is already falsified by a triangle with s and t attached as degree-1 leaves, for which |F|=2 and the algorithm outputs one tracker.","supporting_citations":[{"cited_title":"A polynomial sized kernel for tracking paths problem","cited_arxiv_id":null,"evidence_quote":"Supplies the lemma that a set is a tracking set iff every simple cycle has a tracker outside its entry-exit pairs, and the safety of the initial reduction that removes vertices not on any s-t path."}],"review_version":1}