pith. sign in

arxiv: 2605.19853 · v1 · pith:NTOXVX7Xnew · submitted 2026-05-19 · 💻 cs.DS

Linear Kernels for l-Exact Component Order Connectivity

Yuxi Liu , Mingyu Xiao This is my paper

Pith reviewed 2026-05-20 02:05 UTC · model grok-4.3

classification 💻 cs.DS
keywords kernelizationl-exact component order connectivitycrown decompositionlinear programmingvertex deletionparameterized algorithmsgraph connectivity
0
0 comments X

The pith

The l-Exact Component Order Connectivity problem admits an O(kl)-vertex kernel for each fixed l at least 3.

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

The paper studies the problem of deleting at most k vertices so every remaining connected component has exactly l vertices. The authors construct a reduction that shrinks any input graph to an equivalent instance on O(kl) vertices, running in time n to the power O(l). This supplies the first linear kernel for every fixed l of 3 or larger. For the special case l equals 1 the bound recovers the classic 2k-vertex kernel for vertex cover; for l equals 2 it improves the prior 6k-vertex bound to 3k plus 1. Readers care because a linear kernel lets any later exact or heuristic solver run on an instance whose size is controlled by the two natural parameters.

Core claim

We present an O(kl)-vertex kernel for the l-Exact Component Order Connectivity problem, computable in n to the O(l) time. This is the first known linear kernel for each fixed l greater than or equal to 3. When l equals 1 the problem is vertex cover and the kernel matches the best-known 2k-vertex bound. When l equals 2 the problem is deletion to an induced matching and the new kernel has 3k plus 1 vertices, improving the previous 6k-vertex result. The algorithm relies on an extended crown decomposition together with linear programming and additional reduction rules.

What carries the argument

Extended crown decomposition combined with linear programming

If this is right

  • For every fixed l the problem has a kernel whose size is linear in the deletion parameter k.
  • Any instance can be reduced to O(kl) vertices before invoking an exact solver or other FPT technique.
  • The l equals 2 case improves the previous best kernel from 6k to 3k plus 1 vertices.
  • The l equals 1 case recovers the optimal 2k-vertex kernel already known for vertex cover.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same crown-plus-LP approach may adapt to other deletion problems whose target components have bounded but non-uniform sizes.
  • A linear kernel opens the door to single-exponential FPT algorithms once a bounded-search-tree or dynamic-programming routine is applied to the reduced instance.
  • Empirical tests on random or scale-free graphs could measure how often the reduction actually reaches the O(kl) size in practice.

Load-bearing premise

The particular mix of extended crown decomposition, linear programming and auxiliary rules produces a kernel whose vertex count is linear in both k and l.

What would settle it

An infinite family of graphs for some fixed l where every equivalent instance still requires more than C kl vertices for any constant C would refute the linear bound.

Figures

Figures reproduced from arXiv: 2605.19853 by Mingyu Xiao, Yuxi Liu.

Figure 1
Figure 1. Figure 1: An ECOC crown decomposition (I, J, R) with l = 3. The four bold edges form an injective matching from J to the collection of connected components C of G[I]. 3 ECOC Crown Decomposition First, we present a variant of VC crown decomposition for l-ECOC, called ECOC crown decomposition. Definition 2. An ECOC crown decomposition of a graph G = (V, E) is a par￾tition (I, J, R) of the vertex set V satisfying the f… view at source ↗
Figure 2
Figure 2. Figure 2: Sets S and S ′ in the proof of Lemma 2. Let T = V (C ′ ) ∪ V (C2). We will focus on the vertex set T in the remaining part of this proof. Let D = V (C ′ ) \ V (C2). Note that J2 ⊆ D. We construct a new solution candidate S ′ = S \ V (C2) ∪ D. See [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: A minimal strict ECOC crown decomposition (I, J, R) where l = 3 and J ′ 2 = J2. The four bold edges form an injective matching from J to the collection of connected components C of G[I]. exactly l. Thus, K must contain at least one vertex from N(I). Since N(I) ⊆ J, K contains some vertex v ∈ J. By our construction and the fact that J1 was already set to 1, SL′ satisfies xv = 1 for all v ∈ J. Therefore, P w… view at source ↗
read the original abstract

The \textsc{$l$-Exact Component Order Connectivity} problem asks whether, given an input graph $G$ and an integer $k$, there exists a vertex subset $S\subseteq V(G)$ of size at most $k$ such that every connected component in $G - S$ has exactly $l$ vertices. In this paper, we present an $O(kl)$-vertex kernel for this problem, computable in $|V(G)|^{O(l)}$ time. This is the first known linear kernel for each fixed $l\geq 3$. For $l=1$, this problem reduces to the classical \textsc{Vertex Cover}, and our result matches the best-known $2k$-vertex kernel. For $l=2$ (known as \textsc{Deletion to Induced Matching}), we can get a $(3k + 1)$-vertex kernel, improving the previously known result of $6k$ vertices. Our kernelization algorithm is built upon on an extended crown decomposition combined with linear programming and other techniques.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper studies the l-Exact Component Order Connectivity problem: given graph G and integer k, decide if there is a vertex set S of size at most k such that every component of G-S has exactly l vertices. It claims an O(kl)-vertex kernel computable in |V(G)|^{O(l)} time for any fixed l >= 3; this is presented as the first linear kernel for these cases. Special cases recover the 2k-vertex kernel for Vertex Cover (l=1) and improve the prior 6k bound to 3k+1 for Deletion to Induced Matching (l=2). The algorithm is built from an extended crown decomposition combined with linear programming and additional reduction rules.

Significance. If the claimed kernel holds, the result is significant for parameterized complexity: linear kernels remain rare and valuable for FPT problems, and the O(kl) bound for fixed l is tight in the parameter dependence. The constructive approach supplies explicit reduction rules (Section 3) and a direct size analysis (Section 4) that counts remaining vertices after exhaustive application, together with the |V|^{O(l)} runtime that is polynomial for fixed l. These elements provide independent, verifiable support for the central claim and demonstrate how extended crown decompositions plus LP can be combined to eliminate hidden multiplicative factors in l or k.

minor comments (2)
  1. [Section 3] Section 3: the reduction rules are stated explicitly, yet the precise way the LP-based covering argument interacts with the extended crown decomposition to bound component sizes to O(l) would benefit from a short illustrative example or pseudocode snippet.
  2. [Section 4] Section 4: the size proof directly counts vertices after rule application and obtains the O(kl) bound, but stating the leading constants (rather than big-O only) would make the linear dependence on k and l fully transparent.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work on l-Exact Component Order Connectivity and for recommending minor revision. The referee summary correctly identifies the main result—an O(kl)-vertex kernel for fixed l >= 3, the first linear kernel in this regime—along with the special-case improvements for l=1 (Vertex Cover) and l=2 (Deletion to Induced Matching) and the algorithmic ingredients (extended crown decomposition, LP, and explicit reduction rules).

Circularity Check

0 steps flagged

No significant circularity detected in derivation chain

full rationale

The paper's central result is a constructive O(kl)-vertex kernel obtained via explicit reduction rules based on extended crown decomposition and LP techniques, followed by a direct counting argument in the size analysis. No step reduces a claimed prediction or first-principles result to its own inputs by construction, nor does any load-bearing premise collapse to a self-citation or fitted parameter. The derivation is internally consistent and self-contained against the stated assumptions, with independent support from the reduction rules and size proof.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The abstract relies on standard graph-theoretic definitions and existing parameterized techniques such as crown decomposition and linear programming; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)
  • standard math Standard definitions of graphs, connected components, and vertex deletion preserve the problem semantics.
    The problem statement in the abstract presupposes ordinary undirected graphs and component connectivity.

pith-pipeline@v0.9.0 · 5704 in / 1122 out tokens · 46360 ms · 2026-05-20T02:05:38.839734+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    In: Arge, L., Italiano, G.F., Sedgewick, R

    Abu-Khzam, F.N., Collins, R.L., Fellows, M.R., Langston, M.A., Suters, W.H., Symons, C.T.: Kernelization algorithms for the vertex cover problem: Theory and experiments. In: Arge, L., Italiano, G.F., Sedgewick, R. (eds.) Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Work- shop on Analytic Algorithmics and Combina...

    work page 2004

  2. [2]

    Information Processing Letters65(3), 163–168 (1998)

    Balasubramanian, R., Fellows, M.R., Raman, V.: An improved fixed-parameter algorithm for vertex cover. Information Processing Letters65(3), 163–168 (1998)

    work page 1998

  3. [3]

    Proceedings of the National Academy of Sciences43(9), 842–844 (1957)

    Berge, C.: Two theorems in graph theory. Proceedings of the National Academy of Sciences43(9), 842–844 (1957)

    work page 1957

  4. [4]

    Buss,J.F.,Goldsmith,J.:Nondeterminismwithinpˆ.SIAMJournalonComputing 22(3), 560–572 (1993)

    work page 1993

  5. [5]

    arXiv preprint arXiv:2011.04528 (2020)

    Casel, K., Friedrich, T., Issac, D., Niklanovits, A., Zeif, Z.: Balanced crown decom- position for connectivity constraints. arXiv preprint arXiv:2011.04528 (2020)

    work page arXiv 2011

  6. [6]

    Information Processing Letters93(3), 125–131 (2005)

    Chandran, L.S., Grandoni, F.: Refined memorization for vertex cover. Information Processing Letters93(3), 125–131 (2005)

    work page 2005

  7. [7]

    Journal of Algorithms41(2), 280–301 (2001)

    Chen, J., Kanj, I.A., Jia, W.: Vertex cover: further observations and further im- provements. Journal of Algorithms41(2), 280–301 (2001)

    work page 2001

  8. [8]

    Theoretical Computer Science411(40-42), 3736–3756 (2010)

    Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theoretical Computer Science411(40-42), 3736–3756 (2010)

    work page 2010

  9. [9]

    Networks: An International Journal35(4), 253–259 (2000)

    Chen, J., Liu, L., Jia, W.: Improvement on vertex cover for low-degree graphs. Networks: An International Journal35(4), 253–259 (2000)

    work page 2000

  10. [10]

    In: International workshop on graph-theoretic concepts in computer science

    Chor, B., Fellows, M., Juedes, D.: Linear kernels in linear time, or how to save k colors ino(n2)steps. In: International workshop on graph-theoretic concepts in computer science. pp. 257–269. Springer (2004)

    work page 2004

  11. [11]

    Algorithmica76(4), 1181–1202 (2016)

    Drange, P.G., Dregi, M., van’t Hof, P.: On the computational complexity of vertex integrity and component order connectivity. Algorithmica76(4), 1181–1202 (2016)

    work page 2016

  12. [12]

    Theoretical Computer Science411(7-9), 1045–1053 (2010)

    Fomin, F.V., Gaspers, S., Kratsch, D., Liedloff, M., Saurabh, S.: Iterative com- pression and exact algorithms. Theoretical Computer Science411(7-9), 1045–1053 (2010)

    work page 2010

  13. [13]

    In: 41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024, March 12-14, 2024, Clermont-Ferrand, France (2024)

    Harris, D.G., Narayanaswamy, N.S.: A faster algorithm for vertex cover parame- terized by solution size. In: 41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024, March 12-14, 2024, Clermont-Ferrand, France (2024)

    work page 2024

  14. [14]

    SIAM Journal on computing2(4), 225–231 (1973)

    Hopcroft,J.E.,Karp,R.M.:Ann 5/2 algorithmformaximummatchingsinbipartite graphs. SIAM Journal on computing2(4), 225–231 (1973)

    work page 1973

  15. [15]

    arXiv:2008.09660 (2020)

    Kumar, A., Kumar, M.: Deletion to induced matching. arXiv:2008.09660 (2020)

    work page arXiv 2008

  16. [16]

    In: Guo, J., Hermelin, D

    Kumar, M., Lokshtanov, D.: A 2lk kernel for l-component order connectivity. In: Guo, J., Hermelin, D. (eds.) 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24-26, 2016, Aarhus, Denmark. LIPIcs, vol. 63, pp. 20:1–20:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

    work page 2016

  17. [17]

    Theoretical Computer Science1041, 115215 (2025)

    Liu, Y., Xiao, M.: An improved kernel and parameterized algorithm for deletion to induced matching. Theoretical Computer Science1041, 115215 (2025)

    work page 2025

  18. [18]

    Journal of Computer and System Sciences78(1), 179–191 (2012)

    Mathieson, L., Szeider, S.: Editing graphs to satisfy degree constraints: A parame- terized approach. Journal of Computer and System Sciences78(1), 179–191 (2012)

    work page 2012

  19. [19]

    Journal of Discrete Algorithms7(2), 181–190 (2009)

    Moser, H., Thilikos, D.M.: Parameterized complexity of finding regular induced subgraphs. Journal of Discrete Algorithms7(2), 181–190 (2009)

    work page 2009

  20. [20]

    Mathematical programming6(1), 48–61 (1974)

    Nemhauser, G.L., Trotter Jr, L.E.: Properties of vertex packing and independence system polyhedra. Mathematical programming6(1), 48–61 (1974)

    work page 1974

  21. [21]

    In: Annual Symposium on Theoretical Aspects of Computer Science

    Niedermeier, R., Rossmanith, P.: Upper bounds for vertex cover further improved. In: Annual Symposium on Theoretical Aspects of Computer Science. pp. 561–570. Springer (1999)

    work page 1999

  22. [22]

    Journal of Discrete Algorithms1(1), 89–102 (2003)

    Niedermeier, R., Rossmanith, P.: An efficient fixed-parameter algorithm for 3- hitting set. Journal of Discrete Algorithms1(1), 89–102 (2003)

    work page 2003

  23. [23]

    Journal of Computer and System Sciences88, 260–270 (2017)

    Xiao, M.: Linear kernels for separating a graph into components of bounded size. Journal of Computer and System Sciences88, 260–270 (2017)

    work page 2017

  24. [24]

    Theoretical Computer Science846, 103–113 (2020)

    Xiao, M., Kou, S.: Parameterized algorithms and kernels for almost induced match- ing. Theoretical Computer Science846, 103–113 (2020)

    work page 2020