TY - JOUR

T1 - On making a distinguished vertex of minimum degree by vertex deletion

AU - Betzler, Nadja

AU - Bodlaender, Hans L.

AU - Bredereck, Robert

AU - Niedermeier, Rolf

AU - Uhlmann, Johannes

PY - 2014/1/1

Y1 - 2014/1/1

N2 - For directed and undirected graphs, we study how to make a distinguished vertex the unique minimum-(in)degree vertex through deletion of a minimum number of vertices. The corresponding NP-hard optimization problems are motivated by applications concerning control in elections and social network analysis. Continuing previous work for the directed case, we show that the problem is W[2]-hard when parameterized by the graph's feedback arc set number, whereas it becomes fixed-parameter tractable when combining the parameters "feedback vertex set number" and "number of vertices to delete". For the so far unstudied undirected case, we show that the problem is NP-hard and W[1]-hard when parameterized by the "number of vertices to delete". On the positive side, we show fixed-parameter tractability for several parameterizations measuring tree-likeness. In particular, we provide a dynamic programming algorithm for graphs of bounded treewidth and a vertex-linear problem kernel with respect to the parameter "feedback edge set number". On the contrary, we show a non-existence result concerning polynomial-size problem kernels for the combined parameter "vertex cover number and number of vertices to delete", implying corresponding non-existence results when replacing vertex cover number by treewidth or feedback vertex set number.

AB - For directed and undirected graphs, we study how to make a distinguished vertex the unique minimum-(in)degree vertex through deletion of a minimum number of vertices. The corresponding NP-hard optimization problems are motivated by applications concerning control in elections and social network analysis. Continuing previous work for the directed case, we show that the problem is W[2]-hard when parameterized by the graph's feedback arc set number, whereas it becomes fixed-parameter tractable when combining the parameters "feedback vertex set number" and "number of vertices to delete". For the so far unstudied undirected case, we show that the problem is NP-hard and W[1]-hard when parameterized by the "number of vertices to delete". On the positive side, we show fixed-parameter tractability for several parameterizations measuring tree-likeness. In particular, we provide a dynamic programming algorithm for graphs of bounded treewidth and a vertex-linear problem kernel with respect to the parameter "feedback edge set number". On the contrary, we show a non-existence result concerning polynomial-size problem kernels for the combined parameter "vertex cover number and number of vertices to delete", implying corresponding non-existence results when replacing vertex cover number by treewidth or feedback vertex set number.

KW - Graph modification problem

KW - Parameterized complexity

KW - Treewidth

UR - http://www.scopus.com/inward/record.url?scp=84897669208&partnerID=8YFLogxK

U2 - 10.1007/s00453-012-9695-6

DO - 10.1007/s00453-012-9695-6

M3 - Article

AN - SCOPUS:84897669208

SN - 0178-4617

VL - 68

SP - 715

EP - 738

JO - Algorithmica

JF - Algorithmica

IS - 3

ER -