检索结果-内蒙古大学图书馆

The complexity of degree anonymization by vertex addition

THEORETICAL COMPUTER SCIENCE 2015年第Part1期607卷 16-34页

作者： Bredereck, Robert Froese, Vincent Hartung, Sepp Nichterlein, Andre Niedermeier, Rolf Talmon, Nimrod TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany

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. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Graph modification Degree-constrained editing NP-hardness parameterized complexity Fixed-parameter tractability Kernelization

来源：评论

学校读者我要写书评

暂无评论

On families of categorial grammars of bounded value, their learnability and related complexity questions

引用

THEORETICAL COMPUTER SCIENCE 2012年 452卷 21-38页

作者： Florencio, Christophe Costa Fernau, Henning Univ Amsterdam Inst Informat ILPS Amsterdam Netherlands Univ Trier FB 4 Abt Informat D-54286 Trier Germany

In Kanazawa (1998) [1], the learnability of several parameterized families of categorial grammar classes was studied. These classes were shown to be learnable in the technical sense of identifiability in the limit from positive data. They are defined in terms of bounds on parameters of the grammars which intuitively correspond to restrictions on linguistic aspects, such as the amount of lexical ambiguity. The time complexity of learning these classes has been studied in Costa Florncio (2003) [2]. It was shown that, for most of these classes, selecting a grammar from the class that is consistent with given data is NP-hard. In this paper existing complexity results are sharpened by demonstrating W[2]-hardness. Additionally, parameters are defined that allow FPT-results;roughly, this implies that if these parameters are fixed, these problems become tractable. We also define the new family G(k-sum-val), which is natural from the viewpoints of parameterized complexity, a flourishing area of complexity Theory (see Downey and Fellows (1999) [3]) and from Descriptional complexity, a sub-area of Formal Language Theory (see Holzer and Kutrib (2010) [4]). We prove its learnability, analyze its relation to other classes from the literature and prove a hierarchy theorem. This approach is then generalized to a parameterized family defined in terms of a bound on the descriptional complexity expressed as a Holder norm. We show that both the hierarchy result and the property of finite elasticity (and thus learnability) are preserved under this generalization. (c) 2012 Elsevier B.V. All rights reserved.

关键词： Grammar induction Identification in the limit Finite elasticity parameterized complexity Categorial grammar Regular tree languages Holder norms

来源：评论

学校读者我要写书评

暂无评论

FPT algorithms for packing k-safe spanning rooted sub(di)graphs☆

引用

DISCRETE APPLIED MATHEMATICS 2024年 346卷 80-94页

作者： Bessy, Stephane Hoersch, Florian Maia, Ana Karolinna Rautenbach, Dieter Sau, Ignasi Univ Montpellier LIRMM CNRS Montpellier France CISPA Helmholtz Ctr Informat Secur Saarbrucken Germany Univ Fed Ceara Dept Computacao Fortaleza Brazil Ulm Univ Inst Optimizat & Operat Res Ulm Germany

We study three problems introduced by Bang-Jensen and Yeo (2015) and by Bang-Jensen et al. (2016) about finding disjoint "balanced"spanning rooted substructures in graphs and digraphs, which generalize classic packing problems such as detecting the existence of multiple arc-disjoint spanning arborescences. Namely, given a positive integer k, a digraph D = (V, A), and a root r is an element of V, we first consider the problem of finding two arc-disjoint k-safe spanning r-arborescences, meaning arborescences rooted at a vertex r such that deleting any arc rv and every vertex in the sub-arborescence rooted at v leaves at least k vertices. Then, we consider the problem of finding two arc-disjoint (r, k)-flow branchings meaning arc sets admitting a flow that distributes one unit from r to every other vertex while respecting a capacity limit of n - k on every arc. We show that both these problems are FPT with parameter k, improving on existing XP algorithms. The latter of these results answers a question of Bang-Jensen et al. (2016). Further, given a positive integer k, a graph G = (V, E), and r is an element of V, we consider the problem of finding two edge-disjoint (r, k)-safe spanning trees meaning spanning trees such that the component containing r has size at least k when deleting any vertex different from r. We show that this problem is also FPT with parameter k, again improving on a previous XP algorithm. Our main technical contribution is to prove that the existence of such spanning substructures is equivalent to the existence of substructures with size and maximum (out-)degree both bounded by a (linear or quadratic) function of k, which may be of independent interest.

关键词： Digraphs Packing problems Arborescences Branching flows Safe spanning trees parameterized complexity Fixed-parameter tractability

来源：评论

学校读者我要写书评

暂无评论

Combinatorial optimization with interaction costs: complexity and solvable cases

引用

DISCRETE OPTIMIZATION 2019年 33卷 101-117页

作者： Lendl, Stefan Custic, Ante Punnen, Abraham P. Graz Univ Technol Inst Discrete Math Steyrergasse 30 A-8010 Graz Austria Simon Fraser Univ Surrey Dept Math 250-13450 102nd AV Surrey BC V3T 0A3 Canada

We introduce and study the combinatorial optimization problem with interaction costs (COPIC). COPIC is the problem of finding two combinatorial structures, one from each of two given families, such that the sum of their independent linear costs and the interaction costs between elements of the two selected structures is minimized. COPIC generalizes the quadratic assignment problem and many other well studied combinatorial optimization problems, and hence covers many real world applications. We show how various topics from different areas in the literature can be formulated as special cases of COPIC. The main contributions of this paper are results on the computational complexity and approximability of COPIC for different families of combinatorial structures (e.g. spanning trees, paths, matroids), and special structures of the interaction costs. More specifically, we analyze the complexity if the interaction cost matrix is parameterized by its rank and if it is a diagonal matrix. Also, we determine the structure of the intersection cost matrix, such that COPIC is equivalent to independently solving linear optimization problems for the two given families of combinatorial structures. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Quadratic combinatorial optimization Computational complexity Parametric optimization parameterized complexity Fixed-rank matrix Linearization

来源：评论

学校读者我要写书评

暂无评论

Multistage graph problems on a global budget

引用

THEORETICAL COMPUTER SCIENCE 2021年 868卷 46-64页

作者： Heeger, Klaus Himmel, Anne-Sophie Kammer, Frank Niedermeier, Rolf Renken, Malte Sajenko, Andrej TU Berlin Fac 4 Algorithm & Computat Complex Berlin Germany Univ Appl Sci Mittelhessen THM Giessen Germany

Time-evolving or temporal graphs gain more and more popularity when exploring complex networks. In this context, the multistage view on computational problems is among the most natural frameworks. Roughly speaking, herein one studies the different (time) layers of a temporal graph (effectively meaning that the edge set may change over time, but the vertex set remains unchanged), and one searches for a solution of a given graph problem for each layer. The twist in the multistage setting is that the solutions found must not differ too much between subsequent layers. We relax on this already established notion by introducing a global instead of the local budget view studied so far. More specifically, we allow for few disruptive changes between subsequent layers but request that overall, that is, summing over all layers, the degree of change is moderate. Studying several classical graph problems (both NP-hard and polynomial-time solvable ones) from a parameterized complexity angle, we encounter both fixed-parameter tractability and parameterized hardness results. Surprisingly, we find that sometimes the global multistage versions of NP-hard problems such as VERTEX COVER turn out to be computationally more tractable than the ones of polynomial-time solvable problems such as MATCHING. In addition to time complexity, we also analyze the space efficiency of our algorithms. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Temporal graphs Time-varying graphs NP-hardness parameterized complexity Multivariate algorithmics Space complexity

来源：评论

学校读者我要写书评

暂无评论

Hitting minors on bounded treewidth graphs. III. Lower bounds

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2020年第0期109卷 56-77页

作者： Baste, Julien Sau, Ignasi Thilikos, Dimitrios M. Univ Montpellier LIRMM Montpellier France Sorbonne Univ LIP6 Lab Informat Paris 6 Paris France Ulm Univ Inst Optimizat & Operat Res Ulm Germany Univ Montpellier CNRS LIRMM AIGCo Project Team Montpellier France

For a finite fixed collection of graphs the F-M-DELETION problem consists in, given a graph G and an integer k, decide whether there exists S subset of V (G) with vertical bar S vertical bar <= k such that G \ S does not contain any of the graphs in F as a minor. We provide lower bounds under the ETH on the smallest function f(F) such that F-M -DELETION can be solved in time f(F)(tw) . n(O(1)) on n-vertex graphs, where tw denotes the treewidth of G. We first prove that for any F containing connected graphs of size at least two, f(F)(tw) = 2(Omega(tw)), even if G is planar. Our main result is that if F contains a single connected graph H that is either P-5 tw or is not a minor of the banner, then f(F)(tw) = 2(Omega(*** tw)). (C) 2019 Elsevier Inc. All rights reserved.

关键词： parameterized complexity Graph minors Treewidth Hitting minors Topological minors Dynamic programming Exponential Time Hypothesis

来源：评论

学校读者我要写书评

暂无评论

Computing the chromatic number using graph decompositions via matrix rank

引用

THEORETICAL COMPUTER SCIENCE 2019年 795卷 520-539页

作者： Jansen, Bart M. P. Nederlof, Jesper Eindhoven Univ Technol Dept Math & Comp Sci POB 513 NL-5600 MB Eindhoven Netherlands

Computing the smallest number q such that the vertices of a given graph can be properly q-colored, known as the chromatic number, is one of the oldest and most fundamental problems in combinatorial optimization. The q-COLORING problem has been studied intensively using the framework of parameterized algorithmics, resulting in a very good understanding of the best-possible algorithms for several parameterizations based on the structure of the graph. For example, algorithms are known to solve the problem on graphs of treewidth tw in time O*q(tw)), while a running time of O*((q - epsilon)(tw)) is impossible assuming the Strong Exponential Time Hypothesis (SETH). While there is an abundance of work for parameterizations based on decompositions of the graph by vertex separators, almost nothing is known about parameterizations based on edge separators. We fill this gap by studying q-COLORING parameterized by cutwidth, and parameterized by pathwidth in bounded-degree graphs. Our research uncovers interesting new ways to exploit small edge separators. We present two algorithms for q-COLORING parameterized by cutwidth ctw: a deterministic one that runs in time O*(2(***)), where w is the square matrix multiplication exponent, and a randomized one with runtime O*(2(ctw)). In sharp contrast to earlier work, the running time is independent of q. The dependence on cutwidth is optimal: we prove that even 3-COLORING cannot be solved in O*((2 - epsilon)(ctw)) time assuming SETH. Our algorithms rely on a new rank bound for a matrix that describes compatible colorings. Combined with a simple communication protocol for evaluating a product of two polynomials, this also yields an O*(([d/2] + 1)(pw)) time randomized algorithm for q-COLORING on graphs of pathwidth pw and maximum degree d. Such a runtime was first obtained by Bjorklund, but only for graphs with few proper colorings. We also prove that this result is optimal in the sense that no O*(([d/2] +1 - epsilon)(pw))-time algor

关键词： parameterized complexity Chromatic number Graph decompositions

来源：评论

学校读者我要写书评

暂无评论

EXPLICIT LINEAR KERNELS VIA DYNAMIC PROGRAMMING

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2015年第4期29卷 1864-1894页

作者： Garnero, Valentin Paul, Christophe Sau, Ignasi Thilikos, Dimitrios M. CNRS LIRMM AIGCo Project Team Montpellier France Univ Athens Dept Math Athens Greece

Several algorithmic meta-theorems on kernelization have appeared in the last years, starting with the result of Bodlaender et al. [(Meta) kernelization, in Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, 2009, pp. 629638] on graphs of bounded genus, then generalized by Fomin et al. [Bidimensionality and kernels, in Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadephia, 2010, pp. 503-510] to graphs excluding a fixed minor, and by Kim et al. [Linear kernels and single-exponential algorithms via protrusion decompositions, in Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Comput. Sci., 7965 (2013), pp. 613-624] to graphs excluding a fixed topological minor. Typically, these results guarantee the existence of linear or polynomial kernels on sparse graph classes for problems satisfying some generic conditions, but, mainly due to their generality, it is not clear how to derive from them constructive kernels with explicit constants. In this paper, we make a step toward a fully constructive meta-kernelization theory on sparse graphs. Our approach is based on a more explicit protrusion replacement machinery that, instead of expressibility in counting monadic second order logic, uses dynamic programming, which allows us to find an explicit upper bound on the size of the derived kernels. We demonstrate the usefulness of our techniques by providing the first explicit linear kernels for r-DOMINATING SET and r-SCATTERED SET on apex-minor-free graphs, and for PLANAR-F-DELETION on graphs excluding a fixed (topological) minor in the case where all the graphs in F are connected.

关键词： parameterized complexity linear kernels dynamic programming protrusion replacement graph minors

来源：评论

学校读者我要写书评

暂无评论

complexity results for rainbow matchings

引用

THEORETICAL COMPUTER SCIENCE 2014年第0期524卷 27-33页

作者： Le, Van Bang Pfender, Florian Univ Rostock Inst Informat D-18055 Rostock Germany Univ Colorado Dept Math & Stat Denver CO 80202 USA

A rainbow matching in an edge-colored graph is a matching whose edges have distinct colors. We address the complexity issue of the following problem, MAX RAINBOW MATCHING: Given an edge-colored graph G, how large is the largest rainbow matching in G? We present several sharp contrasts in the complexity of this problem. We show, among others, that MAX RAINBOW MATCHING can be approximated by a polynomial algorithm with approximation ratio 2/3 - epsilon. MAX RAINBOW MATCHING is APX-complete, even when restricted to properly edge-colored linear forests without a 5-vertex path, and is solvable in polynomial time for edge-colored forests without a 4-vertex path. MAX RAINBOW MATCHING is APX-complete, even when restricted to properly edge-colored trees without an 8-vertex path, and is solvable in polynomial time for edge-colored trees without a 7-vertex path. MAX RAINBOW MATCHING is APX-complete, even when restricted to properly edge-colored paths. These results provide a dichotomy theorem for the complexity of the problem on forests and trees in terms of forbidding paths. The latter is somewhat surprising, since, to the best of our knowledge, no (unweighted) graph problem prior to our result is known to be NP-hard for simple paths. We also address the parameterized complexity of the problem. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Rainbow matching Computational complexity NP-completeness APX-completeness parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

One Hierarchy Spawns Another: Graph Deconstructions and the complexity Classification of Conjunctive Queries

引用

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC 2017年第4期18卷 1–37页

作者： Chen, Hubie Mueller, Moritz Univ Basque Country Bilbao Spain Basque Fdn Sci Ikerbasque Bilbao Spain Birkbeck Univ London Dept Comp Sci & Informat Syst Malet St London WC1E 7HX England Univ Vienna Kurt Godel Res Ctr Wahringer Str 25 A-1090 Vienna Austria

We study the problem of conjunctive query evaluation relative to a class of queries. This problem is formulated here as the relational homomorphism problem relative to a class of structures A, in which each instance must be a pair of structures such that the first structure is an element of A. We present a comprehensive complexity classification of these problems, which strongly links graph-theoretic properties of A to the complexity of the corresponding homomorphism problem. In particular, we define a binary relation on graph classes, which is a preorder, and completely describe the resulting hierarchy given by this relation. This relation is defined in terms of a notion that we call graph deconstruction and that is a variant of the well-known notion of tree decomposition. We then use this hierarchy of graph classes to infer a complexity hierarchy of homomorphism problems that is comprehensive up to a computationally very weak notion of reduction, namely, a parameterized version of quantifier-free, first-order reduction. In doing so, we obtain a significantly refined complexity classification of homomorphism problems as well as a unifying, modular, and conceptually clean treatment of existing complexity classifications. We then present and develop the theory of Ehrenfeucht-Fraisse-style pebble games, which solve the homomorphism problems where the cores of the structures in A have bounded tree depth. This condition characterizes those classical homomorphism problems decidable in logarithmic space, assuming a hypothesis from parameterized space complexity. Finally, we use our framework to classify the complexity of model checking existential sentences having bounded quantifier rank.

关键词： Theory Conjunctive queries homomorphisms graph decompositions parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：