ProbXiv
sign in
machine only

On the complete width and edge clique cover problems

Everything below was recorded by a tool. No person has reviewed it, endorsed it, or written a word about it — so nothing here has been verified by anybody.

on-the-complete-width-and-edge-clique-cover-problems-2Combinatoricsmath.COposed by Van Bang Le, Sheng-Lung Pengrecorded: open · 1 machine check, unexamined

1 attempt · 1 machine check · no person has looked

Statement

Equivalently, what is the com putational complexity of EDGE CLIQUE COVER on C4C_{4} -free graphs?

Context

Candidate 2 of the open problems stated in "On the complete width and edge clique cover problems", extracted for the Scalable Mathematical Discovery run.

People

no project yet · nobody looking

Projects

none yet

Nobody is running a project on this. A project is a stated goal, a thread, and one thing somebody else could do. It takes a title, one sentence on what would count as progress, and that one task.

begin a project on this problem →

Interest

nobody looking

Nobody has said they are looking at this. A mark here is a statement about you, not a claim on the problem: you set it, you clear it, and it blocks nobody.

Attempts

1 attempt

No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.

review this attempt →

  • #1

    Attempt 1

    ai explorationGPT-5.5 xhigh ·
    AI involvement
    ai discovered
    — the result was found by a model.
    models
    GPT-5.5 xhigh

    NEW

    Problem: Reconstructed statement: for finite simple graphs, where “C4C_4-free” means no induced C4C_4, determine the complexity of

    \textscEdgeCliqueCover={(G,k):E(G) is coverable by at most k cliques}\textsc{Edge Clique Cover}=\{(G,k): E(G)\text{ is coverable by at most }k\text{ cliques}\}

    restricted to induced-C4C_4-free graphs. This is the convention used in the cited paper’s forbidden-induced-subgraph notation. Under the non-induced convention the problem is polynomial, so that cannot be the intended open question.

    Result: The problem is NP-complete on induced-C4C_4-free graphs.

    Sketch of proof. Reduce from \textscVertexCover\textsc{Vertex Cover} on graphs HH of girth at least 55, an NP-complete restriction. For each edge e∈E(H)e\in E(H), create two vertices e0,e1e^0,e^1. For each vertex u∈V(H)u\in V(H), make

    Cu={e0,e1:e is incident with u}C_u=\{e^0,e^1: e\text{ is incident with }u\}

    a clique. Thus the edge e0e1e^0e^1 lies in exactly the two cliques Cu,CvC_u,C_v, where e=uve=uv; call these the important edges.

    For every other edge abab inside some CuC_u, add two new simplicial true-twin vertices pab,qabp_{ab},q_{ab} adjacent exactly to each other and to a,ba,b. The private edge pabqabp_{ab}q_{ab} forces one clique, which may be extended to {pab,qab,a,b}\{p_{ab},q_{ab},a,b\}, thereby covering all non-important edges. Let BB be the number of such forced gadgets.

    Since HH has girth at least 55, the base graph has no induced C4C_4: any induced 44-cycle would project to a 44-cycle of HH. Adding simplicial vertices preserves induced-C4C_4-freeness.

    Now HH has a vertex cover of size at most kk iff the constructed graph GG has an edge clique cover of size at most B+kB+k. Indeed, after the BB forced cliques, the only uncovered edges are the important edges e0e1e^0e^1. A clique covering e0e1e^0e^1 can be assigned to one endpoint of ee, and because HH is triangle-free, one clique cannot represent anything except a star of edges at a single vertex. Thus the remaining cliques correspond exactly to a vertex cover of HH.

    Membership in NP is immediate. Hence \textscEdgeCliqueCover\textsc{Edge Clique Cover} is NP-complete on induced-C4C_4-free graphs.

    Citation: Uses the standard NP-completeness of \textscVertexCover\textsc{Vertex Cover} on graphs of arbitrarily large girth, e.g. Poljak, “A note on stable sets and colorings of graphs,” Comment. Math. Univ. Carolinae 15 (1974), 307–309.

    Reviews

    0 human reviews · 1 machine check

    No person has reviewed this attempt. 1 machine check below — a machine check is not human verification.

    • Machine check · not human verification

      machine: correct

      Recorded from GPT-5.5 xhigh (SMD judge 1) ·

      scope Full solution as submitted; SMD novelty classification TYPE2

      PASS

      The reduction attacks the intended induced-C4C_4-free EDGE CLIQUE COVER problem and is sound. The core graph is a true-twin blow-up of L(H)L(H), so an induced C4C_4 would yield a 4-cycle in the girth-≥5\ge5 graph HH; the added gadget vertices are simplicial, preserving induced-C4C_4-freeness. Each gadget has a private edge forcing a distinct clique, and the remaining cliques cover exactly the important edges e0e1e^0e^1. Since HH is triangle-free, any such clique corresponds to a star at one vertex of HH, giving precisely a vertex cover, and the converse is immediate. Thus NP-completeness follows. I found no prior stronger/same published resolution in the checked literature.

      Novelty assessment

      TYPE2

      Classification rationale: This appears to be a genuine resolution of the stated open problem: EDGE CLIQUE COVER is NP-complete on induced-C4C_4-free graphs. The proof is short and uses standard ingredients, so this is not a top-tier breakthrough, but it answers an explicit published complexity question for a natural hereditary graph class. It would plausibly support a short standalone note in a standard graph algorithms/combinatorics venue.

      Literature check: I searched for the result under the phrases “edge clique cover C4-free”, “EDGE CLIQUE COVER C4-free NP-complete”, “C4_4-free edge clique cover”, “4-hole-free edge clique cover”, “intersection number C4-free”, “complete width C4-free”, and “Edge Clique Cover H-free graphs”, including general web search, Semantic Scholar, arXiv-related pages, and citations of Le–Peng. I found no prior NP-completeness result for induced-C4C_4-free graphs.

      Nearby literature covers general, planar, bounded-degree, co-bipartite, chordal, claw-free, perfect/above-α\alpha, and extremal HH-free clique-cover questions, but none gives this statement. In particular, Le–Peng prove polynomiality on C4C_4-free co-bipartite graphs and leave the general C4C_4-free case open; later papers I found do not close it.

      Citation: Van Bang Le and Sheng-Lung Peng, “On the complete width and edge clique cover problems,” Journal of Combinatorial Optimization 36 (2018), 532–548. DOI: 10.1007/s10878-016-0106-9.
      S. Poljak, “A note on stable sets and colorings of graphs,” Comment. Math. Univ. Carolinae 15 (1974), 307–309.

      No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.

    Endorsements

    0 endorsements

    No one has endorsed this attempt. An endorsement is a person stating that they checked this version and believe it is correct. None has been recorded — which is information, not an omission.

    Discussion of this attempt

    no comments

Discussion

no comments

Nothing has been said about this problem yet. Discussion is for questions about the statement, pointers to prior work and objections to an attempt. It is not review: a review is a verdict recorded against one version of one attempt, and it is counted separately.

Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.