Pith. sign in

REVIEW 2 major objections 5 minor 16 references

How Difficult Is It to Recognize CIS Graphs?

T0 review · 2 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Recognizing CIS graphs is coNP-complete.

desk verdict 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. read the letter →

arxiv 2608.11289 v1 pith:ME6D4XEW submitted 2026-08-11 cs.DM math.CO

Rongchuan Tao , Mengxi Yang , Wenan Zang This is my paper · ORCID
classification cs.DMmath.CO MSC 05C6968Q2568R10
keywords CISgraphmaximalcliquestablesetrecognitioncoNP-complete3SATreductioncomputationalcomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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?"

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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).
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

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.

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 (2)
  1. [§2, WLOG assumptions (1)–(2) and (14)] 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.
  2. [§2, WLOG assumption (1)] 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.
minor comments (5)
  1. [§2, proof of (12), Case 2] 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.
  2. [§2, notation after (10)] 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.
  3. [§2, statement (10)] 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.
  4. [§2, Case 1 of (12)] There is a typo: 'exsits' should be 'exists'.
  5. [Introduction, reference [16]] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: self-contained 3SAT reduction proves coNP-hardness and coNP-membership.

full rationale

The derivation is a direct many-one reduction from external 3SAT to the complement of CIS recognition. The graph G is built explicitly from the clause/variable structure, and the key claims—classification (11) of maximal stable sets, the intersection property (12), and the maximal-clique claim (14)—are proved inside the paper from the adjacency rules (7)–(8). No parameter is fitted from the target property, no equivalent of the CIS-recognition problem is assumed as an input, and no theorem from the authors' prior work is load-bearing; citations to Zang [15] and to Deng, Li, and Zang [9,10] are contextual and are not used to establish the reduction. The possible gap concerning WLOG assumption (2) (trivially satisfiable formulas with a literal in every clause are not mapped to an explicit graph) is a completeness or correctness caveat, not a circularity: it does not make the construction's output equivalent to its input by definition. Hence no circular step is present.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The proof uses standard background: NP-completeness of 3SAT, definitions of maximal clique and maximal stable set, and WLOG simplifications for the 3SAT instance. It introduces no free parameters and no new postulated physical or mathematical entities; the auxiliary vertices in the reduction are part of the explicit construction.

assumptions (3)
  • standard math 3SAT is NP-complete.
    Used as the source problem for the polynomial reduction at the start of Section 2; standard result from Garey and Johnson [12].
  • domain assumption The WLOG simplifications (1)-(4) preserve satisfiability of the 3SAT instance.
    These assumptions allow the reduction to assume each literal occurs, no literal occurs in every clause, no clause contains both signs of a variable, and n is at least 4. They are used in Section 2 immediately before the graph construction.
  • standard math Maximality of a clique or stable set is polynomial-time checkable.
    Needed for coNP membership of the recognition problem; a certificate is a maximal clique and a maximal stable set that are disjoint, and maximality is verified by checking all outside vertices.

how reviews work

0 comments
Cite this review

Pith. "Pith review of How Difficult Is It to Recognize CIS Graphs?." pith.science (2026). https://pith.science/paper/ME6D4XEW

@misc{pith2026260811289,
  author       = {Pith},
  title        = {Pith review of: How Difficult Is It to Recognize CIS Graphs?},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ME6D4XEW}},
  note         = {Machine review of arXiv:2608.11289}
}
abstract

A graph $G$ is called $CIS$ if each maximal clique intersects each maximal stable set of $G$, with maximality taken with respect to set inclusion. CIS graphs resemble perfect graphs in several respects and have interesting applications in game theory. The complexity of recognizing CIS graphs was posed as an open problem by Chv\'atal in the 1990s and has since led to conflicting conjectures. We settle the problem by showing that recognizing CIS graphs is $\mathsf{coNP}\text{-complete}$.

Figures

Figures reproduced from arXiv: 2608.11289 by the authors.

Figure 1
Figure 1. The graph G for the 3SAT instance (in CNF) with clauses c1 = (u1 ∨ u2 ∨ u3), c2 = (¯u1 ∨ u¯2 ∨ u4), c3 = (u1 ∨ u¯3 ∨ u¯4). Each blue edge represents a complete join between a vertex in Fi and all vertices in Hj for some i ∈ {1, 2, 3, 4} and j ∈ {1, 2, 3}. For example, vertex u1 is adjacent to every vertex in H3; vertex ¯u1 is adjacent to every vertex in H2; and vertex u3 is adjacent to every vertex in H1. Let V1 := … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

  1. [1]

    Alc´ on, M

    L. Alc´ on, M. Gutierrez, and M. Milaniˇ c, A characteriza tion of claw-free CIS graphs and new results on the order of CIS graphs, Electron. Notes Theor. Comput. Sci. 346 (2019), 15-27

    work page 2019

  2. [2]

    Andrade, E

    D. Andrade, E. Boros, and V. Gurvich, On graphs whose maxi mal cliques and stable sets intersect, DIMACS Technical Report 2006-16, New Jersey, 20 06

    work page 2006

  3. [3]

    Andrade, E

    D. Andrade, E. Boros, and V. Gurvich, On graphs whose maxi mal cliques and stable sets intersect, in: Optimization Problems in Graph Theory , Springer Optimization and Its Applications 139, Springer, 2018, pp. 3-63

    work page 2018

  4. [4]

    Berge, Problems 9.11 and 9.12, in: Graphs and Order (I

    C. Berge, Problems 9.11 and 9.12, in: Graphs and Order (I. Rival, Ed.), Reidel, Dordrecht, 1985, pp. 583-584

    work page 1985

  5. [5]

    Boros, V

    E. Boros, V. Gurvich, and M. Milaniˇ c, On equistable, spl it, CIS, and related classes of graphs, Discrete Appl. Math. 216 (2017), 47-66

    work page 2017

  6. [6]

    Boros, V

    E. Boros, V. Gurvich, and I. Zverovich, On split and almos t CIS-graphs, Australas. J. Combin. 43 (2009), 163–180

    work page 2009

  7. [7]

    Chudnovsky, N

    M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, T he strong perfect graph theorem, Ann. of Math. (2) 164 (2006), 51-229

    work page 2006

  8. [8]

    Chv´ atal, Two research problems on Grillet graphs, Personal Communication, 1992

    V. Chv´ atal, Two research problems on Grillet graphs, Personal Communication, 1992

    work page 1992

Show all 16 references
  1. [9]

    X. Deng, G. Li, and W. Zang, Proof of Chv´ atal’s conjectur e on maximal stable sets and maximal cliques in graphs, J. Combin. Theory Ser. B 91 (2004), 301-325. 6

    2004

  2. [10]

    Proof of Chv ´ atal’s conjecture on maximal stable sets and maximal cliques in graphs

    X. Deng, G. Li, and W. Zang, Corrigendum to: “Proof of Chv ´ atal’s conjecture on maximal stable sets and maximal cliques in graphs” [ J. Combin. Theory Ser. B 91 (2004), 301–325], J. Combin. Theory Ser. B 94 (2005), 352–353

    2004

  3. [11]

    Dobson, A

    E. Dobson, A. Hujdurovi´ c, M. Milaniˇ c, and G. Verret, Vertex-transitive CIS graphs, Euro- pean J. Combin. 44 (2015), 87-98

    2015

  4. [12]

    Garey and D

    M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP- Completeness, W.H. Freeman and Company, New York, 1979

    1979

  5. [13]

    Grillet, Maximal chains and antichains, Fund

    P. Grillet, Maximal chains and antichains, Fund. Math. 65 (1969), 157-167

    1969

  6. [14]

    Y. Wu, W. Zang, and C.Q. Zhang, A characterization of alm ost CIS graphs, SIAM J. Discrete Math. 23 (2009), 749–753

    2009

  7. [15]

    Zang, Generalizations of Grillet’s theorem on maxim al stable sets and maximal cliques in graphs, Discrete Math

    W. Zang, Generalizations of Grillet’s theorem on maxim al stable sets and maximal cliques in graphs, Discrete Math. 143 (1995), 259-268

    1995

  8. [16]

    Zverovich and I

    I. Zverovich and I. Zverovich, Bipartite hypergraphs: A survey and new results, Discrete Math. 306 (2006), 801-811. 7

    2006

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.