Pith. sign in

REVIEW 2 major objections 2 minor 27 references

Fair Vertex Problems Parameterized by Cluster Vertex Deletion

T0 review · 2 major / 2 minor · reviewed 2026-05-23 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Fair MSO1 definable problems are W[1]-hard parameterized by cluster vertex deletion in general, but FPT under a sufficient condition on the formula.

desk verdict The paper settles the open question by proving W[1]-hardness for general fair MSO1 under CVD while giving a sufficient condition that yields FPT for several natural problems. read the letter →

arxiv 2502.01400 v2 submitted 2025-02-03 cs.DS cs.CCcs.LO

Tomáš Masařík , Jędrzej Olkowski , Anna Zych-Pawlewicz This is my paper · ORCID
classification cs.DScs.CCcs.LO
keywords fairvertexproblemsclusterdeletionMSO1fixed-parametertractabilityW[1]-hardnessfeedbacksetdominating[σρ]-domination
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 fair variants of MSO1 definable graph problems, where a solution set X must satisfy that no vertex neighborhood contains more than k vertices from X. It proves that these problems cannot be solved in FPT time by cluster vertex deletion number in full generality, establishing W[1]-hardness. The authors then supply a sufficient condition on the MSO1 formula that restores fixed-parameter tractability under the same parameterization. This condition covers the fair versions of feedback vertex set, vertex cover, dominating set, odd cycle transversal and their connected variants, plus the fair [σ,ρ]-domination problem for the stated cases on σ and ρ.

What carries the argument

The sufficient condition on the MSO1 formula that enables an FPT algorithm for the fair version of the problem parameterized by cluster vertex deletion number.

What would settle it

A W[1]-hardness proof for fair vertex cover parameterized by cluster vertex deletion, or an instance family showing that one of the listed problems fails the sufficient condition.

Watch

Extended reading notes

Core claim

We prove that in full generality fair MSO1 definable problems are W[1]-hard parameterized by cluster vertex deletion number. We give a sufficient condition under which a fair MSO1 definable problem admits an FPT algorithm parameterized by the cluster vertex deletion number. Our algorithm captures the fair variant of feedback vertex set, vertex cover, dominating set, odd cycle transversal, connected variants thereof, and the fair [σ,ρ]-domination problem for σ finite or both σ and ρ cofinite.

Load-bearing premise

The listed problems satisfy the sufficient condition on their MSO1 formulas.

Editorial extensions

If this is right

  • Fair feedback vertex set is solvable in FPT time parameterized by cluster vertex deletion.
  • Fair vertex cover, dominating set, and odd cycle transversal are FPT under the same parameterization when they meet the condition.
  • Connected variants of these problems are also FPT parameterized by cluster vertex deletion.
  • Fair [σ,ρ]-domination admits an FPT algorithm when σ is finite or both σ and ρ are cofinite.

Reading between the lines

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

  • The gap between twin-cover and cluster-vertex-deletion tractability may be explained by how the fairness bound interacts with clique partitions.
  • The sufficient condition could be applied to classify additional MSO1 problems whose complexity status is currently unknown.
  • The W[1]-hardness construction might be adaptable to show intractability for other parameters between twin cover and cluster vertex deletion.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 2 minor

Summary. The paper studies fair MSO1-definable vertex problems parameterized by cluster vertex deletion (cvd) number. It proves that no FPT algorithm exists in full generality by showing W[1]-hardness, but identifies a sufficient condition on the MSO1 formula that yields an FPT algorithm parameterized by cvd; this condition is claimed to hold for the fair variants of Feedback Vertex Set, Vertex Cover, Dominating Set, Odd Cycle Transversal (including connected versions) and for Fair [σ,ρ]-Domination when σ is finite or both σ and ρ are cofinite.

Significance. The results partially answer the open question of Knop, Masařík and Toufar by separating the general case (W[1]-hard) from tractable special cases under cvd. If the sufficient condition is correctly stated and the verifications for the listed problems are complete, the work supplies both a meta-theorem and concrete FPT algorithms for several natural fair problems, extending the twin-cover results.

major comments (2)
  1. [Section stating the sufficient condition and the subsequent applications] The load-bearing step for all positive results is the verification that the concrete MSO1 formulas for fair FVS, VC, DS, OCT and the [σ,ρ]-domination cases satisfy the sufficient condition. The manuscript must contain explicit lemmas or arguments (with section references) showing how each formula meets every clause of the condition; without these checks the claims that the algorithm captures the listed problems remain unsupported.
  2. [Hardness section] § on the W[1]-hardness proof: the reduction must be shown to work for an arbitrary MSO1 property (not merely for a specific problem); the construction and the argument that the fair-cost constraint preserves the hardness should be spelled out with the precise gadget and the MSO1 sentence used.
minor comments (2)
  1. Clarify the precise syntactic form of the sufficient condition (e.g., which quantifiers or predicates are restricted) so that a reader can mechanically check new formulas against it.
  2. Add a short table or list that maps each concrete problem (fair FVS, etc.) to the exact property of its MSO1 formula that triggers the sufficient condition.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed report and for identifying points where the manuscript's arguments can be strengthened. We address each major comment below and commit to revisions that will make the sufficient-condition verifications and the hardness reduction fully explicit.

read point-by-point responses

  1. Referee: [Section stating the sufficient condition and the subsequent applications] The load-bearing step for all positive results is the verification that the concrete MSO1 formulas for fair FVS, VC, DS, OCT and the [σ,ρ]-domination cases satisfy the sufficient condition. The manuscript must contain explicit lemmas or arguments (with section references) showing how each formula meets every clause of the condition.

    Authors: We agree that the current presentation leaves the verifications implicit. In the revised manuscript we will insert a new subsection (immediately after the statement of the sufficient condition) containing one lemma per problem family. Each lemma will list every clause of the condition and give a short, self-contained argument (with direct references to the MSO1 formula) showing why the clause holds for that problem. This will be done for Fair FVS, Fair VC, Fair DS, Fair OCT (including connected variants), and the two cases of Fair [σ,ρ]-Domination. revision: yes

  2. Referee: [Hardness section] § on the W[1]-hardness proof: the reduction must be shown to work for an arbitrary MSO1 property (not merely for a specific problem); the construction and the argument that the fair-cost constraint preserves the hardness should be spelled out with the precise gadget and the MSO1 sentence used.

    Authors: We accept that the hardness argument must be stated for a generic MSO1 sentence rather than for a concrete problem. In the revision we will replace the current sketch with a self-contained subsection that (i) fixes an arbitrary MSO1 sentence φ, (ii) describes the precise gadget (including the auxiliary vertices and edges added to each original vertex), (iii) writes the concrete MSO1 sentence φ' that encodes both φ and the fair-cost bound, and (iv) proves that the fair-cost constraint does not alter the yes/no answer of the original instance. This will establish W[1]-hardness for the entire class of fair MSO1 problems. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: independent hardness proof and explicit sufficient condition with problem verification

full rationale

The derivation consists of a W[1]-hardness reduction for arbitrary fair MSO1 properties (independent of the positive results) plus a new sufficient condition on the MSO1 formula that yields an FPT algorithm parameterized by cvd. The paper then verifies that the concrete formulas for fair FVS/VC/DS/OCT and finite/cofinite [σ,ρ]-domination satisfy the condition. This verification is a direct, non-referential check rather than a self-definition, fitted parameter, or load-bearing self-citation. The cited MFCS 2019 result (twin cover) addresses a strictly stronger parameter and is not invoked to justify the cvd condition or the listed problems. No equation reduces to its own input by construction, and the central claims remain externally falsifiable.

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

The paper relies on standard concepts from parameterized complexity and monadic second-order logic; no free parameters, ad-hoc axioms, or invented entities are visible in the abstract.

assumptions (2)
  • standard math MSO1 logic defines a broad class of graph properties for which meta-theorems can be applied
    Standard background assumption in parameterized complexity for graph problems.
  • standard math W[1]-hardness implies no FPT algorithm exists unless FPT = W[1]
    Standard complexity-theoretic assumption used to interpret hardness results.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fair Vertex Problems Parameterized by Cluster Vertex Deletion." pith.science (2026). https://pith.science/paper/2502.01400

@misc{pith2026250201400,
  author       = {Pith},
  title        = {Pith review of: Fair Vertex Problems Parameterized by Cluster Vertex Deletion},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2502.01400}},
  note         = {Machine review of arXiv:2502.01400}
}
abstract

In this paper we study fair variants of MSO$_1$ definable problems parameterized by cluster vertex deletion number, i.e., the smallest number of vertices required to be removed from the graph such that what remains is a collection of cliques. While typical graph problems seek the smallest set of vertices satisfying some property, their fair variants seek such a set that does not contain too many vertices in any neighborhood of any vertex. Formally, the task is to find a set $X\subseteq V(G)$ satisfying some MSO$_1$ definable property, whose fair cost is at most $k$, i.e., such that for all $v\in V(G)$ it holds that $|X\cap N(v)|\le k$. Recently, Knop, Masa\v{r}\'ik, and Toufar [MFCS 2019] showed that all fair MSO$_1$ definable problems can be solved in FPT time parameterized by the twin cover of a graph. They asked whether such a statement can be achieved for a more general parameterization by cluster vertex deletion number. In this paper, we prove that in full generality this is not possible by demonstrating W[1]-hardness. On the other hand, we give a sufficient condition under which a fair MSO$_1$ definable problem admits an FPT algorithm parameterized by the cluster vertex deletion number. Our algorithm is general enough to capture the fair variant of many natural graph problems such as the Fair Feedback Vertex Set problem, the Fair Vertex Cover problem, the Fair Dominating Set problem, the Fair Odd Cycle Transversal problem, as well as connected variants thereof. Moreover, we solve the Fair $[\sigma,\rho]$-Domination problem for $\sigma$ finite, or when both $\sigma$ and $\rho$ are cofinite. That is, given finite or cofinite $\rho,\sigma\subseteq \mathbb{N}$, the task is to find set of vertices $X\subseteq V(G)$ of fair cost at most $k$ such that for all $v\in X$, $|N(v)\cap X| \in\sigma$ and for all $v\in V(G)\setminus X$, $|N(v)\cap X|\in\rho$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [1]

    Dominator coloring and CD coloring in almost cluster graphs

    Aritra Banik, Prahlad Narasimhan Kasthurirangan, and Venkatesh Raman. Dominator coloring and CD coloring in almost cluster graphs. In Pat Morin and Subhash Suri, editors, Algorithms and Data Structures (WADS 2023) , pages 106--119, Cham, 2023. Springer Nature Switzerland. https://doi.org/10.1007/978-3-031-38906-1_8 doi:10.1007/978-3-031-38906-1_8

    work page doi:10.1007/978-3-031-38906-1_8 2023

  2. [2]

    On Sparse Hitting Sets: From Fair Vertex Cover to Highway Dimension

    Johannes Blum, Yann Disser, Andreas Emil Feldmann, Siddharth Gupta, and Anna Zych-Pawlewicz. On Sparse Hitting Sets: From Fair Vertex Cover to Highway Dimension . In Holger Dell and Jesper Nederlof, editors, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022) , volume 249 of Leibniz International Proceedings in Informatics (LIP...

    work page doi:10.4230/lipics.ipec.2022.5 2022

  3. [3]

    Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach, volume 138 of Encyclopedia of mathematics and its applications

    Bruno Courcelle and Joost Engelfriet. Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach . Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2012. https://doi.org/10.1017/CBO9780511977619 doi:10.1017/CBO9780511977619

    work page doi:10.1017/cbo9780511977619 2012

  4. [4]

    9 Marc Distel, Robert Hickingbotham, Tony Huynh, and David R

    Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory of Computing Systems , 33(2):125--150, 2000. https://doi.org/10.1007/s002249910009 doi:10.1007/s002249910009

    work page doi:10.1007/s002249910009

  5. [5]

    o hler, Nikolaos Melissinos, and Manolis Vasilakis. Bandwidth Parameterized by Cluster Vertex Deletion Number . In Neeldhara Misra and Magnus Wahlstr\

    Tatsuya Gima, Eun Jung Kim, Noleen K\" o hler, Nikolaos Melissinos, and Manolis Vasilakis. Bandwidth Parameterized by Cluster Vertex Deletion Number . In Neeldhara Misra and Magnus Wahlstr\" o m, editors, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023) , volume 285 of Leibniz International Proceedings in Informatics (LIPIcs...

    work page doi:10.4230/lipics.ipec.2023.21 2023

  6. [6]

    32 Yasuaki Kobayashi and Hisao Tamaki

    Tatsuya Gima and Yota Otachi. Extended MSO model checking via small vertex integrity. Algorithmica , 86(1):147--170, August 2023. https://doi.org/10.1007/s00453-023-01161-9 doi:10.1007/s00453-023-01161-9

    work page doi:10.1007/s00453-023-01161-9 2023

  7. [7]

    Tight Algorithms for Connectivity Problems Parameterized by Clique-Width , booktitle =

    Falko Hegerfeld and Stefan Kratsch. Tight algorithms for connectivity problems parameterized by clique-width. In Inge Li G rtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman, editors, 31st Annual European Symposium on Algorithms (ESA 2023) , volume 274 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 59:1--59:19, Dagstuhl...

    work page doi:10.4230/lipics.esa.2023.59 2023

  8. [8]

    Fixed-parameter algorithms for fair hitting set problems

    Tanmay Inamdar, Lawqueen Kanesh, Madhumita Kundu, Nidhi Purohit, and Saket Saurabh. Fixed-parameter algorithms for fair hitting set problems. Information and Computation , 302:105261:1--105261:19, 2025. https://doi.org/10.1016/j.ic.2024.105261 doi:10.1016/j.ic.2024.105261

    work page doi:10.1016/j.ic.2024.105261 2025

Show all 27 references
  1. [9]

    Italiano, Athanasios L

    Giuseppe F. Italiano, Athanasios L. Konstantinidis, and Charis Papadopoulos. Structural parameterization of cluster deletion. In Chun-Cheng Lin, Bertrand M.T. Lin, and Giuseppe Liotta, editors, WALCOM: Algorithms and Computation , pages 371--383, Cham, 2023. Springer Nature Sw...

    2023 doi

  2. [10]

    Deconstructing parameterized hardness of fair vertex deletion problems

    Ashwin Jacob, Venkatesh Raman, and Vibha Sahlot. Deconstructing parameterized hardness of fair vertex deletion problems. In Ding-Zhu Du, Zhenhua Duan, and Cong Tian, editors, Computing and Combinatorics , pages 325--337. Springer International Publishing, 2019. https://doi.org...

    2019 doi

  3. [11]

    Bin packing with fixed number of bins revisited

    Klaus Jansen, Stefan Kratsch, D \' a niel Marx, and Ildik \' o Schlotter. Bin packing with fixed number of bins revisited. Journal of Computer and System Sciences , 79(1):39--49, 2013. https://doi.org/10.1016/j.jcss.2012.04.004 doi:10.1016/j.jcss.2012.04.004

    2013 doi

  4. [12]

    Parameterized complexity of fair feedback vertex set problem

    Lawqueen Kanesh, Soumen Maity, Komal Muluk, and Saket Saurabh. Parameterized complexity of fair feedback vertex set problem. Theoretical Computer Science , 867:1--12, 2021. https://doi.org/10.1016/j.tcs.2021.03.008 doi:10.1016/j.tcs.2021.03.008

    2021 doi

  5. [13]

    Local linear set on graphs with bounded twin cover number

    Dušan Knop. Local linear set on graphs with bounded twin cover number. Information Processing Letters , 170:106118:1--106118:4, September 2021. https://doi.org/10.1016/j.ipl.2021.106118 doi:10.1016/j.ipl.2021.106118

    2021 doi

  6. [14]

    Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity

    Dušan Knop, Martin Koutecký, Tomáš Masařík, and Tomáš Toufar. Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity . Logical Methods in Computer Science , 15(4):12:1--12:32, 2019. https://doi.org/10.23638/LMCS-15(4:12)2019 doi:10.23638/LMCS-15(4:12)2019

    2019 doi

  7. [15]

    Parameterized complexity of fair vertex evaluation problems, 2018

    Dušan Knop, Tomáš Masařík, and Tomáš Toufar. Parameterized complexity of fair vertex evaluation problems, 2018. https://arxiv.org/abs/1803.06878 arXiv:1803.06878

    2018

  8. [16]

    Parameterized complexity of fair vertex evaluation problems

    Dušan Knop, Tomáš Masařík, and Tomáš Toufar. Parameterized complexity of fair vertex evaluation problems. In Peter Rossmanith, Pinar Heggernes, and Joost - Pieter Katoen, editors, 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 2...

    2019 doi

  9. [17]

    Fair edge deletion problems on treedecomposable graphs and improper colorings, 2010

    Petr Kolman, Bernard Lidick \' y , and Jean-S \' e bastien Sereni. Fair edge deletion problems on treedecomposable graphs and improper colorings, 2010. URL: http://orion.math.iastate.edu/lidicky/pub/kls10.pdf

    2010

  10. [18]

    On minimum fair odd cycle transversal

    Petr Kolman, Bernard Lidick \'y , and Jean-S \'e bastien Sereni. On minimum fair odd cycle transversal. KAM-DIMATIA Series , 2010. URL: https://kam.mff.cuni.cz/ kamserie/serie/clanky/2010/s956.ps

    2010

  11. [19]

    Minimum eccentricity shortest path problem with respect to structural parameters

    Martin Kučera and Ondřej Suchý. Minimum eccentricity shortest path problem with respect to structural parameters. Algorithmica , 85(3):762--782, March 2023. https://doi.org/10.1007/s00453-022-01006-x doi:10.1007/s00453-022-01006-x

    2023 doi

  12. [20]

    Algorithmic meta-theorems for restrictions of treewidth

    Michael Lampis. Algorithmic meta-theorems for restrictions of treewidth. Algorithmica , 64(1):19--37, September 2012. https://doi.org/10.1007/s00453-011-9554-x doi:10.1007/s00453-011-9554-x

    2012 doi

  13. [21]

    Model checking lower bounds for simple graphs

    Michael Lampis. Model checking lower bounds for simple graphs. Logical Methods in Computer Science , 10(1):1--21, 2014. https://doi.org/10.2168/LMCS-10(1:18)2014 doi:10.2168/LMCS-10(1:18)2014

    2014 doi

  14. [22]

    Lenstra, Jr

    Hendrik W. Lenstra, Jr. Integer programming with a fixed number of variables. Mathematics of Operations Research , 8(4):538--548, 1983. https://doi.org/10.1287/moor.8.4.538 doi:10.1287/moor.8.4.538

    1983 doi

  15. [23]

    Fair edge deletion problems

    Li-Shin Lin and Sartaj Sahni. Fair edge deletion problems. IEEE Transactions on Computers , 38(5):756--761, 1989. https://doi.org/10.1109/12.24280 doi:10.1109/12.24280

    1989 doi

  16. [24]

    Parameterized complexity of fair deletion problems

    Tomáš Masařík and Tomáš Toufar. Parameterized complexity of fair deletion problems. Discrete Applied Mathematics , 278:51--61, 2020. https://doi.org/10.1016/j.dam.2019.06.001 doi:10.1016/j.dam.2019.06.001

    2020 doi

  17. [25]

    The subspace flatness conjecture and faster integer programming

    Victor Reis and Thomas Rothvoss. The subspace flatness conjecture and faster integer programming. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science ( FOCS ) , pages 974--988. IEEE, November 2023. https://doi.org/10.1109/FOCS57990.2023.00060 doi:10.1109/FOCS...

    2023 doi

  18. [26]

    Monadic second order logic on graphs with local cardinality constraints

    Stefan Szeider. Monadic second order logic on graphs with local cardinality constraints. ACM Transactions on Computational Logic , 12(2):1--21, 2011. https://doi.org/10.1145/1877714.1877718 doi:10.1145/1877714.1877718

    2011 doi

  19. [27]

    Complexity of domination-type problems in graphs

    Jan Arne Telle. Complexity of domination-type problems in graphs. Nordic Journal of Computing , 1(1):157--171, March 1994. URL: http://www.cs.helsinki.fi/njc/njc1_papers/number1/reg_paper3.pdf

    1994

Pith tools

Reviewed May 23, 2026 · model on record in the stance chip above.