Here is what I did for TWORK (I will let Adrian explain his approach for the two challenge problems).
The input is a graph with n mod 4 = 0 and in which each node has degree 2 or 3. The problem amounts to find a maximal vertex cover (also known as vertex packing) using only "carets" or 3-paths (3 nodes and 2 edges), such that at least 3/4 of the nodes are covered.
I start by building a cover tree for the graph, and root it with a node with degree at most 2. This way we have a binary tree, with at most 2 sons for every node. Then, I use a bottom-up traversal, trying to pack as much carets as possible. The non-trivial is when we consider a node with 2 sons. When each of them has been packed, they contain 0, 1 or 2 nodes each. When there is a 0, the considered node does not really have two sons anymore, and we continue packing trivially. If there are 1 and 1, we can place a caret. If there are 1 and 2, we also place a caret, leaving one node uncovered (but since we cover 3 others, we still respect the 3/4 bound). The bad case is when we have 2 and 2 sons. Then, we place a caret BUT leave 2 nodes uncovered, which means one too much.
Now, notice that for all trivial packing (case 0-x and case 1-1), we actually save one node there. Since generally speaking there will be more such cases than the bad cases, we should still respect the 3/4 bound in the end.
There are only few cover trees with n mod 4 = 0 that cannot be covered with carets. The simplest such example is:
which cannot be covered with 3 carets. When such a case happens, we only need to construct another random cover tree of the initial graph and start again. If the problem is solvable (I would be happy to see a proof), we must find a convenient cover tree at some point, and in practice it turned out to be pretty efficient.