On the computational complexity of defining sets

DOI10.1016/J.DAM.2005.03.004MaRDI QIDQ2387433zbMATH OpenOpenAlexFDO

Authors Hamed Hatami, Hossein Maserrat

Publication date 2 September 2005

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

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

zbMATH Keywords

ComplexityDefining setsGraph coloringSatisfiability

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Analysis of algorithms and problem complexity (68Q25)

Abstract: Suppose we have a family $calF$ of sets. For every $SincalF$, a set $DsubseteqS$ is a {sf defining set} for $(calF,S)$ if $S$ is the only element of $calF$ that contains $D$ as a subset. This concept has been studied in numerous cases, such as vertex colorings, perfect matchings, dominating sets, block designs, geodetics, orientations, and Latin squares. In this paper, first, we propose the concept of a defining set of a logical formula, and we prove that the computational complexity of such a problem is $Sigm{a}_2$-complete. We also show that the computational complexity of the following problem about the defining set of vertex colorings of graphs is $Sigm{a}_2$-complete: {sc Instance:} A graph $G$ with a vertex coloring $c$ and an integer $k$. {sc Question:} If $calC(G)$ be the set of all $chi(G)$-colorings of $G$, then does $(calC(G),c)$ have a defining set of size at most $k$? Moreover, we study the computational complexity of some other variants of this problem.

Recommendations

• Defining sets in vertex colorings of graphs and latin rectangles
• Defining sets and uniqueness in graph colorings: A survey
• On the defining number of (2n-2)-vertex colorings of K_n K_n
• scientific article; zbMATH DE number 5053295
• Graph coloring applications and defining sets in graph theory

Cites work

• Complete sets and the polynomial-time hierarchy
• Defining sets in vertex colorings of graphs and latin rectangles
• scientific article; zbMATH DE number 3873343 (Why is no real title available?)
• scientific article; zbMATH DE number 1208724 (Why is no real title available?)
• scientific article; zbMATH DE number 1792651 (Why is no real title available?)
• scientific article; zbMATH DE number 841577 (Why is no real title available?)
• scientific article; zbMATH DE number 913534 (Why is no real title available?)
• On the complexity of the circular chromatic number
• On the forced matching numbers of bipartite graphs
• On the minimum number of blocks defining a design
• On the spectrum of the forced matching number of graphs
• STACS 2005
• The forcing geodetic number of a graph
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete

Cited in

(11)

• The complexity types of computable sets
• Some descriptive-set-theoretical problems in complexity theory
• On the complexity of computing with zero-dimensional triangular sets
• The Computational Complexity of Choice Sets
• Critical sets for Sudoku and general graph colorings
• scientific article; zbMATH DE number 1114037 (Why is no real title available?)
• Graph coloring applications and defining sets in graph theory
• On computational complexity of set automata
• Sets computable in polynomial time on average
• The complexity of pre-assignment problem for unique minimum vertex cover on bipartite graphs
• On the algebraic complexity of set equality and inclusion

This page was built for publication: On the computational complexity of defining sets

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