<p>I am interested in a certain type of independent set I call an "odd cover". A set of vertices is independent if no two vertices in the set are connected with an edge. A set of vertices is an "odd cover" if for any graph vertex, v, at least one vertex in the odd cover is an odd distance from v. The distance between two vertices is the minimum number of edges that connects them.</p>

<p>This question is related to the <a href="http://home.comcast.net/~logiclab/EvenSat.html" rel="nofollow noreferrer">Exactly 1 in 3 Satisfiability</a> problem so I am mostly interested in triangular graphs. I would be interested in anything that can be said about independent sets that are odd covers. Has anyone seen anything similar? For example, is it NP-Hard to prove a graph has no independent set that is an odd cover? This is an example of an independent set that is an odd cover:</p>

<pre>
a-b-d
|/ \|
c   e
|\ /|
f-g-h

Odd cover: {a, d, f, h}
</pre>

<p>This corresponds to the X3SAT instance (a,b,c) (b,d,e) (c,f,g) (e,g,h). Any satisfying assignment will be a maximum weight independent set where the weight of a vertex is its degree. Of the seven satisfying assignments, only {a, d, f, h} is an odd cover.</p>

<p>I asked this <a href="https://math.stackexchange.com/questions/796560/independent-sets-that-are-odd-covers">question</a> on SE and go no responses.</p>

<hr>

<p>An odd cover means any vertex in the graph is an odd distance from at least one vertex in the odd cover. In my example:</p>

<pre>
Vertex - Vertex in Odd Cover
a - h
b - a
c - a
d - f
e - d
f - d
g - f
h - a
</pre>

<p>This is related to the X3SAT problem. Any satisfying assignment will be a maximum weight independent set, but only some of the solutions will also be odd covers. For example, {b,g} is a maximum weight independent set but is not an odd cover. Adding the clauses in the comments gives us (a,b,c)(b,d,e)(c,f,g)(e,g,h)(a,i,j)(j,k,l)(l,m,n). This has a maximum weight independent odd cover: {a,d,f,h,k,m}. A straight chain of triangles like (a,b,c)(c,d,e)(e,f,g)(g,h,i) can not have an odd cover.</p>

CC BY-SA 3.0
2014-05-20T22:45:56.653Z
If I'm not missing something, suppose that you have a clause $(a, b, c)$ then you can add the following clauses $(a,x_1,x_2), (x_2,x_3,x_4), (x_4,x_5,x_6)$, where the $x_i$s are new variables (informally 3 triangles whose bases form a path of length 3). Then the new valid cover $C'$ needs two extra vertices that can be $C \cup \{x_1,x_4\}$ if ($a \notin C$) or $C \cup \{x_3, x_6\}$ if $a \in C$; and the lengths of the two shortest path between any vertex $v$ and them have different parity.
Marzio De Biasi
CC BY-SA 3.0
2014-05-21T00:46:12.540Z
@Marzio De Biasi: I don't think a chain of triangles like you describe can have an odd cover that is also an independent set. Adding such a chain to an existing graph doesn't seem to change anything. {a,d,f,h} is still an odd cover after adding the clauses (a,i,j) and (j,k,l) to my graph. {a,d,f,h,k} would be a maximum weight independent odd cover for the new graph.
Russell Easterly
CC BY-SA 3.0
2014-05-21T23:24:25.783Z
A clarification of what I had in mind: if you have an instance X of a max-weight indep. cover problem (which is NP-hard) and you augment it with the 3 triangles, you get an instance X' that has a  max-weight indep. *odd* cover if and only if X has a max-weight indep. cover (because the triangles always give you the possibility of building a cover which is odd). So the new problem X' is NP-hard. In the question you ask for the complexity of checking if it *doesn't have* a max-weight  indep. odd cover, so it should be coNP-hard.
Marzio De Biasi
CC BY-SA 3.0
2014-05-21T23:26:12.410Z
Furthermore you say that (a,b,c)(c,d,e)(e,f,g)(g,h,i) cannot have an odd cover, but isn't {c,f,i} an odd cover? (perhaps this is the point where I'm wrong or that I don't understand well ... I'm probably missing something trivial )-:
Marzio De Biasi
CC BY-SA 3.0
2014-05-22T00:20:41.053Z
I assume every vertex is an even distance from itself. {c,f,i} are all an even distance from f. I know finding a maximum weight independent set is NP-hard. I would like to know how hard it is to determine if a graph has an odd cover. The odd cover doesn't have to be max weight or independent.
Russell Easterly
CC BY-SA 3.0
2014-05-22T00:43:44.537Z
An odd cover does need to be an independent set. Otherwise, {a,b,c} would be an odd cover for any graph containing the triangle (a,b,c). I would be interested in any algorithm for finding an odd cover.
Russell Easterly
CC BY-SA 3.0
2014-05-22T07:39:54.930Z
Ok, [take a look to this slightly more complex construction](http://www.nearly42.org/misc/oddcover.png) (the idea is always to prove that you can add some nodes that guarantee an odd cover).
Marzio De Biasi
CC BY-SA 3.0
2014-05-22T23:21:19.163Z
Yes. Your diagram shows how an odd cover can be added to a graph that doesn't have one and how to extend an existing odd cover. I am not sure we need to do anything to extend an odd cover. Is it possible to make an existing odd cover go away by adding triangles?
Russell Easterly
CC BY-SA 3.0
2014-05-23T08:27:35.863Z
I'll think about it. But if the construction is enough to guarantee an odd cover, then the problem of finding a max-weight independent set can be reduced to the problem of finding a max-weight independent set with an odd cover. So the latter is NP-hard, too. And this should prove that your problem (checking if there is *not* a max-weight independent with an odd cover) is coNP-hard. But perhaps I'm still missing something.
Marzio De Biasi
<graph-theory><graph-algorithms><sat>
Independent Sets that are Odd Covers
Russell Easterly
# Independent Sets that are Odd Covers

(Asked by: username_0 on 2014-05-20)

I am interested in a certain type of independent set I call an "odd cover". A set of vertices is independent if no two vertices in the set are connected with an edge. A set of vertices is an "odd cover" if for any graph vertex, v, at least one vertex in the odd cover is an odd distance from v. The distance between two vertices is the minimum number of edges that connects them.
This question is related to the Exactly 1 in 3 Satisfiability problem so I am mostly interested in triangular graphs. I would be interested in anything that can be said about independent sets that are odd covers. Has anyone seen anything similar? For example, is it NP-Hard to prove a graph has no independent set that is an odd cover? This is an example of an independent set that is an odd cover:

a-b-d
|/ \|
c   e
|\ /|
f-g-h

Odd cover: {a, d, f, h}

This corresponds to the X3SAT instance (a,b,c) (b,d,e) (c,f,g) (e,g,h). Any satisfying assignment will be a maximum weight independent set where the weight of a vertex is its degree. Of the seven satisfying assignments, only {a, d, f, h} is an odd cover.
I asked this question on SE and go no responses.

An odd cover means any vertex in the graph is an odd distance from at least one vertex in the odd cover. In my example:

Vertex - Vertex in Odd Cover
a - h
b - a
c - a
d - f
e - d
f - d
g - f
h - a

This is related to the X3SAT problem. Any satisfying assignment will be a maximum weight independent set, but only some of the solutions will also be odd covers. For example, {b,g} is a maximum weight independent set but is not an odd cover. Adding the clauses in the comments gives us (a,b,c)(b,d,e)(c,f,g)(e,g,h)(a,i,j)(j,k,l)(l,m,n). This has a maximum weight independent odd cover: {a,d,f,h,k,m}. A straight chain of triangles like (a,b,c)(c,d,e)(e,f,g)(g,h,i) can not have an odd cover.

**Tags:** graph-theory, graph-algorithms, sat
> **Comments:**
> **username_1**: If I'm not missing something, suppose that you have a clause $(a, b, c)$ then you can add the following clauses $(a,x_1,x_2), (x_2,x_3,x_4), (x_4,x_5,x_6)$, where the $x_i$s are new variables (informally 3 triangles whose bases form a path of length 3). Then the new valid cover $C'$ needs two extra vertices that can be $C \cup \{x_1,x_4\}$ if ($a \notin C$) or $C \cup \{x_3, x_6\}$ if $a \in C$; and the lengths of the two shortest path between any vertex $v$ and them have different parity.  
> **username_0**: @Marzio De Biasi: I don't think a chain of triangles like you describe can have an odd cover that is also an independent set. Adding such a chain to an existing graph doesn't seem to change anything. {a,d,f,h} is still an odd cover after adding the clauses (a,i,j) and (j,k,l) to my graph. {a,d,f,h,k} would be a maximum weight independent odd cover for the new graph.  
> **username_1**: A clarification of what I had in mind: if you have an instance X of a max-weight indep. cover problem (which is NP-hard) and you augment it with the 3 triangles, you get an instance X' that has a  max-weight indep. *odd* cover if and only if X has a max-weight indep. cover (because the triangles always give you the possibility of building a cover which is odd). So the new problem X' is NP-hard. In the question you ask for the complexity of checking if it *doesn't have* a max-weight  indep. odd cover, so it should be coNP-hard.  
> **username_1**: Furthermore you say that (a,b,c)(c,d,e)(e,f,g)(g,h,i) cannot have an odd cover, but isn't {c,f,i} an odd cover? (perhaps this is the point where I'm wrong or that I don't understand well ... I'm probably missing something trivial )-:  
> **username_0**: I assume every vertex is an even distance from itself. {c,f,i} are all an even distance from f. I know finding a maximum weight independent set is NP-hard. I would like to know how hard it is to determine if a graph has an odd cover. The odd cover doesn't have to be max weight or independent.  
> **username_0**: An odd cover does need to be an independent set. Otherwise, {a,b,c} would be an odd cover for any graph containing the triangle (a,b,c). I would be interested in any algorithm for finding an odd cover.  
> **username_1**: Ok, [take a look to this slightly more complex construction](http://www.nearly42.org/misc/oddcover.png) (the idea is always to prove that you can add some nodes that guarantee an odd cover).  
> **username_0**: Yes. Your diagram shows how an odd cover can be added to a graph that doesn't have one and how to extend an existing odd cover. I am not sure we need to do anything to extend an odd cover. Is it possible to make an existing odd cover go away by adding triangles?  
> **username_1**: I'll think about it. But if the construction is enough to guarantee an odd cover, then the problem of finding a max-weight independent set can be reduced to the problem of finding a max-weight independent set with an odd cover. So the latter is NP-hard, too. And this should prove that your problem (checking if there is *not* a max-weight independent with an odd cover) is coNP-hard. But perhaps I'm still missing something.  

---

## 0 answers

