{"id":"5fc95138-bc6b-4563-a162-836fc3359968","arxiv_id":"1908.03389","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Both connectivity-constrained cut problems are NP-complete on planar bipartite and split graphs, yet they are fixed-parameter tractable in treewidth, twin-cover number, and solution size.","lead":"Connected Maximum Cut and Maximum Minimal Cut are two graph-cutting problems that add connectivity requirements to the classic Maximum Cut problem. This paper maps exactly where they become intractable and how fast they can be solved when a small structural parameter is fixed.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 46's solution-size FPT results rest on an unproven k-prism lemma: the sketch does not show a k-prism minor yields a connected partition of all of G with at least k cut edges, leaving the otherwise branch unsupported.","rationale":"The reader's weakest_assumption is exactly the theorem I would stress: the FPT-by-solution-size results depend on it, and the manuscript's proof is only a sketch. In good faith, I believe the lemma is true: a k-prism has a natural cut separating its two cycles, and a minor realization can be extended to a connected partition of the whole graph via a spanning-tree assignment. But the paper does not show this, and a two-sentence appeal to adding edges is not a rigorous derivation. This is an addressable gap, not a demonstrated falsehood. I also checked the other flagged issues: the Theorem 7 (if-and-only-if) arithmetic is indeed wrong as printed because the bound adds nK^2 edges that should not be cut, but the intended contradiction is recovered by noting that helper-pendant edges are internal in the case considered; this is another repairable proof slip. The omitted treewidth DP correctness proof is standard but should be supplied. None of these issues makes me think the central results are false; they make the paper conditional rather than accepted as-is, matching the reader's CONDITIONAL verdict.","tokens_in":23945,"tokens_out":34614,"duration_ms":371385,"concrete_test":"Formalize the missing lemma for Theorem 46: let {B_x} be connected branch sets of a k-prism minor in G, contract each B_x, take a spanning tree of the contracted graph, delete tree edges so each component contains exactly one branch set, assign every other vertex to its component, and set S to the union of the a-side branch sets plus their assigned vertices. Then verify that G[S] and G[V\\S] are connected and that each of the k rung pairs B_{a_i}, B_{b_i} contributes at least one edge to delta(S). If this construction goes through for every connected G containing a k-prism minor, Theorem 46's otherwise branch is sound; if not, the O*(2^{O(k^2)}) algorithms need a different argument.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing gap is in Theorem 46 (Section 4.4). The algorithm runs the treewidth DP when tw(G)=O(k^2), and otherwise concludes that G has a minimal cut (and a connected cut) of size at least k because G contains a k-prism minor. The proof given is: take k middle edges corresponding to K2 in the k-prism minor and add some edges to make these edges form a cutset of some minimal cut. This is not a proof: a cut is a partition of V(G), not an edge set that can be augmented, and the text never specifies how the branch sets of the minor are extended to cover vertices outside the branch sets while keeping both sides connected and while preserving at least k cut edges. Without this lemma, the O*(2^{O(k^2)}) algorithms for both Connected Maximum Cut and Maximum Minimal Cut lose their otherwise branch. The claim is plausible and can likely be proved by taking connected branch sets B_{a_i} and B_{b_i} for the prism, assigning every remaining vertex via a spanning tree of the contracted graph, and counting one rung edge per i; but the paper does not supply this argument. A second, smaller issue is the (if-and-only-if) direction of Theorem 7: the displayed bound adds nK^2 as though helper-pendant edges were cut, although those edges are internal to V\\S in the case considered, so the stated contradiction does not follow as written; the bound can be repaired by omitting nK^2.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies two variants of Maximum Cut with connectivity constraints: Connected Maximum Cut (CMC), where one side of the cut must induce a connected subgraph, and Maximum Minimal Cut (MMC), where the cutset must be inclusion-minimal (equivalently, both sides must be connected in a connected graph). The main claimed contributions are: (i) NP-completeness of CMC on planar bipartite graphs (Theorem 7) and on split graphs (Theorem 9); (ii) NP-completeness of MMC on planar bipartite subcubic graphs (Theorem 8) and on split graphs (Theorem 10); (iii) FPT algorithms parameterized by treewidth, including deterministic O*(tw^{O(tw)}) algorithms, rank-based single-exponential algorithms (Theorems 32--33), and Monte-Carlo O*(3^{tw}) and O*(4^{tw}) algorithms via Cut & Count (Theorems 36--37); (iv) XP algorithms parameterized by clique-width (Theorem 42); (v) FPT algorithms parameterized by twin-cover number (Theorems 43--44); and (vi) FPT algorithms parameterized by solution size k, namely O*(2^{O(k^2)}) for both problems (Theorem 46), an O*(9^k) randomized algorithm and an O*(38.2^k) deterministic algorithm for CMC (Theorems 47--48), and no-polynomial-kernel results (Theorem 49). The paper also positions these results relative to the known polynomial-time solvability of plain Maximum Cut on planar and bipartite graphs.","tokens_in":24111,"tokens_out":14243,"duration_ms":127395,"significance":"If the results are correct after revision, the paper makes a solid contribution to the parameterized complexity of connectivity-constrained cut problems. The planar-bipartite NP-completeness results are genuinely striking, since plain Maximum Cut is polynomial on both planar graphs and bipartite graphs, and the split-graph hardness complements known results for Maximum Cut. The FPT algorithms for treewidth, twin-cover, and solution size are nontrivial and improve on the prior O*(2^{2^{O(k)}}) bound for CMC. The paper gives explicit running times, a useful summary table, and reductions from well-chosen source problems. However, two load-bearing proof gaps--the inequality in the (⇐) direction of Theorem 7 and the unproved k-prism lemma behind Theorem 46--must be repaired, and the correctness of the main treewidth DP is omitted. These issues do not appear fatal to the overall research program, but they are central enough to preclude acceptance in the current form.","major_comments":[{"comment":"The displayed inequality '|δ(S)| ≤ m√K + 3m + 2nK + (K + 4)(n−1) + nK^2' is not valid in the scenario being considered. When neither literal vertex of a variable x_i lies in S, all helper vertices h_i^k and their pendant vertices must lie in V\\S (otherwise G[S] would contain an isolated vertex), so the nK^2 helper--pendant edges are internal to V\\S and contribute zero to δ(S). Adding the nK^2 term makes the upper bound larger than the target threshold for every K, since the difference between the threshold and this bound is −nK − 2n + 2, which is negative for all n ≥ 1. The claimed contradiction therefore does not follow as written. The argument is repairable by deleting the nK^2 term from the upper bound, but the proof must be corrected.","section":"Section 3.1, Theorem 7 (⇐ direction)"},{"comment":"The 'otherwise' branch of the algorithm is not established. The statement 'we take k middle edges corresponding to K2 in the k-prism minor and add some edges to make these edges form a cutset of some minimal cut of G' does not constitute a proof, because a cut of G is a partition of V(G), not an edge set that can be augmented arbitrarily. The proof does not specify how the two cycles of the k-prism minor are extended to a partition of all of V(G) such that both sides induce connected subgraphs and at least k rung edges are cut; vertices outside the branch sets may need to be assigned in a way that preserves connectivity on both sides. Since this k-prism lemma is the sole justification for the otherwise branch of the O*(2^{O(k^2)}) algorithms for both CMC and MMC, the lemma must be proved rigorously or replaced by another argument. The claim is plausible and can likely be proved by taking connected branch sets for the two cycles, assigning all remaining vertices via spanning trees of the contracted graph while maintaining connectivity, and counting one rung edge per i; however, this argument is absent from the manuscript.","section":"Section 4.4, Theorem 46"},{"comment":"The treewidth dynamic programming for Maximum Minimal Cut (and Connected Maximum Cut) is stated without a correctness proof. The sentence 'The correctness of the formulas are similar to ones for other connectivity problems, and hence we omit the proof here' is not sufficient for a self-contained journal paper, particularly because the DP tracks partitions on both sides of the cut and the forget and join operations interact with the requirement that both sides of the final cut are connected. These algorithms are also used as subroutines in the solution-size FPT algorithms of Theorem 46, so a rigorous correctness proof (or a precise reference to a proof for this exact DP) should be supplied.","section":"Section 4.1.1, Theorems 12 and 13"}],"minor_comments":[{"comment":"The consistency condition 'V1\\V2 = ∅' should presumably read 'V1 ∩ V2 = ∅'; in addition, the assertion that a connected graph with k components has 2^{k−1} consistent cuts implicitly fixes a vertex in V1, and this should be stated explicitly.","section":"Section 2, Definition 34"},{"comment":"The proof text says 'we show that G has a cut of size at least k if and only if G′ has a connected cut of size at least k n^3'; since the problem being reduced to is Maximum Minimal Cut, this should read 'minimal cut' rather than 'connected cut'.","section":"Section 3.2, Theorem 10 proof"},{"comment":"The same symbols S_i and T_i are used both for subsets of a bag and for partitions of those subsets, making formulas such as mci(S_i,T_i,S_i,T_i) hard to parse; using different alphabets (e.g., script letters) for partitions would improve readability.","section":"Section 4.1.1, Definition 11 and recurrences"},{"comment":"The sentence 'This means that there is no path between v and s in G[S] of any partial solution at any ancestor node k of i. Therefore, v is contained in a block of size at least two in node j.' is confusingly phrased and appears to state the opposite of the intended meaning; it should say that a singleton block at a forget node can never connect to s later and is therefore discarded, which is why the recurrence merges v into an existing block.","section":"Section 4.1.1, forget node paragraph"},{"comment":"The phrase 'with at least twin-classes' should read 'with at least two twin-classes'.","section":"Section 4.2, Observation 2"},{"comment":"In the converse direction, 'the cut edges between two twin-classes of Lv is counted by mc(b,tb)' should presumably read 'between two twin-classes of Lb'.","section":"Section 4.2, Lemma 41 proof"},{"comment":"The sentence 'we further guess each type of cliques in G[V\\X] has an intersection with only S, with only V\\S, or with both S and V\\S' should be rephrased for grammatical clarity, e.g., 'we guess, for each type of cliques, whether the type intersects only S, only V\\S, or both'.","section":"Section 4.3, Theorem 44 proof"}],"recommendation":"major_revision","confidential_remarks":"The two main gaps (Theorem 7's inequality and Theorem 46's k-prism lemma) are substantial but appear repairable within the scope of the paper. The k-prism lemma is the most critical: if it fails, the solution-size FPT algorithms lose their otherwise branch and Theorem 46 collapses. I recommend a major revision with a specific request for a complete proof of that lemma, a corrected bound in Theorem 7, and a correctness proof for the treewidth DP. The problem is well cited and within the journal's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the paper is worth reading: the planar-bipartite NP-completeness results are genuinely interesting—Maximum Cut is polynomial on both planar graphs and bipartite graphs, yet both connectivity-constrained variants become NP-complete on the intersection—and the O*(9^k) randomized algorithm for Connected Maximum Cut is a real improvement over the previous double-exponential bound. Second, it is not referee-ready as written. Two proofs have real holes, and both look repairable.\n\nWhat it does well: the treewidth machinery (rank-based approach, Cut & Count) is competently applied, the twin-cover algorithms extend Ganian's Maximum Cut work naturally, and the clique-width XP algorithms fill a gap. The summary table is clear and the citation pattern is honest.\n\nThe soft spots, in order of importance. Theorem 46 is the load-bearing one. The 'otherwise' branch concludes that G has a minimal cut of size at least k because it contains a k-prism minor, but the argument is two sentences: take the k middle edges and 'add some edges' to make them a cutset of a minimal cut. A cut is a partition of V(G), not an edge set; the text never shows how the prism's branch sets are extended to cover every vertex while keeping both sides connected and preserving k cut edges. The claim is plausible, but as written it is not a proof, and both O*(2^{O(k^2)}) algorithms depend on it.\n\nTheorem 7, only-if direction: the bound |δ(S)| ≤ m√K + 3m + 2nK + (K+4)(n−1) + nK^2 is just the total number of edges in the reduced graph, which is larger than the threshold, so the claimed contradiction does not follow. The proof needs to subtract the helper-pendant edges forced internal to V\\S in the dead-variable case. The fix is routine, but it is not in the paper.\n\nMinor items: the correctness proof for the base treewidth DP is explicitly omitted; Theorems 8 and 10 write S'_i \\ V where they mean S'_i ∩ V; and the Cut & Count introduce-edge formula checks |(S^l_i ∪ S^r_i) \\ {u,v}| = 1 instead of |{u,v} ∩ (S^l_i ∪ S^r_i)| = 1.\n\nWho it is for: people working on parameterized complexity of cut problems with connectivity constraints. The core results are likely all true, and the paper deserves a serious referee, but I would ask for a rewritten proof of Theorem 46 and a repaired bound in Theorem 7 before signing off.","headline":"A useful, mostly well-executed parameterized-complexity paper that is not referee-ready as written: the planar-bipartite NP-hardness proof has a counting gap in the only-if direction, and the solution-size FPT theorem rests on a two-sentence sketch of the k-prism lemma.","tokens_in":24798,"tokens_out":11023,"would_cite":true,"duration_ms":97845,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that Connected Maximum Cut and Maximum Minimal Cut are NP-complete even on planar bipartite graphs and on split graphs, and gives fixed-parameter tractable algorithms for treewidth, twin-cover number, and solution size.","keywords":["maximum cut","connected maximum cut","maximum minimal cut","parameterized complexity","NP-hardness","treewidth","twin-cover number","clique-width"],"falsifier":"Construct a graph containing a $k$-prism minor, for example the prism itself with arbitrary gadgets attached, and compute its maximum minimal cut; if any such graph has maximum minimal cut size below $k$, the large-cut branch of the $O^{*}(2^{O(k^2)})$ algorithm collapses, and inspecting the branch-set partition induced by the two cycles would show where the sketched argument fails.","tokens_in":23618,"feed_emoji":"✂️","tokens_out":11560,"duration_ms":104901,"temperature":0.7,"pith_summary":"This paper studies two variants of Maximum Cut in which the sides of the cut must themselves be connected: Connected Maximum Cut requires one side to induce a connected subgraph, and Maximum Minimal Cut requires both sides to be connected, which is equivalent to the cut set being inclusion-minimal. The paper's central result is that both problems remain NP-complete even on planar bipartite graphs and on split graphs, despite the fact that ordinary Maximum Cut is solvable in polynomial time on planar graphs and on bipartite graphs. On the algorithmic side, the paper proves that both problems are fixed-parameter tractable when parameterized by treewidth, by twin-cover number, and by the size of the solution, and gives an XP algorithm when parameterized by clique-width. The results draw a precise boundary: the connectivity requirement turns two of the most tractable classes for Maximum Cut into intractable ones, yet the structural parameters that make other hard graph problems manageable still control these variants.","feed_headline":"Connectivity makes max cut NP-hard even on planar bipartite graphs","feed_subtitle":"Plain maximum cut is polynomial there; one connectivity constraint flips it, but treewidth and size parameters tame it.","key_machinery":"The central mechanism is dynamic programming on a tree decomposition whose states record, for each bag, a partition of the vertices on each side of the cut into connectivity blocks, so that merging blocks joined by an edge preserves the connectivity information needed to test the one-sided or two-sided condition. Two accelerators are applied to this dynamic program: a rank-based reduction that keeps only $2^{O(tw)}$ representative weighted partitions, and the randomized Cut & Count method, which counts consistent cuts modulo two so that connectedness is detected by parity and isolated by the Isolation Lemma. For the solution-size parameter, the load-bearing structural theorem is that a graph either has treewidth $O(k^2)$ or contains a $k$-prism minor, two $k$-cycles joined by a matching; the paper asserts that the prism minor case forces a minimal cut of size at least $k$, which supplies the large-cut branch of the win-win argument.","core_discovery":"On a connected graph, a cut is minimal if and only if both sides induce connected subgraphs, so Maximum Minimal Cut asks for a large cut whose two sides are both connected, while Connected Maximum Cut asks for a large cut with one connected side. The paper proves that both problems are NP-complete on planar bipartite graphs and on split graphs, so the polynomial-time algorithms for Maximum Cut on planar and bipartite graphs do not survive the addition of the connectivity constraint even when these two tractable classes are combined. For parameters, the paper establishes fixed-parameter algorithms: $O^{*}(3^{tw})$ randomized and $O^{*}((1+2^{\\omega+1})^{tw})$ deterministic for Connected Maximum Cut, $O^{*}(4^{tw})$ randomized and $O^{*}(2^{(\\omega+2)tw})$ deterministic for Maximum Minimal Cut parameterized by treewidth; $O^{*}(2^{2^{tc}+tc})$ and $O^{*}(2^{tc}3^{2^{tc}})$ algorithms parameterized by twin-cover number; and $O^{*}(2^{O(k^2)})$ algorithms parameterized by solution size, with a randomized $O^{*}(9^k)$ and a deterministic $O^{*}(38.2^k)$ algorithm for Connected Maximum Cut. It also gives $n^{O(w)}$ algorithms when parameterized by clique-width and shows that neither problem admits a polynomial kernel parameterized by solution size unless NP $\\subseteq$ coNP/poly.","pith_inferences":["If the $k$-prism premise is verified, the same win-win strategy likely applies to other cut problems in which a large prism minor forces a large feasible cut; if the premise fails, the solution-size algorithms still work on bounded-treewidth graphs but lose their large-cut branch.","Since Maximum Cut is already hard for the clique-width parameter and the paper's clique-width algorithms are only XP, it is likely that both connectivity-constrained variants inherit hardness for clique-width as well, though the paper does not show this.","The disjoint-union composition behind the no-kernel result suggests that adding a second parameter such as treewidth or vertex-cover size might restore kernelizability and is a natural next target."],"forward_implications":["Since both problems are NP-complete on planar bipartite graphs, no polynomial-time algorithm for either variant on planar or bipartite graphs can exist unless P = NP, even though ordinary Maximum Cut is polynomial on both classes.","The treewidth algorithms make both problems tractable on graphs of bounded treewidth, and the $O^{*}(3^{tw})$ and $O^{*}(4^{tw})$ randomized bounds cannot give false positives, matching the practical behavior of the Cut & Count technique.","The twin-cover FPT algorithms extend tractability to graphs whose non-twin adjacencies are covered by a small vertex set, so the parameterized behavior mirrors that of Maximum Cut itself on this parameter.","The solution-size algorithms run in $O^{*}(2^{O(k^2)})$ for both problems and in $O^{*}(9^k)$ randomized time for Connected Maximum Cut, meaning instances with a small optimum cut can be solved even when the graph is large, and the deterministic $O^{*}(38.2^k)$ bound removes randomness for Connected Maximum Cut.","Neither problem has a polynomial kernel parameterized by solution size unless NP $\\subseteq$ coNP/poly, so the fixed-parameter algorithms cannot be compressed into small equivalent instances by standard kernelization."],"supporting_citations":[{"why":"supplies the planar NP-hardness reduction that the paper adapts with bridge vertices to prove Connected Maximum Cut NP-complete on planar bipartite graphs.","marker":"[32]"},{"why":"proves Maximum Minimal Cut NP-complete on planar graphs and supplies the equivalence between minimal cuts and two-sided connected cuts used throughout.","marker":"[31]"},{"why":"provides the rank-based representative-set reduction used to speed the treewidth dynamic program to single-exponential deterministic time.","marker":"[3]"},{"why":"provides the Cut & Count parity-counting technique and Isolation Lemma framework behind the $O^{*}(3^{tw})$ and $O^{*}(4^{tw})$ randomized algorithms.","marker":"[17]"},{"why":"states that graphs without a $k$-prism minor have treewidth $O(k^2)$, the structural win-win used for the solution-size FPT algorithms.","marker":"[2]"},{"why":"defines twin-cover number and gives the algorithm to compute a minimum twin-cover, on which the twin-cover FPT algorithms rely.","marker":"[24]"},{"why":"gives the Maximum Cut NP-completeness on split graphs that the Theorem 10 reduction to Maximum Minimal Cut on split graphs starts from.","marker":"[7]"},{"why":"shows Maximum Cut is polynomial-time solvable on planar graphs, the tractability boundary that the planar bipartite NP-completeness theorems sharpen.","marker":"[30, 39]"},{"why":"supplies Planar Monotone 3-SAT, the source problem for the planar bipartite NP-completeness reduction.","marker":"[18]"}],"fun_headline_variants":["Connectivity makes max cut NP-hard on planar bipartite graphs","Max cut connectivity: NP-hard even on planar bipartite graphs","Connectivity constraint flips max cut tractability","One connectivity condition makes max cut NP-hard on planar bipartite"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The algorithm parameterized by solution size assumes that every graph containing a $k$-prism minor, two $k$-cycles connected by a matching, has a minimal cut with at least $k$ edges, an assertion the paper backs with a two-sentence sketch rather than a detailed proof.","fun_headline_variants_meta":{"raw":{"variants":["Connectivity makes max cut NP-hard on planar bipartite graphs","Max cut connectivity: NP-hard even on planar bipartite graphs","Connectivity constraint flips max cut tractability","One connectivity condition makes max cut NP-hard on planar bipartite"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000944,"raw_usage":{"total_tokens":4041,"prompt_tokens":962,"completion_tokens":3079,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":578,"completion_tokens_details":{"reasoning_tokens":3011}},"tokens_in":578,"tokens_out":3079,"duration_ms":21570,"temperature":1.0,"reasoning_tokens":3011,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:17:47.500220+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a graph containing a $k$-prism minor, for example the prism itself with arbitrary gadgets attached, and compute its maximum minimal cut; if any such graph has maximum minimal cut size below $k$, the large-cut branch of the $O^{*}(2^{O(k^2)})$ algorithm collapses, and inspecting the branch-set partition induced by the two cycles would show where the sketched argument fails.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the planar NP-hardness reduction that the paper adapts with bridge vertices to prove Connected Maximum Cut NP-complete on planar bipartite graphs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"proves Maximum Minimal Cut NP-complete on planar graphs and supplies the equivalence between minimal cuts and two-sided connected cuts used throughout."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the rank-based representative-set reduction used to speed the treewidth dynamic program to single-exponential deterministic time."},{"cited_title":"Cygan, J","cited_arxiv_id":null,"evidence_quote":"provides the Cut & Count parity-counting technique and Isolation Lemma framework behind the $O^{*}(3^{tw})$ and $O^{*}(4^{tw})$ randomized algorithms."},{"cited_title":"Birmel \\'e , J","cited_arxiv_id":null,"evidence_quote":"states that graphs without a $k$-prism minor have treewidth $O(k^2)$, the structural win-win used for the solution-size FPT algorithms."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"defines twin-cover number and gives the algorithm to compute a minimum twin-cover, on which the twin-cover FPT algorithms rely."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the Maximum Cut NP-completeness on split graphs that the Theorem 10 reduction to Maximum Minimal Cut on split graphs starts from."},{"cited_title":"de Berg and A","cited_arxiv_id":null,"evidence_quote":"supplies Planar Monotone 3-SAT, the source problem for the planar bipartite NP-completeness reduction."}],"review_version":1}