RNDr. Ondřej Suchý, Ph.D.

Článek

10.1016/j.disopt.2022.100756

Katedra teoretické informatiky

Consider a vertex-weighted graph G with a source s and a target t. TRACKING PATHS requires finding a minimum weight set of vertices (trackers) such that the sequence of trackers in each path from s to t is unique. In this work, we derive a factor 6-approximation algorithm for TRACKING PATHS in 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 related r-FAULT TOLERANT FEEDBACK VERTEX SET problem. There, for a fixed integer r and a given vertex-weighted graph G, the task is to find a minimum weight set of vertices intersecting every cycle of G in at least r+1 vertices. We give a factor O(r) approximation algorithm for r-FAULT TOLERANT FEEDBACK VERTEX SET if r is a constant.

Stať ve sborníku

10.1007/978-3-031-43380-1_12

Katedra teoretické informatiky

Many algorithms which exactly solve hard problems require branching on more or less complex structures in order to do their job. Those who design such algorithms often find themselves doing a meticulous analysis of numerous different cases in order to identify these structures and design suitable branching rules, all done by hand. This process tends to be error prone and often the resulting algorithm may be difficult to implement in practice. In this work, we aim to automate a part of this process and focus on the simplicity of the resulting implementation. We showcase our approach on the following problem. For a constant d, the d-Path Vertex Cover problem (d-PVC) is as follows: Given an undirected graph and an integer k, find a subset of at most k vertices of the graph, such that their deletion results in a graph not containing a path on d vertices as a subgraph. We develop a fully automated framework to generate parameterized branching algorithms for the problem and obtain algorithms outperforming those previously known for 3 < d < 8, e.g., we show that 5-PVC can be solved in O(2.7^kn^{O(1)}) time.

Článek

10.1016/j.artint.2023.104017

Katedra teoretické informatiky

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 some initial complexity-theoretic and existential results concerning Nash and individually stable outcomes. Here, we design new algorithms accompanied with lower bounds which provide a comprehensive 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).

Stať ve sborníku

10.4204/EPTCS.379.22

Katedra teoretické informatiky

Social distance games have been extensively studied as a coalition formation model where the utilities of agents in each coalition were captured using a utility function u that took into account distances in a given social network. In this paper, we consider a non-normalized score-based definition of social distance games where the utility function u_v depends on a generic scoring vector v, which may be customized to match the specifics of each individual application scenario. As our main technical contribution, we establish the tractability of computing a welfare-maximizing partitioning of the agents into coalitions on tree-like networks, for every score-based function u_v. We provide more efficient algorithms when dealing with specific choices of u_v or simpler networks, and also extend all of these results to computing coalitions that are Nash stable or individually rational. We view these results as a further strong indication of the usefulness of the proposed score-based utility function: even on very simple networks, the problem of computing a welfare-maximizing partitioning into coalitions remains open for the originally considered canonical function u.

Článek

10.1007/s00453-022-01006-x

Katedra teoretické informatiky

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 treewidth with the desired eccentricity, and maximum leaf number.

Článek

10.1016/j.ipl.2022.106315

Katedra teoretické informatiky

Given an undirected graph G = (V , E), vertices s,t ∈ V , and an integer k, Tracking Shortest Paths requires deciding whether there exists a set of k vertices T ⊆ V such that for any two distinct shortest paths between s and t, say P1 and P2, we have T ∩ V (P1) != T ∩ V (P2). In this paper, we give the first polynomial size kernel for the problem. Specifically we show the existence of a kernel with O(k2) vertices and edges in general graphs and a kernel with O(k) vertices and edges in planar graphs for the Tracking Paths in DAG problem. This problem admits a polynomial parameter transformation to Tracking Shortest Paths, and this implies a kernel with O(k4) vertices and edges for Tracking Shortest Paths in general graphs and a kernel with O(k2) vertices and edges in planar graphs. Based on the above we also give a single exponential algorithm for Tracking Shortest Paths in planar graphs.

Stať ve sborníku

10.4230/LIPIcs.IPEC.2023.7

Katedra teoretické informatiky

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.

Stať ve sborníku

Katedra teoretické informatiky

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.

Stať ve sborníku

Katedra teoretické informatiky

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).

Stať ve sborníku

10.4230/LIPIcs.MFCS.2022.29

Katedra teoretické informatiky

In this paper we study the kernelization of the d-Path Vertex Cover (d-PVC) problem. Given a graph G, the problem requires finding whether there exists a set of at most k vertices whose removal from G results in a graph that does not contain a path (not necessarily induced) with d vertices. It is known that d-PVC is NP-complete for d≥ 2. Since the problem generalizes to d-Hitting Set, it is known to admit a kernel with O(dk^d) edges. We improve on this by giving better kernels. Specifically, we give kernels with O(k^2) vertices and edges for the cases when d = 4 and d = 5. Further, we give a kernel with O(k^4d^{2d+9}) vertices and edges for general d.

Stať ve sborníku

10.4230/LIPIcs.ESA.2022.22

Katedra teoretické informatiky

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.

Článek

10.1016/j.ipl.2021.106165

Katedra teoretické informatiky

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 2^{O(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

Článek

10.1007/s00224-021-10045-w

Katedra teoretické informatiky

We study the NP-hard graph problem Collapsed k-Core where, given an undirected graph G and integers b, x, and k, we are asked to remove b vertices such that the k-core of remaining graph, that is, the (uniquely determined) largest induced subgraph with minimum degree k, has size at most x. Collapsed k-Core was 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-Core is a generalization of r-Degenerate Vertex Deletion (which is known to be NP-hard for all r >= 0) where, given an undirected graph G and integers b and r, we are asked to remove b vertices such that the remaining graph is r-degenerate, that is, every its subgraph has minimum degree at most r. We investigate the parameterized complexity of Collapsed k-Core with respect to the parameters b, x, and k, and several structural parameters of the input graph. We reveal a dichotomy in the computational complexity of Collapsed k-Core for k <= 2 and k >= 3. For the latter case it is known that for all x >= 0 Collapsed k-Core is W[P]-hard when parameterized by b. For k <= 2 we show that Collapsed k-Core is W[1]-hard when parameterized by b and in FPT when parameterized by (b + x). Furthermore, we outline that Collapsed k-Core is in FPT 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.

Stať ve sborníku

10.1007/978-3-030-92702-8_2

Katedra teoretické informatiky

Consider a vertex-weighted graph G with a source s and a target t. Tracking Paths requires finding a minimum weight set of vertices (trackers) such that the sequence of trackers in each path from s to t is unique. In this work, we derive a factor 66-approximation algorithm for Tracking Paths in 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 related r -Fault Tolerant Feedback Vertex Set problem. There, for a fixed integer r and a given vertex-weighted graph G, the task is to find a minimum weight set of vertices intersecting every cycle of G in at least r+1 vertices. We give a factor O(r^2) approximation algorithm for r -Fault Tolerant Feedback Vertex Set if r is a constant.

Stať ve sborníku

10.1007/978-3-030-79987-8_31

Katedra teoretické informatiky

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.

Stať ve sborníku

10.4230/LIPIcs.IPEC.2018.7

Katedra teoretické informatiky

We study the NP-hard graph problem Collapsed k-Core where, given an undirected graph G and integers b, x, and k, we are asked to remove b vertices such that the k-core of remaining graph, that is, the (uniquely determined) largest induced subgraph with minimum degree k, has size at most x. Collapsed k-Core was introduced by Zhang et al. [AAAI 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-Core is a generalization of r-Degenerate Vertex Deletion (which is known to be NP-hard for all r >=0) where, given an undirected graph G and integers b and r, we are asked to remove b vertices such that the remaining graph is r-degenerate, that is, every its subgraph has minimum degree at most r. We investigate the parameterized complexity of Collapsed k-Core with respect to the parameters b, x, and k, and several structural parameters of the input graph. We reveal a dichotomy in the computational complexity of Collapsed k-Core for k <=2 and k >= 3. For the latter case it is known that for all x >= 0 Collapsed k-Core is W[P]-hard when parameterized by b. We show that Collapsed k-Core is W[1]-hard when parameterized by b and in FPT when parameterized by (b+x) if k <=2. Furthermore, we show that Collapsed k-Core is in FPT 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.

Článek

10.1007/s00453-019-00580-x

Katedra teoretické informatiky

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 T. The question is whether we can orient the undirected edges in a way such that there is a directed s?t path for each terminal pair (s,t)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 nO(k) time for all k1. Pilipczuk and Wahlstrom [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)no(k/logk) algorithm for any computable functionf. In this paper, we give a short and easy proof that the nO(k) algorithm of Cygan etal. 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)no(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 ?>0 such that Planar Steiner Orientation admits an -approximation in FPT time, i.e., no f(k)no(k) time algorithm can distinguish between the case when all k pairs are satisfiable versus the case when less than k pairs are satisfiable. To the best of our knowledge, this is the first FPT inapproximability result on planar graphs.

Stať ve sborníku

10.4230/LIPIcs.STACS.2019.25

Katedra teoretické informatiky

In the Directed Steiner Network problem we are given an arc-weighted digraph G, a set of terminals $T\subseteq V(G)$ with |T|=q, and an (unweighted) directed request graph R with V(R)=T. Our task is to output a subgraph $H \subseteq G$ of the minimum cost such that there is a directed path from s to t in H 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 the Exponential-Time Hypothesis (ETH) fails [Chitnis et al., SODA 2014]. However, the reduction (and other reductions showing hardness of the problem) only shows that the problem cannot be solved in time $|V(G)|^{o(q)}$, unless ETH fails. Therefore, there is a significant gap in the complexity with respect to q in the exponent. We show that \textsc{Directed Steiner Network} is solvable in time $f(q)\cdot |V(G)|^{O(c_g \cdot q)}$, 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(q)\cdot |V(G)|^{o(q^2/ \log q)}$ algorithm for any function f for the problem on general graphs, unless ETH fails.

Stať ve sborníku

10.1007/978-3-030-34029-2_19

Katedra teoretické informatiky

We consider the subgraph isomorphism problem where, given two graphs G (source graph) and F (pattern graph), one is to decide whether there is a (not necessarily induced) subgraph of G isomorphic to F. While many practical heuristic algorithms have been developed for the problem, as pointed out by McCreesh et al. [JAIR 2018], for each of them there are rather small instances which they cannot cope. Therefore, developing an alternative approach that could possibly cope with these hard instances would be of interest. A seminal paper by Alon, Yuster and Zwick [J. ACM 1995] introduced the color coding approach to solve the problem, where the main part is a dynamic programming over color subsets and partial mappings. As with many exponential-time dynamic programming algorithms, the memory requirements constitute the main limiting factor for its usage. Because these requirements grow exponentially with the treewidth of the pattern graph, all existing implementations based on the color coding principle restrict themselves to specific pattern graphs, e.g., paths or trees. In contrast, we provide an efficient implementation of the algorithm significantly reducing its memory requirements so that it can be used for pattern graphs of larger treewidth. Moreover, our implementation not only decides the existence of an isomorphic subgraph, but it also enumerates all such subgraphs (or given number of them). We provide an extensive experimental comparison of our implementation to other available solvers for the problem.

Stať ve sborníku

10.4230/LIPIcs.MFCS.2019.32

Katedra teoretické informatiky

The problem of \textsc{$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 \textsc{$d$-PVC} problem is NP-complete for any $d \ge 2$. When parameterized by the size of the solution $k$, \textsc{5-PVC} has direct trivial algorithm with $\mathcal{O}(5^kn^{\mathcal{O}(1)})$ running time and, since \textsc{$d$-PVC} is a special case of \textsc{$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 \textsc{5-PVC} problem in $\mathcal{O}(4^kn^{\mathcal{O}(1)})$ time.

Stať ve sborníku

10.4230/LIPIcs.ISAAC.2018.24

Katedra teoretické informatiky

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.

Článek

10.1016/j.disopt.2018.05.002

Katedra teoretické informatiky

This work studies the parameterized complexity of finding secluded solutions to classical combinatorial optimization problems on graphs such as finding minimum - separators, feedback vertex sets, dominating sets, maximum independent sets, and vertex Herein, one searches not only to minimize or maximize the size of the solution, but also to minimize the size of its neighborhood. This restriction has applications in secure routing and community detection.

Článek

10.1007/s10951-016-0478-9

Katedra teoretické informatiky

We study the problem of non-preemptively scheduling n jobs, each job j with a release time , a deadline , and a processing time , on m parallel identical machines. Cieliebak et al. (2004) considered the two constraints and and showed the problem to be NP-hard for any and for any . We complement their results by parameterized complexity studies: we show that, for any , the problem remains weakly NP-hard even for and strongly W[1]-hard parameterized by m. We present a pseudo-polynomial-time algorithm for constant m and and a fixed-parameter tractability result for the parameter m combined with sigma.

Stať ve sborníku

10.1007/978-3-319-72453-9_28

Katedra teoretické informatiky

The pattern matching problem with swaps is to find all occurrences of a pattern in a text while allowing the pattern to swap adjacent symbols. The goal is to design fast matching algorithm that takes advantage of the bit parallelism of bitwise machine instructions and has only streaming access to the input. We introduce a new approach to solve this problem based on the graph theoretic model and compare its performance to previously known algorithms. We also show that an approach using deterministic finite automata cannot achieve similarly efficient algorithms. Furthermore, we describe a fatal flaw in some of the previously published algorithms based on the same model. Finally, we provide experimental evaluation of our algorithm on real-world data.

Článek

10.1007/s00453-016-0249-1

Katedra teoretické informatiky

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 et al. (55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, 2014) gave a polynomial kernel for Steiner Tree in planar graphs and graphs of bounded genus, when parameterized by , the total number of vertices in the constructed subgraph. In this paper we present several polynomial time applicable reduction rules for Steiner Tree in graphs of bounded genus. In an instance reduced with respect to the presented reduction rules, the number of terminals |T| is at most cubic 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 graphs of bounded genus for the parameterization by the number k of Steiner vertices in the solution. We give better bounds for Steiner Tree in planar graphs.

Stať ve sborníku

10.4230/LIPIcs.IPEC.2016.5

Katedra teoretické informatiky

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, -free vertex deletion sets, dominating sets, and the maximization of independent sets.

Článek

10.1016/j.dam.2016.12.002

Katedra teoretické informatiky

Finding the origin of short phrases propagating through the web has been formalized by Leskovec et al. (2009) as DAG PARTITIONING: given an arc-weighted directed acyclic graph on n vertices and m arcs, delete arcs with total weight at most k such that each resulting weakly-connected component contains exactly one sink-a vertex without outgoing arcs. DAG PARTITIONING iS NP-hard.

Článek

10.1137/15M103618X

Katedra teoretické informatiky

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.

Stať ve sborníku

10.1007/978-3-662-53536-3_22

Katedra teoretické informatiky

We introduce a new Steiner-type problem for directed graphs named q-Root Steiner Tree. Here one is given a directed graph G = (V, A) and two subsets of its vertices, R of size q and T, and the task is to find a minimum size subgraph of G that contains a path from each vertex of R to each vertex of T. The special case of this problem with q = 1 is the well known Directed Steiner Tree problem, while the special case with T = R is the Strongly Connected Steiner Subgraph problem. We first show that the problem is W[1]-hard with respect to |T| for any q >= 2. Then we restrict ourselves to instances with R \subseteq T (Pedestal version). Generalizing the methods of Feldman and Ruhl [SIAM J. Comput. 2006], we present an algorithm for this restriction with running time O(2^{2q+4|T|}* n^{2q+O(1)}), i.e., this restriction is FPT with respect to |T| for any constant q. We further show that we can, without significantly affecting the achievable running time, loosen the restriction to only requiring that in the solution there is a vertex v and a path from each vertex of R to v and from v to each vertex of T (Trunk version). Finally, we use the methods of Chitnis et al. [SODA 2014] to show that the Pedestal version can be solved in planar graphs in O(2^{O(q \log q+|T|\log q)}\cdot n^{O(\sqrt{q})}) time.

Článek

10.1137/15M1038876

Katedra teoretické informatiky

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 systems of linear equations, that we use to handle the instances on which Tree Deletion Set is hard to approximate.

Článek

10.1016/j.ic.2014.12.017

Katedra teoretické informatiky

Motivated by a strongly growing interest in graph anonymization in the data mining and databases communities, we study the NP-hard textsc{Degree Anonymity} problem asking whether a graph can be made $k$-anonymous by adding at most a given number of edges. Herein, a graph is $k$-anonymous if for every vertex in the graph there are at least $k-1$~other vertices of the same degree. Our algorithmic results shed light on the performance quality of a popular heuristic due to Liu and Terzi~[ACM SIGMOD~2008]; in particular, we show that the heuristic provides optimal solutions if ``many'' edges need to be added. Based on this, we develop a polynomial-time data reduction yielding a polynomial-size problem kernel for textsc{Degree Anonymity} parameterized by the maximum vertex degree. In terms of parameterized complexity analysis, this result is in a sense tight since we also show that the problem is already NP-hard for H-index three, implying NP-hardness for smaller parameters such as average degree and degeneracy.

Stať ve sborníku

10.4230/LIPIcs.IPEC.2015.151

Katedra teoretické informatiky

In the textsc{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 textsc{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 textsc{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 textsc{Steiner Tree} in planar graphs for the parameterization by the number~$k$ of Steiner vertices in the solution.

Článek

10.1016/j.jcss.2014.12.028

Katedra teoretické informatiky

We extend previous studies on ``explaining'' a nonnegative integer vector by sums of few homogeneous segments, that is, vectors where all nonzero entries are equal and consecutive. We study two NP-complete variants which are motivated by radiation therapy and database applications. In textsc{Vector Positive Explanation}, the segments may have only positive integer entries; in textsc{Vector Explanation}, the segments may have arbitrary integer entries. Considering several natural parameterizations such as the maximum vector entry~$gamma$ and the maximum difference~$delta$ between consecutive vector entries, we obtain a refined picture of the computational (in-)tractability of these problems. For example, we show that textsc{Vector Explanation} is fixed-parameter tractable with respect to~$delta$, and that, unless $text{NP}subseteq text{{coNP/poly}}$, there is no polynomial kernelization for textsc{Vector Positive Explanation} with respect to the parameter~$gamma$. We also identify relevant special cases where textsc{Vector Positive Explanation} is~algorithmically~harder than~textsc{Vector Explanation}.

Článek

10.1016/j.dam.2014.11.026

Katedra teoretické informatiky

The NP-hard textsc{$s$-Club} problem is, given an undirected graph $G=(V,E)$ and~$ell in mathbb{N}$, to decide whether there is a vertex set~$Ssubseteq V$ of size at least~$ell$ such that the induced subgraph~$G[S]$ has diameter at most two. We make progress towards a systematic classification of the complexity of textsc{$s$-Club} with respect to a hierarchy of prominent structural graph parameters. First, we present the following tight NP-hardness results: textsc{$s$-Club} is NP-hard on graphs that become bipartite by deleting one vertex, on graphs that can be covered by three cliques, and on graphs with emph{domination number} two and emph{diameter} three. Then, we consider the parameter emph{$h$-index} of the input graph. The study of this parameter is motivated by real-world instances and the fact that textsc{$s$-Club} is fixed-parameter tractable when parameterized by the larger parameter emph{maximum degree}. We present an algorithm that solves textsc{$s$-Club} in~$|V|^{f(k)}$ time with~$k$ being the emph{$h$-index}. By showing W[1]-hardness for this parameter, we provide evidence that the above algorithm cannot be improved to a fixed-parameter algorithm. Furthermore, the reduction used for this hardness result can be modified to show that textsc{$s$-Club} is NP-hard if the input graph has constant emph{degeneracy}. Finally, we show that textsc{$s$-Club} is fixed-parameter tractable when parameterized by emph{distance~to~cographs}.

Článek

10.1007/s00224-014-9557-5

Katedra teoretické informatiky

A balanced partition is a clustering of a graph into a given number of equal-sized parts. For instance, the textsc{Bisection} problem asks to remove at most $k$ edges in order to partition the vertices into two equal-sized parts. We prove that textsc{Bisection} is FPT for the distance to constant cliquewidth if we are given the deletion set. This implies FPT algorithms for some well-studied parameters such as cluster vertex deletion number and feedback vertex set. However, we show that textsc{Bisection} does not admit polynomial-size kernels for these parameters. For the textsc{Vertex Bisection} problem, vertices need to be removed in order to obtain two equal-sized parts. We show that this problem is FPT for the number of removed vertices $k$ if the solution cuts the graph into a constant number $c$ of connected components. The latter condition is unavoidable, since we also prove that textsc{Vertex Bisection} is W[1]-hard w.r.t.~$(k,c)$. Our algorithms for finding bisections can easily be adapted to finding partitions into $d$~equal-sized parts, which entails additional running time factors of~$n^{O(d)}$. We show that a substantial speed-up is unlikely since the corresponding task is W[1]-hard w.r.t.~$d$, even on forests of maximum degree two. We can, however, show that it is FPT for the vertex cover number.

Článek

10.1137/140955057

Katedra teoretické informatiky

The NP-hard textsc{Subset Interconnection Design} problem, also known as textsc{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 textsc{Subset Interconnection Design} in the context of polynomial-time data reduction rules that preserve the possibility to construct 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 textsc{Subset Interconnection Design}.

Článek

10.1613/jair.4285

Katedra teoretické informatiky

Assume that each of n voters may or may not approve each of m issues. If an actor (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 set k rows of a binary n x m-matrix to 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 the natural parameters such 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 optimally if m <= 4. 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 >= 1, thus providing a first natural complete problem from voting for this complexity class of limited nondeterminism.

Článek

10.1016/j.jcss.2014.04.011

Katedra teoretické informatiky

We define strong λ-extendibility as a variant of the notion of λ-extendible properties of graphs (Poljak and Turzík, Discrete Mathematics, 1986). We show that the parameterized APT(Π) problem—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∈Π and H has at least λm+(1−λ)/2*(n−1)+k edges—is fixed-parameter tractable (FPT) for all 0<λ<1, for all strongly λ-extendible graph properties Π for which the APT(Π) problem is FPT on graphs which are O(k) vertices away from being a graph in which each block is a clique. Our results hold for properties of oriented graphs and graphs with edge labels, generalize the recent result of Crowston et al. (ICALP 2012) on Max-Cut parameterized above the Edwards–Erdős bound, and yield FPT algorithms for several graph problems parameterized above lower bounds.

Stať ve sborníku

10.1007/978-3-662-44777-2_55

Katedra teoretické informatiky

In the Multicut problem, we are given an undirected graph G=(V,E) and a family T = {(s_i, t_i) | s_i, t_i in V} of pairs of requests and the objective is to find a minimum sized set S⊆V such that every connected component of G-S contains at most one of s_i and t_i for any pair (s_i, t_i) in T. In this paper we give the first non-trivial algorithm for Multicut running in time O(1.987^n).

Stať ve sborníku

10.4230/LIPIcs.FSTTCS.2014.85

Katedra teoretické informatiky

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.

Stať ve sborníku

10.1007/978-3-642-39212-2_52

Katedra teoretické informatiky

Motivated by a strongly growing interest in graph anonymization in the data mining and databases communities, we study the NP-hard problem of making a graph k-anonymous by adding as few edges as possible. Herein, a graph is k-anonymous if for every vertex in the graph there are at least k − 1 other vertices of the same degree. Our algorithmic results shed light on the performance quality of a popular heuristic due to Liu and Terzi [ACM SIGMOD 2008]; in particular, we show that the heuristic provides optimal solutions in case that many edges need to be added. Based on this, we develop a polynomial-time data reduction, yielding a polynomial-size problem kernel for the problem parameterized by the maximum vertex degree. This result is in a sense tight since we also show that the problem is already NP-hard for H-index three, implying NP-hardness for smaller parameters such as average degree and degeneracy.

Článek

10.7155/jgaa.00308

Katedra teoretické informatiky

We give a~$5^k n^{O(1)}$ time fixed-parameter algorithm for determining whether a given undirected graph on~$n$ vertices has a subset of at most~$k$ vertices whose deletion results in a tree. Such a subset is a restricted form of a feedback vertex set. While parameterized complexity of feedback vertex set problem and several of its variations have been well studied, to the best of our knowledge, this is the first fixed-parameter algorithm for this version of feedback vertex set.

Stať ve sborníku

10.1007/978-3-642-36065-7_27

Katedra teoretické informatiky

We give a $5^k n^{O(1)}$ fixed-parameter algorithm for determining whether a given undirected graph on $n$ vertices has a subset of at most $k$ vertices whose deletion results in a tree. Such a subset is a restricted form of a feedback vertex set. While parameterized complexity of feedback vertex set problem and several of its variations have been well studied, to the best of our knowledge, this is the first fixed-parameter algorithm for this version of feedback vertex set.

Stať ve sborníku

10.1007/978-3-642-45030-3_34

Katedra teoretické informatiky

The NP-hard Subset Interconnection Design problem is motivated by applications in designing vacuum systems and scalable overlay networks. It has as input a set V and a collection of subsets V1, V2, . . . ,Vm, and asks for a minimum-cardinality edge set E such that for the graph G = (V,E) all induced subgraphs G[V1],G[V2], . . . , G[Vm] are connected. It has also been studied under the name Minimum Topic-Connected Overlay. We study Subset Interconnection Design in the context of polynomial-time data reduction rules that preserve optimality. Our contribution is threefold: First, we point out flaws in earlier polynomial-time data reduction rules. Second, we provide a fixed-parameter tractability result for small subset sizes and tree-like output graphs. Third, we show linear-time solvability in case of a constant number m of subsets, implying fixed-parameter tractability for the parameter m. To achieve our results, we elaborate on polynomial-time data reduction rules (partly “repairing” previous flawed ones) which also may be of practical use in solving Subset Interconnection Design.

Stať ve sborníku

10.1007/978-3-642-40104-6_18

Katedra teoretické informatiky

We extend previous studies on NP-hard problems dealing with the decomposition of nonnegative integer vectors into sums of few homogeneous segments. These problems are motivated by radiation therapy and database applications. If the segments may have only positive integer entries, then the problem is called Vector Explanation+. If arbitrary integer entries are allowed in the decomposition, then the problem is called Vector Explanation. Considering several natural parameterizations (including maximum vector entry, maximum difference between consecutive vector entries, maximum segment length), we obtain a refined picture of the computational (in-)tractability of these problems. In particular, we show that in relevant cases Vector Explanation+ is algorithmically harder than Vector Explanation.

Stať ve sborníku

10.1007/978-3-642-45043-3_8

Katedra teoretické informatiky

The Bisection problem asks for a partition of the vertices of a graph into two equally sized sets, while minimizing the cut size. This is the number of edges connecting the two vertex sets. Bisection has been thoroughly studied in the past. However, only few results have been published that consider the parameterized complexity of this problem. We show that Bisection is FPT w.r.t. the minimum cut size if there is an optimum bisection that cuts into a given constant number of connected components. Our algorithm applies to the more general Balanced Biseparator problem where vertices need to be removed instead of edges. We prove that this problem is W[1]-hard w.r.t. the minimum cut size and the number of cut out components. For Bisection we further show that no polynomial-size kernels exist for the cut size parameter. In fact, we show this for all parameters that are polynomial in the input size and that do not increase when taking disjoint unions of graphs. We prove fixed-parameter tractability for the distance to constant cliquewidth if we are given the deletion set. This implies fixed-parameter algorithms for some well-studied parameters such as cluster vertex deletion number and feedback vertex set.

Stať ve sborníku

10.1007/978-3-642-38233-8_5

Katedra teoretické informatiky

The goal of tracking the origin of short, distinctive phrases (memes) that propagate through the web in reaction to current events has been formalized as DAG Partitioning: given a directed acyclic graph, delete edges of minimum weight such that each resulting connected component of the underlying undirected graph contains only one sink. Motivated by NP-hardness and hardness of approximation results, we consider the parameterized complexity of this problem. We show that it can be solved in $O(2^k cdot n^2)$ time, where $k$ is the number of edge deletions, proving fixed-parameter tractability for parameter $k$. We then show that unless the Exponential Time Hypothesis (ETH) fails, this cannot be improved to $2^{o(k)} cdot n^{O(1)}$; further, DAG Partitioning does not have a polynomial kernel unless NP ⊆ coNP/poly. Finally, given a tree decomposition of width $w$, we show how to solve DAG Partitioning in $2^{O(w^2)} cdot n$ time, improving a known algorithm for the parameter pathwidth.

Stať ve sborníku

10.1007/978-3-642-40450-4_57

Katedra teoretické informatiky

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 non-terminals 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 non-terminals in the solution tree. Specifically, we show that the problem is fixed parameter tractable 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 required to be acyclic then the problem becomes FPT on graphs of bounded degeneracy. We also show that our algorithm achieves the best possible 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.

Stať ve sborníku

10.4230/LIPIcs.FSTTCS.2012.412

Katedra teoretické informatiky

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).