Pith. sign in

REVIEW 1 cited by

On the complexity of Dominating Set for graphs with fixed diameter

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2304.09701 v1 pith:KSZ55VEL submitted 2023-04-19 math.CO cs.DM

classification math.COcs.DM
keywords dominatinggraphsproblemclaw-freecompletecomplexitydiameterfixed
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

A set $S\subseteq V$ of a graph $G=(V,E)$ is a dominating set if each vertex has a neighbor in $S$ or belongs to $S$. Dominating Set is the problem of deciding, given a graph $G$ and an integer $k\geq 1$, if $G$ has a dominating set of size at most $k$. It is well known that this problem is $\mathsf{NP}$-complete even for claw-free graphs. We give a complexity dichotomy for Dominating Set for the class of claw-free graphs with diameter $d$. We show that the problem is $\mathsf{NP}$-complete for every fixed $d\ge 3$ and polynomial time solvable for $d\le 2$. To prove the case $d=2$, we show that Minimum Maximal Matching can be solved in polynomial time for $2K_2$-free graphs.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A Survey on Autonomy-Induced Security Risks in Large Model-Based Agents

    cs.AI 2025-06 conditional novelty 4.0 of 10

    The paper surveys security risks of LLM agents, organizes them into a five-level autonomy taxonomy, and proposes an untested CMDP-based architecture called R2A2.

Pith tools