pith. sign in

arxiv: 2511.11546 · v4 · submitted 2025-11-14 · 💻 cs.CC

Parameterized complexity of the f-Critical Set problem

Thiago Marcilon , Murillo In\'acio da Costa Silva This is my paper

Pith reviewed 2026-05-17 21:56 UTC · model grok-4.3

classification 💻 cs.CC
keywords f-critical setreversible processparameterized complexityNP-completenesstreewidthfixed-parameter tractabilitykernelizationbipartite graphs
0
0 comments X

The pith

The f-Critical Set problem is NP-complete for planar subcubic bipartite graphs with maximum threshold 2.

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

The paper studies the complexity of deciding whether a graph has an f-critical set of size at most k under a synchronous reversible labeling rule. In this rule a vertex flips its label precisely when at least f(v) neighbors carry the opposite label, and an f-critical set is an initial set of 1-labeled vertices that drives every vertex to label 1 after exactly one step and then stays fixed. Establishing NP-completeness already on planar subcubic bipartite graphs shows that the decision task remains intractable even when the input is highly restricted. The same work identifies parameter combinations that restore tractability and yield polynomial kernels.

Core claim

The f-Critical Set problem is NP-complete on planar subcubic bipartite graphs when the maximum value m(f) equals 2. The problem is W[1]-hard when parameterized by treewidth alone. It is fixed-parameter tractable when parameterized by treewidth plus m(f), treewidth plus maximum degree, or by the solution size k, and it admits polynomial kernels of size O(k · m(f)) and O(k · Δ(G)).

What carries the argument

The f-critical set: an initial subset of vertices labeled 1 that forces every vertex to label 1 after one synchronous step of the f-reversible process and remains stable thereafter.

If this is right

  • The problem remains NP-hard on planar graphs of maximum degree 3 that are bipartite.
  • Treewidth alone does not suffice for an FPT algorithm.
  • Adding either the maximum threshold m(f) or the maximum degree Δ(G) to the treewidth parameter yields fixed-parameter tractability.
  • The instance can be reduced in polynomial time to one whose size is bounded by O(k · m(f)) or O(k · Δ(G)).

Where Pith is reading between the lines

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

  • For networks whose degrees or thresholds are bounded, the existence of small critical sets can be decided by first reducing the graph and then solving the reduced instance.
  • The same parameterization approach may transfer to other one-step majority or threshold dynamics on graphs.
  • Kernelization results indicate that exhaustive search over a linear number of candidate sets becomes practical once k and the threshold or degree are small.

Load-bearing premise

The reductions that establish NP-completeness and W[1]-hardness preserve the exact critical-set size and the one-step activation property for the chosen graph families and threshold bounds.

What would settle it

A planar subcubic bipartite graph with m(f) = 2 together with an integer k for which the minimum f-critical set size can be computed in polynomial time would falsify the NP-completeness claim if the reduction mapping fails to preserve the property.

Figures

Figures reproduced from arXiv: 2511.11546 by Murillo In\'acio da Costa Silva, Thiago Marcilon.

Figure 1
Figure 1. Figure 1: G′ is the graph resulting from the construction applied to the graph G. v1 v2 v ′ 2 v3 v4 v ′ 4 v5 v ′ 5 v [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The vertices in v1 and v3 are positioned in the circumference of v precisely where the incident edges touch v, assuming dG(v) = 2 and ∆(G) = 3. The other vertices are positioned between or after them. In black, we have the subgraph G′ [Pv ∪ Qv]. Claim 2. G has a vertex cover of size at most k if and only if G′ has an f-critical set of size at most k ′ = |F| + |Q| + k · (2∆(G) − 1). Proof of Claim. Assume t… view at source ↗
Figure 3
Figure 3. Figure 3: The overall structure of G′ resulting from the construction applied to the path P = v1, v2, v3 and k = 3, with Z ∪ W omitted. Unlike gray edges, a black edge between an individual vertex x (white colored nodes) and a set of vertices Q (gray colored nodes) does not necessarily represent an edge between x and every vertex in Q. y 1,2 Y 1,2 3,2 Y 1,2 2,3 Y 1,2 2,1 Y 1,2 1,2 u 1 a 1,2 b 1,2 U 1 1 U 1 2 U 1 3 u… view at source ↗
Figure 4
Figure 4. Figure 4: Part of [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Gadget added to G′ m(f) − f(v) times for each v ∈ V such that f(v) < m(f). Let Q be the set of vertices with degree 1 in G′ . Note that no vertex in Q is originally in G. Let S be an m(f)-critical set of G′ of size k ′ = k + |Q|. It follows that Q ⊆ S for any v ∈ V , since each vertex in Q has degree 1 and m(f) ≥ 2. Furthermore, for any v ∈ V and w ∈ Wv, w has at most k neighbors in S \Q, since |S| = k +|Q… view at source ↗
Figure 6
Figure 6. Figure 6: Let A′ = {q}, B′ = {r, s}, C′ = {t}, and S = {u, v, w} ∈ D(R). Then S ∈ ZR(3, h), where h(q) = 1, h(r) = 2, h(s) = 3 and h(t) = 0. algorithm searches for a combination of k such classes whose cumulative contribution Pk i=1 hi(v) is sufficient to satisfy the threshold inequalities for both Properties 2 and 3 simultaneously. The non-adjacency of the chosen sets ensures that their contributions do not overlap… view at source ↗
read the original abstract

Given a graph $G=(V,E)$, and a function $f:V(G) \rightarrow \mathbb{N}$, an $f$-reversible process on $G$ is a dynamical system such that, given an initial vertex labeling $c_0 : V(G) \rightarrow \{0,1\}$, every vertex $v$ changes its label if and only if it has at least $f(v)$ neighbors with the opposite label. The updates occur synchronously in discrete time steps $t=0,1,2,\ldots$. An $f$-critical set of $G$ is a subset of vertices of $G$ whose initial label is $1$ such that, in an $f$-reversible process on $G$, all vertices reach label $1$ within one time step and then remain unchanged. The critical set number $r^c_f(G)$ is the minimum size of an $f$-critical set of $G$. Given a graph $G$, a threshold function $f$, and an integer $k$, the $f$-Critical Set problem asks whether $r^c_f(G) \leq k$. We prove that this problem is NP-complete for planar subcubic bipartite graphs with maximum threshold $m(f) = 2$ and W[1]-hard when parameterized by the treewidth $tw(G)$ of $G$. Additionally, we show that the problem is FPT when parameterized by $tw(G)+m(f)$, $tw(G)+\Delta(G)$, and $k$, where $\Delta(G)$ denotes the maximum degree of $G$. Finally, we present two kernels of sizes $O(k \cdot m(f))$ and $O(k \cdot \Delta(G))$.

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 / 4 minor

Summary. The paper defines the f-Critical Set problem on a graph G with threshold function f: decide whether there exists a set S of at most k vertices initially labeled 1 such that the synchronous f-reversible process reaches the all-1 labeling in exactly one step and remains stable thereafter. The authors prove that the problem is NP-complete even when restricted to planar subcubic bipartite graphs with m(f)=2, W[1]-hard parameterized by treewidth tw(G), FPT parameterized by tw(G)+m(f), tw(G)+Δ(G), and by k alone, and that it admits kernels of size O(k·m(f)) and O(k·Δ(G)).

Significance. If the claimed reductions and dynamic-programming routines hold, the manuscript supplies a complete complexity map for the f-Critical Set problem, including both strong hardness results on restricted graph classes and practical FPT algorithms together with linear-size kernels. The combination of treewidth-based DP augmented by threshold or degree information and the kernelization rules constitutes a solid algorithmic contribution to the study of reversible processes on graphs.

minor comments (4)
  1. [Abstract] Abstract and §2: the notation m(f) for the maximum value of f is introduced without an explicit sentence stating m(f) := max_v f(v); a one-line definition would remove any ambiguity for readers unfamiliar with the threshold-function literature.
  2. [§4.1] §4.1 (FPT by tw+m(f)): the DP table description lists states for vertex labels and threshold counters but does not explicitly bound the number of states per bag by 2^{O(tw)}·m(f)^{O(tw)}; adding this short calculation would make the runtime claim immediate.
  3. [§5] §5 (kernelization): the safety proof for the O(k·Δ) kernel rule that deletes high-degree vertices relies on a charging argument; a single sentence confirming that the rule never creates a new critical set of size smaller than k would strengthen the presentation.
  4. [Figure 1] Figure 1 and the accompanying caption: the gadget diagram for the NP-completeness reduction is clear, but the caption should state the exact value of f on each vertex type so that the one-step update condition can be verified at a glance.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and for recommending minor revision. The referee's summary correctly captures the key results: NP-completeness on planar subcubic bipartite graphs with m(f)=2, W[1]-hardness parameterized by treewidth, and FPT results with kernels when augmenting the parameter by m(f) or Δ(G).

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's core results consist of explicit NP-completeness and W[1]-hardness reductions from known problems to f-Critical Set on planar subcubic bipartite graphs with m(f)=2, together with standard dynamic-programming algorithms on tree decompositions and safe kernelization rules. These constructions directly encode the one-step synchronous update semantics and critical-set condition via gadgets; no quantity is defined in terms of itself, no fitted parameter is relabeled as a prediction, and no load-bearing premise rests on a self-citation chain. All claims are derived from first-principles reductions and bounded-state DP whose correctness is independent of the target result.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claims rest on standard definitions of graphs, treewidth, and synchronous dynamical systems; no free parameters or invented entities are introduced. The NP-completeness and W[1]-hardness rest on the correctness of (unshown) polynomial reductions.

axioms (1)
  • standard math Standard definitions of planar subcubic bipartite graphs, treewidth, and synchronous label updates under threshold f hold.
    Invoked throughout the problem definition and complexity statements.

pith-pipeline@v0.9.0 · 5613 in / 1452 out tokens · 37618 ms · 2026-05-17T21:56:02.064909+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

31 extracted references · 31 canonical work pages

  1. [1]

    Chen, On the approximability of influence in social networks, SIAM J

    N. Chen, On the approximability of influence in social networks, SIAM J. Discret. Math. 23 (2009) 1400–1415. doi:10.1137/08073617X

    work page doi:10.1137/08073617x 2009

  2. [2]

    French Jr., J. R. P., A formal theory of social power, Psychol. Rev. 63 (1956) 181–194.doi:10.1037/h0046123

    work page doi:10.1037/h0046123 1956

  3. [3]

    Kempe, J

    D. Kempe, J. Kleinberg, E. Tardos, Maximizing the spread of influence through a social network, in: Proc. of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’03, ACM, New York, NY, USA, 2003, pp. 137–146.doi:10.1145/956750.956769

    work page doi:10.1145/956750.956769 2003

  4. [4]

    Poljak, M

    S. Poljak, M. Sůra, On periodical behaviour in societies with symmetric influences, Combinatorica 3 (1) (1983) 119–121.doi:10.1007/BF02579347

    work page doi:10.1007/bf02579347 1983

  5. [5]

    Huang, Gene expression profiling, genetic networks, and cellular states: an integrating concept for tumorigenesis and drug discovery, J

    S. Huang, Gene expression profiling, genetic networks, and cellular states: an integrating concept for tumorigenesis and drug discovery, J. Mol. Med. 77 (6) (1999) 469–480.doi:10.1007/s001099900023

    work page doi:10.1007/s001099900023 1999

  6. [6]

    Agur, Fixed points of majority rule cellular automata with application to plasticity and precision of the immune system, Complex Syst

    Z. Agur, Fixed points of majority rule cellular automata with application to plasticity and precision of the immune system, Complex Syst. 5 (1991) 351–357

    work page 1991

  7. [7]

    Allouche, M

    J.-P. Allouche, M. Courbage, G. Skordev, Notes on cellular automata, Complex Syst. 3 (2001) 213–244

    work page 2001

  8. [8]

    Domingos, M

    P. Domingos, M. Richardson, Random majority percolation, Proc. 7th ACM SIGKDD Int. Conf. Knowl. Discov. Data Min. (2001) 57–67

    work page 2001

  9. [9]

    P. A. . Dreyer Jr., F. S. Roberts, Irreversiblek-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion, Discret. Appl. Math. 157 (7) (2009) 1615–1627.doi:10.1016/j.dam.2008.09.012

    work page doi:10.1016/j.dam.2008.09.012 2009

  10. [10]

    M. H. DeGroot, Reaching a consensus, J. Am. Stat. Assoc. 69 (1974) 167–182.doi:10.1080/01621459.1974. 10480137

    work page doi:10.1080/01621459.1974 1974

  11. [11]

    A. R. Mikler, S. Venkatachalam, K. Abbas, Modeling infectious diseases using global stochastic cellular automata, J. Biol. Syst. 13 (2005) 421–439.doi:10.1142/S0218339005001604

    work page doi:10.1142/s0218339005001604 2005

  12. [12]

    J. Knutson, A survey of the use of cellular automata and cellular automata-like models for simulating a population of biological cells, Graduate theses and dissertations, Iowa State University, USA (2011)

    work page 2011

  13. [13]

    Goles, J

    E. Goles, J. Olivos, Comportement périodique des fonctions á seuil binaires et applications, Discrete Appl. Math. 3 (2) (1981) 93–105.doi:10.1016/0166-218X(81)90034-2

    work page doi:10.1016/0166-218x(81)90034-2 1981

  14. [14]

    Montanari, A

    A. Montanari, A. Saberi, Convergence to equilibrium in local interaction games, SIGecom Exch. 8 (1) (2009) 11:1– 11:4.doi:10.1145/1598780.1598791. 14

    work page doi:10.1145/1598780.1598791 2009

  15. [15]

    Morris, Contagion, Rev

    S. Morris, Contagion, Rev. Econ. Stud. 67 (2000) 57–78.doi:10.1111/1467-937X.00121

    work page doi:10.1111/1467-937x.00121 2000

  16. [16]

    Flocchini, F

    P. Flocchini, F. Geurts, N. Santoro, Optimal irreversible dynamos in chordal rings, Discret. Appl. Math. 113 (1) (2001) 23 – 42, selected Papers: 12th Workshop on Graph-Theoretic Concepts in Computer Science.doi:10.1016/ S0166-218X(00)00388-7

    work page 2001

  17. [17]

    Replacing suffix tr ees with enhanced suffix arrays

    P. Flocchini, R. Královič, P. Ružička, A. Roncato, N. Santoro, On time versus size for monotone dynamic monopolies in regular topologies, J. Discret. Algorithms 1 (2) (2003) 129 – 150, SIROCCO, 2000.doi:10.1016/S1570-8667(03) 00022-4

    work page doi:10.1016/s1570-8667(03 2003

  18. [18]

    Peleg, Local majorities, coalitions and monopolies in graphs: a review, Theor

    D. Peleg, Local majorities, coalitions and monopolies in graphs: a review, Theor. Comput. Sci. 282 (2) (2002) 231–257, FUN with Algorithms.doi:10.1016/S0304-3975(01)00055-X

    work page doi:10.1016/s0304-3975(01)00055-x 2002

  19. [19]

    N. H. Mustafa, A. Pekeč, Listen to your neighbors: How (not) to reach a consensus, SIAM J. Discret. Math. 17 (4) (2004) 634–660.doi:10.1137/S0895480102408213

    work page doi:10.1137/s0895480102408213 2004

  20. [20]

    M. C. Dourado, L. D. Penso, D. Rautenbach, J. L. Szwarcfiter, Reversible iterative graph processes, Theoretical Computer Science 460 (2012) 16–25

    work page 2012

  21. [21]

    C. V. Lima, L. I. Oliveira, V. C. Barbosa, M. C. Dourado, F. Protti, J. L. Szwarcfiter, A computational study of f-reversible processes on graphs, Discrete Applied Mathematics 245 (2018) 77–93

    work page 2018

  22. [22]

    Masset, R

    I. Costa, C. V. Lima, T. Marcilon, The conversion set problem on graphs, Procedia Computer Science 223 (2023) 175–183, XII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 2023).doi:10.1016/j. procs.2023.08.227

    work page doi:10.1016/j 2023

  23. [23]

    L. D. Penso, F. Protti, D. Rautenbach, U. dos Santos Souza, Complexity analysis of p3-convexity problems on bounded-degree and planar graphs, Theoretical Computer Science 607 (2015) 83–95, algorithmic Aspects in Infor- mation and Management.doi:https://doi.org/10.1016/j.tcs.2015.10.003

    work page doi:10.1016/j.tcs.2015.10.003 2015

  24. [24]

    J. F. Fink, M. S. Jacobson, n-domination in graphs, in: Graph Theory with Applications to Algorithms and Computer Science, John Wiley & Sons, 1985, Ch. 20, p. 283–300

    work page 1985

  25. [25]

    Araújo, R

    R. Araújo, R. Sampaio, Domination and convexity problems in the target set selection model, Discret. Appl. Math. 330 (2023) 14–23.doi:10.1016/j.dam.2022.12.021

    work page doi:10.1016/j.dam.2022.12.021 2023

  26. [26]

    Fernandes, T

    P. Fernandes, T. Marcilon, M. Silva, Results on f-reversible processes, in: Annals of the LAWCG 2024 – 11th Latin American Workshop on Cliques in Graphs, Aquiraz, 2024, pp. 74–74

    work page 2024

  27. [27]

    M. R. Cappelle, E. M. Coelho, H. Coelho, B. R. Silva, U. S. Souza, F. Protti,p3-convexity on graphs with diameter two: Computing hull and interval numbers, Discret. Appl. Math. 321 (2022) 368–378.doi:10.1016/j.dam.2022. 07.013

    work page doi:10.1016/j.dam.2022 2022

  28. [28]

    Arnborg, J

    S. Arnborg, J. Lagergren, D. Seese, Easy problems for tree-decomposable graphs, Journal of Algorithms 12 (2) (1991) 308–340

    work page 1991

  29. [29]

    Bollobás, The Art of Mathematics – Coffee Time in Memphis, Cambridge University Press, 2006

    B. Bollobás, The Art of Mathematics – Coffee Time in Memphis, Cambridge University Press, 2006

    work page 2006

  30. [30]

    Komusiewicz, F

    C. Komusiewicz, F. Sommer, Enumerating connected induced subgraphs: Improved delay and experimental com- parison, Discrete Applied Mathematics 303 (2021) 262–282

    work page 2021

  31. [31]

    Cygan, F

    M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, S. Saurabh, Parameterized Algorithms, 1st Edition, Springer, 2015. 15

    work page 2015