pith. sign in

arxiv: 2604.20097 · v1 · submitted 2026-04-22 · 🧮 math.CO

Carath\'eodory Number in Cycle Convexity

Revathy S. Nair , Bijo S. Anand , Ullas Chandran S. V. , Julliano R. Nascimento This is my paper

Pith reviewed 2026-05-10 00:39 UTC · model grok-4.3

classification 🧮 math.CO
keywords Carathéodory numbercycle convexitycycle convex hullNP-completenessbipartite graphsgraph productsconvexity in graphs
0
0 comments X

The pith

Deciding if the Carathéodory number meets or exceeds k is NP-complete even when the graph is bipartite.

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

The paper establishes that determining the Carathéodory number of a graph under cycle convexity is computationally hard in general. The decision problem of whether this number is at least a given k remains NP-complete when the input graph is restricted to be bipartite. For several structured families, including forests, cycles, complete graphs, complete multipartite graphs, split graphs, and P4-sparse graphs, exact values or constant upper bounds are derived that immediately yield polynomial-time algorithms. The authors also characterize all n-vertex graphs achieving the near-extremal values car(G) = n-1 and car(G) = n-2, and they determine how the number transforms under the strong, lexicographic, and Cartesian products.

Core claim

In cycle convexity, a set S is cycle-convex if the induced subgraph on S union any external vertex u contains no cycle through u. The cycle convex hull of S is the smallest cycle-convex set containing S. A set S is Carathéodory independent when some vertex lies in the hull of S yet lies outside the hull of S without any one of its elements. The Carathéodory number car(G) is the maximum size of such an independent set. The central result proves that deciding whether car(G) is at least k is NP-complete, and the same hardness holds even when G is bipartite. Exact values and constant bounds are obtained for multiple graph classes, together with a structural characterization of graphs attaining n

What carries the argument

The cycle convex hull of S, the smallest cycle-convex set containing S, used to define when S is Carathéodory independent.

If this is right

  • No polynomial-time algorithm exists for deciding car(G) >= k on bipartite graphs unless P equals NP.
  • Polynomial-time algorithms exist for computing car(G) exactly on forests, cycles, complete graphs, complete multipartite graphs, split graphs, and P4-sparse graphs.
  • All n-vertex graphs satisfying car(G) = n-1 or car(G) = n-2 admit a simple structural characterization.
  • The value of car(G) can be computed or bounded in closed form for any graph obtained via strong, lexicographic, or Cartesian product from graphs whose numbers are already known.

Where Pith is reading between the lines

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

  • The same decision problem may remain NP-complete for other convexity notions that also admit polynomial-time hull computation.
  • The exact formulas derived for basic classes such as forests and cycles could serve as base cases for dynamic-programming algorithms on graphs of bounded treewidth.
  • The product results suggest that car(G) might be computable in polynomial time on graphs whose prime factors under the studied products are restricted to the classes already solved.

Load-bearing premise

The NP-completeness reduction assumes that the cycle convex hull of any set in the constructed bipartite instances can be computed in polynomial time.

What would settle it

A concrete bipartite graph produced by the reduction together with an explicit superpolynomial-time lower bound on computing its cycle convex hulls would show that the reduction does not establish NP-completeness.

Figures

Figures reproduced from arXiv: 2604.20097 by Bijo S. Anand, Julliano R. Nascimento, Revathy S. Nair, Ullas Chandran S. V..

Figure 1
Figure 1. Figure 1: Subgraphs for the construction presented in Theorem 3. [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Sketch of the graph G constructed for Theorem 3 from an instance of One-In-Three 3-SAT ϕ where the literal p ∈ C2 and p ∈ Cm. The double edges represents all the possible edges between the vertices of the two rectangles. we get that c0 ∈ Hullcc(S) and S ′ = {c0, c1, . . . , cm} ∪ {d1, d2, . . . , dm−1} ∪ {ℓ 0 , ℓ5 , ℓ7 , ℓ8 : ℓ ∈ Ci has an opposite literal in ϕ} ∪ S ⊆ Hullcc(S). By construction, no vertex … view at source ↗
read the original abstract

Let $G$ be a graph and $S \subseteq V(G)$. In the cycle convexity, we say that $S$ is \textit{cycle convex} if for any $u\in V(G)\setminus S$, the induced subgraph of $S\cup\{u\}$ contains no cycle that includes $u$. The \textit{cycle convex hull} of $S$, denoted by $\hullc (S)$, is the smallest cycle convex set containing $S$. A set $S \subseteq V(G)$ is said to be \textit{Carath\'eodory independent} if there exists a vertex $u \in \hullc(S) $ such that $u \notin\displaystyle \bigcup_{a \in S} \hullc (S \setminus \{a\}) $, and the Carath\'eodory number $\car(G)$ is the maximum size of such a set. In this paper, we prove that given a graph $G$ and $k \in \mathbb{N}$, deciding whether $\car(G) \geq k$ is \NP-complete, even when $G$ is bipartite. On the other hand, we derive exact values and constant upper bounds for several graph classes, leading to polynomial-time algorithms. Some of them include forests, cycles, complete graphs, complete multipartite, split, and $P_4$-sparse graphs. In addition, we present a characterization of $n$-vertex graphs $G$ with extremal values near to $n$, including $\car(G) = n-1$ and $\car(G) = n-2$. Furthermore, we investigate the behavior of the Carath\'eodory number under graph products such as the strong, lexicographic, and Cartesian products.

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

Summary. The paper defines cycle-convex sets and the cycle-convex hull in graphs, introduces Carathéodory-independent sets, and defines the Carathéodory number car(G) as the maximum size of such a set. It proves that deciding whether car(G) ≥ k is NP-complete, even restricted to bipartite graphs. It derives exact values or constant upper bounds (yielding polynomial-time algorithms) for forests, cycles, complete graphs, complete multipartite graphs, split graphs, and P4-sparse graphs; characterizes n-vertex graphs with car(G) = n-1 or car(G) = n-2; and determines the behavior of car under strong, lexicographic, and Cartesian products.

Significance. The NP-completeness result for bipartite graphs is a solid contribution to the complexity of convexity parameters. The explicit exact values and bounds for standard hereditary classes, together with the polynomial-time hull algorithm (iterative addition of vertices whose neighbors in the current set lie in one component), directly yield tractable cases. The near-extremal characterizations and product formulas provide structural insight. The work is internally consistent and builds on standard graph-convexity tools without circularity.

minor comments (3)
  1. §3 (NP-completeness): the reduction is stated to preserve bipartiteness, but the manuscript should explicitly verify that the auxiliary vertices introduced do not create odd cycles or alter the hull-computation complexity in the target instances.
  2. Table 1 (summary of bounds): the entry for P4-sparse graphs lists an upper bound of 4; confirm whether this is tight by exhibiting a P4-sparse graph attaining car(G)=4.
  3. §5 (products): the formulas for the strong and lexicographic products are given in terms of the factors' car numbers; add a short remark on whether the same formulas hold when one factor is a single vertex.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work and the recommendation of minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's core results consist of an NP-completeness reduction for deciding whether car(G) >= k (even on bipartite graphs) together with explicit exact values, constant upper bounds, and polynomial-time algorithms for concrete classes (forests, cycles, complete graphs, split graphs, etc.). The cycle-convex hull is defined directly from the standard iterative closure process and is shown to be computable in polynomial time by a direct argument that does not invoke any fitted parameter, self-citation chain, or quantity defined only in terms of the Carathéodory number itself. No derivation step equates a claimed prediction or theorem to its own inputs by construction, and the NP-membership argument rests on an independently verifiable polynomial-time procedure rather than an unverified assumption. The characterizations of graphs with car(G) near n are likewise obtained by direct combinatorial arguments on the hull operator.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The paper rests on the standard definition of induced subgraphs and cycles together with the newly introduced notion of cycle convexity. No numerical parameters are fitted; the only invented entity is the cycle-convex hull operator itself.

axioms (1)
  • standard math The induced subgraph on any vertex set is well-defined and the notion of cycle is the standard graph-theoretic one.
    Invoked in the definition of cycle convexity and hull.
invented entities (1)
  • Cycle-convex set and cycle-convex hull no independent evidence
    purpose: To equip the vertex set with a convexity operator based on absence of cycles through the added vertex.
    New definition introduced in the paper; no independent evidence outside the definition is supplied.

pith-pipeline@v0.9.0 · 5638 in / 1429 out tokens · 21895 ms · 2026-05-10T00:39:22.730288+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]

    Bijo S Anand, Arun Anil, Manoj Changat, Mitre C Dourado, and Sabeer S Ramla,Com- puting the hull number in∆-convexity, Theoretical Computer Science844(2020), 217–226

    work page 2020

  2. [2]

    Bijo S Anand, Arun Anil, Manoj Changat, Prasanth G Narasimha-Shenoi, and Sabeer S Ramla,Carathéodory number and exchange number in∆-convexity, J. Combin. Math. Combin. Comput126(2025), no. 11, 27. 17

    work page 2025

  3. [3]

    Bijo S Anand, Mitre C Dourado, Prasanth G Narasimha-Shenoi, and Sabeer S Ramla, On the∆-interval and the∆-convexity numbers of graphs and graph products, Discrete Applied Mathematics319(2022), 487–498

    work page 2022

  4. [4]

    Bijo S Anand, Prasanth G Narasimha-Shenoi, and Sabeer Sain Ramla,∆-Convexity Num- ber and∆-Number of Graphs and Graph Products, Conference on Algorithms and Discrete Applied Mathematics, Springer, 2020, pp. 209–218

    work page 2020

  5. [5]

    Bijo S Anand, Ullas Chandran SV, Julliano R Nascimento, and Revathy S Nair,Complex- ity and structural results for the hull and convexity numbers in cycle convexity for graph products, Discrete Applied Mathematics377(2025), 552–561

    work page 2025

  6. [6]

    report, Inria & Université Cote d’Azur, CNRS, I3S, Sophia Antipolis, France, 2025

    Júlio Aráujo, Samuel N Aráujo, Pedro P Medeiros, Nicolas Nisse, and Caroline Silva, On the rank and the general position number in cycle convexity, Tech. report, Inria & Université Cote d’Azur, CNRS, I3S, Sophia Antipolis, France, 2025

    work page 2025

  7. [7]

    Júlio Araújo, Victor Campos, Darlan Girão, João Nogueira, António Salgueiro, and Ana Silva,Cycle convexity and the tunnel number of links, arXiv preprint arXiv:2012.05656 (2020), 1–28

    work page arXiv 2012

  8. [8]

    Julio Araujo, Victor Campos, Darlan Girão, João Nogueira, António Salgueiro, and Ana Silva,On the hull number on cycle convexity of graphs, Information Processing Letters183 (2024), 106420

    work page 2024

  9. [9]

    Júlio Araújo, Mitre C Dourado, Fábio Protti, and Rudini M Sampaio,Introduction to graph convexity: An algorithmic approach, Springer Nature, 2025

    work page 2025

  10. [10]

    Graph Theory

    Julio Araujo, Guillaume Ducoffe, Nicolas Nisse, and Karol Suchan,On interval num- ber in cycle convexity, Discrete Mathematics & Theoretical Computer Science20(2018), no. Graph Theory

    work page 2018

  11. [11]

    3, 929–939

    Rommel M Barbosa, Erika MM Coelho, Mitre C Dourado, Dieter Rautenbach, and Jayme L Szwarcfiter,On the carathéodory number for the convexity of paths of order three, SIAM Journal on Discrete Mathematics26(2012), no. 3, 929–939

    work page 2012

  12. [12]

    J Cáceres, C Hernando, M Mora, M Puertas, and C Seara,On monophonic sets in graphs, 20th British Combinatorial Conference, Durham-England, 2005

    work page 2005

  13. [13]

    3, 726–736

    José Cáceres, Alberto Márquez, and María Luz Puertas,Steiner distance and convexity in graphs, European Journal of Combinatorics29(2008), no. 3, 726–736

    work page 2008

  14. [14]

    Victor Campos, Rudini M Sampaio, Ana Silva, and Jayme L Szwarcfiter,Graphs with few P4’s under the convexity of paths of order three, Discrete Applied Mathematics192(2015), 28–39

    work page 2015

  15. [15]

    29, 3693–3700

    Carmen C Centeno, Mitre C Dourado, Lucia Draque Penso, Dieter Rautenbach, and Jayme L Szwarcfiter,Irreversible conversion of graphs, Theoretical Computer Science412 (2011), no. 29, 3693–3700

    work page 2011

  16. [16]

    Erika M. M. Coelho, Hebert Coelho, Julliano R. Nascimento, and Jayme L. Szwarcfiter, On theP 3-hull number of some products of graphs, Discrete Applied Mathematics253 (2019), 2–13

    work page 2019

  17. [17]

    Erika MM Coelho, Mitre C Dourado, Dieter Rautenbach, and Jayme L Szwarcfiter,The Carathéodory number of theP3 convexity of chordal graphs, Discrete Applied Mathematics 172(2014), 104–108. 18

    work page 2014

  18. [18]

    12, 1268–1274

    Mitre C Dourado, Fábio Protti, and Jayme L Szwarcfiter,Complexity results related to monophonic convexity, Discrete Applied Mathematics158(2010), no. 12, 1268–1274

    work page 2010

  19. [19]

    Mitre C Dourado, Dieter Rautenbach, Vinícius Fernandes Dos Santos, Philipp M Schäfer, and Jayme L Szwarcfiter,On the carathéodory number of interval and graph convexities, Theoretical Computer Science510(2013), 127–135

    work page 2013

  20. [20]

    7, 1615–1627

    Paul A Dreyer Jr and Fred S Roberts,Irreversiblek-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion, Discrete Applied Mathematics 157(2009), no. 7, 1615–1627

    work page 2009

  21. [21]

    Pierre Duchet,Convexity in combinatorial structures, Proceedings of the 14th Winter School on Abstract Analysis, Circolo Matematico di Palermo, 1987, pp. 261–293

    work page 1987

  22. [22]

    Minimal path convexity, Journal of Combinatorial The- ory, Series B44(1988), no

    ,Convex sets in graphs, II. Minimal path convexity, Journal of Combinatorial The- ory, Series B44(1988), no. 3, 307–316

    work page 1988

  23. [23]

    3, 217–223

    Martin G Everett and Stephen B Seidman,The hull number of a graph, Discrete Mathe- matics57(1985), no. 3, 217–223

    work page 1985

  24. [24]

    F Harary F Buckley,Distances in graphs, Eddison Wesley, Redwood City CA, 1990

    work page 1990

  25. [25]

    3, 433–444

    Martin Farber and Robert E Jamison,Convexity in graphs and hypergraphs, SIAM Journal on Algebraic Discrete Methods7(1986), no. 3, 433–444

    work page 1986

  26. [26]

    174, Freeman San Francisco, 1979

    Michael R Garey and David S Johnson,Computers and intractability, vol. 174, Freeman San Francisco, 1979

    work page 1979

  27. [27]

    Guilherme CM Gomes, Laila MV Lopes, and Vinicius F dos Santos,Some complexity results on cycle-convex partitions, Procedia Computer Science273(2025), 365–372

    work page 2025

  28. [28]

    C. T. Hoàng,Perfect graphs, Ph.D. thesis, School of Computer Science, McGill University, Montreal, 1985

    work page 1985

  29. [29]

    2, 381–406

    Beverly Jamison and Stephan Olariu,RecognizingP4-sparse graphs in linear time, SIAM Journal on Computing21(1992), no. 2, 381–406

    work page 1992

  30. [30]

    Carlos V G C Lima, Thiago Marcilon, and Pedro P Medeiros,The complexity of convex- ity number and percolation time in the cycle convexity, arXiv preprint arXiv:2404.09236 (2024), 1–24

    work page arXiv 2024

  31. [31]

    van De Vel,Theory of convex structures, Elsevier, 1993

    Marcel L.J. van De Vel,Theory of convex structures, Elsevier, 1993. 19

    work page 1993