On Structural Parameterizations of the Offensive Alliance Problem
The Offensive Alliance problem has been studied extensively during the last twenty years. A set $S\subseteq V$ of vertices is an offensive alliance in an undirected graph $G=(V,E)$ if each $v\in N(S)$ has at least as many neighbours in $S$ as it has neighbours (including itself) not in $S$. We study the parameterized complexity of the Offensive Alliance problem, where the aim is to find a minimum size offensive alliance. Our focus here lies on parameters that measure the structural properties of the input instance. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that the problem is W[1]-hard parameterized by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, treewidth, pathwidth, and treedepth of the input graph.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Alliances and Conflict, or Conflict and Alliances? Appraising the Causal Effect of Alliances on Conflict
The deterrent effect of military alliances is well documented and widely accepted. However, such work has typically assumed that alliances are exogenous. This is problematic as alliances may simultaneously influence the …
Defensive Alliances in Signed Networks
The analysis of (social) networks and multi-agent systems is a central theme in Artificial Intelligence. Some line of research deals with finding groups of agents that could work together to achieve a certain goal. To th…
Strategic Coercion Within Alliances: The Greenland Sovereignty Game as an AI Stress Test
What happens when the strongest alliance member pressures a weaker member over territory and strategic control? We examine the Greenland sovereignty crisis as a stress test for LLM geopolitics, centered on the 2019-2026 …
Analysis of Maximal Topologies Achieving Optimal DoF and DoF $\frac{1}{n}$ in Topological Interference Management
Topological interference management (TIM) can obtain degrees of freedom (DoF) gains with no channel state information at the transmitters (CSIT) except topological information of network in the interference channel. It w…
ManagementWhat can Speech and Language Tell us About the Working Alliance in Psychotherapy
We are interested in the problem of conversational analysis and its application to the health domain. Cognitive Behavioral Therapy is a structured approach in psychotherapy, allowing the therapist to help the patient to …