37th International Conference on Current Trends in Theory and Practice of Computer Science

List of accepted papers

Gianlorenzo D'Angelo, Gabriele Di Stefano and Alfredo Navarra. Bandwidth constrained multi-interface networks Abstract: In heterogeneous networks, devices can communicate by means of multiple wired or wireless interfaces. By switching among interfaces or by combining the available interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost, and provides a communication bandwidth. In this paper, we consider the problem of activating the cheapest set of interfaces among a network G=(V,E) in order to guarantee a minimum bandwidth B of communication between two specified nodes. Nodes V represent the devices, edges E represent the connections that can be established. In practical cases, a bounded number k of different interfaces among all the devices can be considered. Despite this assumption, the problem turns out to be NP-hard even for small values of k and Delta, where Delta is the maximum degree of the network. In particular, the problem is NP-hard for any fixed k >= 2 and Delta >= 3, while it is polynomially solvable when k = 1, or Delta <= 2 and k = O(1). Moreover, we show that the problem is not approximable within \eta log{B} or Omega(log log |V|) for any fixed k >= 3, Delta >= 3, and for a certain constant \eta, unless P=NP. We then provide an approximation algorithm with ratio guarantee of b_{max}, where b_{max} is the maximum communication bandwidth allowed among all the available interfaces. Finally, we focus on particular cases by providing complexity results and polynomial algorithms for Delta <= 2. [slides]
Nadja Betzler, Robert Bredereck, Rolf Niedermeier and Johannes Uhlmann. On Making a Distinguished Vertex Minimum Degree by Vertex Deletion Abstract: For directed and undirected graphs, we study the problem 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. For the directed case where the indegree shall be made minimum, in previous work it was shown that the problem is W[2]-complete with respect to the parameter "number of vertices to delete" (even when the graph is restricted to be a tournament) but it is polynomial-time solvable on dags. Continuing this work, here we show that the problem is also W[2]-hard when parameterized by the graph's feedback arc set number, whereas it becomes fixed-parameter tractable when combining this parameter with the number of deleted vertices. For the undirected case, which surprisingly seemed unstudied so far, 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 with respect to the several parameterizations measuring tree-likeness including 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 also for the parameters treewidth and "feedback vertex set number". [slides]

Papers accepted to Student Research Forum


Created using Fluid 960 Grid, and Sofsems' webs. © Faculty of Mathematics, Physics, and Computer Science, Comenius University, 2010