Talk:Claw-free graph

Time analysis of Sbihi's algorithm

The 2√m degree bound for claw-free graphs implies that the switch graph (or skew-symmetric graph) of saturated and unsaturated vertices has at most 4n√m edges, and therefore that this version of Sbihi's algorithm takes time O(n²√m), improving the O(n³) bound from the original. But this is far too boring to write up and publish as a paper and far too much original research to include in the article, so I guess it will have to languish in obscurity here on the talk page. Anyway, one should hope for a faster algorithm with a time bound more like the O(m√n), matching the one for matching. —David Eppstein (talk) 03:32, 19 February 2009 (UTC)

- Agreed. This is the case with many algorithms on claw-free graphs, I think. Adking80 (talk) 20:43, 5 January 2011 (UTC)

Missing subsection

The article is now basically complete as far as I'm concerned, but I've avoided the inclusion of any material from a large section of the FFR survey, on Hamiltonicity. I'm tempted to write something like the following:

Many researchers have noticed that Euler tours in graphs turn into Hamiltonian cycles in line graphs, and have been tempted by the fact that Eulerian graphs are easy to characterize into looking for similarly easy characterizations of Hamiltonian claw-free graphs. But line graphs may have other kinds of Hamiltonian cycles as well, finding a Hamiltonian cycle even in a line graph is NP-complete, and therefore finding a complete characterization of Hamiltonian claw-free graphs is hopeless. Instead we have hundreds of little results that if the graph is 12-bypass-connected and doesn't contain a double-fishhook subgraph as well as being claw-free, then it's Hamiltonian. What's the point?

But obviously, that would be too much editorialization. So, while I'm a little concerned that I'm abusing WP:NPOV by omitting this material, I think it might be a greater abuse for me to write the missing section. Someone else who likes that material can add it instead. —David Eppstein (talk) 08:15, 22 February 2009 (UTC)

Re : "the graph is 12-bypass-connected and doesn't contain a double-fishhook" - A good while ago (20+ years) I've read a parody graph theory article about what I vaguely remember was called "patriotic graphs", which was somehow related to "patriotic coloring": coloring of a graph into patriotic colors: red, white and blue, or something. It was basically a string of definitions "a graph is called <aaa> if it is <...> and contains <...>. "a graph is called <bbb> if it is <aaa> and <...>, etc. It culminated in a theorem , kind of "a <rrr>-graph which is <qqq> and <ppp> is patriotic iff it is <ooo>, <nnn> and <ddd>". Do you happen to remember something like this? I tried to google it several times, but obviously I've forgot the exact names. Twri (talk) 17:03, 24 February 2009 (UTC)

Doesn't sound familiar, sorry. —David Eppstein (talk) 17:09, 24 February 2009 (UTC)

Error in finding augmenting paths

The 'switch graph' algorithm described in section Independent Sets for finding augmenting paths is wrong. In this counter-example large vertices are in I; there is no augmenting path, but the algo will find a walk that visits the central vertex twice. If you try any fixes, you'll find other counter-examples by adding leaves to (one or both) the bottom two vertices, depending on which one is visited first. In general it seems any easy approach would have to remember where we came from, which is as intractable as Hamiltonian Path. Indeed it would be strange if an algorithm that simple could work: Edmonds, Sbihi and Minty all had to give much more involved constructions. Edmonds's Blossom algorithm in fact solves the same problem in the specific case of line graphs, and is well known, so we'd have to do at least that.

I tried a similar simple approach in my own research, convinced others, and only found the counter-examples much later when trying to write down a proof :) So I think it's best if I remove the paragraph about switch graphs and include the image to explain better why 'Searching for an augmenting path is complicated'. Tokenzero (talk) 15:35, 19 October 2014 (UTC)

I think it's actually not incorrect, but it's not described clearly. What you need to find is a *simple* path in the switch graph, not a walk. An algorithm of Goldberg & Karzanov 2004 (cited at the switch graph wikilink, and expressed in terms of regular paths in skew-symmetric graphs) can do this in linear time as stated. —David Eppstein (talk) 18:17, 19 October 2014 (UTC)

Oh, now I see it works for matchings by generalizing the blossom algorithm, so disregard my comment about it being strange if it worked here too. Still I don't think it does work. Of course you want to search for simple paths, but in this example you *will* find a simple 'alternating' path in the switch graph (or simple regular in the skew-symmetric graph): the problem is it won't correspond to a simple path in the original graph due to the vertices from I we hide - it will correspond to a walk that enters the central vertex twice. You could search for *induced* paths in the switch graph, but I don't see how (Goldberg & Karzanov don't mention such a variant, and the shortest alternating/regular path isn't necessarily induced as the example shows). Tokenzero (talk) 20:11, 20 October 2014 (UTC)