---
abstract: 'We investigate parameterized algorithms for the NP-hard problem <span style="font-variant:small-caps;">Min-Power Asymmetric Connectivity (MinPAC)</span> that has applications in wireless sensor networks. Given a directed arc-weighted graph, MinPAC asks for a strongly connected spanning subgraph minimizing the summed vertex costs. Here, the cost of each vertex is the weight of its heaviest outgoing arc in the chosen subgraph. We present linear-time algorithms for the cases where the number of strongly connected components in a so-called obligatory subgraph or the feedback edge number in the underlying undirected graph is constant. Complementing these results, we prove that the problem is W\[2\]-hard with respect to the solution cost, even on restricted graphs with one feedback arc and binary arc weights.'
author:
- Matthias Bentert
- Roman Haag
- Christian Hofer
- Tomohiro Koana
- André Nichterlein
bibliography:
- 'ref.bib'
date: 'Algorithmics and Computational Complexity, Faculty IV, TU Berlin, Germany, `{matthias.bentert,tomohiro.koana,andre.nichterlein}@tu-berlin.de, {roman.haag,hofer}@campus.tu-berlin.de`'
title: '**Parameterized Complexity of Min-Power Asymmetric Connectivity**'
---

Introduction
============

In wireless ad-hoc networks, nodes equipped with limited power supply transmit data using a multi-hop path. We study the problem of minimizing the overall power consumption while maintaining full network connectivity, that is, each node can send messages to each other node 