ECCO 2024
Abstract Submission

51. Complexity of the uniqueness problem of a minimum vertex cover in a graph

Invited abstract in session FB-1: Complexity, stream Complexity.

Friday, 10:30 - 12:00
Room: L226

Authors (first author is the speaker)

1. Olivier Hudry
Télécom Paris

Abstract

Given an undirected graph G = (V, E), a vertex cover (VC) of G is a subset C of V such that any edge of G has at least one extremity in C. The optimization problem consisting in determining a minimum VC in G is well-known to be NP-hard; more precisely, its decision problem is NP-complete.
We consider the complexity of the following two decision problems:
Name: Uniqueness of VC with bounded size (U-VCBS)
Instance: a graph G; an integer K
Question: Is there a unique VC in G of size less than or equal to K?
and
Name: Uniqueness of the minimum VC (U-MVC)
Instance: a graph G
Question: Is there a unique minimum VC in G?
To study the complexity of U-VCBS and U-MVC, we consider two other uniqueness problems:
Name: Uniqueness for satisfiability problem (U-SAT)
Instance: a set B of Boolean variables, a set of logical clauses defined on B (i.e. containing variables of B or complementary variables of B)
Question: is there a unique assignment function f defined on B such that each clause contains at least one element set to true by f?
and the variant of U-SAT, noted U-1-in-3-SAT, in which each clause contains exactly three elements.
The problems U-VCBS, U-MVC, U-SAT and U-1-in-3-SAT are not known to be in NP or in co-NP but U-SAT and U-1-in-3-SAT have the same complexity, in the sense that one transforms into the other according to polynomial transformations. These two problems are NP-hard and belong to the complexity class noted DP (or also BH2 in the Boolean hierarchy) which contains the decision problems that can be stated, in terms of languages, as the intersection of a language belonging to NP (corresponding here to the question "is there at least one assignment function…") and a language belonging to co-NP (corresponding here to the question "is there at most one assignment function…").
If < denotes the polynomial transformation, we establish the following relationships:
- U-1-in-3-SAT < U-VCBS
- U-VCBS < U-SAT
- U-1-in-3-SAT < U-MVC.
We deduce from this that U-VCBS, U-SAT and U-1-in-3-SAT have the same complexity. As a consequence, U-VCBS is NP-hard and belongs to DP. For U-MVC, this involves that U-MVC is at least as difficult as U-SAT (in particular, U-MVC is NP-hard). Moreover, we show that U-MVC belongs to the class of decision problems that can be solved using an algorithm solving a NP-complete problem called a logarithmic number of times, thus providing an upper bound of the complexity of U-MVC.

Keywords

Status: accepted

Back to the list of papers