3
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – Marzio De Biasi
    May 20, 2014 at 22:45
  • $\begingroup$ @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. $\endgroup$
    – Russell Easterly
    May 21, 2014 at 0:46
  • 1
    $\begingroup$ 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. $\endgroup$
    – Marzio De Biasi
    May 21, 2014 at 23:24
  • $\begingroup$ 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 )-: $\endgroup$
    – Marzio De Biasi
    May 21, 2014 at 23:26
  • 1
    $\begingroup$ 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. $\endgroup$
    – Marzio De Biasi
    May 23, 2014 at 8:27

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.