Editing Graphs to Satisfy Degree Constraints:
A Parameterized Approach
Luke Mathieson and Stefan
Szeider.
Journal of Computer and System Sciences,
vol. 78, no. 1,
pp. 179-191, 2012.
Parts of the paper appeared in preliminary form in:
- Proceedings of
CATS 2008, Computing: The Australasian Theory Symposium, University of
Wollongong, New South Wales, Australia, January 22-25, 2008,
part of the Australasian Computer Society Week (ACSW 2008),
CRPIT vol. 77, pp. 79-86, Australian Computer Society, 2008.
-
Proceedings of
COCOA 2008,
2nd Annual International Conference on Combinatorial
Optimization and Applications,
August 21-24, 2008, in St. John's, Newfoundland, Canada.
Lecture Notes in Computer Science,
vol. 5165, pp. 13-22, Springer-Verlag, 2008.
Abstract:
We study a wide class of graph editing problems that ask whether a given graph
can be modified to satisfy certain degree constraints, using a limited number
of vertex deletions, edge deletions, or edge additions. The problems
generalize several well-studied problems such as the General Factor Problem
and the Regular Subgraph Problem. We classify the parameterized complexity of
the considered problems taking upper bounds on the number of editing steps and
the maximum degree of the resulting graph as parameters.
Keywords: Parameterized Complexity, Computational Complexity, Kernelization,
Graph Editing, Regular Subgraph, General Factor.
Download: [paper pdf]
|