16

X-free graphs are those that contain no graph from X as an induced subgraph. A hole is a cycle with at least 4 vertices. An odd-hole is a hole with an odd number of vertices. An antihole is the complement of a hole.

The (odd-hole,odd-antihole)-free graphs are precisely the perfect graphs; this is the Strong Perfect Graph Theorem. It is possible to find the largest independent set (and largest clique) in a perfect graph in polynomial time, but the only known method of doing so requires building a semi-definite program to compute the Lovász theta number.

The (hole,antihole)-free graphs are called weakly chordal, and constitute a rather easy class for many problems (including INDEPENDENT SET and CLIQUE).

Does anyone know if (odd-hole,antihole)-free graphs have been studied or written about?

These graphs occur quite naturally in constraint satisfaction problems where the graph of related variables forms a tree. Such problems are rather easy, so it would be nice if there were a way to find a largest independent set clique for graphs in this family without having to compute the Lovász theta.

Equivalently, one wants to find a largest independent set for (hole, odd-antihole)-free graphs. Hsien-Chih Chang points out below why this is a more interesting class for INDEPENDENT SET than (odd-hole, antihole)-free graphs.

András Salamon
  • 19,000
  • 3
  • 64
  • 150

1 Answers1

12

In fact, it is relatively easy. Instead for studying independent set problem in (odd-hole,antihole)-free graphs, we take complement of the graphs and try to find a maximum clique in it. Thus it becomes maximum clique problem in (hole, anti-odd-hole)-free graphs.

In section 2 of the paper "Triangulated Neighborhoods in Even-hole-free Graphs" by da Silva and Vuskovic, they stated that Farber first shows

There are $O(n^2)$ maximal cliques in any 4-hole free graphs.

Then their main theorem stated that

There are $O(n + m)$ maximal cliques in even-hole-free graphs, and all the maximal cliques can be found in time $O(n^2m)$.

Since we are dealing with (hole, anti-odd-hole)-free graphs which is clearly even-hole-free, finding a maximum clique takes at most $O(n^2m)$ time.

4-hole-free are critical to these kind of results like a poly-time algorithm for $\overline{K_{2,m}}$-free graphs, so the real challenge may be studying independent set problem in (hole, anti-odd-hole)-free graphs instead, which becomes the maximum clique problem in (odd-hole, anti-hole)-free graphs.

Edit:

Oh, another thought came out. (hole, anti-odd-hole)-free graphs are almost weakly chordal in the following sense: since 4-hole-free implies there are only anti-holes with size 4~7 remains (any k-anti-hole with size > 7 contains a 4-hole), and it is also anti-odd-hole-free which restrict the size of anti-holes down to 4 and 6, it is almost no holes/antiholes in the graph! Thus a poly-time algorithm seems plausible for such graphs.

Hsien-Chih Chang 張顯之
  • 7,638
  • 4
  • 44
  • 83
  • The overline runs away, there I mean the complement of $K_{2,m}$ for any $m\geq 2$. – Hsien-Chih Chang 張顯之 Oct 28 '10 at 15:50
  • 1
    Thanks! Looking again at my result with Peter Jeavons, we actually showed that tree-structured constraint problems yield (hole, odd-antihole)-free graphs in which one wants to find the largest independent set. I will make the question more precise -- I incorrectly suggested IS was the problem one wanted to solve. – András Salamon Oct 29 '10 at 09:23
  • @AndrásSalamon can you give open access to preprints of your work on this topic? I couldn't access through my university's proxy neither – didest Jul 10 '12 at 18:56
  • @DiegodeEstrada: I'd be happy to send you a preprint of our CP 2008 paper, just send me an email. However, it really is a constraints paper so may not be that interesting to you. – András Salamon Jul 13 '12 at 14:17