{"id":"070700b6-cd8f-4b26-960c-b37f09cf40d1","arxiv_id":"2608.11289","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Recognizing CIS graphs is coNP-complete, proved by a polynomial reduction from 3SAT to the complement of the recognition problem.","lead":"This paper proves that recognizing CIS graphs, in which every maximal clique intersects every maximal stable set, is coNP-complete. The result settles an open problem posed by Chvátal in the 1990s that had attracted conflicting conjectures.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Reduction is not total as written: WLOG (2) excludes trivially satisfiable formulas with a literal in every clause and no graph is supplied for them; the theorem is patchable but the proof as stated is incomplete.","rationale":"I checked the construction and the main equivalence in both directions. The classification (11) of maximal stable sets of G is correct: the requirement that S∩N1(cj)=∅ forces \\bar N1(cj)⊆I, and maximality then forces cj as well as exactly the complement copies \\bar σ^j for σ∈I\\bar N1(cj). The converse domination argument also works, including for vertices in other H-components because of the complete join (8). The proof of (12) is sound: in Case 1 the chosen vertex of Hj\\{cj} is adjacent to all of C, and in Case 2 the vertex \\bar ω^j outside C and inside S is adjacent to all of C or the stability of S is contradicted. The sufficiency and necessity arguments using the maximal clique {c1,...,cm} are consistent. The real soft spot is not the graph-theoretic core but the reduction's totality. Assumption (2) removes an entire class of satisfiable 3SAT instances, and assumption (1) can reduce a formula to the empty instance; the paper does not say what graph to output in those cases. This does not undermine the central construction, and the gap is easily repaired by a constant non-CIS output for trivially satisfiable formulas, so the reader's CONDITIONAL verdict remains appropriate.","tokens_in":5994,"tokens_out":32121,"duration_ms":301262,"concrete_test":"Take the excluded 3SAT formula C = (u1∨u2∨u3) ∧ (u1∨\\bar u2∨\\bar u3), in which u1 occurs in every clause. Follow Section 2 literally: since WLOG (2) excludes this instance, identify the graph that the reduction outputs. If no graph is defined, the claimed many-one reduction is undefined on a satisfiable input. Then patch the proof by mapping all such formulas to a fixed non-CIS graph, e.g., C5, and verify by brute force that C5 has a maximal clique disjoint from a maximal stable set, and that every formula with a literal in every clause is satisfiable.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of the theorem is a many-one reduction from 3SAT to the complement of CIS, but the reduction is not total as written. Section 2's WLOG assumption (2) forbids any formula in which a literal occurs in every clause; such formulas are exactly the trivially satisfiable ones. The paper says only that this case is 'trivial' and proceeds, but it never defines a graph for these instances or explains how the reduction maps them. Likewise, applying simplification (1) can leave an empty formula, and the construction assumes m >= 1 clauses. Since coNP-hardness requires a polynomial-time total function from all 3SAT instances, the theorem as stated is not fully proved. This is a completeness gap rather than a flaw in the construction: the core classification (11) of maximal stable sets and the maximality arguments in (12) appear correct after checking the adjacency rules, and the missing cases can be handled by mapping trivially satisfiable formulas to a fixed non-CIS graph such as C5.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims to settle Chvátal's long-standing question by proving that recognizing CIS graphs is coNP-complete. The proof gives an explicit polynomial-time many-one reduction from 3SAT to the complement of CIS recognition. For a 3SAT formula satisfying a list of WLOG assumptions, the authors construct a graph G made of variable components F_i and clause components H_j, with a complete join between different H-components. They classify all maximal stable sets of G into two families ((10) and (11)), prove that every maximal stable set outside S1 intersects every maximal clique ((12)), and exhibit the set of clause vertices as a maximal clique ((14)). The equivalence 'G is not CIS iff the formula is satisfiable' then follows by using a satisfying assignment to build a stable set S in S1 disjoint from that clique, and conversely reading a satisfying assignment off such a disjoint pair. Membership in coNP is by the obvious two-set certificate.","tokens_in":6137,"tokens_out":17154,"duration_ms":164072,"significance":"If the proof is completed, the result settles an open problem posed by Chvátal in the 1990s and contradicts the earlier polynomial-time conjecture of Andrade, Boros, and Gurvich. The paper's core construction is direct and transparent, with no fitted parameters and no circular dependence on the target theorem; the classification of maximal stable sets in (11) is stated explicitly and argued case by case, and the size bounds O(mn) vertices and O(m^2 n^2) edges are clear. The main weakness is formal completeness of the reduction: several easy cases of 3SAT are excluded by WLOG assumptions without being mapped to a graph. This is patchable, but the theorem as stated is not fully proved until the reduction is made total.","major_comments":[{"comment":"The reduction is not total as written. Assumption (2) excludes every formula in which some literal occurs in all clauses, and it also excludes m = 1, since in a single 3-literal clause every literal occurs in every clause. After the simplification described in (1), one can also be left with the empty formula, while the construction assumes m ≥ 1. For these excluded formulas the paper says only that they are 'trivial' and does not define an output graph, so the many-one reduction from all of 3SAT is not defined on them. This is a genuine completeness gap in the proof of coNP-hardness. It is easily patchable: every formula excluded by (2), and the empty formula, is satisfiable, so the authors may map all such instances to a fixed non-CIS graph such as C5; I request that this case be written out explicitly.","section":"§2, WLOG assumptions (1)–(2) and (14)"},{"comment":"The treatment of literals occurring in no clause is asserted rather than demonstrated. If σ never occurs, setting \\barσ to true satisfies the clauses that contain \\barσ, but the remaining clauses still need to be satisfied; the paper does not state how the formula is updated, does not prove that the operation preserves satisfiability, and does not explain how the iteration of this simplification interacts with the requirements that every clause has exactly three distinct literals and that n ≥ 4. Because the later construction depends on conditions (1)–(4), the WLOG paragraph needs a precise preprocessing argument, or the excluded instances must be routed to the trivial-case handler.","section":"§2, WLOG assumption (1)"}],"minor_comments":[{"comment":"The sentence 'If π does not exist, we can reach a contradiction similarly' is too terse; the proof should spell out that C contains at most one vertex of H_j\\{c_j}, and that \\barω_j is adjacent to all vertices of H_i for i ≠ j by (8), so that the maximality contradiction is explicit.","section":"§2, proof of (12), Case 2"},{"comment":"The symbol S is overloaded: it denotes both the family of all maximal stable sets of G and a generic member of that family. Using a script letter for the family, for example \\mathcal{S}, would remove the ambiguity.","section":"§2, notation after (10)"},{"comment":"The proof of (10) is compressed; it would help to state explicitly that a stable set of G2 containing a clause vertex cannot contain any other c_k because of the complete joins in (8), and that maximality forces exactly one vertex from each F_i.","section":"§2, statement (10)"},{"comment":"There is a typo: 'exsits' should be 'exists'.","section":"§2, Case 1 of (12)"},{"comment":"Reference [16] is cited for the conjecture that CIS recognition is coNP-complete, but its title suggests a survey on bipartite hypergraphs; the authors should confirm that this reference indeed contains the attributed conjecture.","section":"Introduction, reference [16]"}],"recommendation":"major_revision","confidential_remarks":"The core reduction and the case analysis in (10)–(14) appear sound; I did not find an error in the classification of maximal stable sets. The main issue is formal: the WLOG assumptions make the reduction non-total, and the excluded trivially satisfiable cases are not mapped to graphs. This is a completeness gap that is readily fixable, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The real news: recognizing CIS graphs is coNP-complete, and this paper proves it by an explicit reduction from 3SAT to the complement. I went through the central lemma (11), which classifies all maximal stable sets of the constructed graph, and the maximality arguments in (12). The adjacency rules (7) and (8) are doing the work, and the classification appears correct. If (11) holds, the two directions of the equivalence follow cleanly. This is a substantial result, not an incremental one, and it resolves conflicting conjectures from the 1990s.\n\nThe gadget technique is the genuinely new piece: add auxiliary vertices to eliminate problematic maximal stable sets while keeping the reduction polynomial. The paper explains the intuition and then makes it rigorous. I checked the case analysis in (12); it is coherent. The citations to prior work are appropriate, including the conflicting conjectures on both sides. Self-citation is fair here because the cited Zang 1995 result is a different but relevant coNP-completeness statement, not a reused version of this theorem.\n\nNow the soft spots. The reduction is not total as written. Section 2 makes WLOG assumption (2): no literal occurs in every clause. Such formulas are trivially satisfiable, and the paper says so, but it never defines where the reduction maps them. Similarly, simplification (1) can produce an empty formula, and the construction assumes at least one clause and n ≥ 4. Since coNP-hardness requires a polynomial-time total function from all 3SAT instances, the theorem as stated is not fully proved. This is a completeness gap, not a fatal flaw: the missing cases can be handled by mapping every trivially satisfiable instance to a fixed non-CIS graph, say C5, and by adding dummy clauses/variables for the edge cases. That is a short patch. I also noticed small notational slips ('exsits', 'π = ω' should compare to ωj), but these are cosmetic.\n\nThe reader's verdict of conditional is fair. The stress-test note is right: the proof is patchable but incomplete as written. I would not desk-reject; I would send it to a competent graph theory referee and ask for a revision that makes the reduction total. Once patched, the paper should be accepted.\n\nWho is this for? Anyone working on CIS graphs, perfect-graph analogues, or graph recognition complexity. It is not a civilizational-scale result, but it settles a named open problem that had conflicting conjectures, and the proof is explicit enough to verify. I would bring it to a reading group and I would cite it once the missing cases are fixed.","headline":"The paper settles Chvátal's CIS recognition question with a coNP-completeness proof whose core construction checks out; the only real gap is that the reduction is not total as written because the WLOG assumptions waive trivially satisfiable cases without supplying an image graph.","tokens_in":6670,"tokens_out":1376,"would_cite":true,"duration_ms":14364,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C69","68Q25","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Recognizing CIS graphs is coNP-complete.","keywords":["CIS graph","maximal clique","maximal stable set","graph recognition","coNP-complete","3SAT reduction","computational complexity"],"falsifier":"Take the printed 3SAT example from Figure 1 (satisfiable, e.g. $u_1=u_2=u_4=\\mathrm{true}$), build the graph $G$ by rules (5)--(8), and compute every maximal stable set by exhaustive search. The theorem predicts $G$ is not CIS and that every maximal stable set matches the two forms in (11); any maximal stable set that does not, or a graph that is CIS, would falsify the central claim.","tokens_in":5759,"feed_emoji":"🧩","tokens_out":13991,"duration_ms":114200,"temperature":0.7,"pith_summary":"Recognizing CIS graphs—graphs in which every maximal clique meets every maximal stable set—turns out to be coNP-complete. The paper proves this by reducing 3SAT to the failure of the CIS property: for every 3SAT formula the construction yields a graph that is not CIS exactly when the formula is satisfiable. This settles a recognition problem that was posed in the 1990s and had drawn contradictory conjectures, one side expecting polynomial time and the other expecting intractability. The consequence is that, unless P equals coNP, no efficient algorithm can decide whether a graph is CIS.","feed_headline":"Recognizing CIS graphs is coNP-complete","feed_subtitle":"A 3SAT-to-graph reduction settles the 1990s open question: no quick recognition algorithm unless P equals coNP.","key_machinery":"The load-bearing object is the gadget graph $G$ assembled from a 3SAT instance. Each variable contributes an edge $u_i\\bar u_i$ (the truth-setting component), and each clause $c_j$ contributes a satisfaction-testing component $H_j$ consisting of an isolated vertex $c_j$ plus disjoint edges $u_j^k\\bar u_j^k$ for every variable absent from $c_j$; adjacency between variable endpoints and $H_j$ records which literals satisfy $c_j$, and all clause components are pairwise completely joined. The key mechanism is classification (11): every maximal stable set of $G$ that is not already a transversal of the variable edges has the exact shape $I\\cup\\{c_j\\}\\cup\\{\\bar\\sigma^j:\\sigma\\in I\\setminus\\bar N_1(c_j)\\}$, with $\\bar N_1(c_j)\\subseteq I$. This classification converts the geometric question \"is there a maximal clique disjoint from a maximal stable set?\" into the logical question \"is there a truth assignment making every clause true?\"","core_discovery":"The paper's central claim is that recognizing CIS graphs is $\\mathsf{coNP}$-complete. The proof reduces 3SAT to the complement of recognition: given any 3SAT formula $C$ with clauses $c_1,\\ldots,c_m$ and variables $u_1,\\ldots,u_n$, it builds a graph $G$ such that $G$ is not CIS exactly when $C$ is satisfiable. The reduction is made to work by a complete classification of the maximal stable sets of $G$: every one either picks one endpoint from each variable edge $u_i\\bar u_i$, or else has the form $I\\cup\\{c_j\\}\\cup\\{\\bar\\sigma^j:\\sigma\\in I\\setminus\\bar N_1(c_j)\\}$ for some clause $j$. With this classification, a satisfying assignment yields a maximal stable set that is disjoint from the maximal clique formed by the clause vertices, and any maximal clique/maximal stable set disjoint pair forces a satisfying assignment. Therefore the recognition problem is both in $\\mathsf{coNP}$ and $\\mathsf{coNP}$-hard.","pith_inferences":["Not claimed by the paper, but a natural check is to enumerate the maximal stable sets of the Figure 1 graph by brute force; the formula there is satisfiable (for instance u1 = u2 = u4 = true), so the reduction predicts a maximal stable set disjoint from the clause clique, and every maximal stable set should match one of the two forms in (11).","The same gadget might transfer to other classes defined by intersection of maximal structures: wherever the obstruction is a disjoint maximal-clique/maximal-stable-set pair, a variant of this construction could yield coNP-completeness for recognizing related classes such as almost-CIS graphs.","Because the classification gives an explicit description of all maximal stable sets of these gadgets, the reduction could serve as a source of worst-case instances for algorithms that enumerate maximal stable sets; one could test whether the number of maximal stable sets of the gadget can be exponential in n while still obeying (11)."],"forward_implications":["No polynomial-time algorithm recognizes CIS graphs unless P equals coNP.","The reduction is polynomial and concrete: the constructed graph has O(mn) vertices and O(m^2 n^2) edges, so the hardness is not hidden in an exponential blow-up.","The classification of maximal stable sets means that a satisfying assignment transparently produces a non-CIS witness: a transversal S of the variable edges disjoint from the maximal clique formed by the clause vertices.","The result confirms the intractability side of the earlier conflicting conjectures, and it rules out a forbidden-induced-subgraph characterization, because every graph is an induced subgraph of some CIS graph."],"supporting_citations":[{"why":"Supplies the NP-completeness of 3SAT, the source problem used in the reduction.","marker":"[12]"},{"why":"Defines CIS graphs and poses the recognition problem whose complexity the paper settles.","marker":"[8]"},{"why":"Establishes the closest prior complexity result, that deciding whether a specified maximal stable set meets every maximal clique is coNP-complete.","marker":"[15]"}],"fun_headline_variants":["CIS recognition: coNP-complete, settling 1990s open problem","Chvátal's CIS question: coNP-complete","CIS recognition: no polynomial-time test, coNP-complete"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that statement (11) really does classify every maximal stable set of the constructed graph; if a maximal stable set mixing two clause components or omitting the clause vertex exists, the claimed equivalence between satisfiability and non-CIS breaks.","fun_headline_variants_meta":{"raw":{"variants":["CIS recognition: coNP-complete, settling 1990s open problem","Chvátal's CIS question: coNP-complete","CIS recognition: no polynomial-time test, coNP-complete"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000616,"raw_usage":{"total_tokens":2807,"prompt_tokens":839,"completion_tokens":1968,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":455,"completion_tokens_details":{"reasoning_tokens":1907}},"tokens_in":455,"tokens_out":1968,"duration_ms":13931,"temperature":1.0,"reasoning_tokens":1907,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T14:15:06.733918+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the printed 3SAT example from Figure 1 (satisfiable, e.g. $u_1=u_2=u_4=\\mathrm{true}$), build the graph $G$ by rules (5)--(8), and compute every maximal stable set by exhaustive search. The theorem predicts $G$ is not CIS and that every maximal stable set matches the two forms in (11); any maximal stable set that does not, or a graph that is CIS, would falsify the central claim.","supporting_citations":[{"cited_title":"Garey and D","cited_arxiv_id":null,"evidence_quote":"Supplies the NP-completeness of 3SAT, the source problem used in the reduction."},{"cited_title":"Chv´ atal, Two research problems on Grillet graphs, Personal Communication, 1992","cited_arxiv_id":null,"evidence_quote":"Defines CIS graphs and poses the recognition problem whose complexity the paper settles."},{"cited_title":"Zang, Generalizations of Grillet’s theorem on maxim al stable sets and maximal cliques in graphs, Discrete Math","cited_arxiv_id":null,"evidence_quote":"Establishes the closest prior complexity result, that deciding whether a specified maximal stable set meets every maximal clique is coNP-complete."}],"review_version":1}