\documentclass[11pt,a4paper]{article} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage{amsmath,amssymb,amsthm,mathtools} \usepackage{enumitem} \usepackage{microtype} \usepackage[hidelinks]{hyperref} \usepackage[margin=1in]{geometry} \hypersetup{ pdftitle={Universal-Clique Amplification and Hardness of Assignment-Optimal Edge Clique Covers}, pdfauthor={Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník}, pdfsubject={Hardness of approximation for minimum-assignment edge clique covers} } \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \DeclareMathOperator{\size}{size} \newcommand{\calC}{\mathcal C} \newcommand{\calF}{\mathcal F} \newcommand{\eps}{\varepsilon} \title{Universal-Clique Amplification and Hardness of\\ Assignment-Optimal Edge Clique Covers\thanks{This work was produced within the Bolzano project (\url{https://bolzano.app}), using AI systems for mathematical research and manuscript preparation. The listed authors contributed to the project and the preparation of this release. The manuscript received only limited human checking.}} \author{Mat\v{e}j Kripner \qquad V\'{a}clav Rozho\v{n} \qquad Robert \v{S}\'{a}mal\\[0.4em] Martin \v{S}indel\'{a}\v{r} \qquad Adri\'{a}n Z\'{a}me\v{c}n\'{i}k} \date{} \AtBeginDocument{\setlength{\emergencystretch}{2em}} \usepackage{xcolor} % Collection typography. \geometry{a4paper,hmargin=23mm,vmargin=25mm} \definecolor{BolzanoInk}{HTML}{24445C} \hypersetup{colorlinks=true,linkcolor=BolzanoInk,citecolor=BolzanoInk, urlcolor=BolzanoInk,pdfauthor={Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník},pdflang={en-US}} \urlstyle{same} \setlength{\emergencystretch}{1em} \let\BolzanoBibliography\thebibliography \renewcommand{\thebibliography}[1]{\BolzanoBibliography{#1}\raggedright} \begin{document} \maketitle \begin{abstract} An edge clique cover has assignment cost equal to the sum of its clique sizes. Unless $P=NP$, this cost admits no polynomial-time $O(N^{1/2-\eta})$-approximation for any fixed $0<\eta<1/2$, even on connected $N$-vertex graphs. A universal-clique join transfers coloring hardness without the additive obstruction in earlier reductions. Its exact residual formula also exhibits a change of optimal cover when a universal twin is added. Explicit counterexamples refute two proposed twin-extension rules, while weighted compression of true-twin classes preserves the optimum. \end{abstract} \section{Introduction} \subsection{Background and the source problem} An edge clique cover compresses a graph by storing complete subgraphs rather than individual edges. Counting the stored cliques is only one measure of its size: a large clique requires more vertex memberships than a small one. For a clique family $\calC$, the corresponding assignment cost and optimum are \[ \size(\calC)=\sum_{C\in\calC}|C|, \qquad A(G)=\min_{\calC\text{ covering }E(G)}\size(\calC). \] Singleton cliques are allowed; an edgeless graph has optimum zero and is solved by the empty cover. Approximation ratios are stated for graphs with at least one edge. Ullah and Pothen call a cover minimizing this quantity \emph{assignment-optimal}~\cite[Def.~3.6]{ullahpothen2026dcc}. Their dual clique-cover representation stores the vertex--clique incidence relation in both directions~\cite[Def.~3.15]{ullahpothen2026dcc}. Double-counting these incidences gives representation size $2\size(\calC)$, so assignment cost controls the storage objective directly. This optimization problem also appears as \emph{assignment-minimum clique cover}~\cite{ennis2012} and \emph{Sigma Clique Cover} ~\cite[Def.~3.1]{firbas2025}. The distinction between the two objectives matters for complexity. Kou, Stockmeyer, and Wong related cardinality-minimum edge clique cover to coloring~\cite{kou1978}; the coloring hardness of Lund and Yannakakis~\cite{lundyannakakis1994} consequently yields hardness for that objective, as reviewed in~\cite[Appendix~A.2]{ullahpothen2026dcc}. Exact NP-hardness for assignment cost is established by Ullah~\cite[Thm.~1.3 and Sec.~3.4]{ullah2022} and by Firbas et al.~\cite[Lem.~3.4 and Thm.~3.5]{firbas2025}. Those reductions add mutually nonadjacent vertices, each adjacent to the base graph. Their cost includes a repeated contribution from every base vertex. Ullah and Pothen calculate explicitly that a $\rho$-approximation then gives at most $(\rho-1)n+\rho\chi(X)+O(\rho)$ colors for an $n$-vertex input $X$~\cite[Lem.~A.2 and the following discussion]{ullahpothen2026dcc}. The term $(\rho-1)n$ prevents the required multiplicative transfer. Ullah and Pothen therefore leave constant-factor approximability open in Section~3.2, repeat this status in Appendix~D.1, and include the objective among the directions in Section~7~\cite{ullahpothen2026dcc}. The explicit question is the following. \begin{question}[Ullah--Pothen] \label{q:source} Does the assignment-optimal edge clique cover problem admit a polynomial-time constant-factor approximation?~\cite[Sec.~3.2]{ullahpothen2026dcc} \end{question} \subsection{Contribution} The reduction replaces the independent added vertices by a clique $U$ of size $L$. If $S$ is a clique in the base graph $H$, a single clique $U\cup S$ can now serve all vertices of $U$ while paying for the vertices of $S$ only once. In the opposite direction, the cover cliques containing any fixed $u\in U$, intersected with $H$, cover every vertex of $H$. Thus each universal vertex still pays for a vertex clique cover, although the base-vertex assignments can be shared. Writing $\theta(H)=\chi(\overline H)$, this gives \[ L\theta(H)\le A(K_L\vee H)\le L\theta(H)+n^2, \qquad n=|V(H)|. \] Taking $L=n^2$ controls the remaining internal-edge cost. The resulting graph has $N=n+n^2$ vertices, which explains the exponent $1/2$ in the hardness bound. The results are organized as follows. \begin{enumerate}[label=(\roman*),leftmargin=2.2em] \item Theorem~\ref{thm:transfer} converts a $\rho(N)$-approximation for assignment cost into a $2\rho(n+n^2)$-approximation for vertex clique cover. Together with Zuckerman's chromatic-number hardness ~\cite[Thm.~1.2]{zuckerman2007}, Corollary~\ref{cor:hardness} excludes $O(N^{1/2-\eta})$ approximation for every fixed $0<\eta<1/2$ unless $P=NP$, even for connected graphs without isolated vertices. This answers Question~\ref{q:source} negatively. \item Theorem~\ref{thm:residual} determines the exact assignment cost of the join as $\min_{q\ge\theta(H)}(Lq+R_q(H))$, where the marked residual $R_q(H)$ measures the base-graph assignments needed when at most $q$ cliques must also cover all base vertices. Corollary~\ref{cor:large-residual} and the triangle-free examples describe this residual explicitly. \item Proposition~\ref{prop:cp3-residual} gives a six-vertex base whose optimal residual changes with the number of marked cliques. Applied to twin extensions, this yields a counterexample to \cite[Rule~3.26]{ullah2022}; a separate six-vertex example refutes Rule~3.27. Proposition~\ref{prop:twin-quotient} gives an exact weighted compression for true-twin classes. \end{enumerate} The issue with the twin rules is that changing the number of copies of a vertex changes the relative costs of competing covers. Synchronizing twins inside a fixed graph is valid, but extending an arbitrary optimum of the smaller graph need not preserve optimality. The marked-residual formula makes this distinction explicit. These counterexamples concern the two stated rules in the 2022 preprint, not its separate NP-hardness reduction. The quantitative approximation threshold remains open. In particular, the hardness statement does not exclude $\sqrt N/\log N$ or other factors of the form $N^{1/2-o(1)}$. The general edge-by-edge upper bound is linear; Theorem~\ref{thm:greedy} and Corollary~\ref{cor:chordal} give a logarithmic bound on graph classes with polynomially many listable maximal cliques. These restricted-class algorithms are compatible with hardness on arbitrary graphs. \subsection{Related work and the scope of the auxiliary results} The same sum-of-clique-sizes objective has a substantial extremal literature under the notation $\operatorname{scc}(G)$. Davoodi, Javadi, and Omoomi~\cite[Thm.~2(i)]{davoodi2016} prove $2|E(G)|/(\omega(G)-1)\le\operatorname{scc}(G)\le2|E(G)|$. Consequently the entire $(\omega(G)-1)$ edge-by-edge guarantee in Proposition~\ref{prop:edge}, including its linear specialization, is already contained in their result. The degeneracy bound follows by $\omega(G)\le d+1$. Davoodi, Gerbner, Methuku, and Vizer~\cite[Thms.~6--7 and Cor.~8]{davoodi2020} study the same objective on complete multipartite graphs, obtaining asymptotically matching upper and lower bounds of order $t\log t$ when the number $t$ of parts grows and each part has fixed size. Those extremal results concern the value of the optimum on specified families, rather than a polynomial-time approximation ratio for arbitrary graphs. Recent work also treats a different valency objective. The local clique cover number minimizes the \emph{maximum} number of cover cliques containing one vertex, whereas assignment cost minimizes the \emph{sum} of these numbers. Davoodi's September 2026 preprint~\cite[Thms.~1.1--1.2]{davoodi2026} bounds the local parameter in terms of chromatic number. Its Lemma~4.1 extends a cover through a universal clique by marking occurrences selected from a maximum matching. This is the matching extension used in the triangle-free example below and already implies that example's upper bound. The local-valency results do not state approximation hardness for the sum objective or the exact marked-residual minimization formula. Practical clique-cover algorithms address a complementary question. Ennis, Fayle, and Ennis~\cite{ennis2012} study the assignment objective; Abdullah and Hossain~\cite[Sec.~5]{abdullah2022} discuss post-processing for assignment minimization after computing covers aimed at small clique cardinality. The worst-case reduction here neither evaluates nor precludes successful compression on such practical instances. True-twin classes are also called critical cliques \cite[Def.~5.2]{firbas2025}. Firbas et al.\ give a valid shrinking rule when the neighborhood of the class in the quotient graph is a clique \cite[Lem.~5.5]{firbas2025}. The universal class over $CP_3$ does not satisfy that hypothesis. The counterexamples below concern the unconditional extensions in \cite[Rules~3.26--3.27]{ullah2022}; the weighted quotient identity follows from an elementary normalization inside the original graph. The greedy analysis is the classical weighted set-cover argument: Johnson and Lov\'asz established the unweighted guarantees ~\cite{johnson1974,lovasz1975}, and Chv\'atal treated positive set costs~\cite{chvatal1979}. The specific implementation in Lemma~\ref{lem:pricing} lists maximal cliques and optimizes over their subsets using maximum-density subgraph, which is polynomial-time solvable by flow~\cite{goldberg1984}. It is essential to optimize over subsets: a maximal clique may contain many vertices but few currently uncovered edges. For chordal graphs, perfect elimination supplies the required short maximal-clique list~\cite{rose1976}. Thus the greedy guarantee and its flow primitive are standard. The join amplification, its exact marked residual, and the consequences for twin extensions form the main argument. \section{Definitions and the join gadget} All graphs are finite, simple, and undirected. Join statements below assume that the base graph $H$ has at least one vertex; this harmless convention is necessary because an empty base would leave the edges of $K_L$ outside the marked-family description. For a graph $H$, let \[ \theta(H) \] denote the minimum number of cliques whose union of vertices is $V(H)$; this is the vertex clique cover number. Equivalently, $\theta(H)=\chi(\overline H)$. \begin{definition}[Universal-clique join] For an integer $L\ge1$, define \[ J_L(H)=K_L\vee H. \] The vertex set is the disjoint union $U\cup W$, where $U$ induces a clique of size $L$, $W=V(H)$, all edges between $U$ and $W$ are present, and the graph induced by $W$ is $H$. \end{definition} The key point is that each universal vertex sees a complete copy of the vertex clique cover problem for $H$. \begin{lemma}[Extraction from a universal vertex] \label{lem:extract} Let $H$ be nonempty, let $G=J_L(H)$, and let $\calC$ be any edge clique cover of $G$. One can extract from $\calC$ a vertex clique cover of $H$ with at most $\size(\calC)/L$ cliques. Consequently, \[ A(J_L(H))\ge L\theta(H). \] \end{lemma} \begin{proof} Index the cliques of $\calC$ as $C_1,\ldots,C_t$. For a universal vertex $u\in U$, let \[ I_u=\{i:u\in C_i\text{ and }C_i\cap W\ne\emptyset\}. \] For each $i\in I_u$, the intersection $C_i\cap W$ is a clique of $H$, because $G[W]=H$. These intersections cover every vertex of $H$: for $w\in W$, the edge $uw$ must be covered by some clique containing both $u$ and $w$, and that clique contributes an intersection containing $w$. Thus $(C_i\cap W)_{i\in I_u}$ is a vertex clique cover of $H$, so $|I_u|\ge\theta(H)$. Summing over all $u\in U$ gives \[ \sum_{u\in U}|I_u| =\sum_{i:C_i\cap W\ne\emptyset}|C_i\cap U| \le \sum_{i=1}^t |C_i| =\size(\calC). \] Therefore some $u^\ast\in U$ has $|I_{u^\ast}|\le \size(\calC)/L$, and its intersections give the desired extracted cover. Since every $|I_u|\ge\theta(H)$, the same displayed inequality also gives $\size(\calC)\ge L\theta(H)$ for every $\calC$. \end{proof} \begin{lemma}[Upper bound for the join] \label{lem:upper} If $H$ has $n\ge1$ vertices and $m$ edges, then \[ A(J_L(H))\le L\theta(H)+n+2m\le L\theta(H)+n^2. \] \end{lemma} \begin{proof} Let $T_1,\ldots,T_\theta$ be a minimum vertex clique cover of $H$, where $\theta=\theta(H)$. Assign each vertex $w\in V(H)$ to one clique $T_i$ that contains it, and let $S_i$ be the set assigned to $T_i$. Each nonempty $S_i$ is a clique, and no $S_i$ is empty, since otherwise the nonempty assigned sets would form a vertex clique cover using fewer than $\theta$ cliques. Hence $S_1,\ldots,S_\theta$ partition $V(H)$ into $\theta$ cliques. For each $i$, include the clique $U\cup S_i$ in the edge clique cover of $J_L(H)$. These cliques cover all edges inside $U$ and all edges between $U$ and $W$. Cover every remaining internal edge of $H$ by its two endpoints. The total assignment cost is at most \[ \sum_{i=1}^\theta (L+|S_i|)+2m =L\theta+n+2m \le L\theta+n^2. \] \end{proof} \section{Approximation hardness} The reduction is now immediate. The additive residual in Lemma~\ref{lem:upper} is made negligible by taking $L=n^2$. \begin{theorem}[Approximation transfer] \label{thm:transfer} Suppose there is a polynomial-time algorithm which, on every connected $N$-vertex graph $G$, outputs an edge clique cover of assignment cost at most $\rho(N)A(G)$. Then there is a polynomial-time $2\rho(n+n^2)$-approximation algorithm for vertex clique cover on $n$-vertex graphs. \end{theorem} \begin{proof} Given an $n$-vertex graph $H$, set $L=n^2$ and $G=J_L(H)$. Then $G$ has $N=n+n^2$ vertices. Run the assumed approximation algorithm on $G$, obtaining a cover $\calC$ with \[ \size(\calC)\le \rho(N)A(G). \] The graph $G$ is connected and has no isolated vertices, so it belongs to the promised input class. By Lemma~\ref{lem:extract}, extract from $\calC$ a vertex clique cover of $H$ with at most $\size(\calC)/L$ cliques. Lemma~\ref{lem:upper} gives \[ A(G)\le L\theta(H)+n^2=L(\theta(H)+1). \] Therefore the extracted vertex clique cover has size at most \[ \frac{\rho(N)A(G)}{L} \le \rho(N)(\theta(H)+1) \le 2\rho(N)\theta(H), \] because $\theta(H)\ge1$ for nonempty $H$. This is the claimed approximation ratio. \end{proof} \begin{corollary}[Nearly square-root hardness] \label{cor:hardness} For every fixed $0<\eta<1/2$ and every constant $C>0$, there is no polynomial-time $CN^{1/2-\eta}$-approximation for assignment-optimal edge clique cover on connected $N$-vertex graphs, unless $P=NP$. Equivalently, no polynomial-time $O(N^\delta)$-approximation exists for any fixed $0\le\delta<1/2$, unless $P=NP$. In particular, no polynomial-time constant-factor approximation exists unless $P=NP$. \end{corollary} \begin{proof} If $H=\overline X$, then $\theta(H)=\chi(X)$. A vertex clique cover of $H$ is exactly a coloring of $X$: assign each vertex to one clique containing it, and the assigned clique index is a color because clique vertices in $H$ are independent in $X$. Fix $\delta<1/2$ and suppose an assignment-cover approximation with ratio at most $cN^\delta$ existed for some fixed $c$. By Theorem~\ref{thm:transfer}, it would give a coloring approximation ratio at most \[ 2c(n+n^2)^\delta \le 2^{1+\delta}c\, n^{2\delta}. \] Choose \[ \eps=\frac{1-2\delta}{2}>0. \] Then $2\delta<1-\eps$, and the constant $2^{1+\delta}c$ is absorbed by the positive exponent gap for all sufficiently large $n$. Thus the displayed ratio is at most $n^{1-\eps}$ for large inputs. Zuckerman proved that, for every $\eps>0$, approximating chromatic number within $n^{1-\eps}$ is NP-hard~\cite[Thm.~1.2]{zuckerman2007}. The finitely many smaller values of $n$ can be solved exactly without affecting polynomial running time, yielding a contradiction. Writing $\delta=1/2-\eta$ gives the first formulation. A constant factor is $O(N^\delta)$ for every fixed $\delta>0$, so constants are also ruled out. \end{proof} \begin{remark} Corollary~\ref{cor:hardness} answers Question~\ref{q:source} in the negative and strengthens the answer to every fixed approximation exponent below $1/2$. It also explains why the earlier non-approximation-preserving exact reduction can be bypassed: the universal clique forces $L$ separate mixed assignments, while the internal residual is only $O(n^2)$ and can be amortized by choosing $L=n^2$. \end{remark} \section{The exact residual in the join} The simple inequality \[ L\theta(H)\le A(J_L(H))\le L\theta(H)+n^2 \] is enough for the hardness transfer, but it hides the exact residual. The residual matters for improving the exponent: if one could guarantee a much smaller yes-case residual for coloring-hard instances, the join size $L$ could be smaller and the hardness exponent would improve. \begin{definition}[Marked residual] For an integer $q\ge0$, a $q$-admissible marked clique family in $H$ is an indexed family of nonempty cliques \[ \calF=(F_1,\ldots,F_t) \] together with a marked set $M\subseteq\{1,\ldots,t\}$ such that $|M|\le q$, the full family $\calF$ covers every edge of $H$, and the marked subfamily $(F_i)_{i\in M}$ covers every vertex of $H$. Let $R_q(H)$ be the minimum of $\sum_i |F_i|$ over all such families, and set $R_q(H)=+\infty$ if none exists. \end{definition} Plainly $R_q(H)<+\infty$ if and only if $q\ge\theta(H)$. \begin{theorem}[Exact residual formula] \label{thm:residual} For every nonempty graph $H$ and every $L\ge1$, \[ A(J_L(H))=\min_{q\ge\theta(H)}\bigl(Lq+R_q(H)\bigr). \] \end{theorem} \begin{proof} Let $G=J_L(H)$ with universal clique $U$ and nonempty base set $W=V(H)$. First take an arbitrary edge clique cover $\calC=(C_1,\ldots,C_t)$ of $G$. Put $W_i=C_i\cap W$ and $U_i=C_i\cap U$. Ignore indices with $W_i=\emptyset$ for the moment; they can only increase the assignment cost and are irrelevant to covering edges incident with $W$. For each $u\in U$, define $I_u=\{i:u\in U_i,\ W_i\ne\emptyset\}$. Choose $u^\ast$ minimizing $|I_u|$ and set $q=|I_{u^\ast}|$. As in Lemma~\ref{lem:extract}, the marked subfamily $(W_i)_{i\in I_{u^\ast}}$ covers every vertex of $H$, so $q\ge\theta(H)$. The full nonempty family $(W_i)$ covers every edge of $H$, because any edge internal to $H$ must be covered by some clique of $\calC$ whose intersection with $W$ contains both endpoints. Thus the $W_i$ form a $q$-admissible marked family, and \[ \sum_{i:W_i\ne\emptyset}|W_i|\ge R_q(H). \] The mixed universal assignments satisfy \[ \sum_{i:W_i\ne\emptyset}|U_i| =\sum_{u\in U}|I_u| \ge Lq. \] Therefore \[ \size(\calC)\ge Lq+R_q(H)\ge \min_{r\ge\theta(H)}(Lr+R_r(H)). \] Conversely, let $(\calF,M)$ be a $q$-admissible marked family with total cost $R_q(H)$. For each marked clique $F_i$, include $U\cup F_i$ in a cover of $J_L(H)$; for each unmarked clique $F_i$, include $F_i$ itself. The marked cliques cover every vertex of $H$, so these joined cliques cover all edges between $U$ and $W$. Since $W$ is nonempty, the marked subfamily is nonempty; hence the joined cliques also cover all edges inside $U$. The full family covers all edges of $H$. The assignment cost is at most \[ L|M|+\sum_i |F_i|\le Lq+R_q(H). \] Minimizing over $q$ gives the reverse inequality. \end{proof} \begin{corollary}[Large-amplification residual] \label{cor:large-residual} Let $H$ be nonempty, and let $\iota(H)$ be its number of isolated vertices. For all sufficiently large $L$, in particular for $L\ge |V(H)|-\iota(H)$, \[ A(J_L(H))=L\theta(H)+R_{\theta(H)}(H). \] Moreover, for every integer $q\ge\theta(H)$, \[ A(H)+\iota(H)\le R_q(H), \qquad R_{\theta(H)}(H)\le A(H)+|V(H)|. \] \end{corollary} \begin{proof} The inequalities follow from the definition. Every $q$-admissible family has to cover all edges of $H$, at cost at least $A(H)$, and each isolated vertex must appear in an additional singleton marked clique. This gives $R_q(H)\ge A(H)+\iota(H)$ for every $q$. For the upper bound at $q=\theta(H)$, take an assignment-optimal edge clique cover of $H$ and add a minimum vertex clique cover of $H$ as marked cliques; assigning each vertex once costs at most $|V(H)|$. If $q>\theta(H)$, then the formula in Theorem~\ref{thm:residual} pays at least $L(q-\theta(H))$ more in the leading term. The possible residual saving relative to $R_{\theta(H)}(H)$ is at most $|V(H)|-\iota(H)$ by the displayed bounds. Therefore, when $L\ge |V(H)|-\iota(H)$, no $q>\theta(H)$ can improve the minimum. \end{proof} \begin{remark}[Triangle-free bases] The matching extension below also appears in~\cite[Lem.~4.1]{davoodi2026}. If $H$ is triangle-free with $n$ vertices, $m$ edges, $\iota$ isolated vertices, and maximum-matching size $\nu(H)$, then every internal edge of $H$ must be covered by its own two-vertex clique. Moreover, \[ \theta(H)=n-\nu(H). \] Indeed, a maximum matching together with singleton cliques for its unmatched vertices is a vertex clique cover with $n-\nu(H)$ members. Conversely, assign each vertex to one member of an arbitrary vertex clique cover. The members assigned two vertices are pairwise vertex-disjoint edges and hence form a matching. If the cover has $q$ members, at least $n-q$ of them must receive two vertices, so $\nu(H)\ge n-q$ and $q\ge n-\nu(H)$. To obtain a marked subfamily without paying for additional nonisolated singletons, start with a maximum matching, choose one incident edge for every unmatched nonisolated vertex, and mark these edge cliques together with the isolated singleton cliques. After duplicate choices are identified, at most $n-\nu(H)=\theta(H)$ members are marked and they cover every vertex. Thus, for every $q\ge\theta(H)$, the forced edge cliques together with the isolated singletons form a $q$-admissible family of cost $2m+\iota$, and no admissible family can cost less. Hence the residual formula gives, for every $L\ge1$, \[ A(J_L(H))=L\theta(H)+2m+\iota. \] For the explicit base $H=K_{r,r}$, a maximum matching has size $r$, so its vertex clique cover number is $\theta(H)=2r-r=r$; moreover $m=r^2$ and $\iota=0$. Hence \[ A(J_L(K_{r,r}))=Lr+2r^2. \] Thus the join gadget can have an intrinsically quadratic residual even when the leading term is controlled by $\theta(H)$. \end{remark} \subsection{A residual that changes with the number of marks} The triangle-free residual is constant once enough marks are available. The following small example shows why this need not hold in general. Let $CP_3$ be the graph obtained from $K_6$ by deleting the matching $\{x_i y_i:1\le i\le3\}$. Write \[ X=\{x_1,x_2,x_3\},\qquad Y=\{y_1,y_2,y_3\}, \] and, for $1\le i\le3$, put \[ C_i=\{x_i\}\cup(Y\setminus\{y_i\}),\qquad D_i=\{y_i\}\cup(X\setminus\{x_i\}). \] \begin{proposition}\label{prop:cp3-residual} For $H=CP_3$, one has \[ \theta(H)=2,\quad A(H)=12,\quad R_2(H)=15,\quad R_q(H)=12\quad(q\ge3). \] Consequently, for every integer $L\ge1$, \begin{equation}\label{eq:cp3-join} A(J_L(CP_3))=\min\{2L+15,\,3L+12\}. \end{equation} \end{proposition} \begin{proof} The cliques $X,Y$ partition the six vertices, and $H$ is not complete, so $\theta(H)=2$. There are twelve edges and no clique larger than three. Every clique $F$ therefore covers at most $\binom{|F|}{2}\le |F|$ edges, giving $A(H)\ge12$. The four triangles $X,C_1,C_2,C_3$ cover all edges: $X$ covers the edges within $X$, each pair within $Y$ occurs in the $C_i$ with the missing index, and $x_i y_j$ belongs to $C_i$ whenever $i\ne j$. Their total cost is twelve. Marking $C_1,C_2,C_3$ covers all vertices, so $R_q(H)=12$ for every $q\ge3$. For $R_2(H)$, mark $X,Y$ and add $D_1,D_2,D_3$. The latter three triangles cover every cross edge, and the total cost is fifteen. Conversely, two marked cliques covering all six vertices must be disjoint triangles $P,Q$. Each deleted pair has one endpoint in each triangle, so exactly six edges run between $P$ and $Q$. These edges require the unmarked cliques. If such a clique $F$ contains $a$ vertices of $P$ and $b$ of $Q$, then $a+b\le3$ and it covers $ab$ cross edges. For nonnegative integers with $a+b\le3$, one has $ab\le\frac23(a+b)$: the only case with both positive and total three has product two, and the case of total two has product one. Thus \[ 6\le\sum_{F\text{ unmarked}}|F\cap P|\,|F\cap Q| \le\frac23\sum_{F\text{ unmarked}}|F|. \] The unmarked cost is at least nine, in addition to the six marked assignments. Hence $R_2(H)=15$. Theorem~\ref{thm:residual} now gives \eqref{eq:cp3-join}; for $q\ge4$, the term $Lq+12$ exceeds $3L+12$. \end{proof} \section{Twin extensions and weighted compression} For a vertex $x$, write $N(x)$ for its open neighborhood and $N[x]=N(x)\cup\{x\}$. Distinct vertices $x,y$ are \emph{true twins} if $N[x]=N[y]$, and \emph{false twins} if $N(x)=N(y)$ and $xy$ is not an edge. The preceding residual example describes what happens when the size of a true-twin class changes. \begin{definition}[Twin extensions, {\cite[Rules~3.26--3.27]{ullah2022}}] \label{def:twin-rules} Given an edge clique cover $\calC$ of $G-x$ and a twin $y$ of $x$, the true-twin extension replaces each clique $C$ containing $y$ by $C\cup\{x\}$. The false-twin extension retains every clique of $\calC$ and adds $(C\setminus\{y\})\cup\{x\}$ for each $C$ containing $y$. \end{definition} When $y$ has a neighbor in $G-x$, both operations produce covers of $G$. The two cited rules assert that these operations preserve assignment optimality. They fail even on graphs with no isolated vertices. \begin{proposition}[Failure of the true-twin extension]\label{prop:true-twin} There is a ten-vertex graph $G$ with true twins $z,u$ and an assignment-optimal cover of $G-z$ whose true-twin extension has cost $24$, whereas $A(G)=23$. \end{proposition} \begin{proof} Take $G=J_4(CP_3)$, let $U_4$ be its universal clique, and choose $z\in U_4$ and $u\in U_3:=U_4\setminus\{z\}$. Use the notation of Proposition~\ref{prop:cp3-residual}. The cover \[ X,\quad U_3\cup C_1,\quad U_3\cup C_2,\quad U_3\cup C_3 \] of $G-z$ costs $3+3\cdot6=21$, which equals its optimum by \eqref{eq:cp3-join}. The vertex $u$ occurs in the three joined cliques, so the stated extension adds $z$ to all three and costs $3+3\cdot7=24$. However, \[ U_4\cup X,\quad U_4\cup Y,\quad D_1,\quad D_2,\quad D_3 \] is a cover of $G$ of cost $7+7+3+3+3=23$. Equation~\eqref{eq:cp3-join} gives $A(G)=\min\{23,24\}=23$. \end{proof} \begin{proposition}[Failure of the false-twin extension]\label{prop:false-twin} There is a six-vertex graph $G$ with false twins $x,y$ and an assignment-optimal cover of $G-x$ whose false-twin extension has cost $16$, whereas $A(G)=12$. \end{proposition} \begin{proof} Let $1,2,3,4$ induce a four-cycle in that cyclic order, and join each of the nonadjacent vertices $x,y$ to all four cycle vertices. The graph $G-x$ has the cover \[ \{y,1,2\},\quad\{y,3,4\},\quad\{2,3\},\quad\{4,1\} \] of cost ten. Every clique intersects the cycle in at most two vertices, so covering its four edges requires at least eight cycle-vertex assignments. Covering the four edges incident to $y$ requires at least two occurrences of $y$. Thus the displayed cover is optimal. The false-twin extension adds $\{x,1,2\}$ and $\{x,3,4\}$ while retaining the original four cliques, and therefore costs sixteen. In contrast, \[ \{x,1,2\},\quad\{x,3,4\},\quad\{y,2,3\},\quad\{y,4,1\} \] covers $G$ at cost twelve. The graph has twelve edges and clique number three, so the edge-count argument in Proposition~\ref{prop:cp3-residual} gives the matching lower bound. \end{proof} These examples distinguish extension from normalization. Within a fixed graph it is possible to synchronize true twins without increasing cost. After compression, their multiplicity must remain in the objective. \begin{proposition}[Weighted true-twin quotient]\label{prop:twin-quotient} Partition $V(G)$ into its maximal true-twin classes. Let $Q$ have these classes as vertices, with two classes adjacent when their vertices are adjacent in $G$. Give a quotient vertex $v$ the weight $w_v$ equal to the size of its class. Let $A_w(Q)$ be the minimum weighted edge clique cover cost $\sum_{C}\sum_{v\in C}w_v$, where the minimum is over clique covers of $E(Q)$. Then \begin{equation}\label{eq:twin-quotient} A(G)=A_w(Q)+ \sum_{\substack{v\text{ isolated in }Q\\w_v\ge2}}w_v. \end{equation} Moreover, an optimum of $G$ exists in which each clique contains either all or none of each true-twin class. \end{proposition} \begin{proof} Fix a cover and a true-twin class $T$ with at least two vertices. Choose $t\in T$ occurring in the fewest cliques. Remove $T\setminus\{t\}$ from all cliques and insert all of $T$ in each clique containing $t$. These remain cliques because the vertices in $T$ are pairwise adjacent and have the same neighbors outside $T$. Every edge from $T$ to an outside vertex $v$ is covered: some original clique covered $tv$, and its replacement contains $T\cup\{v\}$. The vertex $t$ occurs at least once, since its edges to $T\setminus\{t\}$ were covered, so the internal edges of $T$ are covered as well. Edges disjoint from $T$ retain their original covers. If the old occurrence counts were $r_s$ for $s\in T$, then, keeping the clique indices, the new cost on $T$ is $|T|r_t\le\sum_{s\in T}r_s$; outside assignments are unchanged. Empty cliques may be omitted. Apply this operation successively to all classes. An already synchronized class stays synchronized because later operations alter only vertices of other classes. Starting from an optimum proves the normalization assertion. Every nonisolated quotient vertex appears in a cover of $E(Q)$, so lifting that cover to whole classes covers both edges between classes and internal edges of those classes. An isolated quotient vertex of weight at least two represents a complete connected component, whose optimal cost is exactly its order. Such components contribute the additional sum in \eqref{eq:twin-quotient}; isolated classes of size one contribute zero. This proves the upper bound. Conversely, project a normalized optimum to $Q$. Its cliques involving nonisolated quotient vertices have weighted cost at least $A_w(Q)$, while each isolated class of size at least two costs at least its order. This gives the reverse inequality. \end{proof} In \eqref{eq:cp3-join}, the coefficient $L$ is precisely the weight of the universal class. Increasing it from three to four changes which cover minimizes the total. The weighted quotient retains this change; the unweighted extension rule does not. \section{Upper bounds and structured classes} The hardness above does not eliminate all approximation guarantees. The elementary edge-by-edge algorithm gives a linear bound, and the same counting proof becomes sharper when large cliques are absent. \begin{proposition}[Edge-by-edge approximation] \label{prop:edge} Let $G$ have $N$ vertices and $m>0$ edges. Covering every edge by its two endpoints is an $(N-1)$-approximation. More generally, it is an $(\omega(G)-1)$-approximation, where $\omega(G)$ is the clique number. In particular, it is a $d$-approximation on graphs of degeneracy $d$. \end{proposition} \begin{proof} The edge-by-edge cover has cost $2m$. In any assignment cover $\calC$, each clique $C$ covers at most \[ \binom{|C|}{2}\le \frac{|C|(N-1)}2 \] edges. Hence \[ m\le\sum_{C\in\calC}\binom{|C|}{2} \le\frac{N-1}{2}\size(\calC), \] so $A(G)\ge 2m/(N-1)$. The ratio of the edge-by-edge cover is at most $N-1$. If every clique has size at most $\omega(G)$, the same argument gives \[ m\le \frac{\omega(G)-1}{2}\size(\calC), \] and the ratio is at most $\omega(G)-1$. A $d$-degenerate graph has clique number at most $d+1$. \end{proof} The full clique-number estimate is due to~\cite[Thm.~2(i)]{davoodi2016}; the proof is included for completeness. For a set $R\subseteq E(G)$ of uncovered edges and a clique $C$, put \[ g_R(C)=|E(C)\cap R|, \qquad d_R(C)=\frac{g_R(C)}{|C|}. \] \begin{theorem}[Weighted set-cover greedy specialization] \label{thm:greedy} Suppose that, for every nonempty current set $R$ of uncovered edges, one can find a positive-gain clique maximizing $d_R(C)$. Repeatedly selecting such a clique gives an $H_m$-approximation, where $m=|E(G)|$ and \[ H_m=\sum_{j=1}^m\frac1j\le1+\ln m. \] More generally, an oracle returning a clique of density at least $1/\alpha$ times the maximum gives an $\alpha H_m$-approximation. \end{theorem} \begin{proof} This is weighted greedy set cover with universe $E(G)$ and a set of cost $|C|$ for every clique $C$~\cite{johnson1974,lovasz1975,chvatal1979}. The standard charging proof is recalled for completeness. Let $\mathcal O$ be an optimal assignment cover. At a step with $R$ containing $r$ edges, \[ \sum_{O\in\mathcal O}g_R(O)\ge r, \qquad \sum_{O\in\mathcal O}|O|=A(G). \] Consequently some $O\in\mathcal O$ has density at least $r/A(G)$. If the oracle is an $\alpha$-approximation and returns $C$ with $h=g_R(C)$ and $c=|C|$, then \[ \frac{c}{h}\le\frac{\alpha A(G)}r. \] Charge the cost $c$ equally to the $h$ newly covered edges. If this step changes the number of uncovered edges from $r$ to $r-h$, then \[ c\le \alpha A(G)\frac hr \le \alpha A(G)\sum_{j=r-h+1}^{r}\frac1j. \] The index intervals from successive steps partition $\{1,\ldots,m\}$. Summing the charges therefore gives total cost at most $\alpha H_mA(G)$. \end{proof} \begin{lemma}[Pricing from maximal cliques] \label{lem:pricing} If every graph in a class has polynomially many maximal cliques and they can all be listed in polynomial time, then the exact density oracle in Theorem~\ref{thm:greedy} is polynomial-time implementable on that class. \end{lemma} \begin{proof} Every clique is contained in a maximal clique, so list the maximal cliques and optimize separately inside each one. Fix a maximal clique $M$. Every subset $S\subseteq M$ is a clique of $G$, and its density is \[ \frac{|R\cap\binom S2|}{|S|}. \] Thus the subproblem inside $M$ is the maximum-density-subgraph problem in the auxiliary graph with vertex set $M$ and edge set $R\cap\binom M2$. This problem is polynomial-time solvable~\cite{goldberg1984}. For completeness, a threshold $\lambda$ can be tested by a maximum-closure instance: create a profit-$1$ node for each auxiliary edge, a profit-$-\lambda$ node for each vertex, and implication arcs from an edge node to its endpoints of capacity $|R|+1$. This finite capacity exceeds the total positive profit, so no minimum cut violates an implication. The maximum closure has positive value exactly when some $S\subseteq M$ satisfies \[ |R\cap\tbinom S2|-\lambda|S|>0. \] Maximum closure reduces to one minimum $s$--$t$ cut. Every candidate density is $a/b$ with $0\le a\le |R|$ and $1\le b\le |M|$; enumerating these polynomially many rational thresholds (and scaling capacities by $b$) recovers an exact optimum. If the auxiliary graph has an edge, let $\lambda_-$ be the largest candidate threshold at which the optimum closure value is positive. The next distinct candidate is its maximum density $d^*$: the test is positive precisely below $d^*$. A positive closure at $\lambda_-$ supplies a vertex set of density greater than $\lambda_-$, which must therefore have density $d^*$. If the auxiliary graph has no edges, any nonempty subset has optimum density zero. Taking the best solution over all listed maximal cliques proves the lemma. \end{proof} \begin{corollary}[Polynomial-maximal-clique classes] \label{cor:chordal} Every class satisfying Lemma~\ref{lem:pricing} admits a polynomial-time $H_m$-approximation. In particular, chordal graphs admit a polynomial-time ratio \[ H_m\le1+\ln m\le1+2\ln n. \] \end{corollary} \begin{proof} Combine Lemma~\ref{lem:pricing} with Theorem~\ref{thm:greedy}. A chordal graph has a polynomial-time computable perfect elimination ordering~\cite{rose1976}. For each vertex, take it together with its later neighbors; these form a clique. Every maximal clique equals one of these $n$ sets, by considering its earliest vertex. Deleting repeated sets and sets properly contained in another gives all maximal cliques in polynomial time. Finally, $m