Using the Method of Extremal Structure, which combines the use of reduction rules as a preprocessing technique and combinatorial extremal arguments, we will prove the fixed-parameter tractability and find a problem kernel for k-MAXIMUM CUT. This kernel has 2k edges, the same as that found by Mahajan and Raman in (Mahajan & Raman 1999), but using our methodology we also find a bound of k vertices leading to a running time of O(k ? 2k/2 + n2).
|Cite as: Prieto, E. (2005). The Method of Extremal Structure on the k-Maximum Cut Problem. In Proc. Eleventh Computing: The Australasian Theory Symposium (CATS2005), Newcastle, Australia. CRPIT, 41. Atkinson, M. and Dehne, F., Eds. ACS. 119-126. |
(local if available)