{"id":"48dbd816-9cf3-4451-90d6-73f44de06fcf","arxiv_id":"1908.03870","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For the dual parameter ℓ, CGM is SETH-hard to improve beyond 2^ℓ on general graphs, LGM is W[1]-hard even with lists of size two, and tree inputs admit an O(3^ℓ) algorithm for GM, an O(√2^ℓ) algorithm and linear kernel for CGM.","lead":"This paper maps the complexity of Graph Motif, Colorful Graph Motif, and List-Colored Graph Motif when the parameter is the number of vertices left out of the solution. It proves a tight SETH-based lower bound for the colorful case, W[1]-hardness for list-colored instances with two-color lists, and gives fast algorithms and kernel bounds on trees.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the SETH-conditional lower bound and the positive tree algorithms are coherent.","rationale":"The reader identified SETH and NP⊄coNP/poly as the weakest assumptions, and I agree that these are the only conditional bases of the negative results. I independently checked the reduction for Theorem 1: the constructed CGM instance has ℓ=|X|, the occurrence corresponds exactly to a satisfying assignment, and the implication to a (2−ε)^r poly(q) algorithm for CNF-SAT is sound. The tree DP (Theorem 4) has correct recurrences and a correct running-time maximization; the kernelization (Theorem 7) is correct up to a typo in the proof text; and the branching algorithm (Theorem 8) correctly reduces ℓ by at least two per branch. The cross-composition in Theorem 6 is intricate but the argument for parameter bound and correctness is plausible; a minor omission is that the equivalence relation should also fix k, which is easily repaired. None of these issues affect the central claims, so the ACCEPT verdict stands unchanged.","tokens_in":19194,"tokens_out":29988,"duration_ms":314240,"concrete_test":"As a verification step, implement the DP of Theorem 4 and compare against brute force on all vertex-colored trees with up to 10 vertices; a mismatch would indicate a hidden recurrence error, while success would further support the O(3^ℓ n) claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I examined the central SETH lower bound (Theorem 1), the W[1]-hardness reductions, and the tree DP/kernelization results. The reduction from CNF-SAT correctly sets ℓ=|X|, the equivalence argument is valid, and the DP recurrences for GM on trees correctly track deletion counts; the cross-composition kernel lower bound is technically sound modulo minor typos (e.g., a repeated 'c1' in the recurrence display and 'unique' for 'non-unique' in Theorem 7's size argument). The only assumptions are the standard SETH and NP⊄coNP/poly, and the theorems are explicitly conditional on them. I find no load-bearing flaw that would change the verdict.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Graph Motif (GM), Colorful Graph Motif (CGM), and List-Colored Graph Motif (LGM) parameterized by the dual parameter ℓ = |V| − |M|. For general graphs it proves a SETH-conditional (2−ε)^ℓ · n^{O(1)} lower bound for CGM, a polynomial-kernel lower bound under NP ⊄ coNP/poly, and W[1]-hardness of LGM for ℓ even when every list has size at most two. For trees it gives an O(3^ℓ · n) dynamic program for GM, a kernelization lower bound for GM via cross-composition, an O(√2^ℓ + n) algorithm for CGM with a (2ℓ+1)-vertex kernel, and an FPT algorithm for a restricted class of LGM instances whose vertex-color graph is a forest. All results are proved by explicit reductions, dynamic-programming recurrences, or branching arguments; the paper is self-contained apart from standard hypotheses such as SETH and NP ⊄ coNP/poly.","tokens_in":19271,"tokens_out":41905,"duration_ms":435103,"significance":"The paper resolves or significantly tightens the parameterized complexity of three central motif problems under the dual parameter. The SETH lower bound for CGM is a clean and convincing argument that the earlier O(2^ℓ · m) algorithm is essentially optimal; the W[1]-hardness reduction for LGM with list size two is a nice strengthening; and the tree-case algorithms and kernel lower bound are natural and mostly well executed. The cross-composition lower bound for GM on trees is technically sound. The main caveat is that two of the positive tree results, the CGM kernelization and the linear-time base case of the CGM branching algorithm, are not correct as stated when the input graph contains colors absent from the motif M; the proofs appear to rely on an unstated and nontrivial assumption about such colors. If that gap is repaired, the paper would be a solid contribution.","major_comments":[{"comment":"The equivalence proof of the kernelization is invalid when G contains colors not appearing in M. The proof claims that every occurrence of M contains all vertices removed in Phase I, because such vertices are unique or lie on paths between unique vertices; this is false for a unique vertex whose color is not in M. Concrete counterexample: let G be the path v1-v2-v3 with colors a, d, b respectively and let M = {a, b}. Then ℓ = 1 and the instance is a no-instance, since any connected set containing both colors a and b must include v2, whose color d is not in M. The kernelization, rooted at v1, finds no pendant non-unique subtrees, removes v2 and v3 in Phase I, removes b from M, and outputs the single vertex v1 with motif {a}, a yes-instance. Thus the kernelization does not preserve equivalence for general CGM instances. A component-wise reduction that first deletes vertices whose colors are absent from M appears necessary before the Phase I/Phase II argument can go through.","section":"4, Theorem 7"},{"comment":"The linear-time base case is also incorrect when vertices have colors not in M. Example: let G be a star with center r of color a ∈ M and two leaves of color b ∉ M, with M = {a}. Then Branching Rule 2 does not apply, since color b occurs only in leaves. The algorithm of Lemma 3 deletes occ(b)−1 = 1 leaf of color b, leaving a graph whose colors are a and b; this graph is not an occurrence of M, although the original instance is a yes-instance because S = {r} is a valid occurrence. The proof that the remaining graph 'contains each color exactly once' does not imply that its color set equals M. The lemma needs an explicit treatment of colors absent from M, or a restriction to instances in which every color of G occurs in M, which in turn requires the component-splitting reduction mentioned above.","section":"4, Lemma 3"}],"minor_comments":[{"comment":"In the recurrence for D^i_v, the first case writes the last coordinate as λ_j − occ(T_ui, c1); the second occurrence of c1 should be c_j, so that the expression reads λ_j − occ(T_ui, c_j).","section":"3.1, DP recurrence"},{"comment":"The sentence 'the resulting instance has at most 2ℓ+1 vertices since all vertices except r are unique' states the condition backwards: after the kernelization, r is the only unique vertex and all other vertices are non-unique, so Lemma 2 bounds their number by 2ℓ. As printed, the sentence contradicts the use of Lemma 2.","section":"4, Theorem 7 proof"},{"comment":"The proof of Rule 3 says that each costly component forces at least one deleted vertex; this is correct, but the phrase 'all color vertices c in H′ have multiplicity exactly deg_H(c)−1' should be read as multiplicity in M, which is clear from context but could be stated explicitly.","section":"3.2, Reduction Rule 3"}],"recommendation":"major_revision","confidential_remarks":"Both major concerns arise from an implicit assumption that every color appearing in G is present in M. This is not stated in the paper and is not WLOG without a component-splitting reduction: deleting vertices whose colors are absent from M splits the input, and the motif must be restricted to each component. The counterexamples are small and easy to verify; I believe the results of Theorems 7 and 8 can be repaired by adding such a reduction, but the current text does not establish them as stated. The rest of the paper, including the lower bounds and the GM-on-trees DP, appears sound."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Let me cut to the point: this is a solid, standard parameterized complexity paper, and it deserves publication. The main new results are the SETH lower bound for Colorful Graph Motif parameterized by ℓ = n − |M|, showing the earlier O(2^ℓ · m) algorithm is optimal, and the W[1]-hardness of List-Colored Graph Motif with lists of size two. On trees, the paper gives an O(3^ℓ · n) algorithm for Graph Motif, proves that no polynomial kernel exists, and for Colorful Graph Motif gives a (2ℓ+1)-vertex kernel and an O(√2^ℓ + n) algorithm. These close the dual-parameter picture for CGM and considerably improve the tree case.\n\nThe reductions are clean. The CGM lower bound is the standard CNF-SAT-to-motif construction; the equivalence argument holds. The LGM hardness from Multicolored Independent Set is straightforward, and the list-size-2 restriction is a nice touch. The dynamic program for GM on trees is the right kind of DP; the recurrence correctly tracks deletion counts for abundant colors, and the O(3^ℓ) bound follows from a legitimate product maximization.\n\nSoft spots are cosmetic rather than substantive. The recurrence for the auxiliary table D^i_v has a typo: the last coordinate should subtract occ(T_{u_i}, c_j), not occ(T_{u_i}, c_1). And in the proof of Theorem 7, the phrase \"all vertices except r are unique\" is wrong; the size bound follows from Lemma 2 (at most 2ℓ non-unique vertices), not from uniqueness. The cross-composition for the kernel lower bound is intricate, and I had to read the gadget construction twice to be comfortable, but the correctness argument holds together. All negative results are explicitly conditional on SETH and NP ⊄ coNP/poly, which is standard and stated up front.\n\nI don't see a load-bearing flaw. The paper is self-contained, the citations look appropriate, and the claimed novelty checks out against the cited earlier work. This is a paper for parameterized complexity specialists, but within that audience it is a useful and complete piece of work. I would send it to a serious referee and would cite it in future work on dual parameters or motif problems.","headline":"Solid parameterized complexity paper that closes the dual-parameter question for CGM and gives tight tree algorithms; typos are minor, no load-bearing flaw.","tokens_in":19842,"tokens_out":10025,"would_cite":true,"duration_ms":94533,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","68Q25","68Q27"],"pacs":[],"model":"deepseek-v4-flash","headline":"Colorful Graph Motif cannot beat 2^ℓ on general graphs, and becomes fast on trees.","keywords":["Graph Motif","Colorful Graph Motif","List-Colored Graph Motif","dual parameter","fixed-parameter tractability","SETH lower bound","problem kernel","parameterized complexity"],"falsifier":"Take a small CNF formula, build the Colorful Graph Motif instance described in the proof of Theorem 1, and solve it by exhaustive search: the answer must match the formula's satisfiability and the dual parameter must equal the number of variables, so any mismatch would falsify the reduction lemma on which the lower bound rests.","tokens_in":18978,"feed_emoji":"🌳","tokens_out":7115,"duration_ms":70541,"temperature":0.7,"pith_summary":"The paper studies three vertex-colored subgraph problems—Graph Motif, Colorful Graph Motif, and List-Colored Graph Motif—parameterized by the dual parameter ℓ = |V| − |M|, the number of vertices one must delete rather than keep. On general graphs, the central claim is that Colorful Graph Motif cannot be solved in (2−ε)^ℓ · $n^{{O(1)}}$ time unless the strong exponential time hypothesis (SETH) fails, so the known O(2^ℓ · |E|) deletion-branching algorithm is essentially optimal. It also proves that List-Colored Graph Motif remains W[1]-hard for parameter ℓ even when every vertex has a list of at most two colors. On trees the picture changes: Graph Motif becomes solvable in O(3^ℓ · n) time, Colorful Graph Motif in O(√2^ℓ + n) time with a (2ℓ+1)-vertex kernel, while Graph Motif on trees has no polynomial-size kernel unless NP ⊆ coNP/poly. The paper's point is that the dual parameter separates the easy tree case from the hard general case and yields a near-complete complexity landscape.","feed_headline":"Dual parameter: no faster Colorful Graph Motif unless SETH fails","feed_subtitle":"On trees the dual parameter yields a 3^ℓ-time algorithm and a (2ℓ+1)-vertex kernel for the colorful case.","key_machinery":"The central objects are the dual parameter ℓ = |V| − |M| and a reduction from CNF-SAT that makes ℓ equal the number of Boolean variables. For the tree algorithms, the load-bearing machinery is a dynamic-programming table over safe rooted subtrees: a connected subtree containing the root and all vertices whose colors are non-abundant, with entries indexed by how many vertices of each abundant color are deleted. The O(3^ℓ · n) bound comes from showing that the product of per-color deletion counts is maximized when all ℓ deletions are spread one per color. For Colorful Graph Motif on trees, a two-phase kernelization contracts paths between unique vertices and then removes color-conflicting vertices, yielding the (2ℓ+1)-vertex bound.","core_discovery":"For general graphs, the paper proves a SETH-based lower bound: any algorithm for Colorful Graph Motif running in (2−ε)^ℓ · $n^{{O(1)}}$ time would refute the strong exponential time hypothesis, via a polynomial reduction from CNF-SAT in which ℓ equals the number of Boolean variables. This makes the previously known O(2^ℓ · |E|) search-tree algorithm optimal up to polynomial factors. For trees, the paper proves that Graph Motif is solvable in O(3^ℓ · n) by dynamic programming over safe subtrees, that Colorful Graph Motif is solvable in O(√2^ℓ + n) by branching on repeated colors, and that Colorful Graph Motif admits a kernel with at most 2ℓ+1 vertices computed in linear time. In the other direction, it shows that Graph Motif on trees admits no polynomial-size kernel unless NP ⊆ coNP/poly, using an or-cross-composition from Multicolored Clique.","pith_inferences":["Editorial extension: the tight SETH reduction suggests the dual parameter is the right lens for practical motif search, since the bottleneck is deleting stray occurrences of repeated colors rather than matching the motif itself.","Editorial extension: the safe-subtree dynamic programming may transfer to bounded-treewidth graphs, where the analogous table would index deletions by abundant colors across bags; the tree result is the width-one case.","Editorial extension: the open case of List-Colored Graph Motif on trees with a forest vertex-color graph might be resolved by the same branching on 2-abundant colors, with the hardness for size-two lists suggesting that the degree structure of the color-vertex graph, not list size, is what matters."],"forward_implications":["The O(2^ℓ · |E|) algorithm for Colorful Graph Motif on general graphs cannot be improved to (2−ε)^ℓ · n^{O(1)} unless SETH fails, so its exponential dependence on the dual parameter is essentially optimal.","Any fixed-parameter algorithm for List-Colored Graph Motif parameterized by ℓ must exploit more than list-size structure, since W[1]-hardness persists with lists of size at most two.","On trees, Graph Motif is fixed-parameter tractable for ℓ, in contrast to its W[1]-hardness on general graphs.","Colorful Graph Motif on trees is substantially easier than the general case: it has a linear-vertex kernel and a search tree of size O(√2^ℓ), giving an O(√2^ℓ + n) algorithm.","Graph Motif on trees does not admit a polynomial-size kernel for ℓ unless NP ⊆ coNP/poly, so the kernel gap between Graph Motif and Colorful Graph Motif on trees is real."],"supporting_citations":[{"why":"Supplies the O(2^ℓ · |E|) algorithm for Colorful Graph Motif whose optimality is proved, and the W[1]-hardness of List-Colored Graph Motif under ℓ that is strengthened.","marker":"[2]"},{"why":"Provides earlier dynamic programming on trees and polynomial-time cases for Colorful Graph Motif that the new recurrences and branching build on.","marker":"[12]"},{"why":"States the strong exponential time hypothesis on which the (2−ε)^ℓ lower bound is conditional.","marker":"[19]"},{"why":"Gives the result that CNF-SAT has no polynomial-size kernel unless NP ⊆ coNP/poly, used for the Colorful Graph Motif kernel lower bound.","marker":"[10]"},{"why":"Supplies the W[1]-hardness of Multicolored Independent Set and Multicolored Clique used in the List-Colored Graph Motif hardness and in the cross-composition.","marker":"[13]"},{"why":"Defines or-cross-composition, the technique used to rule out polynomial kernels for Graph Motif on trees.","marker":"[4]"},{"why":"Provides the interleaving of kernelization with search-tree branching that removes the linear factor from the Colorful Graph Motif tree algorithm.","marker":"[21]"}],"fun_headline_variants":["SETH rules out faster Colorful Graph Motif: 2^ℓ is tight","Dual ℓ: CGM optimal, LGM W[1]-hard, trees beat it","On trees: GM in 3^ℓ, CGM in √2^ℓ, CGM has kernel","Tree Graph Motif: no polynomial kernel, but CGM has one"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The negative results for general graphs assume that SAT cannot be solved much faster than 2^n; if that assumption is false, the claimed optimality of the 2^ℓ algorithm for Colorful Graph Motif no longer follows.","fun_headline_variants_meta":{"raw":{"variants":["SETH rules out faster Colorful Graph Motif: 2^ℓ is tight","Dual ℓ: CGM optimal, LGM W[1]-hard, trees beat it","On trees: GM in 3^ℓ, CGM in √2^ℓ, CGM has kernel","Tree Graph Motif: no polynomial kernel, but CGM has one"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000936,"raw_usage":{"total_tokens":4087,"prompt_tokens":1113,"completion_tokens":2974,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":729,"completion_tokens_details":{"reasoning_tokens":2878}},"tokens_in":729,"tokens_out":2974,"duration_ms":22708,"temperature":1.0,"reasoning_tokens":2878,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:02:03.266482+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small CNF formula, build the Colorful Graph Motif instance described in the proof of Theorem 1, and solve it by exhaustive search: the answer must match the formula's satisfiability and the dual parameter must equal the number of variables, so any mismatch would falsify the reduction lemma on which the lower bound rests.","supporting_citations":[{"cited_title":"Fellows, and Rolf Nie- dermeier","cited_arxiv_id":null,"evidence_quote":"Supplies the O(2^ℓ · |E|) algorithm for Colorful Graph Motif whose optimality is proved, and the W[1]-hardness of List-Colored Graph Motif under ℓ that is strengthened."},{"cited_title":"Fellows, Guillaume Fertin, Danny Hermelin, and Stéphane Vialette","cited_arxiv_id":null,"evidence_quote":"Provides earlier dynamic programming on trees and polynomial-time cases for Colorful Graph Motif that the new recurrences and branching build on."},{"cited_title":"Which problems have strongly exponential complexity? Journal of Computer and System Sciences , 63(4):512–530, 2001","cited_arxiv_id":null,"evidence_quote":"States the strong exponential time hypothesis on which the (2−ε)^ℓ lower bound is conditional."},{"cited_title":"Satisfiability al lows no nontrivial sparsification unless the polynomial-time hierarchy collapses","cited_arxiv_id":null,"evidence_quote":"Gives the result that CNF-SAT has no polynomial-size kernel unless NP ⊆ coNP/poly, used for the Colorful Graph Motif kernel lower bound."},{"cited_title":"Fellows, Danny Hermelin, Frances Rosamond, and Stéphane Vialette","cited_arxiv_id":null,"evidence_quote":"Supplies the W[1]-hardness of Multicolored Independent Set and Multicolored Clique used in the List-Colored Graph Motif hardness and in the cross-composition."},{"cited_title":"Bodlaender, Bart M","cited_arxiv_id":null,"evidence_quote":"Defines or-cross-composition, the technique used to rule out polynomial kernels for Graph Motif on trees."},{"cited_title":"A general metho d to speed up fixed-parameter- tractable algorithms","cited_arxiv_id":null,"evidence_quote":"Provides the interleaving of kernelization with search-tree branching that removes the linear factor from the Colorful Graph Motif tree algorithm."}],"review_version":1}