The complexity of recognizing minimally tough graphs

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 delet...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-11
Main Authors: Katona, Gyula Y, Kovács, István, Varga, Kitti
Format: Article
Language:English
Subjects:
Complexity
Deletion
Graphs
Numbers
Toughness
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422
DOI:10.48550/arxiv.1705.10570