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

Vertex Cover Kernelization Revisited

THEORY OF COMPUTING SYSTEMS 2013年第2期53卷 263-299页

作者： Jansen, Bart M. P. Bodlaender, Hans L. Univ Utrecht NL-3508 TB Utrecht Netherlands

An important result in the study of polynomial-time preprocessing shows that there is an algorithm which given an instance (G,k) of Vertex Cover outputs an equivalent instance (G',k') in polynomial time with the guarantee that G' has at most 2k' vertices (and thus edges) with k'a parts per thousand currency signk. Using the terminology of parameterized complexity we say that k-Vertex Cover has a kernel with 2k vertices. There is complexity-theoretic evidence that both 2k vertices and I similar to(k (2)) edges are optimal for the kernel size. In this paper we consider the Vertex Cover problem with a different parameter, the size of a minimum feedback vertex set for G. This refined parameter is structurally smaller than the parameter k associated to the vertex covering number since and the difference can be arbitrarily large. We give a kernel for Vertex Cover with a number of vertices that is cubic in : an instance (G,X,k) of Vertex Cover, where X is a feedback vertex set for G, can be transformed in polynomial time into an equivalent instance (G',X',k') such that |V(G')|a parts per thousand currency sign2k and . A similar result holds when the feedback vertex set X is not given along with the input. In sharp contrast we show that the Weighted Vertex Cover problem does not have a polynomial kernel when parameterized by the cardinality of a given vertex cover of the graph unless NP aS dagger coNP/poly and the polynomial hierarchy collapses to the third level.

关键词： Kernelization Vertex cover structural parameterization

来源：评论

学校读者我要写书评

暂无评论

On design sensitivities in the structural analysis and optimization of flexible multibody systems

引用

MULTIBODY SYSTEM DYNAMICS 2022年第1期54卷 53-74页

作者： Held, Alexander Hamburg Univ Technol Inst Mech & Ocean Engn Eissendorfer Str 42 D-21073 Hamburg Germany

The structural analysis and optimization of flexible multibody systems become more and more popular due to the ability to efficiently compute gradients using sophisticated approaches such as the adjoint variable method and the adoption of powerful methods from static structural optimization. To drive the improvement of the optimization process, this work addresses the computation of design sensitivities for multibody systems with arbitrarily parameterized rigid and flexible bodies that are modeled using the floating frame of reference formulation. It is shown that it is useful to augment the body describing standard input data files by their design derivatives. In this way, a clear separation can be achieved between the body modeling and parameterization and the system simulation and analysis.

关键词： Flexible multibody system Adjoint sensitivity analysis structural parameterization Standard input data

来源：评论

学校读者我要写书评

暂无评论

Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs

引用

ALGORITHMICA 2021年第7期83卷 2170-2214页

作者： Fomin, Fedor, V Golovach, Petr A. Univ Bergen Dept Informat PB 7803 N-5020 Bergen Norway

We study algorithmic properties of the graph class CHORDAL-ke, that is, graphs that can be turned into a chordal graph by adding at most k edges or, equivalently, the class of graphs of fill-in at most k. It appears that a number of fundamental intractable optimization problems being parameterized by k admit subexponential algorithms on graphs from CHORDAL-ke. More precisely, we identify a large class of optimization problems on CHORDAL-ke solvable in time 2O((root k log k)) center dot n(O(1)). Examples of the problems from this class are finding an independent set of maximum weight, finding a feedback vertex set or an odd cycle transversal of minimum weight, or the problem of finding a maximum induced planar subgraph. On the other hand, we show that for some fundamental optimization problems, like finding an optimal graph coloring or finding a maximum clique, are FPT on CHORDAL-ke when parameterized by k but do not admit subexponential in k algorithms unless ETH fails. Besides subexponential time algorithms, the class of CHORDAL-ke graphs appears to be appealing from the perspective of kernelization (with parameter k). While it is possible to show that most of the weighted variants of optimization problems do not admit polynomial in k kernels on CHORDAL-ke graphs, this does not exclude the existence of Turing kernelization and kernelization for unweighted graphs. In particular, we construct a polynomial Turing kernel for Weighted Clique on CHORDAL-ke graphs. For (unweighted) Independent Set we design polynomial kernels on two interesting subclasses of CHORDAL-ke, namely, INTERVAL-ke and SPLIT-ke graphs.

关键词： Parameterized complexity structural parameterization Subexponential algorithms Kernelization Chordal graphs Fill-in Independent set Clique Coloring

来源：评论

学校读者我要写书评

暂无评论

The Graph Motif problem parameterized by the structure of the input graph

引用

DISCRETE APPLIED MATHEMATICS 2017年 231卷 78-94页

作者： Bonnet, Edouard Sikora, Florian Hungarian Acad Sci MTA SZTAKI Inst Comp Sci & Control Budapest Hungary PSL Res Univ Univ Paris Dauphine CNRS LAMSADE Paris France

The GRAPH MOTIF problem was introduced in 2006 in the context of biological networks. It consists of deciding whether or not a multiset of colors occurs in a connected subgraph of a vertex-colored graph. GRAPH MOTIF has been mostly analyzed from the standpoint of parameterized complexity. The main parameters which came into consideration were the size of the multiset and the number of colors. In the many utilizations of GRAPH MOTIF, however, the input graph originates from real-life applications and has structure. Motivated by this prosaic observation, we systematically study its complexity relatively to graph structural parameters. For a wide range of parameters, we give new or improved FPT algorithms, or show that the problem remains intractable. For the FPT cases, we also give some kernelization lower bounds as well as some ETH-based lower bounds on the worst case running time. Interestingly, we establish that GRAPH MOTIF is W[1]-hard (while in W[P]) for parameter max leaf number, which is, to the best of our knowledge, the first problem to behave this way. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Parameterized complexity Graph motif problem structural parameterization Computational biology

来源：评论

学校读者我要写书评

暂无评论

Polynomial Kernels for Vertex Cover Parameterized by Small Degree Modulators

引用

THEORY OF COMPUTING SYSTEMS 2018年第8期62卷 1910-1951页

作者： Majumdar, Diptapriyo Raman, Venkatesh Saurabh, Saket HBNI Inst Math Sci Madras Tamil Nadu India

VERTEX COVER is one of the most well studied problems in the realm of parameterized algorithms. It admits a kernel with O( 2) edges and 2 vertices where denotes the size of the vertex cover we are seeking for. A natural question is whether VERTEX COVER is fixed- parameter tractable or admits a polynomial kernel with respect to a parameter k, that is, provably smaller than the size of the vertex cover. Jansen and Bodlaender [ STACS 2011, TOCS 2013] raised this question and gave a kernel for VERTEX COVER of size O(f 3), where f is the size of a feedback vertex set of the input graph. We continue this line of work and study VERTEX COVER with respect to a parameter that is always smaller than the solution size and incomparable to the size of the feedback vertex set of the input graph. Our parameter is the number of vertices whose removal results in a graph of maximum degree two. While vertex cover with this parameterization can easily be shown to be fixed- parameter tractable (FPT), we show that it has a polynomial kernel. The input to our problem consists of an undirected graph G, S. V (G) such that | S| = k and G[ V (G) \ S] has maximum degree at most two and a positive integer . Given (G, S, ), in polynomial time we output an instance (G , S , ) such that | V (G )| is O(k5), | E(G )| is O(k6) and G has a vertex cover of size at most if and only if G has a vertex cover of size at most . When G[ V (G) \ S] has maximum degree at most one, we improve the known kernel bound from O(k3) vertices to O(k2) vertices (and O(k3) edges). More generally, given (G, S, ) where every connected component of G\ S is a clique of at most d vertices (for constant d), in polynomial time, we output an equivalent instance (G , S , ) for the same problem where | V (G )| is O(kd). We also show that for this problem, when d = 3, a kernel with O(kd- e) bits cannot exist for any e > 0 unless NP. coNP/ poly.

关键词： Parameterized complexity Kernelization Expansion lemma Vertex cover structural parameterization

来源：评论

学校读者我要写书评

暂无评论

Parameterized Edge Hamiltonicity

引用

DISCRETE APPLIED MATHEMATICS 2018年 248卷 68-78页

作者： Lampis, Michael Makino, Kazuhisa Mitsou, Valia Uno, Yushi Univ Paris 09 PSL Res Univ CNRS UMR 7243LAMSADE F-75016 Paris France Kyoto Univ Res Inst Math Sci Kyoto Japan Univ Lyon 1 Univ Lyon CNRS LIRISUMR 5205 F-69622 Lyon France Osaka Prefecture Univ Grad Sch Sci Dept Math & Informat Sci Sakai Osaka Japan

We study the parameterized complexity of the classical EDGE HAMILTONIAN PATH problem and give several fixed-parameter tractability results. First, we settle an open question of Demaine et al. (2014) by showing that EDGE HAMILTONIAN PATH is FPT parameterized by vertex cover, and that it also admits a cubic kernel. We then show fixed-parameter tractability even for a generalization of the problem to arbitrary hypergraphs, parameterized by the size of a (supplied) hitting set. As an interesting consequence, we show that this implies an FPT algorithm for (VERTEX) HAMILTONIAN PATH parameterized by (vertex) clique cover. We also consider the problem parameterized by treewidth or clique-width. Surprisingly, we show that the problem is FPT for both of these standard parameters, in contrast to its vertex version, which is W[1]-hard for clique-width. Our technique, which may be of independent interest, relies on a structural characterization of clique-width in terms of treewidth and complete bipartite subgraphs due to Gurski and Wanke. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Edge Hamiltonicity Fixed parameter tractability structural parameterization Polynomial kernel

来源：评论

学校读者我要写书评

暂无评论

Revisiting Connected Vertex Cover: FPT Algorithms and Lossy Kernels

引用

THEORY OF COMPUTING SYSTEMS 2018年第8期62卷 1690-1714页

作者： Krithika, R. Majumdar, Diptapriyo Raman, Venkatesh HBNI Inst Math Sci Madras Tamil Nadu India

The CONNECTED VERTEX COVER problem asks for a vertex cover in a graph that induces a connected subgraph. The problem is known to be fixedparameter tractable ( FPT), and is unlikely to have a polynomial sized kernel ( under complexity theoretic assumptions) when parameterized by the solution size. In a recent paper, Lokshtanov et al. [ STOC 2017], have shown an a- approximate kernel for the problem for every a > 1, in the framework of approximate or lossy kernelization. In this work, we exhibit lossy kernels and FPT algorithms for CONNECTED VERTEX COVER for parameters that are more natural and functions of the input, and in some cases, smaller than the solution size. Our first result is a lossy kernel for CONNECTED VERTEX COVER parameterized by the size of a split deletion set. Let n denote the number of vertices in the input graph. We show that CONNECTED VERTEX COVER parameterized by the size k of a split deletion set admits an a- approximate kernel with O( k + ( 2k + 2a- 1 a- 1 ) 2a- 1 a- 1 ) vertices and an algorithm with O( 3kn O( 1)) running time. For the special case when the split deletion set is a clique deletion set, the algorithm runs in O( 2kn O( 1)) time and the lossy kernel has O( k + 2a- 1 a- 1 ) *** the best of our knowledge, this (approximate) kernel is one of the few lossy kernels for problems parameterized by a structural parameter (that is not solution size). We extend this lossy kernelization to CONNECTED VERTEX COVER parameterized by an incomparable parameter, and that is the size of a clique cover. We show that CONNECTED VERTEX COVER parameterized by the size k of a clique cover is W[ 1]-hard but admits an a-approximate kernel with O(k 2a-1 a-1 ) vertices for every a > 1. This is one of the few problems that are not FPT but admit a lossy kernel. Finally, we consider the size of a cluster deletion set as parameter. We show that CONNECTED VERTEX COVER parameterized by the size k of a cluster deletion set is FPT via an algorithm with runnin

关键词： Parameterized complexity Connected vertex cover Lossy kernelization structural parameterization W-hardness

来源：评论

学校读者我要写书评

暂无评论

KERNELIZATION LOWER BOUNDS BY CROSS-COMPOSITION

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2014年第1期28卷 277-305页

作者： Bodlaender, Hans L. Jansen, Bart M. P. Kratsch, Stefan Univ Utrecht Dept Informat & Comp Sci NL-3508 TB Utrecht Netherlands Univ Bergen Dept Informat N-5020 Bergen Norway Tech Univ Berlin Dept Software Engn & Theoret Comp Sci D-10587 Berlin Germany

We introduce the framework of cross-composition for proving kernelization lower bounds. A classical problem L AND/OR-cross-composes into a parameterized problem Q if it is possible to efficiently construct an instance of Q with polynomially bounded parameter value that expresses the logical and or or of a sequence of instances of L. Building on work by Bodlaender et al. and using results of Fortnow and Santhanam, Dell and van Melkebeek, and Drucker, we show that if an NP-hard problem AND/OR-cross-composes into a parameterized problem Q, then Q does not admit a polynomial kernel unless NP subset of coNP/poly and the polynomial hierarchy collapses. Our technique generalizes and strengthens the techniques of using composition algorithms and of transferring the lower bounds via polynomial parameter transformations. We show its applicability by proving kernelization lower bounds for a number of important graphs problems with structural (nonstandard) parameterizations, e. g., Clique, Chromatic Number, Weighted Feedback Vertex Set, and Weighted Odd Cycle Transversal do not admit polynomial kernels with respect to the vertex cover number of the input graphs unless the polynomial hierarchy collapses, contrasting the fact that these problems are trivially fixed-parameter tractable for this parameter. We have similar lower bounds for Feedback Vertex Set and Odd Cycle Transversal under structural parameterizations. After learning of our results, several teams of authors have successfully applied the cross-composition framework to different parameterized problems. For completeness, our presentation of the framework includes several extensions based on this follow-up work. For example, we show how a relaxed version of OR-cross-compositions may be used to give lower bounds on the degree of the polynomial in the kernel size.

关键词： kernelization kernel lower bounds parameterized complexity structural parameterization

来源：评论

学校读者我要写书评

暂无评论

b-Coloring Parameterized by Clique-Width

引用

THEORY OF COMPUTING SYSTEMS 2024年第4期68卷 1049-1081页

作者： Jaffke, Lars Lima, Paloma T. Lokshtanov, Daniel Univ Bergen Bergen Norway IT Univ Copenhagen Copenhagen Denmark Univ Calif Santa Barbara Santa Barbara CA 93106 USA

We provide a polynomial-time algorithm for b- COLORING on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial time results on graph classes, and answers open questions posed by Campos and Silva (Algorithmica 80(1), 104-115, 2018) and Bonomo et al. (Graphs and Combinatorics 25(2), 153-167, 2009). This constitutes the first result concerning structural parame-terizations of this problem. We show that the problem is FPT when parameterized by the vertex cover number on general graphs, and on chordal graphs when parameterized by the number of colors. Additionally, we observe that our algorithm for graphs of bounded clique-width can be adapted to solve the FALL COLORING problem within the same runtime bound. The running times of the clique-width based algorithms for b-COLORING and FALL COLORING are tight under the Exponential Time Hypothesis.

关键词： B-coloring Clique-width Vertex cover structural parameterization

来源：评论

学校读者我要写书评

暂无评论

Acknowledgments We would like to thank Fedor V. Fomin for hosting Jari in Bergen (Norway).

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2022年 126卷 59-79页

作者： Jansen, Bart M. P. de Kroon, Jari J. H. Eindhoven Univ Technol Eindhoven Netherlands

We consider the -FREE DELETION problem parameterized by the size of a vertex cover, for a range of graph properties . Given an input graph G, this problem asks whether there is a subset of at most k vertices whose removal ensures the resulting graph does not contain a graph from  as an induced subgraph. We introduce the concept of characterizing a graph property  by low-rank adjacencies, and use it as the cornerstone of a general kernelization theorem for -FREE DELETION parameterized by the size of a vertex cover. The resulting framework captures problems such as AT-FREE DELETION, WHEEL-FREE DELETION, and INTERVAL DELETION. Moreover, our new framework shows that the vertex-deletion problem to perfect graphs has a polynomial kernel when parameterized by vertex cover, thereby resolving an open question by Fomin et al. (2014) [18]. (c) 2021 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： Kernelization Vertex-deletion Graph modification structural parameterization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：