Covering graphs with convex sets and partitioning graphs into convex sets

Luc\'ia M. Gonz\'alez; Luciano N. Grippo; Mart\'in D. Safe; Vin\'icius F. dos Santos

arxiv: 1907.01581 · v1 · pith:5QLNWQTBnew · submitted 2019-07-02 · 🧮 math.CO · cs.DM

Covering graphs with convex sets and partitioning graphs into convex sets

Luc\'ia M. Gonz\'alez , Luciano N. Grippo , Mart\'in D. Safe , Vin\'icius F. dos Santos This is my paper

Pith reviewed 2026-05-25 10:33 UTC · model grok-4.3

classification 🧮 math.CO cs.DM

keywords graph convexityconvex set coverconvex partitioncomputational complexityNP-completenessdigital convexitymonophonic convexityP3-convexity

0 comments

The pith

Covering or partitioning a graph into p convex sets is NP-complete under digital, monophonic, P3 and P3* convexities.

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

This paper examines the computational complexity of covering the vertices of a graph with exactly p convex sets and of partitioning the vertices into exactly p convex sets. Four notions of convexity are treated: digital convexity, monophonic convexity, P3-convexity, and P3*-convexity. The work supplies reductions and algorithms that locate these problems in the complexity hierarchy for each convexity. A reader cares because the results separate the cases in which the problems remain tractable from those in which they become intractable as p grows.

Core claim

The problems of covering a graph with p convex sets and of partitioning a graph into p convex sets admit complexity classifications that depend on the chosen convexity; the paper derives these classifications for digital convexity, monophonic convexity, P3-convexity, and P3*-convexity.

What carries the argument

Reductions that map instances of known NP-complete problems onto instances of convex cover and convex partition while preserving the closure properties that define each of the four convexities.

If this is right

For each of the four convexities the cover and partition problems belong to NP.
When the reductions succeed, the problems are NP-hard for sufficiently large fixed p.
Polynomial-time solvability holds only for the special cases the paper identifies as tractable.
The same graph may require different numbers of convex sets depending on which convexity is used.

Where Pith is reading between the lines

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

Similar hardness may appear for other closure-based convexities not studied here.
Fixed-parameter tractability results with respect to p could still exist even when the problems are NP-complete.
The results supply a template for classifying convexity variants that arise in discrete geometry or network analysis.

Load-bearing premise

The standard definitions and closure properties of the four convexities are correctly invoked when constructing the reductions or algorithms that establish the complexity claims.

What would settle it

A polynomial-time algorithm for partitioning an arbitrary graph into three P3-convex sets would falsify the corresponding NP-completeness claim, provided the reduction used in the paper is valid.

read the original abstract

We present some complexity results concerning the problems of covering a graph with $p$ convex sets and of partitioning a graph into $p$ convex sets. The following convexities are considered: digital convexity, monophonic convexity, $P_3$-convexity, and $P_3^*$-convexity.

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.

Desk Editor's Note private letter to a colleague

The paper gives complexity classifications for covering and partitioning graphs into p convex sets under digital, monophonic, P3 and P3* convexities.

read the letter

The one or two things to know are that the authors present complexity results for covering a graph with p convex sets and for partitioning a graph into p convex sets, and they do this for digital convexity, monophonic convexity, P3-convexity, and P3*-convexity. The paper does well in bringing these four convexities under one study. This allows for a side-by-side view of how the complexity changes with the choice of convexity. That is a practical contribution for anyone who might use these concepts in algorithm design. The soft spots are limited. Since only the abstract is visible in the initial review, the actual arguments are not available for inspection. This means we cannot confirm the validity of any reductions or algorithms they use. However, the problem statement itself does not show any circularity or invented entities, and the stress-test did not identify any load-bearing flaws in the setup. The paper is for researchers who work on convexity in graphs and who care about the computational side of covering and partitioning problems. A reader who already knows the definitions of these convexities will get the most value, as the paper supplies the complexity classifications for different values of p. It deserves a serious referee. The results, if correct, would be useful within the subfield. I recommend that an editor send this to peer review.

Referee Report

0 major / 1 minor

Summary. The manuscript presents complexity results for the problems of covering a graph with p convex sets and of partitioning a graph into p convex sets, considering the convexities digital convexity, monophonic convexity, P3-convexity, and P3*-convexity.

Significance. If the claimed complexity classifications are supported by correct reductions or algorithms that properly invoke the closure properties of each convexity, the results would provide a useful classification of these graph problems under standard complexity assumptions. The work follows the standard template of complexity classification papers in structural graph theory.

minor comments (1)

The abstract states the problems and convexities considered but provides no indication of the specific complexity outcomes (e.g., which cases are polynomial-time solvable versus NP-complete). A clearer statement of the main theorems would help readers assess the contribution immediately.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for reviewing our manuscript on the complexity of p-convex-set cover and partition problems under digital, monophonic, P3, and P3* convexities. The recommendation is listed as uncertain with no specific major comments provided in the report. We are happy to address any points if they can be clarified.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper presents direct complexity results (NP-completeness or polynomial-time solvability) for covering and partitioning problems under four standard graph convexities via reductions and algorithms that invoke the convexity definitions and closure properties. No derivation chain reduces a claimed result to a fitted parameter, self-definition, or load-bearing self-citation; the work is a standard classification paper whose technical steps rest on external graph-theoretic facts and explicit constructions rather than internal re-labeling of inputs as outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard graph-theoretic definitions of convexity; no free parameters or invented entities are introduced in the abstract.

axioms (1)

domain assumption The four listed notions of convexity (digital, monophonic, P3, P3*) are well-defined and satisfy the usual closure properties used in complexity reductions.
All complexity claims rest on these established definitions being applied correctly.

pith-pipeline@v0.9.0 · 5583 in / 1149 out tokens · 27306 ms · 2026-05-25T10:33:56.079704+00:00 · methodology

Covering graphs with convex sets and partitioning graphs into convex sets

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)