On the Computational Complexity of Defining Sets

Details On the Computational Complexity of Defining Sets On the Computational Complexity of Defining Sets

2006-12-31

arxiv.org/abs/cs/0701008v1

Journal of Discrete Applied Mathematics .149(1-3) (2005) pp. 101-110

Computer Science

Computational Complexity

Scientific paper

Suppose we have a family ${\cal F}$ of sets. For every $S \in {\cal F}$, a set $D \subseteq S$ is a {\sf defining set} for $({\cal F},S)$ if $S$ is the only element of $\cal{F}$ 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 $\Sigma_2$-complete. We also show that the computational complexity of the following problem about the defining set of vertex colorings of graphs is $\Sigma_2$-complete: {\sc Instance:} A graph $G$ with a vertex coloring $c$ and an integer $k$. {\sc Question:} If ${\cal C}(G)$ be the set of all $\chi(G)$-colorings of $G$, then does $({\cal C}(G),c)$ have a defining set of size at most $k$? Moreover, we study the computational complexity of some other variants of this problem.

Affiliated with

Also associated with

No associations

Rating

On the Computational Complexity of Defining Sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Computational Complexity of Defining Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Computational Complexity of Defining Sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-293940