Pith. sign in

REVIEW 2 major objections 3 minor 52 references

Edge Clique Partition and Cover Beyond Independence

T0 review · 2 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read The paper proves a complexity dichotomy for edge clique partition and cover parameterized above the independence number: partition with α(G)+k cliques is fixed-parameter tractable, while cover with the same budget is NP-complete for every…

desk verdict New parameterization, useful framework, but the central reduction (Lemma 5) is wrong, invalidating the polynomial and sparse-graph results as stated. read the letter →

arxiv 2506.21216 v1 pith:ALB2ZBGC submitted 2025-06-26 cs.DS cs.DM

Fedor V. Fomin , Petr A. Golovach , Danil Sagunov , Kirill Simonov This is my paper · ORCID
classification cs.DScs.DM MSC 68Q2705C6905C8568Q17
keywords edgecliquecoverpartitionabove-guaranteeparameterizationsimplicialcliquesfixed-parametertractablepara-NP-completeperfectgraphsH-minor-free
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

The paper studies two classical problems — covering or partitioning a graph's edges with cliques — under a new budget: at most α(G)+k cliques, where α(G) is the size of the largest independent set, a natural lower bound because one clique can hold at most one vertex of an independent set. The central finding is that the two problems diverge at this parameterization: Edge Clique Partition above α is fixed-parameter tractable in k, solvable in $2^{O(k^{3/2}\log k)}\cdot n^{O(1)}$ time, while Edge Clique Cover above α is NP-complete for every fixed k ≥ 2, even on perfect graphs where α(G) itself is easy to compute. The boundary is tight: for k = 0 and k = 1 the cover problem is polynomial-time solvable. On sparse graph classes the cover problem regains tractability, with FPT algorithms depending on clique number, degeneracy, and a subexponential $f(H)^{\sqrt{k}}$ bound on H-minor-free graphs. If correct, this gives a complete complexity dichotomy for the above-α parameterization and shows that the regime real-world instances occupy — covers very close to α(G) — is algorithmically meaningful.

What carries the argument

The load-bearing mechanism is Lemma 1: any cover (or partition) using at most α(G)+k cliques can contain at most 2k non-simplicial cliques, and any maximum independent set can contain at most k non-simplicial vertices — so near-optimal solutions are almost entirely built from simplicial cliques, the closed neighborhoods of simplicial vertices. This observation turns the unknown quantity α(G) into a computational handle: Lemma 3 computes α(G) itself in $2^{O(k^{3/2}\log k)}\cdot n^{O(1)}$ time by counting simplicial cliques and invoking the de Bruijn–Erdős theorem (an edge clique partition of $K_n$ into smaller cliques needs at least $n$ cliques) to bound the residual graph. Lemma 4 then uses critical cliques — maximal true-twin cliques — to extract every large forced clique of a solution in polynomial time, and Lemma 5 factors ECC/α through Annotated ECC by deleting simplicial vertices, which is how k-coloring supplies the hardness.

What would settle it

Run an exhaustive search over small graphs: list all simplicial cliques, choose one simplicial vertex per clique, and test whether some maximum independent set contains all chosen vertices; the first counterexample would invalidate Lemma 3 and with it Theorem 1. Separately, any algorithm deciding in $f(k)\cdot n^{O(1)}$ time whether α(G)+2 cliques suffice to cover the edges of a perfect graph would refute Theorem 2.

Watch

Extended reading notes

Core claim

The paper's central claim is a dichotomy between the two above-α variants. ECP/α is FPT: a subexponential routine first computes α(G) or certifies a no-instance from the simplicial cliques alone, then polynomial-time preprocessing identifies every clique of size at least 6k+1 that any valid partition must contain, and after branching over which simplicial cliques are 'broken' the remaining problem reduces to standard Edge Clique Partition on a residual graph with $O(k^2)$ vertices, solvable by the best known ECP algorithm. ECC/α, by contrast, is para-NP-complete: for every k ≥ 2, deciding coverability with α(G)+k cliques is NP-complete, and the hardness survives on perfect graphs; the reduction routes through Annotated Edge Clique Cover, descending from the NP-completeness of k-coloring via co-bipartite graphs. The polynomial algorithms for k = 0 and k = 1 close the dichotomy in k, and the sparse-graph theorems show that on minor-free and low-degeneracy graph classes the hardness dissolves into fixed-parameter algorithms.

Load-bearing premise

Lemma 3 leans on an unproved 'well-known' fact: from each simplicial clique one can pick a simplicial vertex so that all chosen vertices lie together in some maximum independent set; if any graph violates this, the computed α(G) is wrong and the ECP/α algorithm collapses with it.

Editorial extensions

If this is right

  • The k = 0 cases of both problems are polynomial: any cover of size α(G) must consist only of simplicial cliques, which can be listed and checked directly.
  • No faster algorithm for ECP/α can exist than for the underlying ECP, and any improved ECP algorithm immediately speeds up Theorem 1 — the two running-time problems are the same up to a $k^{O(k)}$ factor.
  • On graphs of degeneracy d ≥ 3, ECC/α is solvable in $2.081^{(d-1)k}\cdot n^{O(1)}$ time, and on 2-degenerate graphs in $1.619^k\cdot n^{O(1)}$ time; under the Exponential Time Hypothesis the $2^{o(k)}$ barrier for the latter cannot be broken.
  • On H-minor-free graphs, ECC/α runs in $f(H)^{\sqrt{k}}\cdot n^{O(1)}$ time without being told H, bundling planar and bounded-treewidth graphs into one subexponential regime.
  • The ECC/α dichotomy in k is complete: NP-complete for every k ≥ 2, polynomial for k ∈ {0, 1}.

Reading between the lines

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

  • The contrast suggests that the partition requirement itself is what buys tractability above α: a partition is forced to mirror the simplicial skeleton of the graph, while a cover may hide arbitrary non-simplicial cliques — and that freedom carries the k-coloring hardness.
  • Because hardness survives on perfect graphs, where α(G) is polynomial-time computable, future algorithmic progress on ECC/α cannot come from computing α; it has to come from sparsity, as the degenerate and minor-free FPT results indicate.
  • A testable extension is to apply the same above-α lens to vertex clique cover and partition; the split may persist, with the vertex versions' different counting of independent sets in cliques changing which side stays tractable.
  • For practical instances near the α-boundary, the paper implies a certificate-friendly workflow: find a large independent set, then run the k-parameterized cover algorithms on the residual graph, since the small-parameter regime is exactly where real-world covers are reported to sit.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 3 minor

Summary. The paper studies two natural above-guarantee parameterizations of edge clique cover and partition: ECC/α and ECP/α, where the goal is to use at most α(G)+k cliques. The main results are: Theorem 1 gives a 2^{O(k^{3/2} log k)} n^{O(1)} FPT algorithm for ECP/α; Theorem 2 shows ECC/α is NP-complete for every k≥2 even on perfect graphs; Theorem 3 claims polynomial-time algorithms for k=0,1; Theorem 4 claims FPT algorithms for ECC/α on graphs of bounded clique number, bounded degeneracy, and H-minor-free graphs, with subexponential running times; Proposition 5 gives ETH-based lower bounds. The proofs for ECP/α are detailed and appear technically sound, relying on a new way to compute α(G) using the FPT algorithm for ECP. The results for ECC/α, however, are obtained through a Turing reduction to Annotated ECC that contains a concrete error.

Significance. If correct, the dichotomy between ECP/α (FPT) and ECC/α (para-NP-complete for k≥2) would be a clean and interesting contribution, and the FPT algorithms for sparse graph classes would be useful. The paper is honest in its use of black-box algorithms and gives explicit running times. The proof of Theorem 1 and the reduction for Theorem 2 appear sound. Unfortunately, the reduction in Lemma 5, which is the engine behind Theorems 3 and 4, defines the edge set B incorrectly, and the counterexample in the report shows the reduction is unsound. As a result, several of the paper's central claims are not supported as written, although the error appears fixable.

major comments (2)
  1. [Section 4.1, Lemma 5 (Claim 8)] The definition B = E(G') \ E(G'[F]) in Lemma 5 is not the set of edges of G that are not contained in simplicial cliques, as Claim 8 asserts. For G = P4 on vertices a-b-c-d, the simplicial vertices are a and d, so S' = {a,d}, G' is the edge bc, F = {b,c}, and B = {bc} \ {bc} = ∅. The edge bc is contained in no simplicial clique of G, so the claimed equality ecc(G) = aecc_B(G') + |S'| would give 3 = 0 + 2, which is false. Consequently, the reduction declares the no-instance (P4, 0) of ECC/α (since ecc(P4) = 3 > α(P4) + 0) to be a yes-instance: it sets k' = 0, computes t = α(G'-F) = 0, and reports yes because 0 ≤ 0 + 0. This error propagates to Theorem 3 (the k = 1 case) and to all four algorithms in Theorem 4, since those results are proved by pipelining Lemma 5 or Corollary 1. The intended definition should be B = {uv ∈ E(G') : no simplicial vertex s satisfies u,v ∈ N[s]}; with this definition the equality in Claim 8 and the correctness proof of the reduction can be repaired.
  2. [Section 5.4, Proposition 5] The proof of the 2-degenerate lower bound states that 'Independent Set does not admit subexponential algorithms for connected graphs of maximum degree three and, consequently, 2-degenerate graphs.' The 'consequently' is unjustified: connected graphs of maximum degree three are 3-degenerate, not 2-degenerate. The reduction that follows in the same paragraph assumes an NP-hardness base for Independent Set on 2-degenerate graphs, but no proof or reference for such hardness is given. As written, the claimed 2^{o(k)} lower bound for ECC/α on 2-degenerate graphs is unsupported. Separately, the transfer of the ECC lower bounds to ECC/α should be stated as an explicit parameter-preserving reduction (e.g., add a pendant neighbor to every vertex and keep the same parameter), since Observation 2, to which the proof refers, is an NP-completeness statement rather than an ETH-lower-bound transfer.
minor comments (3)
  1. [Section 3, Lemma 3] The 'well-known' assertion that there is a maximum independent set containing the chosen simplicial vertices X (one from each simplicial clique) is used to compute α(G) in the FPT algorithm, but no proof or citation is given. The statement is true and can be shown by the standard exchange argument for simplicial vertices, applied sequentially to the pairwise non-adjacent vertices of X; the proof should be included.
  2. [Section 5.4, Proposition 5] As noted in the major comments, the parameter-preserving transfer of ETH lower bounds from ECC to ECC/α should be written out explicitly rather than deferred with 'similarly to Observation 2'.
  3. [Throughout] There are several typos and inconsistent notations: 'cannon' for 'cannot' (Section 2), 'reposts' for 'reports' (Theorem 1 proof), 'wtith' for 'with' (Claim 5), 'of of' (Observation 3), 'simlicial' for 'simplicial' (Claim 3), 'de Brujin' for 'de Bruijn' (Proposition 1), 'prefect' for 'perfect' (Section 1.1), and the statement of Lemma 5 uses R' where the body uses B. These should be fixed.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the derivation chain is self-contained and rests on external black-box results rather than on its own conclusions.

full rationale

All four main theorems are proved from graph-theoretic definitions using explicit lemmas and external published results, with no fitted parameters and no 'prediction' that is by construction equal to an input quantity. Theorem 1 (ECP/α FPT) uses the external ECP algorithm of Feldmann, Issac, and Rai [18, Prop. 2] as a black box, combined with Lemmas 1–4; the noted running-time match is stated as an explicit reduction in both directions, not as an imported conclusion. Theorems 2–3 use standard reductions to and from Vertex Clique Cover and k-Coloring (Lemma 7, Orlin [48], Kou–Stockmeyer–Wong [40]); Theorem 4 pipelines Lemma 5/Corollary 1 with external Ramsey, Moon–Moser, treewidth, and H-minor-free results. The only author-overlapping citations are standard textbooks [12,21], and they are not load-bearing for the new dichotomy. Two support gaps exist but are not circular: (i) Lemma 3 invokes a 'well-known' fact that a maximum independent set contains the chosen simplicial vertices, with no proof supplied; (ii) Lemma 5/Claim 8 defines B = E(G')\E(G'[F]) and asserts these are exactly the edges of G not contained in simplicial cliques; on the P4 example from the review note this definition omits edge bc, which would be a correctness problem in the reduction pipeline rather than a self-referential one. Since no equation is equivalent to its own input and no fitted quantity is renamed as a prediction, the circularity score is 0.

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

The paper introduces no new entities or fitted parameters. It relies on standard external results (de Bruijn-Erdős, Moon-Moser, perfect graph theorem, ETH, known FPT algorithms for ECP and Annotated ECC, and a standard simplicial-vertex fact that is stated without proof).

assumptions (11)
  • standard math de Bruijn-Erdős theorem: any edge clique partition of K_n into cliques of size at most n-1 contains at least n cliques (Proposition 1).
    Used in Lemma 4 to force that large critical cliques must be contained in a single solution clique; without it, the forced-clique argument collapses.
  • standard math FPT algorithm for ECP parameterized by the number of cliques, running in 2^{O(k^{3/2} log k)} n^{O(1)} time (Proposition 2, Feldmann-Issac-Rai).
    Black-box subroutine in Theorem 1 and Lemma 3; the paper's running time matches this bound.
  • standard math There is a poly-time algorithm that, given n ≥ binom(p+q-2, p-1), finds a p-clique or a q-independent set (Proposition 3, Erdős-Szekeres).
    Used in Lemma 8 to bound the clique number ω in FPT time without computing it directly.
  • standard math Given a nice tree decomposition of width t, Annotated ECC can be solved in 2^{O(dt)} n^{O(1)} time where d is degeneracy (Proposition 4, Blanchette-Kim-Vetta).
    Used in Lemma 10 for H-minor-free graphs.
  • standard math An n-vertex graph has at most 3^{n/3} maximal cliques (Moon-Moser bound).
    Used in Lemma 9 to bound the branching factor c_{d-1} ≤ 3^{(d-1)/3}.
  • standard math A graph is perfect iff it has no odd holes or odd antiholes (Strong Perfect Graph Theorem).
    Used in Theorem 2 to show the constructed graph is perfect.
  • standard math The Exponential Time Hypothesis: 3-SAT cannot be solved in 2^{o(n)} time.
    Used for all conditional lower bounds in Proposition 5.
  • standard math Every graph has a maximum independent set containing any chosen set of one simplicial vertex per simplicial clique.
    Stated without proof in Lemma 3; load-bearing for computing α(G) in the ECP/α algorithm.
  • standard math Critical cliques can be found in linear time (Lin-Jiang-Kearney).
    Used in Lemma 4 to find forced large cliques.
  • standard math Simplicial cliques can be listed in polynomial time (Kloks-Kratsch-Müller).
    Used to compute S and S' in Lemma 3 and Lemma 5.
  • domain assumption Input graphs have no isolated vertices.
    The lower bound α(G) ≤ ecc(G) ≤ ecp(G) fails with isolated vertices; the paper excludes them by definition.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Edge Clique Partition and Cover Beyond Independence." pith.science (2026). https://pith.science/paper/ALB2ZBGC

@misc{pith2026250621216,
  author       = {Pith},
  title        = {Pith review of: Edge Clique Partition and Cover Beyond Independence},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ALB2ZBGC}},
  note         = {Machine review of arXiv:2506.21216}
}
read the original abstract

Covering and partitioning the edges of a graph into cliques are classical problems at the intersection of combinatorial optimization and graph theory, having been studied through a range of algorithmic and complexity-theoretic lenses. Despite the well-known fixed-parameter tractability of these problems when parameterized by the total number of cliques, such a parameterization often fails to be meaningful for sparse graphs. In many real-world instances, on the other hand, the minimum number of cliques in an edge cover or partition can be very close to the size of a maximum independent set \alpha(G). Motivated by this observation, we investigate above \alpha parameterizations of the edge clique cover and partition problems. Concretely, we introduce and study Edge Clique Cover Above Independent Set (ECC/\alpha) and Edge Clique Partition Above Independent Set (ECP/\alpha), where the goal is to cover or partition all edges of a graph using at most \alpha(G) + k cliques, and k is the parameter. Our main results reveal a distinct complexity landscape for the two variants. We show that ECP/\alpha is fixed-parameter tractable, whereas ECC/\alpha is NP-complete for all k \geq 2, yet can be solved in polynomial time for k \in {0,1}. These findings highlight intriguing differences between the two problems when viewed through the lens of parameterization above a natural lower bound. Finally, we demonstrate that ECC/\alpha becomes fixed-parameter tractable when parameterized by k + \omega(G), where \omega(G) is the size of a maximum clique of the graph G. This result is particularly relevant for sparse graphs, in which \omega is typically small. For H-minor free graphs, we design a subexponential algorithm of running time f(H)^{\sqrt{k}}n^{O(1)}.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

52 extracted references · 51 canonical work pages

  1. [1]

    W. M. Abdullah and S. Hossain , A sparse matrix approach for covering large complex networks by cliques , in International Conference on Computational Science, Springer, 2022, pp. 505–517

    work page 2022

  2. [2]

    P. K. Agarwal, N. Alon, B. Aronov, and S. Suri , Can visibility graphs be represented compactly?, Discrete & Computational Geometry, 12 (1994), pp. 347–365

    work page 1994

  3. [3]

    Ausiello, P

    G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi , Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer, 1999

    work page 1999

  4. [4]

    Behrisch and A

    M. Behrisch and A. Taraz , Efficiently covering complex networks with cliques of similar vertices, Theoretical Computer Science, 355 (2006), pp. 37–47. 25

    work page 2006

  5. [5]

    Bj ¨orklund, T

    A. Bj ¨orklund, T. Husfeldt, and M. Koivisto , Set partitioning via inclusion-exclusion , SIAM Journal on Computing, 39 (2009), pp. 546–563

    work page 2009

  6. [6]

    Blanchette, E

    M. Blanchette, E. Kim, and A. Vetta, Clique cover on sparse networks, in Proceedings of the 14th Meeting on Algorithm Engineering & Experiments (ALENEX), SIAM / Omnipress, 2012, pp. 93–102

    work page 2012

  7. [7]

    Boole, Of Propositions Numerically Definite , Watts, London, 1952

    G. Boole, Of Propositions Numerically Definite , Watts, London, 1952. Originally published in 1868, Chapter IV

    work page 1952

  8. [8]

    M. R. Cerioli, L. F aria, T. O. Ferreira, C. A. J. Martinhon, F. Protti, and B. A. Reed, Partition into cliques for cubic graphs: Planar case, complexity and approximation , Discret. Appl. Math., 156 (2008), pp. 2270–2278

    work page 2008

Show all 52 references
  1. [9]

    Chang and H

    M. Chang and H. M ¨uller, On the tree-degree of graphs , in In Proceedings of Graph- Theoretic Concepts in Computer Science, 27th International Workshop (WG 2001), vol. 2204 of Lecture Notes in Computer Science, Springer, 2001, pp. 44–54

    2001

  2. [10]

    Chudnovsky, N

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

    2006

  3. [11]

    Conte, R

    A. Conte, R. Grossi, and A. Marino , Large-scale clique cover of real-world networks , Information and Computation, 270 (2020), p. 104464

    2020

  4. [12]

    Cygan, F

    M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh , Parameterized Algorithms, Springer, 2015

    2015

  5. [13]

    Cygan, M

    M. Cygan, M. Pilipczuk, and M. Pilipczuk , Known algorithms for edge clique cover are probably optimal, SIAM J. Comput., 45 (2016), pp. 67–83

    2016

  6. [14]

    N. G. de Bruijn and P. Erd ˝os, On a combinatorial problem , Nederl. Akad. Wetensch., Proc., 51 (1948), pp. 1277–1279 = Indagationes Math. 10, 421–423

    1948

  7. [15]

    Diestel, Graph theory, vol

    R. Diestel, Graph theory, vol. 173 of Graduate Texts in Mathematics, Springer-Verlag, Berlin, 5th ed., 2017

    2017

  8. [16]

    Erd ˝os, A

    P. Erd ˝os, A. W. Goodman, and L. P ´osa, The representation of a graph by set intersec- tions, Canadian Journal of Mathematics, 18 (1966), pp. 106–112

    1966

  9. [17]

    Erd˝os and G

    P. Erd˝os and G. Szekeres, A combinatorial problem in geometry, Compositio Mathematica, 2 (1935), pp. 463–470

    1935

  10. [18]

    A. E. Feldmann, D. Issac, and A. Rai , Fixed-parameter tractability of the weighted edge clique partition problem, in 15th International Symposium on Parameterized and Exact Com- putation (IPEC), vol. 180 of LIPIcs. Leibniz Int. Proc. Inform., Schloss Dagstuhl. Leibniz-Zent. I...

    2020

  11. [19]

    Figueroa, J

    A. Figueroa, J. Bornemann, and T. Jiang , Clustering binary fingerprint vectors with missing values for dna array data analysis , Journal of Computational Biology, 11 (2004), pp. 887–901

    2004

  12. [20]

    Fleischer and X

    R. Fleischer and X. Wu, Edge clique partition of k 4-free and planar graphs, in International Conference on Computational Geometry, Graphs and Applications, Springer, 2010, pp. 84–95. 26

    2010

  13. [21]

    F. V. Fomin, D. Lokshtanov, S. Saurabh, and M. Zehavi , Kernelization. Theory of Parameterized Preprocessing, Cambridge University Press, 2019

    2019

  14. [22]

    M. R. Garey and D. S. Johnson, The rectilinear steiner tree problem is np-complete, SIAM Journal on Applied Mathematics, 32 (1977), p. 826–834

    1977

  15. [23]

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

    1979

  16. [24]

    M. R. Garey, D. S. Johnson, and L. Stockmeyer, Some simplified np-complete problems, in Proceedings of the sixth annual ACM symposium on Theory of computing - STOC ’74, STOC ’74, ACM Press, 1974, p. 47–63

    1974

  17. [25]

    Gramm, J

    J. Gramm, J. Guo, F. H ¨uffner, and R. Niedermeier , Data reduction and exact algo- rithms for clique cover , ACM J. Exp. Algorithmics, 13 (2008)

    2008

  18. [26]

    Gramm, J

    J. Gramm, J. Guo, F. H ¨uffner, R. Niedermeier, H.-P. Piepho, and R. Schmid , Algorithms for compact letter displays: Comparison and evaluation , Computational Statistics & Data Analysis, 52 (2007), pp. 725–736

    2007

  19. [27]

    Grohe, Local tree-width, excluded minors, and approximation algorithms , Combinatorica, 23 (2003), p

    M. Grohe, Local tree-width, excluded minors, and approximation algorithms , Combinatorica, 23 (2003), p. 613–632

    2003

  20. [28]

    Gr ¨otschel, L

    M. Gr ¨otschel, L. Lov ´asz, and A. Schrijver , Geometric Algorithms and Combinatorial Optimization, vol. 2 of Algorithms and Combinatorics, Springer, 1988

    1988

  21. [29]

    Guillaume and M

    J.-L. Guillaume and M. Latapy, Bipartite structure of all complex networks , Inf. Process. Lett., 90 (2004), pp. 215–221

    2004

  22. [30]

    M. Hall Jr. , A problem in partitions , Bulletin of the American Mathematical Society, 47 (1941), pp. 804–807

    1941

  23. [31]

    Hevia, B

    A. Hevia, B. Kallus, S. McClintic, S. Reisner, D. Strash, and J. Wilson , Solv- ing Edge Clique Cover Exactly via Synergistic Data Reduction , in 31st Annual European Symposium on Algorithms (ESA), vol. 274 of Leibniz International Proceedings in Informat- ics (LIPIcs), Dagstu...

    2023

  24. [32]

    D. N. Hoover , Complexity of graph covering problems for graphs of low degree , Journal of Combinatorial Mathematics and Combinatorial Computing, 11 (1992), pp. 187–208

    1992

  25. [33]

    Hsu and K.-H

    W.-L. Hsu and K.-H. Tsai , Linear time algorithms on circular-arc graphs , Inf. Process. Lett., 40 (1991), pp. 123–129

    1991

  26. [34]

    H. B. Hunt III, M. V. Marathe, V. Radhakrishnan, and R. E. Stearns , The com- plexity of planar counting problems , SIAM J. Comput., 27 (1998), pp. 1142–1167

    1998

  27. [35]

    Impagliazzo, R

    R. Impagliazzo, R. Paturi, and F. Zane, Which problems have strongly exponential com- plexity, J. Computer and System Sciences, 63 (2001), pp. 512–530

    2001

  28. [36]

    Kellerman , Determination of keyword conflict , IBM Technical Disclosure Bulletin, 16 (1973), pp

    E. Kellerman , Determination of keyword conflict , IBM Technical Disclosure Bulletin, 16 (1973), pp. 544–546. 27

    1973

  29. [37]

    Kloks, D

    T. Kloks, D. Kratsch, and H. M ¨uller, Finding and counting small induced subgraphs efficiently, Inf. Process. Lett., 74 (2000), pp. 115–121

    2000

  30. [38]

    Korhonen , A single-exponential time 2-approximation algorithm for treewidth , in 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), IEEE, Feb

    T. Korhonen , A single-exponential time 2-approximation algorithm for treewidth , in 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), IEEE, Feb. 2022, p. 184–192

    2021

  31. [39]

    A. V. Kostochka , Lower bound of the hadwiger number of graphs by their average degree , Combinatorica, 4 (1984), p. 307–316

    1984

  32. [40]

    L. T. Kou, L. J. Stockmeyer, and C. K. Wong , Covering edges by cliques with regard to keyword conflicts and intersection graphs , Communications of the ACM, 21 (1978), pp. 135– 139

    1978

  33. [41]

    G. Lin, T. Jiang, and P. E. Kearney, Phylogenetic k-root and steiner k-root, in Algorithms and Computation, 11th International Conference, ISAAC 2000, Taipei, Taiwan, December 18- 20, 2000, Proceedings, D. T. Lee and S. Teng, eds., vol. 1969 of Lecture Notes in Computer Scienc...

    2000

  34. [42]

    Lov ´asz, On covering of graphs , in Theory of Graphs, Proceedings of the Colloquium Tihany, Hungary, 1966, Academic Press, Budapest, 1968, pp

    L. Lov ´asz, On covering of graphs , in Theory of Graphs, Proceedings of the Colloquium Tihany, Hungary, 1966, Academic Press, Budapest, 1968, pp. 231–236

    1966

  35. [43]

    Lund and M

    C. Lund and M. Yannakakis, On the hardness of approximating minimization problems , J. ACM, 41 (1994), pp. 960–981

    1994

  36. [44]

    S. Ma, W. D. W allis, and J. Wu, Clique covering of chordal graphs, Utilitas Mathematica, 36 (1989), pp. 151–152

    1989

  37. [45]

    J. W. Moon and L. Moser , On cliques in graphs , Israel Journal of Mathematics, 3 (1965), p. 23–28

    1965

  38. [46]

    Mujuni and F

    E. Mujuni and F. A. Rosamond, Parameterized complexity of the clique partition problem., in CATS, Citeseer, 2008, pp. 75–78

    2008

  39. [47]

    Niedermeier , Invitation to fixed-parameter algorithms , vol

    R. Niedermeier , Invitation to fixed-parameter algorithms , vol. 31 of Oxford Lecture Series in Mathematics and its Applications, Oxford University Press, Oxford, 2006

    2006

  40. [48]

    J. B. Orlin, Contentment in graph theory: Covering graphs with cliques , Indagationes Math- ematicae (Proceedings), 80 (1977), pp. 406–424

    1977

  41. [49]

    Piepho , An algorithm for a letter-based representation of all-pairwise comparisons , Journal of Computational and Graphical Statistics, 13 (2004), pp

    H.-P. Piepho , An algorithm for a letter-based representation of all-pairwise comparisons , Journal of Computational and Graphical Statistics, 13 (2004), pp. 456–466

    2004

  42. [50]

    Rajagopalan, M

    S. Rajagopalan, M. V achharajani, and S. Malik , Handling irregular ILP within con- ventional VLIW schedulers using artificial resource constraints, in CASES 2000, 2000, pp. 157– 164

    2000

  43. [51]

    F. P. Ramsey, On a problem of formal logic, Proceedings of the London Mathematical Society, s2-30 (1930), pp. 264–286

    1930

  44. [52]

    H. J. Ryser, Intersection properties of finite sets, Combinatorial Theory, 14 (1973), pp. 79–92. 28

    1973

Pith tools

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