The complexity of recognizing minimally tough graphs

DOI10.1016/J.DAM.2021.01.022MaRDI QIDQ2656956zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 17 March 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/1705.10570

zbMATH Keywords

DP-complete graphminimally toughweighted toughness

Mathematics Subject Classification ID

Connectivity (05C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: A graph is called $t$-tough if the removal of any vertex set $S$ that disconnects the graph leaves at most $|S|/t$ components. The toughness of a graph is the largest $t$ for which the graph is $t$-tough. A graph is minimally $t$-tough if the toughness of the graph is $t$ and the deletion of any edge from the graph decreases the toughness. The complexity class DP is the set of all languages that can be expressed as the intersection of a language in NP and a language in coNP. In this paper, we prove that recognizing minimally $t$-tough graphs is DP-complete for any positive rational number $t$. We introduce a new notion called weighted toughness, which has a key role in our proof.

Recommendations

• On the complexity of recognizing tough graphs
• Properties of minimally \(t\)-tough graphs
• Recognizing tough graphs is NP-hard
• The complexity of recognizing tough cubic graphs
• scientific article; zbMATH DE number 6770058

Cites work

• Eine Eigenschaft der Atome endlicher Graphen
• Hamiltonian results inK1,3-free graphs
• scientific article; zbMATH DE number 5174567 (Why is no real title available?)
• Matching theory
• On toughness and Hamiltonicity of \(2K_{2}\)-free graphs
• Properties of minimally \(t\)-tough graphs
• Recognizing tough graphs is NP-hard
• The complexity of facets (and some facets of complexity)
• The complexity of facets resolved
• The toughness of split graphs
• Tough graphs and Hamiltonian circuits.
• Toughness, hamiltonicity and split graphs

Cited in

(10)

• On the complexity of recognizing tough graphs
• The complexity of recognizing tough cubic graphs
• A note on the approximability of the toughness of graphs
• Properties of minimally \(t\)-tough graphs
• scientific article; zbMATH DE number 6770058 (Why is no real title available?)
• The complexity of learning minor closed graph classes
• The fully weighted toughness of a graph
• Minimal toughness in special graph classes
• On minimally t-tough graphs with t 1
• Recognizing tough graphs is NP-hard

This page was built for publication: The complexity of recognizing minimally tough graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2656956)