pith. machine review for the scientific record. sign in

arxiv: 2604.20457 · v1 · submitted 2026-04-22 · 💻 cs.DS

Recognition: unknown

Cluster Vertex Deletion on Chordal Graphs

Yixin Cao , Peng Li
Authors on Pith no claims yet

Pith reviewed 2026-05-09 23:30 UTC · model grok-4.3

classification 💻 cs.DS
keywords cluster vertex deletionchordal graphsdynamic programmingclique treessubmodular set function minimizationpolynomial-time algorithmsgraph modification problems
0
0 comments X

The pith

Cluster vertex deletion admits a polynomial-time algorithm on chordal graphs via dynamic programming on clique trees.

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

The paper shows that deleting the fewest vertices to turn a chordal graph into a cluster graph (a disjoint union of cliques) can be done in polynomial time. It does so by running dynamic programming along the clique tree that every chordal graph possesses, where each subproblem value is obtained by minimizing a submodular set function over a suitable ground set. Because submodular minimization is polynomial-time solvable, the overall procedure runs in polynomial time. This settles an open complexity question that had been posed in several recent papers for this specific graph class.

Core claim

We present a polynomial-time algorithm for the cluster vertex deletion problem on chordal graphs. We use dynamic programming over clique trees and reduce the computation of the optimal subproblem value to the minimization of a submodular set function.

What carries the argument

Dynamic programming over a clique tree, with each table entry computed by minimizing a submodular set function on the bags or separators of the tree.

If this is right

  • The cluster vertex deletion problem is in P when restricted to chordal graphs.
  • The clique-tree structure of chordal graphs allows reduction of the deletion task to submodular minimization.
  • Similar dynamic-programming schemes may apply to other vertex-deletion problems whose target graphs admit natural characterizations on chordal inputs.
  • The running time is governed by the cost of submodular minimization on sets whose size is bounded by the treewidth or clique size of the input.

Where Pith is reading between the lines

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

  • The same clique-tree DP may extend to other deletion problems whose forbidden subgraphs interact cleanly with chordal structure.
  • Because chordal graphs are perfect, the algorithm might serve as a building block for approximation schemes on slightly non-chordal inputs obtained by adding a few edges or vertices.
  • Practical implementations could exploit fast submodular minimization oracles specialized to the particular ground sets arising from clique-tree bags.

Load-bearing premise

The input graph is chordal and therefore possesses a clique tree that supports the dynamic-programming recurrence without additional verification overhead.

What would settle it

A concrete chordal graph together with a vertex set whose size the algorithm reports as optimal, yet which leaves the remaining graph not a cluster graph, or a larger deletion set that is smaller than the reported optimum.

Figures

Figures reproduced from arXiv: 2604.20457 by Peng Li, Yixin Cao.

Figure 1
Figure 1. Figure 1: (a) A chordal graph with 11 maximal cliques; (b) one of its clique trees. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The bipartite graph B when the graph is in [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
read the original abstract

We present a polynomial-time algorithm for the cluster vertex deletion problem on chordal graphs, resolving an open question posed in different contexts by Cao et al. [Theoretical Computer Science, 2018], Aprile et al. [Mathematical Programming, 2023], Chakraborty et al. [Discrete Applied Mathematics, 2024], and Hsieh et al. [Algorithmica, 2024]. We use dynamic programming over clique trees and reduce the computation of the optimal subproblem value to the minimization of a submodular set function.

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 manuscript claims to resolve an open question by presenting a polynomial-time algorithm for the Cluster Vertex Deletion problem on chordal graphs. The algorithm uses dynamic programming over a clique tree of the input graph, with the optimal value for each subproblem obtained by minimizing a submodular set function that encodes the P3-free deletion objective.

Significance. If the result holds, the contribution is significant: it supplies the first polynomial-time algorithm for this problem on chordal graphs, a natural and well-studied class. The approach correctly combines two standard polynomial-time primitives (linear-time clique-tree construction and submodular-function minimization) and is presented as preserving optimality for the deletion objective. This strengthens the algorithmic toolbox for vertex-deletion problems on perfect graphs and directly answers questions left open by Cao et al. (2018), Aprile et al. (2023), Chakraborty et al. (2024), and Hsieh et al. (2024).

minor comments (2)
  1. [Abstract] The abstract would be strengthened by stating an explicit polynomial running-time bound (e.g., O(n^3) or whatever the analysis yields) rather than only asserting polynomial time.
  2. A short paragraph comparing the new algorithm with known FPT or approximation results for Cluster Vertex Deletion on general graphs would help readers place the result in context.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The approach rests on two standard facts from graph theory and combinatorial optimization; no new entities or fitted constants are introduced.

axioms (2)
  • standard math Every chordal graph has a clique tree (perfect elimination ordering) that can be computed in linear time.
    Invoked implicitly when the dynamic program is defined over the clique tree.
  • standard math Submodular set-function minimization can be solved in polynomial time.
    Used to conclude that each subproblem is tractable.

pith-pipeline@v0.9.0 · 5368 in / 1069 out tokens · 101508 ms · 2026-05-09T23:30:08.772287+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

15 extracted references · 13 canonical work pages

  1. [1]

    Jungho Ahn, Lars Jaffke, O-joung Kwon, and Paloma T. Lima. Well-partitioned chordal graphs.Discrete Mathematics, 345(10):112985, 2022.doi:10.1016/J.DISC.2022.112985

    work page doi:10.1016/j.disc.2022.112985 2022

  2. [2]

    The effect of local constraints on the complexity of determi- nation of the graph independence number

    Vladimir Evgen’evich Alekseev. The effect of local constraints on the complexity of determi- nation of the graph independence number. InCombinatorial-algebraic methods in applied mathematics, chapter 3, pages 3–13. Gorkiy University Press, 1982. in Russian

    1982

  3. [3]

    A tight approximation algorithm for the cluster vertex deletion problem.Mathematical Programming, 197(2):1069– 1091, 2023.doi:10.1007/S10107-021-01744-W

    Manuel Aprile, Matthew Drescher, Samuel Fiorini, and Tony Huynh. A tight approximation algorithm for the cluster vertex deletion problem.Mathematical Programming, 197(2):1069– 1091, 2023.doi:10.1007/S10107-021-01744-W

    work page doi:10.1007/s10107-021-01744-w 2023

  4. [4]

    Local ratio: A unified framework for approximation algorithms

    Reuven Bar-Yehuda, Keren Bendel, Ari Freund, and Dror Rawitz. Local ratio: A unified framework for approximation algorithms. in memoriam: Shimon Even 1935-2004.ACM Computing Surveys, 36(4):422–463, 2004.doi:10.1145/1041680.1041683

    work page doi:10.1145/1041680.1041683 1935

  5. [5]

    Thilikos, and Sebastian Wiederrecht

    St´ephane Bessy, Marin Bougeret, Dimitrios M. Thilikos, and Sebastian Wiederrecht. Ker- nelization for graph packing problems via rainbow matching. InProceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, pages 3654–3663. SIAM, 2023. doi:10.1137/1.9781611977554.CH139

    work page doi:10.1137/1.9781611977554.ch139 2023

  6. [6]

    Nascimento, Fabiano de S

    Flavia Bonomo-Braberman, Julliano R. Nascimento, Fabiano de S. Oliveira, U´everton S. Souza, and Jayme Luiz Szwarcfiter. Linear-time algorithms for eliminating claws in graphs.International Transactions in Operational Research, 31(1):296–315, 2024.doi: 10.1111/ITOR.13100

    work page doi:10.1111/itor.13100 2024

  7. [7]

    Vertex deletion problems on chordal graphs

    Yixin Cao, Yuping Ke, Yota Otachi, and Jie You. Vertex deletion problems on chordal graphs. Theoretical Computer Science, 745:75–86, 2018.doi:10.1016/j.tcs.2018.05.039

    work page doi:10.1016/j.tcs.2018.05.039 2018

  8. [8]

    Sunil Chandran, Sajith Padinhatteeri, and Raji R

    Dibyayan Chakraborty, L. Sunil Chandran, Sajith Padinhatteeri, and Raji R. Pillai. s-Club cluster vertex deletion on interval and well-partitioned chordal graphs.Discrete Applied Mathematics, 345:170–189, 2024.doi:10.1016/J.DAM.2023.11.048

    work page doi:10.1016/j.dam.2023.11.048 2024

  9. [9]

    Gabriel A. Dirac. On rigid circuit graphs.Abhandlungen aus dem Mathematischen Seminar der Universit¨at Hamburg, 25(1):71–76, 1961.doi:10.1007/BF02992776

    work page doi:10.1007/bf02992776 1961

  10. [10]

    Cluster vertex deletion: A parameterization between vertex cover and clique-width

    Martin Doucha and Jan Kratochv´ıl. Cluster vertex deletion: A parameterization between vertex cover and clique-width. InProceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 7464 ofLNCS, pages 348–359. Springer, 2012.doi:10.1007/978-3-642-32589-2_32

    work page doi:10.1007/978-3-642-32589-2_32 2012

  11. [11]

    Nicolás, The bar derived category of a curved dg algebra, Journal of Pure and Applied Algebra 212 (2008) 2633–2659

    Dishant Goyal, Ashwin Jacob, Kaushtubh Kumar, Diptapriyo Majumdar, and Venkatesh Raman. Parameterized complexity of dominating set variants in almost cluster and split graphs.Journal of Computer and System Sciences, 150:103631, 2025.doi:10.1016/J. JCSS.2025.103631. 10

    work page doi:10.1016/j 2025

  12. [12]

    On thed-claw vertex deletion problem.Algorithmica, 86:505–525, 2024.doi:10.1007/S00453-023-01144-W

    Sun-Yuan Hsieh, Ho`ang-Oanh Le, Van Bang Le, and Sheng-Lung Peng. On thed-claw vertex deletion problem.Algorithmica, 86:505–525, 2024.doi:10.1007/S00453-023-01144-W

    work page doi:10.1007/s00453-023-01144-w 2024

  13. [13]

    Minimizing convex functions with rational minimizers.Journal of the ACM, 70(1):5:1–5:27, 2022.doi:10.1145/3566050

    Haotian Jiang. Minimizing convex functions with rational minimizers.Journal of the ACM, 70(1):5:1–5:27, 2022.doi:10.1145/3566050

    work page doi:10.1145/3566050 2022

  14. [14]

    Lewis and Mihalis Yannakakis

    John M. Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is NP-complete.Journal of Computer and System Sciences, 20(2):219–230, 1980.doi: 10.1016/0022-0000(80)90060-4

    work page doi:10.1016/0022-0000(80)90060-4 1980

  15. [15]

    Improved parameterized algorithms for cluster vertex deletion.Theory of Computing Systems, 69(4):37, 2025.doi:10.1007/ S00224-025-10247-6

    Kangyi Tian, Mingyu Xiao, and Boting Yang. Improved parameterized algorithms for cluster vertex deletion.Theory of Computing Systems, 69(4):37, 2025.doi:10.1007/ S00224-025-10247-6. 11

    2025