pith. sign in

arxiv: 2502.01400 · v2 · submitted 2025-02-03 · 💻 cs.DS · cs.CC· cs.LO

Fair Vertex Problems Parameterized by Cluster Vertex Deletion

Tom\'a\v{s} Masa\v{r}\'ik , J\k{e}drzej Olkowski , Anna Zych-Pawlewicz This is my paper

Pith reviewed 2026-05-23 04:29 UTC · model grok-4.3

classification 💻 cs.DS cs.CCcs.LO
keywords fair vertex problemscluster vertex deletionMSO1fixed-parameter tractabilityW[1]-hardnessfeedback vertex setdominating set[σ,ρ]-domination
0
0 comments X

The pith

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

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

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 ρ.

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.

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.

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.

Where Pith is reading between the lines

These are 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.

Load-bearing premise

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

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.

read the original 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$.

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

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

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.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 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.

axioms (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.

pith-pipeline@v0.9.0 · 5966 in / 1373 out tokens · 63592 ms · 2026-05-23T04:29:05.812659+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

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

    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]

    Makowsky, and Udi Rotics

    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 2000

  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]

    Extended MSO model checking via small vertex integrity

    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

    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

  9. [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 Switzerland. https://doi.org/10.1007/978-3-031-27051-2_31 doi:10.1007/978-3-031-27051-2_31

    work page doi:10.1007/978-3-031-27051-2_31 2023

  10. [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/10.1007/978-3-030-26176-4_27 doi:10.1007/978-3-030-26176-4_27

    work page doi:10.1007/978-3-030-26176-4_27 2019

  11. [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

    work page doi:10.1016/j.jcss.2012.04.004 2013

  12. [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

    work page doi:10.1016/j.tcs.2021.03.008 2021

  13. [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

    work page doi:10.1016/j.ipl.2021.106118 2021

  14. [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

    work page doi:10.23638/lmcs-15(4:12)2019 2019

  15. [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

    work page arXiv 2018

  16. [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 26-30, 2019, Aachen, Germany , volume 138 of LIPIcs , pages 33:1--33:16. Schloss ...

    work page doi:10.4230/lipics.mfcs.2019.33 2019

  17. [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

    work page 2010

  18. [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

    work page 2010

  19. [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

    work page doi:10.1007/s00453-022-01006-x 2023

  20. [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

    work page doi:10.1007/s00453-011-9554-x 2012

  21. [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

    work page doi:10.2168/lmcs-10(1:18)2014 2014

  22. [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

    work page doi:10.1287/moor.8.4.538 1983

  23. [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

    work page doi:10.1109/12.24280 1989

  24. [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

    work page doi:10.1016/j.dam.2019.06.001 2020

  25. [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/FOCS57990.2023.00060

    work page doi:10.1109/focs57990.2023.00060 2023

  26. [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

    work page doi:10.1145/1877714.1877718 2011

  27. [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

    work page 1994