Return to Question

It is well known result proved by Holyer that deciding 3-edge colorability of cubic graphs is $NP$-complete problem.

By Vizing's theorem, all cubic graphs are edge colorable using $\Delta +1$ colors. So, the property of 3-edge colorabilty partitions cubic graphs into two infinite sets. Therefore, the property of 3-edge colorability is an interesting natural property of cubic graphs. Another example is the the $NP$-complete problem of deciding whether a cubic graph $G(V, E)$ has a partitioning of $V$ as $T_1 ∪ T_2$ such that $T_1$ and $T_2$ induce trees of equal size (Deciding whether a cubic graph is Yutsis graph). The preceding two example problems demonstrates what I mean by natural interesting property of cubic graphs.

Another natural interesting property of cubic graphs is the problem of deciding the existence of 2-colorable perfect matching in cubic graphs which was proved to be $NP$-complete by Schaefer using his famous dichotomy theorem of CSP's. The problem is to decide the existence of 2-coloring of the vertices of cubic graph such that every vertex has exactly one neighbor of the same color as itself.

I'm interested in a dichotomy theorem that tells us which natural interesting problems on cubic graphs are polynomial-time decidable and which ones are $NP$-complete.

Is there a P/NP-complete dichotomy theorem for natural interesting properties of cubic graphs?

As it is apparent from the examples, I'm only interested in decision problems where the validity of a solution can be expressed independent of the solution size. I require that the solution has a specific structural property. Bach's post may help in clarifying my motivation. My answer to Bach's post which involves the efficient dominating set problem ( 1-perfect code ) on cubic graphs is a perfect example for natural interesting property of cubic graphs.

Another famous natural interesting property of cubic graphs is being Hamiltonian. Also, it may not be obvious, I'm only interested in natural interesting properties of connected cubic graphs.

EDIT 1-30-2014: To capture the essence of natural property of cubic graphs, I accept a natural $NP$ property $X$ of cubic graphs where there is natural efficient verifier that verifies a natural interesting relation $(x, c)$ where $x$ is an input instance (i.e. connected cubic graph) and $c$ is a short witness of membership of $x$ in $X$. All witnesses are indistinguishable to the verifier. The validity of witnesses must be decided by running the natural verifier. Such natural $NP$ property must partition the class of cubic graphs into two infinite sets.

It is well known result proved by Holyer that deciding 3-edge colorability of cubic graphs is $NP$-complete problem.

By Vizing's theorem, all cubic graphs are edge colorable using $\Delta +1$ colors. So, the property of 3-edge colorabilty partitions cubic graphs into two infinite sets. Therefore, the property of 3-edge colorability is an interesting natural property of cubic graphs. Another example is the the $NP$-complete problem of deciding whether a cubic graph $G(V, E)$ has a partitioning of $V$ as $T_1 ∪ T_2$ such that $T_1$ and $T_2$ induce trees of equal size (Deciding whether a cubic graph is Yutsis graph). The preceding two example problems demonstrates what I mean by natural interesting property of cubic graphs.

Another natural interesting property of cubic graphs is the problem of deciding the existence of 2-colorable perfect matching in cubic graphs which was proved to be $NP$-complete by Schaefer using his famous dichotomy theorem of CSP's. The problem is to decide the existence of 2-coloring of the vertices of cubic graph such that every vertex has exactly one neighbor of the same color as itself.

I'm interested in a dichotomy theorem that tells us which natural interesting problems on cubic graphs are polynomial-time decidable and which ones are $NP$-complete.

Is there a P/NP-complete dichotomy theorem for natural interesting properties of cubic graphs?

As it is apparent from the examples, I'm only interested in decision problems where the validity of a solution can be expressed independent of the solution size. I require that the solution has a specific structural property. Bach's post may help in clarifying my motivation. My answer to Bach's post which involves the efficient dominating set problem ( 1-perfect code ) on cubic graphs is a perfect example for natural interesting property of cubic graphs.

Another famous natural interesting property of cubic graphs is being Hamiltonian. Also, it may not be obvious, I'm only interested in natural interesting properties of connected cubic graphs.

EDIT 1-30-2014: To capture the essence of natural property of cubic graphs, I accept a natural $NP$ property $X$ of cubic graphs where there is natural efficient verifier that verifies a natural interesting relation $(x, c)$ where $x$ is an input instance (i.e. connected cubic graph) and $c$ is a short witness of membership of $x$ in $X$. All witnesses are indistinguishable to the verifier. The validity of witnesses must be decided by running the natural verifier. Such natural $NP$ property must partition the class of cubic graphs into two infinite sets.

It is well known result proved by Holyer that deciding 3-edge colorability of cubic graphs is $NP$-complete problem.

By Vizing's theorem, all cubic graphs are edge colorable using $\Delta +1$ colors. So, the property of 3-edge colorabilty partitions cubic graphs into two infinite sets. Therefore, the property of 3-edge colorability is an interesting natural property of cubic graphs. Another example is the the $NP$-complete problem of deciding whether a cubic graph $G(V, E)$ has a partitioning of $V$ as $T_1 ∪ T_2$ such that $T_1$ and $T_2$ induce trees of equal size (Deciding whether a cubic graph is Yutsis graph). The preceding two example problems demonstrates what I mean by natural interesting property of cubic graphs.

Another natural interesting property of cubic graphs is the problem of deciding the existence of 2-colorable perfect matching in cubic graphs which was proved to be $NP$-complete by Schaefer using his famous dichotomy theorem of CSP's. The problem is to decide the existence of 2-coloring of the vertices of cubic graph such that every vertex has exactly one neighbor of the same color as itself.

I'm interested in a dichotomy theorem that tells us which natural interesting problems on cubic graphs are polynomial-time decidable and which ones are $NP$-complete.

Is there a P/NP-complete dichotomy theorem for natural interesting properties of cubic graphs?

As it is apparent from the examples, I'm only interested in decision problems where the validity of a solution can be expressed independent of the solution size. I require that the solution has a specific structural property. Bach's post may help in clarifying my motivation. My answer to Bach's post which involves the efficient dominating set problem ( 1-perfect code ) on cubic graphs is a perfect example for natural interesting property of cubic graphs.

Another famous natural interesting property of cubic graphs is being Hamiltonian. Also, it may not be obvious, I'm only interested in natural interesting properties of connected cubic graphs.

EDIT: To capture the essence of natural property of cubic graphs, I accept a natural $NP$ property $X$ of cubic graphs where there is natural efficient verifier that verifies a natural interesting relation $(x, c)$ where $x$ is an input instance (i.e. connected cubic graph) and $c$ is a short witness of membership of $x$ in $X$. All witnesses are indistinguishable to the verifier. The validity of witnesses must be decided by running the natural verifier. Such natural $NP$ property must partition the class of cubic graphs into two infinite sets.

It is well known result proved by Holyer that deciding 3-edge colorability of cubic graphs is $NP$-complete problem.

By Vizing's theorem, all cubic graphs are edge colorable using $\Delta +1$ colors. So, the property of 3-edge colorabilty partitions cubic graphs into two infinite sets. Therefore, the property of 3-edge colorability is an interesting natural property of cubic graphs. Another example is the the $NP$-complete problem of deciding whether a cubic graph $G(V, E)$ has a partitioning of $V$ as $T_1 ∪ T_2$ such that $T_1$ and $T_2$ induce trees of equal size (Deciding whether a cubic graph is Yutsis graph). The preceding two example problems demonstrates what I mean by natural interesting property of cubic graphs.

Another natural interesting property of cubic graphs is the problem of deciding the existence of 2-colorable perfect matching in cubic graphs which was proved to be $NP$-complete by Schaefer using his famous dichotomy theorem of CSP's. The problem is to decide the existence of 2-coloring of the vertices of cubic graph such that every vertex has exactly one neighbor of the same color as itself.

I'm interested in a dichotomy theorem that tells us which natural interesting problems on cubic graphs are polynomial-time decidable and which ones are $NP$-complete.

Is there a P/NP-complete dichotomy theorem for natural interesting properties of cubic graphs?

As it is apparent from the examples, I'm only interested in decision problems where the validity of a solution can be expressed independent of the solution size. I require that the solution has a specific structural property. Bach's post may help in clarifying my motivation. My answer to Bach's post which involves the efficient dominating set problem ( 1-perfect code ) on cubic graphs is a perfect example for natural interesting property of cubic graphs.

Another famous natural interesting property of cubic graphs is being Hamiltonian. Also, it may not be obvious, I'm only interested in natural interesting properties of connected cubic graphs.

EDIT 1-30-2014: To capture the essence of natural property of cubic graphs, I accept a natural $NP$ property $X$ of cubic graphs where there is natural efficient verifier that verifies a natural interesting relation $(x, c)$ where $x$ is an input instance (i.e. connected cubic graph) and $c$ is a short witness of membership of $x$ in $X$. All witnesses are indistinguishable to the verifier. The validity of witnesses must be decided by running the natural verifier. Such natural $NP$ property must partition the class of cubic graphs into two infinite sets.

It is well known result proved by Holyer that deciding 3-edge colorability of cubic graphs is $NP$-complete problem.

By Vizing's theorem, all cubic graphs are edge colorable using $\Delta +1$ colors. So, the property of 3-edge colorabilty partitions cubic graphs into two infinite sets. Therefore, the property of 3-edge colorability is an interesting natural property of cubic graphs. Another example is the the $NP$-complete problem of deciding whether a cubic graph $G(V, E)$ has a partitioning of $V$ as $T_1 ∪ T_2$ such that $T_1$ and $T_2$ induce trees of equal size (Deciding whether a cubic graph is Yutsis graph). The preceding two example problems demonstrates what I mean by natural interesting property of cubic graphs.

Another natural interesting property of cubic graphs is the problem of deciding the existence of 2-colorable perfect matching in cubic graphs which was proved to be $NP$-complete by Schaefer using his famous dichotomy theorem of CSP's. The problem is to decide the existence of 2-coloring of the vertices of cubic graph such that every vertex has exactly one neighbor of the same color as itself.

I'm interested in a dichotomy theorem that tells us which natural interesting problems on cubic graphs are polynomial-time decidable and which ones are $NP$-complete.

Is there a P/NP-complete dichotomy theorem for natural interesting properties of cubic graphs?

As it is apparent from the examples, I'm only interested in decision problems where the validity of a solution can be expressed independent of the solution size. I require that the solution has a specific structural property. Bach's post may help in clarifying my motivation. My answer to Bach's post which involves the efficient dominating set problem ( 1-perfect code ) on cubic graphs is a perfect example for natural interesting property of cubic graphs.

Another famous natural interesting property of cubic graphs is being Hamiltonian. Also, it may not be obvious, I'm only interested in natural interesting properties of connected cubic graphs.

It is well known result proved by Holyer that deciding 3-edge colorability of cubic graphs is $NP$-complete problem.

By Vizing's theorem, all cubic graphs are edge colorable using $\Delta +1$ colors. So, the property of 3-edge colorabilty partitions cubic graphs into two infinite sets. Therefore, the property of 3-edge colorability is an interesting natural property of cubic graphs. Another example is the the $NP$-complete problem of deciding whether a cubic graph $G(V, E)$ has a partitioning of $V$ as $T_1 ∪ T_2$ such that $T_1$ and $T_2$ induce trees of equal size (Deciding whether a cubic graph is Yutsis graph). The preceding two example problems demonstrates what I mean by natural interesting property of cubic graphs.

Another natural interesting property of cubic graphs is the problem of deciding the existence of 2-colorable perfect matching in cubic graphs which was proved to be $NP$-complete by Schaefer using his famous dichotomy theorem of CSP's. The problem is to decide the existence of 2-coloring of the vertices of cubic graph such that every vertex has exactly one neighbor of the same color as itself.

I'm interested in a dichotomy theorem that tells us which natural interesting problems on cubic graphs are polynomial-time decidable and which ones are $NP$-complete.

Is there a P/NP-complete dichotomy theorem for natural interesting properties of cubic graphs?

As it is apparent from the examples, I'm only interested in decision problems where the validity of a solution can be expressed independent of the solution size. I require that the solution has a specific structural property. Bach's post may help in clarifying my motivation. My answer to Bach's post which involves the efficient dominating set problem ( 1-perfect code ) on cubic graphs is a perfect example for natural interesting property of cubic graphs.

Another famous natural interesting property of cubic graphs is being Hamiltonian. Also, it may not be obvious, I'm only interested in natural interesting properties of connected cubic graphs.

EDIT: To capture the essence of natural property of cubic graphs, I accept a natural $NP$ property $X$ of cubic graphs where there is natural efficient verifier that verifies a natural interesting relation $(x, c)$ where $x$ is an input instance (i.e. connected cubic graph) and $c$ is a short witness of membership of $x$ in $X$. All witnesses are indistinguishable to the verifier. The validity of witnesses must be decided by running the natural verifier. Such natural $NP$ property must partition the class of cubic graphs into two infinite sets.