Search

We study the computational complexity of k-anonymizing a given graph by as few graph contractions as possible. A graph is said to be k-anonymous if for every vertex in it, there are at least k − 1 other vertices with exactly the same degree. The general degree anonymization problem is motivated by applications in privacy-preserving data publishing, and was studied to some extent for various graph operations (most notable operations being edge addition, edge deletion, vertex addition, and vertex deletion). We complement this line of research by studying the computational complexity of degree anonymization by graph contractions. We consider several variants of graph contractions, which are operations of interest, for example, in the contexts of social networks and clustering algorithms. We show that the problem of degree anonymization by graph contractions is NP -hard even for some very restricted inputs, and identify some fixed-parameter tractable cases.

International audience; A graph is said to be k-anonymous for an integer k, if for every vertex in the graph there are at least k−1k−1 other vertices with the same degree. We examine the computational complexity of making a given undirected graph k-anonymous either through at most s vertex deletions or through at most s edge deletions; the corresponding problem variants are denoted by Anonym V-Del and Anonym E-Del. We present a variety of hardness results, most of them hold for both problems. The two variants are intractable from the parameterized as well as from the approximation point of view. In particular, we show that both variants remain NP-hard on very restricted graph classes like trees even if k=2k=2. We further prove that both variants are W[1]-hard with respect to the combined parameter solutions size s and anonymity level k . With respect to approximability, we obtain hardness results showing that neither variant can be approximated in polynomial time within a factor better than View the MathML sourcen12 (unless P=NPP=NP). Furthermore, for the optimization variants where the solution size s is given and the task is to maximize the anonymity level k , this inapproximability result even holds if we allow a running time of f(s)⋅nO(1)f(s)⋅nO(1) for any computable function f. On the positive side, we classify both problem variants as fixed-parameter tractable with respect to the combined parameter solution size s and maximum degree Δ.

Motivated by applications in privacy-preserving data publishing, we study the problem of making an undirected graph k-anonymous by adding few vertices (together with some incident edges). That is, after adding these "dummy vertices", for every vertex degree d appearing in the resulting graph, there shall be at least k vertices with degree d. We explore three variants of vertex addition (justified by real-world considerations) and study their (parameterized) computational complexity. We derive mostly intractability results, even for very restricted cases (including trees and bounded-degree graphs) but also obtain some encouraging fixed-parameter tractability results. Degree anonymization by vertex addition is computationally intractable in general.Posing structural restrictions on the edges connected to the new vertices seems to make the problem even harder.There are some tractable special cases, for example, when the number of new edges is small.

Motivated by a strongly growing interest in graph anonymization, we study the NP-hard 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 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.

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 Vector Positive Explanation , the segments may have only positive integer entries; in Vector Explanation , the segments may have arbitrary integer entries. Considering several natural parameterizations such as the maximum vector entry γ and the maximum difference δ between consecutive vector entries, we obtain a refined picture of the computational (in-)tractability of these problems. For example, we show that Vector Explanation is fixed-parameter tractable with respect to δ, and that, unless NP ⊆ coNP / poly , there is no polynomial kernelization for Vector Positive Explanation with respect to the parameter γ. We also identify relevant special cases where Vector Positive Explanation is algorithmically harder than Vector Explanation .

Given an undirected graph G=(V,E) and an integer l≥1, the NP-hard 2-Club problem asks for a vertex set S⊆V of size at least l such that the subgraph induced by S has diameter at most two. In this work, we extend previous parameterized complexity studies for 2-Club. On the positive side, we give polynomial kernels for the parameters "feedback edge set size of G" and "size of a cluster editing set of G" and present a direct combinatorial algorithm for the parameter "treewidth of G". On the negative side, we first show that unless NP⊆coNP/poly, 2-Club does not admit a polynomial kernel with respect to the "size of a vertex cover of G". Next, we show that, under the strong exponential time hypothesis, a previous O*(2|V|−l) search tree algorithm [Schafer et al., Optim. Lett. 2012] cannot be improved and that, unless NP⊆coNP/poly, there is no polynomial kernel for the dual parameter |V|−l. Finally, we show that, in spite of this lower bound, the search tree algorithm for the dual parameter |V|−l can be tuned into an efficient exact algorithm for 2-Club that substantially outperforms previous implementations.

Incrementally k-list coloring a graph means that a graph is given by adding vertices step by step, and for each intermediate step we ask for a vertex coloring such that each vertex has one of the colors specified by its associated list containing some of in total k colors. We introduce the ''conservative version'' of this problem by adding a further parameter c@?N specifying the maximum number of vertices to be recolored between two subsequent graphs (differing by one vertex). The ''conservation parameter'' c models the natural quest for a modest evolution of the coloring in the course of the incremental process instead of performing radical changes. We show that even on bipartite graphs the problem is NP-hard for k>=3 and W[1]-hard for an unbounded number of colors when parameterized by c. In contrast, also on general graphs the problem becomes fixed-parameter tractable with respect to the combined parameter (k,c). We prove that the problem has an exponential-size kernel with respect to (k,c) and there is no polynomial-size kernel unless NP@?coNP/poly. Furthermore, we investigate the parameterized complexity on various subclasses of perfect graphs. We show fixed-parameter tractability for the combined parameter treewidth and number k of colors. Finally, we provide empirical findings on the practical relevance of our approach in terms of an effective graph coloring heuristic.

Finding the origin of short phrases propagating through the web has been formalized by Leskovec et al. [ACM SIGKDD 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. We show an algorithm to solve DAG Partitioning in $O(2^k \cdot (n+m))$ time, that is, in linear time for fixed $k$. We complement it with linear-time executable data reduction rules. Our experiments show that, in combination, they can optimally solve DAG Partitioning on simulated citation networks within five minutes for $k\leq190$ and $m$ being $10^7$ and larger. We use our obtained optimal solutions to evaluate the solution quality of Leskovec et al.'s heuristic. We show that Leskovec et al.'s heuristic works optimally on trees and generalize this result by showing that DAG Partitioning is solvable in $2^{O(w^2)}\cdot n$ time if a width-$w$ tree decomposition of the input graph is given. Thus, we improve an algorithm and answer an open question of Alamdari and Mehrabian [WAW 2012]. We complement our algorithms by lower bounds on the running time of exact algorithms and on the effectivity of data reduction., Comment: A preliminary version of this article appeared at CIAC'13. Besides providing full proof details, this revised and extended version improves our O(2^k * n^2)-time algorithm to run in O(2^k * (n+m)) time and provides linear-time executable data reduction rules. Moreover, we experimentally evaluated the algorithm and compared it to known heuristics

We extend previous work on the parameterized complexity of local search for the Traveling Salesperson Problem (TSP). So far, its parameterized complexity has been investigated with respect to the distance measures (defining the local search area) “Edge Exchange” and “Max-Shift”. We perform studies with respect to the distance measures “Swap” and “r-Swap”, “Reversal” and “r-Reversal”, and “Edit”, achieving both fixed-parameter tractability and W[1]-hardness results. In particular, from the parameterized reduction showing W[1]-hardness we infer running time lower bounds (based on the exponential time hypothesis) for all corresponding distance measures. Moreover, we provide non-existence results for polynomial-size problem kernels and we show that some in general W[1]-hard problems turn fixed-parameter tractable when restricted to planar graphs.

Given an undirected graph with edge costs and edge demands, the Capacitated Arc Routing problem ( CARP ) asks for minimum-cost routes for equal-capacity vehicles so as to satisfy all demands. Constant-factor polynomial-time approximation algorithms were proposed for CARP with triangle inequality, while CARP was claimed to be NP-hard to approximate within any constant factor in general. Correcting this claim, we show that any factor α approximation for CARP with triangle inequality yields a factor α approximation for the general CARP .

Motivated by applications in privacy-preserving data publishing, we study the problem of making an undirected graph k-anonymous by adding few vertices (together with incident edges). That is, after adding these “dummy vertices”, for every vertex degree d in the resulting graph, there shall be at least k vertices with degree d. We explore three variants of vertex addition (justified by real-world considerations) and study their (parameterized) computational complexity. We derive mostly (worst-case) intractability results, even for very restricted cases (including trees or bounded-degree graphs) but also obtain a few encouraging fixed-parameter tractability results.

International audience; Co-clustering, that is partitioning a numerical matrix into " homogeneous " submatrices, has many applications ranging from bioinformatics to election analysis. Many interesting variants of co-clustering are NP-hard. We focus on the basic variant of co-clustering where the homogeneity of a submatrix is defined in terms of minimizing the maximum distance between two entries. In this context, we spot several NP-hard, as well as a number of relevant polynomial-time solvable special cases, thus charting the border of tractability for this challenging data clustering problem. For instance, we provide polynomial-time solvability when having to partition the rows and columns into two subsets each (meaning that one obtains four submatrices). When partitioning rows and columns into three subsets each, however, we encounter NP-hardness, even for input matrices containing only values from {0, 1, 2}.

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

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 .

The NP-hard 2-Club problem is, given an undirected graph G = (V,E) and a positive integer l, to decide whether there is a vertex set of size at least l that induces a subgraph of diameter at most two. We make progress towards a systematic classification of the complexity of 2-Club with respect to structural parameterizations of the input graph. Specifically, we show NP-hardness of 2-Club on graphs that become bipartite by deleting one vertex, on graphs that can be covered by three cliques, and on graphs with domination number two and diameter three. Moreover, we present an algorithm that solves 2-Club in |V| f(k) time, where k is the so-called h-index of the input graph. By showing W[1]-hardness for this parameter, we provide evidence that the above algorithm cannot be improved to a fixed-parameter algorithm. This also implies W[1]-hardness with respect to the degeneracy of the input graph. Finally, we show that 2-Club is fixed-parameter tractable with respect to “distance to co-cluster graphs” and “distance to cluster graphs”.

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.

We present a linear-time kernelization algorithm that transforms a given planar graph G with domination number γ(G) into a planar graph G′ of size O(γ(G)) with γ(G)=γ(G′). In addition, a minimum dominating set for G can be inferred from a minimum dominating set for G′. In terms of parameterized algorithmics, this implies a linear-size problem kernel for the NP-hard Dominating Set problem on planar graphs, where the kernelization takes linear time. This improves on previous kernelization algorithms that provide linear-size kernels in cubic time.

The NP-hard Metric Dimension problem is to decide for a given graph G and a positive integer k whether there is a vertex subset of size at most k that separates all vertex pairs in G. Herein, a vertex v separates a pair {u,w} if the distance (length of a shortest path) between v and u is different from the distance of v and w. We give a polynomial-time computable reduction from the Bipartite Dominating Set problem to Metric Dimension on maximum degree three graphs such that there is a one-to-one correspondence between the solution sets of both problems. There are two main consequences of this: First, it proves that Metric Dimension on maximum degree three graphs is W[2]-complete with respect to the parameter k. This answers an open question concerning the parameterized complexity of Metric Dimension posed by D\'iaz et al. [ESA'12] and already mentioned by Lokshtanov [Dagstuhl seminar, 2009]. Additionally, it implies that Metric Dimension cannot be solved in n^{o(k)} time, unless the assumption FPT \neq W[1] fails. This proves that a trivial n^{O(k)} algorithm is probably asymptotically optimal. Second, as Bipartite Dominating Set is inapproximable within o(log n), it follows that Metric Dimension on maximum degree three graphs is also inapproximable by a factor of o(log n), unless NP=P. This strengthens the result of Hauptmann et al. [JDA 2012] who proved APX-hardness on bounded-degree graphs., Comment: 15 pages, 3 figures

In graph realization problems one is given a degree sequence and the task is to decide whether there is a graph whose vertex degrees match the given sequence. This realization problem is known to be polynomial-time solvable when the graph is directed or undirected. In contrast, we show NP-completeness for the problem of realizing a given sequence of pairs of positive integers (representing indegrees and outdegrees) with a directed acyclic graph, answering an open question of Berger and Muller-Hannemann [FCT 2011]. Furthermore, we classify the problem as fixed-parameter tractable with respect to the parameter "maximum degree".

In graph realization problems one is given a degree sequence and the task is to decide whether there is a graph whose vertex degrees match to the given sequence. This realization problem is known to be polynomial-time solvable when the graph is directed or undirected. In contrary, we show NP-completeness for the problem of realizing a given sequence of pairs of positive integers (representing indegrees and outdegrees) with a directed acyclic graph, answering an open question of Berger and M\"uller-Hannemann [FCT 2011]. Furthermore, we classify the problem as fixed-parameter tractable with respect to the parameter "maximum degree"., Comment: new author Sepp Hartung, new section with fixed-parameter tractability result; 25 pages, 4 figures

We extend previous work on the parameterized complexity of local search for the Travelling Salesperson Problem (TSP). So far, its parameterized complexity has been investigated with respect to the distance measures (which define the local search area) "Edge Exchange" and "Max-Shift". We perform studies with respect to the distance measures "Swap" and "m-Swap", "Reversal" and "m-Reversal", and "Edit", achieving both fixed-parameter tractability and W[1]-hardness results. Moreover, we provide non-existence results for polynomial-size problem kernels and we show that some in general W[1]-hard problems turn fixed-parameter tractable when restricted to planar graphs.

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.