I'm still fighting with the aforementioned paper "Improved upper bounds for vertex cover" by Chen, Kanj, Xia (PDF kindly provided by Yuval Filmus).
My current problem is that it's specified that the main vertex cover algorithm VC (page 7/21) has the following header VC(G, T, k), where G is the graph to process, T is a set of tuples and k is the bounding parameter.
My question is: what should the set of tuples contain in the first execution of VC?
It's said multiple times that the algorithm maintains this structure and generates tuples.
This is obvious, given the Reducing subroutine behavior.
What is giving me trouble is that Reducing is called before any further logic in VC and Reducing itself begins with a loop saying for each tuple (S, q) in T, which implies that the set T should be pre-populated.
Should I scan the whole graph for all the structures that would fulfill the criteria for being included in T? This seems a bit drastic, since the operations of Struction and General-Fold will cause the structures in T to be invalidated.
Currently, my best bet is that, given the list of priorities (page 8/21) of certain structures as well as the definition of a good pair (page 5/21, after Observation 3.3) I should search the whole graph for tuples, good pairs and vertices with high degrees and put them into T with appropriate priorities.
The first sentence from section 4. The algorithm VC (page 8/21) seems quite convincing:
A tuple, a good pair, or a vertex of degree at least seven, will be referred to by the word structure. The algorithm will maintain a list of structures T, and then it will pick a structure and process it.
Can somebody provide some intuition? Maybe I'm just missing something that's staring at me from the paper itself...
Reading deeper into section updating tuples (page 6/21), one can see the following paragraph:
Since a tuple imposes certain constraints on the minimum vertex cover sought, one needs to be careful that the constraints imposed by the creation of a tuple do not conflict with the conditions imposed by other operations of the algorithm.
The other operations that do impose constraints on the minimum vertex cover sought are the creation of (other) tuples, the struction operation, and the general folding operation.
For example, the general folding operation assumes that when we are looking for a minimum vertex cover, we can look for one that either contains the set I or the set N ( I ) in the structure ( I , N ( I )) . This is mainly the reason why the set N ( I ) can be folded.
If the general folding operation is applied, then this constraint imposed by the operation on the minimum vertex cover might conflict with the constraints imposed by a certain tuple. Therefore, to be on the safe side, when we decide to apply the struction or the general folding operations, we will invalidate all the constraints imposed by the tuples. That is, we will basically remove all the tuples.
So, even when I pre-seed T with some structures, they will most likely be removed anyway sooner or later, leaving an empty set and going back to square 1.
