{"id":"ce0f9472-b5b4-43c5-99a2-d82e5c88ead2","arxiv_id":"1908.02174","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A convex bipartite graph on n vertices has at most O(1.7254^n) minimal connected dominating sets, and all of them can be enumerated within the same time bound.","lead":"This paper gives the first input-sensitive enumeration algorithm for minimal connected dominating sets in convex bipartite graphs, running in O(1.7254^n) time. It also constructs convex bipartite graphs with at least 3^((n-2)/3) such sets.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 6 is the load-bearing structural claim, but its proof and the Step 6 containment assertion it supports are not rigorously established; the 1.7254^n bound depends on them.","rationale":"I read the paper in good faith: the algorithm is a plausible first input-sensitive enumeration for convex bipartite graphs, and the lower-bound construction is standard modulo the missing figure. The weakest point is not a demonstrated counterexample but an unproven structural lemma that carries both correctness and complexity. Lemma 6 is invoked in exactly the two places that bound the search tree: Stage 2 Step 6 limits the number of simultaneously selected U-vertices adjacent to r, and Stage 3 stops when deg(r)>3. Moreover, Step 6's branching vector, which produces the largest branching number 1.7254, depends on the additional unstated claim that every such x has Ix⊂(Iu∪Ij). The paper says 'straightforward to see'; this is load-bearing because if the claim fails, the number of branches could be larger or some valid solution could be discarded. The proof of Lemma 6 as written is too compressed: the cut-vertex assertions and the W-vertex ordering are not justified, and the route via wx,wx',wy,wy' is not verifiable as printed. I am not claiming the lemma is false; my own small attempts to construct four U-intervals all sharing one W-vertex produced non-minimal sets, and the lemma is likely true. But likelihood is not proof, and the theorem as submitted is conditional on a missing structural argument. The reader's weakest-assumption identification matches mine, and no verdict change is needed.","tokens_in":10029,"tokens_out":39601,"duration_ms":436446,"concrete_test":"Independently reconstruct Lemma 6 and the Step 6 containment claim. Concretely, prove from Lemmas 1, 2, 4 and 5 that (a) every x in D∩N(r)\\{{u,j}} satisfies l(Iu)<l(Ix)<l(Ij) and r(Iu)<r(Ix)<r(Ij); (b) such an x has no private neighbor and is a cut vertex; and (c) two such x's would force a selected W-vertex in Ii∩Ij, contradicting Lemma 5. If this derivation cannot be completed, or requires a new structural fact, the paper's central bound is unsupported. As a complementary falsification test, exhaustively enumerate all convex bipartite graphs with n≤11 and all their minimal connected dominating sets and verify Lemma 6.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4's Step 6 relies on the unproved assertion that, with current selected vertex u and j the N(r)-neighbor of largest right endpoint, every x in D∩N(r)\\{{u,j}} has Ix⊂(Iu∪Ij); only then can Lemma 6 limit |N(r)∩D\\{{u,j}}|≤1 and justify the branching vector (t,t+1,...,t+1,1). The same Lemma 6 justifies the Stage 3 stop when deg(r)>3. The proof of Lemma 6 is not complete: after fixing the endpoint order, it asserts \"It is clear that k,l are cut vertices,\" then invokes W-vertices wx,wx',wy,wy' whose existence and order are not derived. A rigorous argument must show that a vertex k with Ik strictly between intersecting Ii,Ij has no private neighbor (every W in Ik lies in Ii∪Ij), hence is a cut vertex, and then rule out two such vertices by the forbidden intersection Ii∩Ij. The text never supplies this argument, and the containment assertion in Step 6 is likewise stated without proof. Since both correctness (no valid solutions pruned) and the upper bound depend on these points, the central claim is conditional on a missing structural proof.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the maximum number and enumeration of minimal connected dominating sets (MCDS) in convex bipartite graphs. It proposes a four-stage branching algorithm: EnumLevel1 selects the unique U-neighbor of w1; EnumLevel2 branches on U-vertices using the rightmost selected interval and Lemma 6 to restrict the number of selected U-neighbors of a W-vertex r; EnumLevel3 filters partial solutions using degree conditions on the interval representation; EnumLevel4 selects W-vertices from a set of interval constraints J. A measure-and-conquer analysis with measure |U|+|W\\F| claims a worst-case branching number below 1.7254, giving the main theorem (Theorem 7): O(1.7254^n) MCDS and O(1.7254^n) enumeration time. A lower bound construction yields 3^{(n-2)/3} MCDS, matching the known general-graph lower bound.","tokens_in":10215,"tokens_out":18787,"duration_ms":189387,"significance":"If the technical gaps identified below can be closed, the result is a valuable contribution: it is the first input-sensitive enumeration bound for minimal connected dominating sets in a nontrivial bipartite subclass, and the upper bound O(1.7254^n) is substantially better than the best known general bound while being reasonably close to the lower bound 3^{(n-2)/3}≈1.4422^n. The algorithm is parameter-free, uses no fitted constants, and the lower-bound construction is simple and explicit. The claimed constants are derived within the standard Fomin–Kratsch branching framework rather than by numerical fitting. However, the paper currently does not supply a complete correctness proof, and the proof of the key structural lemma is partially asserted rather than derived; these are load-bearing gaps rather than presentation issues.","major_comments":[{"comment":"Lemma 6 is load-bearing for the Step 6 branching rule and for the Stage 3 stop rule when deg(r)>3, but the proof as written is not rigorous. After the endpoint ordering, the proof states 'It is clear that k,l are cut vertices' and then posits W-vertices w_x, w_x', w_y, w_y' with various separation properties; the inequalities w_y<l(I_j) and w_x'>r(I_i) are introduced without derivation. In particular, the proof never shows that the required vertices exist in D∩I_k and D∩I_l with the claimed component structure. A complete proof should establish, from the interval representation and Lemmas 1, 2, and 5, that a vertex k with I_k strictly contained in I_i∪I_j can be a cut vertex only if it has W-neighbors outside the intervals of all other selected U-vertices, and that two such vertices k,l would create a path contradicting the endpoint order. Without this argument, the assertion |N(r)∩D\\{u,j}|≤1 in Section 4 Step 6 is unsupported.","section":"Section 3, Lemma 6"},{"comment":"The branching analysis of Step 6 is asserted rather than derived. The text says 'It is straightforward to see' that the worst case is |I_u∩I_j|=1 and no x with I_x⊆I_j, yielding the vector (t,t+1,...,t+1,1), but no proof is supplied. The containment assertion 'for any x∈D∩N(r)\\{{u,j}} we have I_x⊂(I_u∪I_j)' is also stated without proof; it can be derived from Lemma 1 and the maximality of j's right endpoint, but the derivation should be written out. For the branching vector, the paper should explicitly compute the measure decreases: branch (i) removes all of N(r) (decrease t), each branch (ii) removes N(r) and forbids I_j∩I_u (decrease at least t+1), and branch (iii) removes only j (decrease 1), and should then prove that configurations with I_x⊆I_j or with a larger intersection are majorized by the vector (3,4,4,1). As it stands, the claimed bound α6<1.7254 is not justified.","section":"Section 4, Step 6 and Section 5, running-time analysis"},{"comment":"The paper never states or proves a correctness theorem for the enumeration algorithm. There is no formal invariant relating a partial solution (D,T,F) to the set of minimal connected dominating sets that extend it, no proof that every MCDS is generated by at least one leaf of the search tree, no proof that every leaf output is an MCDS, and no discussion of duplicate outputs. The pruning decisions in Stage 3 (the deg(r)>3 stop, the deg(r)=2 interval-intersection update, and the deg(r)=3 constraints added to J) are described only by informal arguments. Since the central claim is an enumeration bound, soundness and completeness of the algorithm are as important as the branching analysis; both need to be stated as lemmas or as a theorem with proofs.","section":"Section 4 (all stages)"},{"comment":"The lower-bound graph is claimed to be convex bipartite, but the proof ends with 'It remains to observe that G is convex bipartite from its following model' and no explicit interval representation is given; the figure labels intervals I_u and I_v but the ordering of the W-vertices and the neighbor intervals of the U-vertices are not specified. Since convexity is the defining property of the class, this must be demonstrated: give the ordering of W and the interval for every U-vertex, or a precise description from which the ordering is evident. In addition, the characterization of the MCDS of this graph ('if and only if u,v∉D and |D∩T_i|=1') is asserted without proof; a short proof of minimality and completeness should be included.","section":"Section 6, Proposition 1"}],"minor_comments":[{"comment":"The edge sets E' and E'' are never defined; they should be defined as the edge sets of the induced subgraphs on (U',W') and (U'',W''). Also, the phrase 'there is no w_j u∈E' is ambiguous because w_j denotes both the vertex and its index.","section":"Section 3, Lemma 3 proof"},{"comment":"The notation I_k⊂{I_i∪I_j} should be I_k⊂I_i∪I_j; as written it suggests an element of a set of intervals. Several occurrences of 'It is clear' in the proofs should be replaced by explicit arguments, especially where the existence of specific W-vertices is asserted.","section":"Section 3, Lemmas 5 and 6"},{"comment":"The typeset branching vector contains LaTeX artifacts ('/bracehtipupleft ...'); in the final version use standard notation such as (t, underbrace{t+1,...,t+1}_{t-1}, 1).","section":"Section 5, running-time analysis"},{"comment":"The figure should be described in the caption or text; the interval representation is not self-explanatory, and the interval for each U-vertex (x_i, y_i, z_i) should be listed or described.","section":"Section 6, Proposition 1"},{"comment":"The paper does not discuss how duplicate solutions are handled by EnumLevel4; if the search tree can reach the same output set via different branches, a deduplication argument or another mechanism should be stated.","section":"Section 4, EnumLevel4"}],"recommendation":"major_revision","confidential_remarks":"The main technical risk is Lemma 6 together with the Step 6 running-time analysis; if the authors can supply the missing proofs, the paper is likely acceptable. The lower-bound convexity gap is easy to close but should be addressed before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline: this paper has a plausible new result—an O(1.7254^n) upper bound and matching-ish enumeration algorithm for minimal connected dominating sets in convex bipartite graphs, plus a 3^{(n-2)/3} lower bound. The lower bound is a standard construction, and the upper bound approach fits with known measure-and-conquer work. If correct, it fills a real gap in the landscape, since bipartiteness is usually hard to exploit.\n\nThe paper does useful things well. The structural lemmas leading to the algorithm are sensible. Observation 2 and Lemmas 1–4 establish the basic properties of minimal connected dominating sets in convex bipartite graphs. The algorithm’s high-level plan—choose vertices in U first, then complete with W, using intervals to prune—is coherent. The lower bound construction is correct (though the convexity argument relies on a missing figure; that’s a minor presentation issue, easily fixed).\n\nThe soft spots are real and they sit exactly where the reader’s report says. Lemma 6 is load-bearing: it limits the number of U-vertices whose intervals lie inside the union of two intersecting intervals. The proof as written is too sketchy. After fixing an endpoint order, it simply states that k and l are cut vertices and then invokes vertices wx, wx' whose existence and relative order are not derived. The containment assertion used in Stage 2 Step 6—that every x in D∩N(r)\\ {u,j} has Ix⊂(Iu∪Ij)—is also stated without proof. If that assertion fails, the branching vector bounding for deg(r)≥3 falls apart, and the 1.7254^n bound is not established.\n\nThe running-time analysis has the same disease. The branching vector for Step 6 is asserted as 'straightforward to see' and the vector itself is written ambiguously (t, t+1, ..., t+1, 1). A careful argument is needed to show that the worst case is when all neighbors of r are branched with a single forbidden vertex. The correctness invariant of the four stages is never stated precisely, so it’s hard to verify that the pruning rules don’t discard valid solutions.\n\nNone of this looks fatal. The approach is credible and the missing pieces appear to be fillable. But the current text does not contain enough detail for a referee to certify the theorem.\n\nMy bottom line: this deserves serious peer review. A good referee will either fix the gaps or uncover a real flaw. I would not cite it in its current state; I’d wait for a revised version. It’s worth bringing to a reading group for the technique, if people are interested in exact exponential algorithms.\n\nRecommendation: send to a journal with a request for major revision before acceptance.","headline":"Promising new upper bound for convex bipartite graphs, but the proof is too sketchy to certify as written.","tokens_in":10786,"tokens_out":3346,"would_cite":false,"duration_ms":33394,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C69","05C85","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every convex bipartite graph on n vertices has at most O(1.7254^n) minimal connected dominating sets, and the paper gives an algorithm that lists them all in O(1.7254^n) time.","keywords":["minimal connected dominating set","convex bipartite graph","enumeration algorithm","input-sensitive algorithm","exact exponential algorithm","branching vector","interval representation","lower bound"],"falsifier":"Search for a convex bipartite graph with a minimal connected dominating set D containing i,j,k,l such that Ii \\cap Ij is nonempty and both Ik and Il are contained in Ii \\cup Ij; such an instance would falsify Lemma 6 and invalidate the branching analysis. A weaker empirical check is to enumerate all minimal connected dominating sets in large random convex bipartite graphs and look for a count exceeding 1.7254^n.","tokens_in":9772,"feed_emoji":"🔢","tokens_out":11379,"duration_ms":102675,"temperature":0.7,"pith_summary":"This paper proves a worst-case enumeration bound for a structured class of bipartite graphs: every convex bipartite graph on n vertices has at most O(1.7254^n) minimal connected dominating sets, and all of them can be listed in O(1.7254^n) time. The class is the first nontrivial bipartite family for which such an algorithm is known; for bipartite graphs in general, the best input-sensitive algorithms were previously no better than the general-graph bound. The proof exploits convexity, meaning one side of the bipartition can be ordered so that each vertex on the other side has a consecutive interval of neighbors, to keep the search tree small. It is complemented by a construction of convex bipartite graphs with at least $3^{{(n-2)/3}}$ such sets.","feed_headline":"Convex bipartite graphs: max 1.7254^n min. connected dominating sets","feed_subtitle":"First input-sensitive enumeration for a bipartite class, with graphs reaching 3^{(n-2)/3} sets.","key_machinery":"The central object is the interval representation of a convex bipartite graph: fix an ordering of W so that every u in U has neighbors forming one consecutive interval Iu. On top of this representation, Lemma 6 is the load-bearing structural fact: for two selected U-vertices i,j with intersecting intervals, at most one further selected U-vertex can have its interval contained in the union Ii \\cup Ij. This lemma bounds the branching in EnumLevel2 Step 6 and justifies the stop rules in EnumLevel3, and together with the final interval-hitting stage it yields the branching number below 1.7254.","core_discovery":"Theorem 7 is the central claim: in a convex bipartite graph, the number of minimal connected dominating sets is O(1.7254^n), and the sets can be enumerated in time O(1.7254^n). The algorithm first fixes the U-side of a solution by a branching procedure whose worst-case branching vector stays below 1.7254, then completes the solution by selecting W-vertices that hit a family of required intervals. The paper also proves a complementary lower bound: a family of convex bipartite graphs has $3^{{(n-2)/3}}$ minimal connected dominating sets, so the maximum number is exponential with base between $3^{{1/3}}$ \\approx 1.4422 and 1.7254, improving on the general-graph state of the art for this class.","pith_inferences":["The same interval-nesting mechanism could be tried on chordal bipartite graphs, for which no input-sensitive enumeration better than the general bound is known; an analogue of Lemma 6 there would likely give a similar exponential constant.","The gap between 3^{1/3} \\approx 1.4422 and 1.7254 suggests two possible routes to a tighter constant: refining the EnumLevel2 branching vector, or constructing lower-bound families with larger base.","The final interval-hitting stage is generic enough that it may also enumerate minimal dominating sets or maximal irredundant sets in convex bipartite graphs, both problems the paper leaves open."],"forward_implications":["Every n-vertex convex bipartite graph has at most O(1.7254^n) minimal connected dominating sets.","All minimal connected dominating sets of a convex bipartite graph can be enumerated in O(1.7254^n) time.","For convex bipartite graphs this replaces the best known general-graph input-sensitive bound, which is only of the form O(2^{(1-\\epsilon)n}) with an extremely small \\epsilon.","The lower-bound construction gives convex bipartite graphs with at least 3^{(n-2)/3} minimal connected dominating sets, so the upper bound is complemented by an exponential lower bound with base about 1.4422."],"supporting_citations":[{"why":"supplies the general-graph upper bound O(2^{(1-\\epsilon)n}) that this paper improves for the convex bipartite class.","marker":"[1]"},{"why":"provides the 3^{(n-2)/3} lower-bound construction and the enumeration methodology for chordality-bounded graph classes that the convex bipartite result adapts.","marker":"[2]"},{"why":"shows that minimum connected dominating set is solvable in polynomial time for convex bipartite graphs, the tractability backdrop for the class.","marker":"[5]"},{"why":"gives linear-time recognition of convex bipartite graphs and the interval-model background used throughout the proof.","marker":"[15]"},{"why":"supplies the branching-vector and branching-number analysis used to derive the O(1.7254^n) running time.","marker":"[16]"}],"fun_headline_variants":["Convex bipartite enumeration: O(1.7254^n) algorithm","First input-sensitive enumeration for convex bipartite graphs","Minimal connected dominating sets: convex bipartite bound at 1.7254","Bipartite gap: enumeration in 1.7254^n, count at least 1.4422^n"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The result rests on Lemma 6: once two selected U-vertices have overlapping neighbor intervals, at most one other selected U-vertex can have its interval inside their union; if that lemma or its ordering argument fails, the branching vector and the O(1.7254^n) bound do not follow.","fun_headline_variants_meta":{"raw":{"variants":["Convex bipartite enumeration: O(1.7254^n) algorithm","First input-sensitive enumeration for convex bipartite graphs","Minimal connected dominating sets: convex bipartite bound at 1.7254","Bipartite gap: enumeration in 1.7254^n, count at least 1.4422^n"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001346,"raw_usage":{"total_tokens":5454,"prompt_tokens":917,"completion_tokens":4537,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":533,"completion_tokens_details":{"reasoning_tokens":4451}},"tokens_in":533,"tokens_out":4537,"duration_ms":36015,"temperature":1.0,"reasoning_tokens":4451,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:54:03.219558+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search for a convex bipartite graph with a minimal connected dominating set D containing i,j,k,l such that Ii \\cap Ij is nonempty and both Ik and Il are contained in Ii \\cup Ij; such an instance would falsify Lemma 6 and invalidate the branching analysis. A weaker empirical check is to enumerate all minimal connected dominating sets in large random convex bipartite graphs and look for a count exceeding 1.7254^n.","supporting_citations":[{"cited_title":"Below all subsets for minimal connected dominating set","cited_arxiv_id":null,"evidence_quote":"supplies the general-graph upper bound O(2^{(1-\\epsilon)n}) that this paper improves for the convex bipartite class."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the 3^{(n-2)/3} lower-bound construction and the enumeration methodology for chordality-bounded graph classes that the convex bipartite result adapts."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"shows that minimum connected dominating set is solvable in polynomial time for convex bipartite graphs, the tractability backdrop for the class."},{"cited_title":"Brandst\\\" a dt, V","cited_arxiv_id":null,"evidence_quote":"gives linear-time recognition of convex bipartite graphs and the interval-model background used throughout the proof."}],"review_version":1}