16
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
12
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ The overline runs away, there I mean the complement of $K_{2,m}$ for any $m\geq 2$. $\endgroup$
    – Hsien-Chih Chang 張顯之
    Oct 28, 2010 at 15:50
  • 1
    $\begingroup$ 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. $\endgroup$
    – András Salamon
    Oct 29, 2010 at 9:23
  • $\begingroup$ @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 $\endgroup$
    – didest
    Jul 10, 2012 at 18:56
  • $\begingroup$ @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. $\endgroup$
    – András Salamon
    Jul 13, 2012 at 14:17

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.