The tree-independence number of a graph is the minimum, over all tree-decompositions of the graph, of the maximum size of an independent set contained in a bag. Graph classes of bounded tree-independence number have strong structural and algorithmic properties, but the parameter can be unbounded even in quite restricted classes. In particular, the presence of an induced biclique K_{𝓁,𝓁} forces tree-independence number at least 𝓁. This leads to the question whether large induced bicliques are the only obstruction to bounded tree-independence number in natural hereditary classes. A conjecture of Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht states that for all positive integers t and 𝓁, {P_t,K_{𝓁,𝓁}}-free graphs have bounded tree-independence number. We prove this conjecture for t = 5 by showing that every {P₅,K_{𝓁,𝓁}}-free graph has tree-independence number at most 4𝓁. We also obtain related bounds for the weaker parameter of α-degeneracy.

Inspired by the famous Target Set Selection problem, we propose a new discrete model to simultaneously spread two opinions within a social network and perform an initial study of its complexity. Here, we are given a social network, a seed-set of agents for each opinion, two thresholds for each agent, a budget, and a number of rounds. The first threshold represents the willingness of an agent to adopt an opinion if the agent has no opinion at all, while the second threshold states the willingness to acquire a second opinion if the agent already has one. The goal is to add at most budget-many agents to the initial seed-sets such that the process started with these extended seed-sets stabilizes within the given number of rounds, with each agent having either both opinions or none. That is, our goal is to ensure that the spread of opinions is balanced. We show that the problem is NP-hard, and thus we study the problem from the perspective of parameterized complexity. In particular, we show that the problem is FPT when parameterized by the number of rounds, the maximum threshold, and the treewidth combined. This algorithm also applies to the combined parameter, the treedepth and the maximum threshold. Finally, we show that the problem is FPT when parameterized by the vertex cover number, the $3$-path vertex cover number, or the vertex integrity of the input network alone. To complement our tractability results, we show that the problem is W[1]-hard with respect to a) the sizes of the initial seed-sets and the feedback-vertex set number combined, even if all thresholds are bounded by a constant, and b) the budget, the 4-path vertex cover number, and the feedback-vertex set number combined, even if every activation process stabilizes in at most 4 rounds.

The Directed Traveling Salesman Problem (DTSP) is a variant of the classical Traveling Salesman Problem in which the edges in the graph are directed and a vertex and edge can be visited multiple times. The goal is to find a directed closed walk of minimum length (or total weight) that visits every vertex of the given graph at least once. In a yet more general version, Directed Waypoint Routing Problem (DWRP), some vertices are marked as terminals and we are only required to visit all terminals. Furthermore, each edge has its capacity bounding the number of times this edge can be used by a solution. While both problems (and many other variants of TSP) were extensively investigated, mostly from the approximation point of view, there are surprisingly few results concerning the parameterized complexity. Our starting point is the result of Marx et al. [APPROX/RANDOM 2016] who proved that DTSP is W[1]-hard parameterized by distance to pathwidth 3. In this paper we aim to initiate the systematic complexity study of variants of Directed Traveling Salesman Problem with respect to various, mostly structural, parameters. We show that DWRP is FPT parameterized by the solution size, the feedback edge number and the vertex integrity of the underlying undirected graph. Furthermore, the problem is XP parameterized by treewidth. On the complexity side, we show that the problem is W[1]-hard parameterized by the distance to constant treedepth.

In this paper, we study the problem of pathfinding on traversal-dependent graphs, i.e., graphs whose edges change depending on the previously visited vertices. In particular, we study self-deleting graphs, introduced by Carmesin et al. [Sarah Carmesin et al., 2023], which consist of a graph G = (V, E) and a function f: V → 2^E, where f(v) is the set of edges that will be deleted after visiting the vertex v. In the (Shortest) Self-Deleting s-t-path problem we are given a self-deleting graph and its vertices s and t, and we are asked to find a (shortest) path from s to t, such that it does not traverse an edge in f(v) after visiting v for any vertex v. We prove that Self-Deleting s-t-path is NP-hard even if the given graph is outerplanar, bipartite, has maximum degree 3, bandwidth 2 and |f(v)| ≤ 1 for each vertex v. We show that Shortest Self-Deleting s-t-path is W[1]-complete parameterized by the length of the sought path and that Self-Deleting s-t-path is W[1]-complete parameterized by the vertex cover number, feedback vertex set number and treedepth. We also show that the problem becomes FPT when we parameterize by the maximum size of f(v) and several structural parameters. Lastly, we show that the problem does not admit a polynomial kernel even for parameterization by the vertex cover number and the maximum size of f(v) combined already on 2-outerplanar graphs.

In this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9. We add a new and simpler proof of the NP-completeness of treewidth, and show that Treewidth remains NP-complete on subcubic induced subgraphs of the infinite 3-dimensional grid.

Hedonic diversity games are a variant of the classical Hedonic games designed to better model a variety of questions concerning diversity and fairness. Previous works mainly targeted the case with two diversity classes (represented as colors in the model) and provided a set of initial complexity-theoretic and existential results concerning Nash and Individually stable outcomes. Here, we design new algorithms accompanied with lower bounds which provide a full parameterized-complexity picture for computing Nash and Individually stable outcomes with respect to the most natural parameterizations of the problem. Crucially, our results hold for general Hedonic diversity games where the number of colors is not necessarily restricted to two, and show that---apart from two trivial cases---a necessary condition for tractability in this setting is that the number of colors is bounded by the parameter. Moreover, for the special case of two colors we resolve an open question asked in previous work~(Boehmer and Elkind, AAAI 2020).

We propose a new discrete model for simultaneously spreading two opinions within a social network inspired by the famous Target Set Selection problem. We are given a social network, a seed-set of agents for each opinion, and two thresholds per agent. The first threshold represents the willingness of an agent to adopt an opinion if she has no opinion at all, while the second threshold states the readiness to acquire a second opinion. The goal is to add as few agents as possible to the initial seed-sets such that, once the process started with these seed-set stabilises, each agent has either both opinions or none. We perform an initial study of its computational complexity. It is not surprising that the problem is NP-hard even in quite restricted settings. Therefore, we investigate the complexity of the problem from the parameterized point-of-view with special focus on sparse networks, which appears often in practice. Among other things, we show that the proposed problem is in the FPT complexity class if we parameterize by the vertex cover number of the underlying graph.

For many problems, the important instances from practice possess certain structure that one should reflect in the design of specific algorithms. As data reduction is an important and inextricable part of today's computation, we employ one of the most successful models of such precomputation -- the kernelization. Within this framework, we focus on Traveling Salesperson Problem (TSP) and some of its generalizations. We provide a kernel for TSP with size polynomial in either the feedback edge set number or the size of a modulator to constant-sized components. For its generalizations, we also consider other structural parameters such as the vertex cover number and the size of a modulator to constant-sized paths. We complement our results from the negative side by showing that the existence of a polynomial-sized kernel with respect to the fractioning number, the combined parameter maximum degree and treewidth, and, in the case of Subset-TSP, modulator to disjoint cycles (i.e., the treewidth two graphs) is unlikely.

In the Waypoint Routing Problem one is given an undirected capacitated and weighted graph G, a source-destination pair s,t∈V(G) and a set W⊆V(G), of waypoints. The task is to find a walk which starts at the source vertex s, visits, in any order, all waypoints, ends at the destination vertex t, respects edge capacities, that is, traverses each edge at most as many times as is its capacity, and minimizes the cost computed as the sum of costs of traversed edges with multiplicities. We study the problem for graphs of bounded treewidth and present a new algorithm for the problem working in 2O(tw)⋅n time, significantly improving upon the previously known algorithms. We also show that this running time is optimal for the problem under Exponential Time Hypothesis.

Abstract The Minimum Eccentricity Shortest Path Problem consists in finding a shortest path with minimum eccentricity in a given undirected graph. The problem is known to be NP-complete and W[2]-hard with respect to the desired eccentricity. We present fpt algorithms for the problem parameterized by the modular width, distance to cluster graph, the combination of distance to disjoint paths with the desired eccentricity, and maximum leaf number.

Abstract Consider a vertex-weighted graphGwith a sourcesand a targett.Tracking Pathsrequires finding a minimum weight set of vertices (trackers) such that the sequence of trackers in each path fromstotis unique. In this work, we derive a factor 66-approximation algorithm forTracking Pathsin weighted graphs and a factor 4-approximation algorithm if the input is unweighted. This is the first constant factor approximation for this problem. While doing so, we also study approximation of the closely relatedr-Fault Tolerant Feedback Vertex Setproblem. There, for a fixed integer rand a given vertex-weighted graphG, the task is to find a minimum weight set of vertices intersecting every cycle of Gin at least $$r+1$$ r+1 vertices. We give a factor $$\mathcal {O}(r^2)$$ O(r2) approximation algorithm forr-Fault Tolerant Feedback Vertex Setifris a constant.

Abstract We study the -hard graph problemCollapsed k-Corewhere, given an undirected graphGand integersb,x, andk, we are asked to removebvertices such that thek-core of remaining graph, that is, the (uniquely determined) largest induced subgraph with minimum degreek, has size at mostx.Collapsed k-Corewas introduced by Zhang et al. (2017) and it is motivated by the study of engagement behavior of users in a social network and measuring the resilience of a network against user drop outs.Collapsed k-Coreis a generalization ofr-Degenerate Vertex Deletion(which is known to be -hard for allr≥ 0) where, given an undirected graphGand integersbandr, we are asked to removebvertices such that the remaining graph isr-degenerate, that is, every its subgraph has minimum degree at mostr. We investigate the parameterized complexity ofCollapsed k-Corewith respect to the parametersb,x, andk, and several structural parameters of the input graph. We reveal a dichotomy in the computational complexity ofCollapsed k-Corefork≤ 2 andk≥ 3. For the latter case it is known that for allx≥ 0Collapsed k-Coreis -hard when parameterized byb. Fork≤ 2 we show thatCollapsed k-Coreis -hard when parameterized byband in when parameterized by (b+x). Furthermore, we outline thatCollapsed k-Coreis in when parameterized by the treewidth of the input graph and presumably does not admit a polynomial kernel when parameterized by the vertex cover number of the input graph.

The problem of $d$-Path Vertex Cover, $d$-PVC lies in determining a subset $F$ of vertices of a given graph $G=(V,E)$ such that $G \setminus F$ does not contain a path on $d$ vertices. The paths we aim to cover need not to be induced. It is known that the $d$-PVC problem is NP-complete for any $d \ge 2$. When parameterized by the size of the solution $k$, 5-PVC has direct trivial algorithm with $\mathcal{O}(5^kn^{\mathcal{O}(1)})$ running time and, since $d$-PVC is a special case of $d$-Hitting Set, an algorithm running in $\mathcal{O}(4.0755^kn^{\mathcal{O}(1)})$ time is known. In this paper we present an iterative compression algorithm that solves the 5-PVC problem in $\mathcal{O}(4^kn^{\mathcal{O}(1)})$ time.

In the Directed Steiner Network problem we are given an arc-weighted digraph $G$, a set of terminals $T \subseteq V(G)$, and an (unweighted) directed request graph $R$ with $V(R)=T$. Our task is to output a subgraph $G' \subseteq G$ of the minimum cost such that there is a directed path from $s$ to $t$ in $G'$ for all $st \in A(R)$. It is known that the problem can be solved in time $|V(G)|^{O(|A(R)|)}$ [Feldman&Ruhl, SIAM J. Comput. 2006] and cannot be solved in time $|V(G)|^{o(|A(R)|)}$ even if $G$ is planar, unless Exponential-Time Hypothesis (ETH) fails [Chitnis et al., SODA 2014]. However, as this reduction (and other reductions showing hardness of the problem) only shows that the problem cannot be solved in time $|V(G)|^{o(|T|)}$ unless ETH fails, there is a significant gap in the complexity with respect to $|T|$ in the exponent. We show that Directed Steiner Network is solvable in time $f(R)\cdot |V(G)|^{O(c_g \cdot |T|)}$, where $c_g$ is a constant depending solely on the genus of $G$ and $f$ is a computable function. We complement this result by showing that there is no $f(R)\cdot |V(G)|^{o(|T|^2/ \log |T|)}$ algorithm for any function $f$ for the problem on general graphs, unless ETH fails.

In the Steiner Orientation problem, the input is a mixed graph G (it has both directed and undirected edges) and a set of k terminal pairs $$\mathscr {T}$$ . The question is whether we can orient the undirected edges in a way such that there is a directed $$s\leadsto t$$ path for each terminal pair $$(s,t)\in \mathscr {T}$$ . Arkin and Hassin [DAM’02] showed that the Steiner Orientation problem is NP-complete. They also gave a polynomial time algorithm for the special case when $$k=2$$ . From the viewpoint of exact algorithms, Cygan et al. [ESA’12, SIDMA’13] designed an XP algorithm running in $$n^{O(k)}$$ time for all $$k\ge 1$$ . Pilipczuk and Wahlström [SODA’16, TOCT’18] showed that the Steiner Orientation problem is W[1]-hard parameterized by k. As a byproduct of their reduction, they were able to show that under the Exponential Time Hypothesis (ETH) of Impagliazzo, Paturi and Zane [JCSS’01] the Steiner Orientation problem does not admit an $$f(k)\cdot n^{o(k/\log k)}$$ algorithm for any computable function f. In this paper, we give a short and easy proof that the $$n^{O(k)}$$ algorithm of Cygan et al. is asymptotically optimal, even if the input graph is planar. Formally, we show that the Planar Steiner Orientation problem is W[1]-hard parameterized by the number k of terminal pairs, and, under ETH, cannot be solved in $$f(k)\cdot n^{o(k)}$$ time for any computable function f. Moreover, under a stronger hypothesis called Gap-ETH of Dinur [ECCC’16] and Manurangsi and Raghavendra [ICALP’17], we are able to show that there is no constant $$\vartheta >0$$ such that Planar Steiner Orientation admits an $$(\frac{19}{20}+\vartheta )$$ -approximation in FPT time, i.e., no $$f(k)\cdot n^{o(k)}$$ time algorithm can distinguish between the case when all k pairs are satisfiable versus the case when less than $$k \cdot (\frac{19}{20}+\vartheta )$$ pairs are satisfiable. To the best of our knowledge, this is the first FPT inapproximability result on planar graphs.

Motivated by the recent rapid growth of research for algorithms to cluster multi-layer and temporal graphs, we study extensions of the classical Cluster Editing problem. In Multi-Layer Cluster Editing we receive a set of graphs on the same vertex set, called layers and aim to transform all layers into cluster graphs (disjoint unions of cliques) that differ only slightly. More specifically, we want to mark at most d vertices and to transform each layer into a cluster graph using at most k edge additions or deletions per layer so that, if we remove the marked vertices, we obtain the same cluster graph in all layers. In Temporal Cluster Editing we receive a sequence of layers and we want to transform each layer into a cluster graph so that consecutive layers differ only slightly. That is, we want to transform each layer into a cluster graph with at most k edge additions or deletions and to mark a distinct set of d vertices in each layer so that each two consecutive layers are the same after removing the vertices marked in the first of the two layers. We study the combinatorial structure of the two problems via their parameterized complexity with respect to the parameters d and k, among others. Despite the similar definition, the two problems behave quite differently: In particular, Multi-Layer Cluster Editing is fixed-parameter tractable with running time k^{O(k + d)} s^{O(1)} for inputs of size s, whereas Temporal Cluster Editing is W[1]-hard with respect to k even if d = 3.

We study the parameterized complexity of the directed variant of the classical Steiner Tree problem on various classes of directed sparse graphs. While the parameterized complexity of Steiner Tree parameterized by the number of terminals is well understood, not much is known about the parameterization by the number of nonterminals in the solution tree. All that is known for this parameterization is that both the directed and the undirected versions are W[2]-hard on general graphs and hence unlikely to be fixed parameter tractable (FPT). The undirected Steiner Tree problem becomes FPT when restricted to sparse classes of graphs such as planar graphs, but the techniques used to show this result break down on directed planar graphs. In this article we precisely chart the tractability border for Directed Steiner Tree (DST) on sparse graphs parameterized by the number of nonterminals in the solution tree. Specifically, we show that the problem is FPT on graphs excluding a topological minor but becomes W[2]-hard on graphs of degeneracy 2. On the other hand we show that if the subgraph induced by the terminals is acyclic, then the problem becomes FPT on graphs of bounded degeneracy. We further show that our algorithm achieves the best possible asymptotic running time dependence on the solution size and degeneracy of the input graph, under standard complexity theoretic assumptions. Using the ideas developed for DST, we also obtain improved algorithms for Dominating Set on sparse undirected graphs. These algorithms are asymptotically optimal. (An erratum is attached.)

Finding a vertex subset in a graph that satisfies a certain property is one of the most-studied topics in algorithmic graph theory. The focus herein is often on minimizing or maximizing the size of the solution, that is, the size of the desired vertex set. In several applications, however, we also want to limit the "exposure" of the solution to the rest of the graph. This is the case, for example, when the solution represents persons that ought to deal with sensitive information or a segregated community. In this work, we thus explore the (parameterized) complexity of finding such secluded vertex subsets for a wide variety of properties that they shall fulfill. More precisely, we study the constraint that the (open or closed) neighborhood of the solution shall be bounded by a parameter and the influence of this constraint on the complexity of minimizing separators, feedback vertex sets, F-free vertex deletion sets, dominating sets, and the maximization of independent sets.

In the Tree Deletion Set problem the input is a graph $G$ together with an integer $k$. The objective is to determine whether there exists a set $S$ of at most $k$ vertices such that $G\setminus S$ is a tree. The problem is \tt NP-complete and even \tt NP-hard to approximate within any factor of $\text{OPT}^c$ for any constant $c$. In this paper we give an $\mathcal{O}(k^5)$ size kernel for the Tree Deletion Set problem. An appealing feature of our kernelization algorithm is a new reduction rule, based on systems of linear equations, that we use to handle the instances on which Tree Deletion Set is hard to approximate.

In the Steiner Tree problem one is given an undirected graph, a subset T of its vertices, and an integer k and the question is whether there is a connected subgraph of the given graph containing all the vertices of T and at most k other vertices. The vertices in the subset T are called terminals and the other vertices are called Steiner vertices. Recently, Pilipczuk, Pilipczuk, Sankowski, and van Leeuwen [FOCS 2014] gave a polynomial kernel for Steiner Tree in planar graphs, when parameterized by |T|+k, the total number of vertices in the constructed subgraph. In this paper we present several polynomial time applicable reduction rules for Planar Steiner Tree. In an instance reduced with respect to the presented reduction rules, the number of terminals |T| is at most quadratic in the number of other vertices k in the subgraph. Hence, using and improving the result of Pilipczuk et al., we give a polynomial kernel for Steiner Tree in planar graphs for the parameterization by the number k of Steiner vertices in the solution.

The NP-hard Subset Interconnection Design problem, also known as Minimum Topic-Connected Overlay, is motivated by numerous applications including the design of scalable overlay networks and vacuum systems. It has as input a finite set $V$ and a collection of subsets $V_1, V_2, \ldots, V_m \subseteq V$, and asks for a minimum-cardinality edge set $E$ such that for the graph $G=(V,E)$ all induced subgraphs $G[V_1], G[V_2], \ldots, G[V_m]$ are connected. We study Subset Interconnection Design in the context of polynomial-time data reduction rules that preserve the possibility of constructing optimal solutions. Our contribution is threefold: First, we show the incorrectness of earlier polynomial-time data reduction rules. Second, we show linear-time solvability in case of a constant number $m$ of subsets, implying fixed-parameter tractability for the parameter $m$. Third, we provide a fixed-parameter tractability result for small subset sizes and tree-like output graphs. To achieve our results, we elaborate on polynomial-time data reduction rules which also may be of practical use in solving Subset Interconnection Design.

In the Tree Deletion Set problem the input is a graph G together with an integer k. The objective is to determine whether there exists a set S of at most k vertices such that G \ S is a tree. The problem is NP-complete and even NP-hard to approximate within any factor of OPT^c for any constant c. In this paper we give an O(k^5) size kernel for the Tree Deletion Set problem. An appealing feature of our kernelization algorithm is a new reduction rule, based on system of linear equations, that we use to handle the instances on which Tree Deletion Set is hard to approximate.

Assume that each of n voters may or may not approve each of m issues. If an agent (the lobby) may influence up to k voters, then the central question of the NP-hard Lobbying problem is whether the lobby can choose the voters to be influenced so that as a result each issue gets a majority of approvals. This problem can be modeled as a simple matrix modification problem: Can one replace k rows of a binary n x m-matrix by k all-1 rows such that each column in the resulting matrix has a majority of 1s? Significantly extending on previous work that showed parameterized intractability (W[2]-completeness) with respect to the number k of modified rows, we study how natural parameters such as n, m, k, or the "maximum number of 1s missing for any column to have a majority of 1s" (referred to as "gap value g") govern the computational complexity of Lobbying. Among other results, we prove that Lobbying is fixed-parameter tractable for parameter m and provide a greedy logarithmic-factor approximation algorithm which solves Lobbying even optimally if m < 5. We also show empirically that this greedy algorithm performs well on general instances. As a further key result, we prove that Lobbying is LOGSNP-complete for constant values g>0, thus providing a first natural complete problem from voting for this complexity class of limited nondeterminism.

We extend work by Christian et al. [Review of Economic Design 2007] on lobbying in multiple referenda by first providing a more fine-grained analysis of the computational complexity of the NP-complete Lobbying problem. Herein, given a binary matrix, the columns represent issues to vote on and the rows correspond to voters making a binary vote on each issue. An issue is approved if a majority of votes has a 1 in the corresponding column. The goal is to get all issues approved by modifying a minimum number of rows to all-1-rows. In our multivariate complexity analysis, we present a more holistic view on the nature of the computational complexity of Lobbying, providing both (parameterized) tractability and intractability results, depending on various problem parameterizations to be adopted. Moreover, we show non-existence results concerning efficient and effective preprocessing for Lobbying and introduce natural variants such as Restricted Lobbying and Partial Lobbying.

Poljak and Turzík (Discrete Math. 1986) introduced the notion of lambda-extendible properties of graphs as a generalization of the property of being bipartite. They showed that for any 0 < lambda < 1 and lambda-extendible property Pi, any connected graph G on n vertices and m edges contains a spanning subgraph H in Pi with at least lambda m+ (1-lambda)/2 (n-1) edges. The property of being bipartite is lambda-extendible for lambda=1/2, and thus the Poljak-Turzík bound generalizes the well-known Edwards-Erdos bound for MAXCUT. We define a variant, namely strong lambda-extendibility, to which the Poljak-Turzík bound applies. For a strong lambda-extendible graph property \Pi, we define the parameterized Above Poljak-Turzík problem as follows: Given a connected graph G on n vertices and m edges and an integer parameter k, does there exist a spanning subgraph H of G such that H in Pi and H has at least lambda m+ (1-lambda)/2 (n-1)+k edges? The parameter is k, the surplus over the number of edges guaranteed by the Poljak-Turzík bound. We consider properties Pi for which the Above Poljak-Turzík problem is fixed-parameter tractable (FPT) on graphs which are O(k) vertices away from being a graph in which each block is a clique. We show that for all such properties, Above Poljak-Turzík is FPT for all 0< lambda <1. Our results hold for properties of oriented graphs and graphs with edge labels. Our results generalize the recent result of Crowston et al. (ICALP 2012) on MAXCUT parameterized above the Edwards-Erdos, and yield FPT algorithms for several graph problems parameterized above lower bounds. For instance, we get that the above-guarantee Max q-Colorable Subgraph problem is FPT. Our results also imply that the parameterized above-guarantee Oriented Max Acyclic Digraph problem thus solving an open question of Raman and Saurabh (Theor. Comput. Sci. 2006).

We start a systematic parameterized computational complexity study of three NP-hard network design problems on arc-weighted directed graphs: directed Steiner tree, strongly connected Steiner subgraph, and directed Steiner network. We investigate their parameterized complexities with respect to the three parameterizations: “number of terminals,” “an upper bound on the size of the connecting network,” and the combination of these two. We achieve several parameterized hardness results as well as some fixed-parameter tractability results, in this way extending previous results of Feldman and Ruhl [SIAM J. Comput., 36 (2006), pp. 543–561].