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

On the parameterized complexity of Maximum Degree Contraction Problem

ALGORITHMICA 2022年第2期84卷 405-435页

作者： Saurabh, Saket Tale, Prafullkumar Inst Math Sci Chennai Tamil Nadu India Univ Bergen Bergen Norway CISPA Helmholtz Ctr Informat Secur Saarbrucken Germany

In the MAXIMUM DEGREE CONTRACTION problem, the input is a graph G on n vertices, and integers k, d, and the objective is to check whether G can be transformed into a graph of maximum degree at most d, using at most k edge contractions. A simple brute-force algorithm that checks all possible sets of edges for a solution runs in time n(O(k)). As our first result, we prove that this algorithm is asymptotically optimal, upto constants in the exponents, under Exponential Time Hypothesis (ETH). Belmonte, Golovach, van't Hof, and Paulusma studied the problem in the realm of parameterized complexity and proved, among other things, that it admits an FPT algorithm running in time (d + k)(2k) . n(O(1)) = 2(O(k log(k+d))) . n(O(1)), and remains NP-hard for every constant d >= 2 (Acta Informatica (2014)). We present a different FPT algorithm that runs in time 2(O(dk)) . n(O(1)). In particular, our algorithm runs in time 2(O(k)) . n(O(1)), for every fixed d. In the same article, the authors asked whether the problem admits a polynomial kernel, when parameterized by k + d. We answer this question in the negative and prove that it does not admit a polynomial compression unless NP subset of coNP/poly.

关键词： Graph contraction Maximum degree contraction parameterized complexity FPT Algorithms No-poly Kernel ETH-lower bound

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of Bend-Minimum Orthogonal Planarity 31st

On the Parameterized Complexity of Bend-Minimum Orthogonal P...

引用

31st International Symposium on Graph Drawing and Network Visualization (GD)

作者： Di Giacomo, Emilio Didimo, Walter Liotta, Giuseppe Montecchiani, Fabrizio Ortali, Giacomo Univ Perugia Dipartimento Ingn Perugia Italy

ISBN: (纸本)9783031492747;9783031492754

Computing planar orthogonal drawings with the minimum number of bends is one of the most relevant topics in Graph Drawing. The problem is known to be NP-hard, even when we want to test the existence of a rectilinear planar drawing, i.e., an orthogonal drawing without bends (Garg and Tamassia, 2001). From the parameterized complexity perspective, the problem is fixed-parameter tractable when parameterized by the sum of three parameters: the number of bends, the number of vertices of degree at most two, and the treewidth of the input graph (Di Giacomo et al., 2022). We improve this last result by showing that the problem remains fixed-parameter tractable when parameterized only by the number of vertices of degree at most two plus the number of bends. As a consequence, rectilinear planarity testing lies in FPT parameterized by the number of vertices of degree at most two.

关键词： Orthogonal drawings bend-minimization parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Elimination Distance to First-Order Logic Properties 21

Parameterized Complexity of Elimination Distance to First-Or...

引用

36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)

作者： Fomin, Fedor, V Golovach, Petr A. Thilikos, Dimitrios M. Univ Bergen Dept Informat Bergen Norway Univ Montpellier CNRS LIRMIM AlGCo Project Team Montpellier France

ISBN: (纸本)9781665448956

The elimination distance to some target graph property P is a general graph modification parameter introduced by Bulian and Dawar. We initiate the study of elimination distances to graph properties expressible in first-order logic. We delimit the problem's fixed-parameter tractability by identifying sufficient and necessary conditions on the structure of prefixes of first-order logic formulas. Our main result is the following meta-theorem: For every graph property P expressible by a first order-logic formula (sic) is an element of Sigma(3), that is, of the form (sic) = there exists x(1)there exists x(2) center dot center dot center dot there exists x(r) for all y(1)for all y(2) center dot center dot center dot for all y(s) there exists z(1)there exists z(2) center dot center dot center dot there exists z(t) psi, where psi is a quantifier-free first-order formula, checking whether the elimination distance of a graph to P does not exceed k, is fixed-parameter tractable parameterized by k. Properties of graphs expressible by formulas from Sigma(3) include being of bounded degree, excluding a forbidden subgraph, or containing a bounded dominating set. We complement this theorem by showing that such a general statement does not hold for formulas with even slightly more expressive prefix structure: There are formulas (sic) is an element of Pi(3), for which computing elimination distance is W[2]-hard.

关键词： first-order logic elimination distance parameterized complexity descriptive complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of BANDWIDTH of Caterpillars and WEIGHTED PATH EMULATION 1

引用

47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Bodlaender, Hans L. Univ Utrecht Dept Informat & Comp Sci POB 80-089 NL-3508 TB Utrecht Netherlands

ISBN: (数字)9783030868383

ISBN: (纸本)9783030868376;9783030868383

In this paper, we show that Bandwidth is hard for the complexity class W[t] for all t is an element of N, even for caterpillars with hair length at most three. As intermediate problem, we introduce the Weighted Path Emulation problem: given a vertex-weighted path P-N and integer M, decide if there exists a mapping of the vertices of P-N to a path P-M, such that adjacent vertices are mapped to adjacent or equal vertices, and such that the total weight of the pre-image of a vertex from P-M equals an integer c. We show that Weighted Path Emulation, with c as parameter, is hard for W[t] for all t is an element of N, and is strongly NP-complete. We also show that Directed Bandwidth is hard for W[t] for all t is an element of N, for directed acyclic graphs whose underlying undirected graph is a caterpillar.

关键词： Bandwidth parameterized complexity Weighted path emulation W-hierarchy Caterpillars

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Categorical Clustering with Size Constraints 17th

Parameterized Complexity of Categorical Clustering with Size...

引用

17th International Symposium on Algorithms and Data Structures (WADS)

作者： Fomin, Fedor, V Golovach, Petr A. Purohit, Nidhi Univ Bergen Dept Informat Bergen Norway

ISBN: (纸本)9783030835088;9783030835071

In the Categorical Clustering problem, we are given a set of vectors (matrix) A = {a(1), . . . , a(n)} over Sigma(m), where Sigma is a finite alphabet, and integers k and B. The task is to partition A into k clusters such that the median objective of the clustering in the Hamming norm is at most B. That is, we seek a partition {I-1, . . . , I-k} of {1, . . . , n} and vectors c(1), . . . , c(k) is an element of Sigma(m) such that Sigma(k)(i=1) Sigma(j is an element of Ii) d(H)(c(i), a(j)) <= B, where d(H)(a, b) is the Hamming distance between vectors a and b. Fomin, Golovach, and Panolan [ICALP 2018] proved that the problem is fixed-parameter tractable (for binary case Sigma = {0, 1}) by giving an algorithm that solves the problem in time 2(O(B logB)) . (mn)(O(1)). We extend this algorithmic result to a popular capacitated clustering model, where in addition the sizes of the clusters should satisfy certain constraints. More precisely, in CAPACITATED CLUSTERING, in addition, we are given two non-negative integers p and q, and seek a clustering with p <= vertical bar I-i vertical bar <= q for all i is an element of {1, . . . , k}. Our main theorem is that CAPACITATED CLUSTERING is solvable in time 2(O(B logB))vertical bar Sigma vertical bar(B) . (mn)(O(1)). The theorem not only extends the previous algorithmic results to a significantly more general model, it also implies algorithms for several other variants of CATEGORICAL CLUSTERING with constraints on cluster sizes.

关键词： Categorical clustering Capacitated clustering parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of d-Hitting Set with Quotas 47th

Parameterized Complexity of <i>d</i>-Hitting Set with Quotas

引用

47th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)

作者： Gupta, Sushmita Jain, Pallavi Petety, Aditya Singh, Sagar HBNI Inst Math Sci IMSc Jodhpur Rajasthan India Indian Inst Technol Jodhpur Jodhpur Rajasthan India HBNI Natl Inst Sci Educ & Res NISER Jodhpur Rajasthan India

ISBN: (纸本)9783030677305;9783030677312

In this paper we study a variant of the classic d-HITTING SET problem with lower and upper capacity constraints, say A and B, respectively. The input to the problem consists of a universe U, a set family, J, of sets over U, where each set in the family is of size at most d, a non-negative integer k;and additionally two functions alpha: J -> {1,..., A} and beta : J -> {1,..., B}. The goal is to decide if there exists a hitting set of size at most k such that for every set S in the family J, the solution contains at least alpha(S) elements and at most beta(S) elements from S. We call this the (A, B)-MULTI d-HITTING SET problem. We study the problem in the realm of parameterized complexity. We show that (A, B)-MULTI d-HITTING SET can be solved in O-star (d(k)) time. For the special case when d = 3 and d = 4, we have an improved bound of O-star (2.2738(k)) and O-star (3.562(k)), respectively. The former matches the running time of the classical 3-HITTING SET problem. Furthermore, we show that if we do not have an upper bound constraint and the lower bound constraint is same for all the sets in the family, say A > 1, then the problem can be solved even faster than d-HITTING SET. We next investigate some graph-theoretic problems which can be thought of as an implicit d-HITTING SET problem. In particular, we study (A, B)-Multi Vertex Cover and (A, B)-MULTI FEEDBACK VERTEX SET IN TOURNAMENTS. In (A, B)-MULTI VERTEX COVER, we are given a graph G and a non-negative integer k, the goal is to find a subset S subset of V (G) of size at most k such that for every edge in G, S contains at least A and at most B of its endpoints. Analogously, we can define (A, B)-MULTI FEEDBACK VERTEX SET IN TOURNAMENTS. We show that unlike VERTEX COVER, which is same as (1, 2)-MULTI VERTEX COVER, (1, 1)-MULTI VERTEX COVER is polynomial-time solvable. Furthermore, unlike Feedback Vertex Set in Tournaments, (A, B)-MULTI FEEDBACK VERTEX SET IN TOURNAMENTS can be solved in polynomial time.

关键词： parameterized complexity Kernelization Multi hitting set

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Defensive and Offensive Alliances in Graphs 17th

Parameterized Complexity of Defensive and Offensive Alliance...

引用

17th International Conference on Distributed Computing and Intelligent Technology

作者： Gaikwad, Ajinkya Maity, Soumen Tripathi, Shuvam Kant Indian Inst Sci Educ & Res Pune Maharashtra India

ISBN: (纸本)9783030656201;9783030656218

In this paper we study the problem of finding small defensive and offensive alliances in a simple graph. Given a graph G = (V, E) and a subset S subset of V (G), we denote by d(S)(v) the degree of a vertex v is an element of V in G[S], the subgraph of G induced by S. A non-empty set S subset of V is a defensive alliance in G = (V, E) if d(S)(v)+ 1 >= d(Sc) (v) for all v is an element of S. A non-empty set S subset of V is an offensive alliance in G if d(S)(v) = d(Sc) (v)+ 1 for all v is an element of N(S). It is known that the problems of finding small defensive and offensive alliances are NP-complete. We enhance our understanding of the problems from the viewpoint of parameterized complexity by showing that (1) the problems are FPT when parameterized by neighbourhood diversity of the input graph, (2) the offensive alliance problem is FPT when parameterized by domino treewidth of the input graph, and (3) the defensive and offensive alliance problems are polynomial time solvable for graphs with bounded treewidth.

关键词： Defensive and offensive alliance parameterized complexity FPT W[1]-hard Treewidth

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Elimination Distance to First-Order Logic Properties

引用

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC 2022年第3期23卷 17-17页

作者： Fomin, Fedor, V Golovach, Petr A. Thilikos, Dimitrios M. Univ Bergen Dept Informat PB 7803 N-5020 Bergen Norway Univ Montpellier CNRS LIRMM 161 Rue Ada F-34095 Montpellier 5 France

The elimination distance to some target graph property P is a general graph modification parameter introduced by Bulian and Dawar. We initiate the study of elimination distances to graph properties expressible in first-order logic. We delimit the problem's fixed-parameter tractability by identifying sufficient and necessary conditions on the structure of prefixes of first-order logic formulas. Our main result is the following meta-theorem: For every graph property P expressible by a first order-logic formula phi is an element of Sigma(3), that is, of the form phi = there exists x(1)there exists x(2) ... there exists x(r) for all y(1)for all y(2) ... for all y(s) there exists z(1)there exists z(2) ... there exists z(t) psi, where psi is a quantifier-free first-order formula, checking whether the elimination distance of a graph to P does not exceed k, is fixed-parameter tractable parameterized by k. Properties of graphs expressible by formulas from Sigma(3) include being of bounded degree, excluding a forbidden subgraph, or containing a bounded dominating set. We complement this theorem by showing that such a general statement does not hold for formulaswith even slightly more expressive prefix structure: There are formulas phi epsilon Pi(3), for which computing elimination distance is W[2]-hard.

关键词： First-order logic elimination distance parameterized complexity descriptive complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity Classes Defined by Threshold Circuits: Using Sorting Networks to Show Collapses with W-hierarchy Classes 15th

Parameterized Complexity Classes Defined by Threshold Circui...

引用

15th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Paranhos, Raffael M. Nascimento Silva, Janio Carlos Souza, Ueverton S. Ochi, Luiz Satoru Univ Fed Fluminense Inst Comp Niteroi RJ Brazil Inst Fed Tocantins Campus Porto Nacl Porto Nacl TO Brazil

ISBN: (纸本)9783030926816;9783030926809

The main complexity classes of the parameterized Intractability Theory are based on weighted Boolean circuit satisfiability problems and organized into a hierarchy so-called W-hierarchy. The W-hierarchy enables fine-grained complexity analyses of parameterized problems that are unlikely to belong to the FPT class. In this paper, we introduce the Th-hierarchy, a natural generalization of the W-hierarchy defined by weighted threshold circuit satisfiability problems. Investigating the relationship between Th-hierarchy and W-hierarchy, we discuss the complexity of transforming Threshold circuits into Boolean circuits, and observe that sorting networks are powerful tools to handle such transformations. First, we show that these hierarchies collapse at the last level (W[P] = Th[P]). After that, we present a time complexity analysis of an AKS sorting network construction, which supports some of our results. Finally, we prove that Th[t] subset of W[SAT] for every t is an element of N.

关键词： Threshold circuits AKS sorting network parameterized complexity W-hierarchy

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of happy coloring problems

引用

THEORETICAL COMPUTER SCIENCE 2020年 835卷 58-81页

作者： Agrawal, Akanksha Aravind, N. R. Kalyanasundaram, Subrahmanyam Kare, Anjeneya Swami Lauri, Juho Misra, Neeldhara Reddy, I. Vinod Ben Gurion Univ Negev Beer Sheva Israel Indian Inst Technol Hyderabad Kandi India Univ Hyderabad Hyderabad India Nokia Bell Labs Dublin Ireland Indian Inst Technol Gandhinagar Palaj India Indian Inst Technol Bhilai Chhattisgarh India Univ Bergen Bergen Norway

In a vertex-colored graph, an edge is happy if its endpoints have the same color. Similarly, a vertex is happy if all its incident edges are happy. Motivated by the computation of homophily in social networks, we consider the algorithmic aspects of the following MAXIMUM HAPPY EDGES (k-MHE) problem: given a partially k-colored graph G and an integer l, find an extended full k-coloring of G making at least l edges happy. When we want to make l vertices happy on the same input, the problem is known as MAXIMUM HAPPY VERTICES (k-MHV). We perform an extensive study into the complexity of the problems, particularly from a parameterized viewpoint. For every k >= 3, we prove both problems can be solved in time 2(n) n(O(1)). Moreover, by combining this result with a linear vertex kernel of size (k + l) for k-MHE, we show that the edge-variant can be solved in time 2(l)n(O(1)). In contrast, we prove that the vertex-variant remains W[1]-hard for the natural parameter l. However, the problem does admit a kernel with O (k(2)l(2)) vertices for the combined parameter k + l. From a structural perspective, we show both problems are fixed-parameter tractable for treewidth and neighborhood diversity, which can both be seen as sparsity and density measures of a graph. Finally, we extend the known NP-completeness results of the problems by showing they remain hard on bipartite graphs and split graphs. On the positive side, we show the vertex-variant can be solved optimally in polynomial-time for cographs. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Computational complexity Happy coloring parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：