Computer Science – Computational Complexity
Scientific paper
2011-08-10
Computer Science
Computational Complexity
A full-featured version can be found at http://robert.bredereck.info, where you can also find the complete abstract. (ArXiv al
Scientific paper
This work investigates the parameterized complexity of three related graph modification problems. Given a directed graph, a distinguished vertex, and a positive integer k, Minimum Indegree Deletion asks for a vertex subset of size at most k whose removal makes the distinguished vertex the only vertex with minimum indegree. Minimum Degree Deletion is analogously defined, but deals with undirected graphs. Bounded Degree Deletion is also defined on undirected graphs, but has a positive integer d instead of a distinguished vertex as part of the input. It asks for a vertex subset of size at most k whose removal results in a graph in which every vertex has degree at most d. The first two problems have applications in computational social choice whereas the third problem is used in computational biology. We investigate the parameterized complexity with respect to the parameters "treewidth", "size of a feedback vertex set" and "size of a feedback edge set" respectively "size of a feedback arc set". Each of these parameters measures the "degree of acyclicity" in different ways.
No associations
LandOfFree
Graph and Election Problems Parameterized by Feedback Set Numbers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Graph and Election Problems Parameterized by Feedback Set Numbers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph and Election Problems Parameterized by Feedback Set Numbers will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-665578