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

Simultaneous consecutive ones submatrix and editing problems: Classical complexity and fixed-parameter tractable results

引用

THEORETICAL COMPUTER SCIENCE 2020年 812卷 13-38页

作者： Rani, M. R. Subashini, R. Jagalmohanan, Mohith Natl Inst Technol Dept Comp Sci & Engn Calicut Kerala India Dell Int Serv Private Ltd Hyderabad India

A binary matrix M has the consecutive ones property (C1P) for rows (resp. columns) if there exists a permutation of its columns (resp. rows) that arranges the ones consecutively in all the rows (resp. columns). If M has the C1P for rows and the C1P for columns, then M is said to have the simultaneous consecutive ones property (SC1P). In this article, we consider the classical complexity and fixed-parameter tractability of a few variants of decision problems related to the SC1P. Given a binary matrix M and a positive integer d, we focus on problems that decide whether there exists a set of rows, columns, and rows as well as columns, respectively, of size at most d in M, whose deletion results in a matrix with the SC1P. We also consider problems that decide whether there exists a set of 0-entries, 1-entries and 0-entries as well as 1-entries, respectively, of size at most din M, whose flipping results in a matrix with the SC1P. In this paper, we show that all the above mentioned problems are NP-complete. We could also prove that all these problems are fixed-parameter tractable with respect to solution size as the parameter, except for two variants (flipping 1-entries and flipping 0/1-entries). We also give improved FPT algorithms for certain problems on restricted binary matrices. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Consecutive Ones Property (C1P) Simultaneous Consecutive Ones Property (SC1P) Fixed-Parameter Tractable (FPT) parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Pursuing a fast robber on a graph

引用

THEORETICAL COMPUTER SCIENCE 2010年第7-9期411卷 1167-1181页

作者： Fomin, Fedor V. Golovach, Petr A. Kratochvil, Jan Nisse, Nicolas Suchan, Karol Univ Bergen Dept Informat N-5020 Bergen Norway Charles Univ Prague Dept Appl Math Inst Theoret Comp Sci Prague Czech Republic UNS CNRS I3S MASCOTTEINRIA Sophia Antipolis France Univ Adolfo Ibanez Fac Ingn & Ciencias Santiago Chile AGH Univ Sci & Technol Fac Appl Math Krakow Poland

The Cops and Robbers game as originally defined independently by Quilliot and by Nowakowski and Winkler in the 1980s has been Much Studied, but very few results pertain to the algorithmic and complexity aspects of it. In this paper we prove that computing the minimum number of cops that are guaranteed to catch a robber on a given graph is NP-hard and that the parameterized version of the problem is W[2]-hard;the proof extends to the case where the robber moves s time faster than the cops. We show that on split graphs, the problem is polynomially solvable if s = 1 but is NP-hard if s = 2. We further prove that on graphs of bounded cliquewidth the problem is polynomially solvable for s <= 2. Finally, we show that for planar graphs the minimum number of cops is unbounded if the robber is faster than the cops. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Pursuit-evasion game on graphs Cops and Robbers complexity parameterized complexity Cliquewidth Planar graph

来源：评论

学校读者我要写书评

暂无评论

Maximum cuts in edge-colored graphs

引用

DISCRETE APPLIED MATHEMATICS 2020年 281卷 229-234页

作者： Faria, Luerbio Klein, Sulamita Sau, Ignasi Souza, Ueverton S. Sucupira, Rubens Univ Estado Rio De Janeiro IME Rio De Janeiro Brazil Univ Fed Rio de Janeiro COPPE IM Rio De Janeiro Brazil Univ Montpellier LIRMM CNRS Montpellier France Univ Fed Ceara Dept Matemat Fortaleza Ceara Brazil Univ Fed Fluminense IC Niteroi RJ Brazil

The input of the Maximum Colored Cut problem consists of a graph G = (V, E) with an edge-coloring c : E -> {1, 2, 3,..., p} and a positive integer k, and the question is whether G has a nontrivial edge cut using at least k colors. The Colorful Cut problem has the same input but asks for a nontrivial edge cut using all p colors. Unlike what happens for the classical Maximum Cut problem, we prove that both problems are NP-complete even on complete, planar, or bounded treewidth graphs. Furthermore, we prove that Colorful Cut is NP-complete even when each color class induces a clique of size at most three, but is trivially solvable when each color induces an edge. On the positive side, we prove that Maximum Colored Cut is fixed-parameter tractable when parameterized by either k or p, by constructing a cubic kernel in both cases. (c) 2019 Elsevier B.V. All rights reserved.

关键词： Colored cut Edge cut Maximum cut Planar graph parameterized complexity Polynomial kernel

来源：评论

学校读者我要写书评

暂无评论

Tractability of Konig edge deletion problem

引用

THEORETICAL COMPUTER SCIENCE 2019年 796卷 207-215页

作者： Majumdar, Diptapriyo Neogi, Rian Raman, Venkatesh Vaishali, S. Royal Holloway Univ London Egham Surrey England HBNI Inst Math Sci Chennai Tamil Nadu India PSG Coll Technol Coimbatore Tamil Nadu India

A graph is said to be a Konig graph if the size of its maximum matching is equal to the size of its minimum vertex cover. The KONIG EDGE DELETION problem asks if in a given graph there exists a set of at most k edges whose deletion results in a Konig graph. While the vertex version of the problem (Konig vertex deletion) has been shown to be fixed-parameter tractable more than a decade ago, the fixed-parameter-tractability of the ICONIC EDGE DELETION problem has been open since then, and has been conjectured to be W[1]-hard in several papers. In this paper, we settle the conjecture by proving it W[1]-hard. We prove that a variant of this problem, where we are given a graph G and a maximum matching M and we want a k-sized Konig edge deletion set that is disjoint from M, is fixed-parameter-tractable. (C) 2019 Elsevier B.V. All rights reserved.

关键词： parameterized complexity W-hardness Konig graphs Vertex cover Konig edge deletion

来源：评论

学校读者我要写书评

暂无评论

On the complexity of restoring corrupted colorings

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2019年第4期37卷 1150-1169页

作者： De Biasi, Marzio Lauri, Juho Tampere Univ Technol Tampere Finland Nokia Bell Labs Dublin Ireland

In the r-Fix problem, we are given a graph G, a (non-proper) vertex-coloring c:V(G)[r], and a positive integerk. The goal is to decide whether a proper r-coloring c is obtainable fromc by recoloring at most k vertices of G. Recently, Junosza-Szaniawski et al. (in: SOFSEM 2015: theory and practice of computer science, Springer, Berlin, 2015) asked whether the problem has a polynomial kernel parameterized by the number of recoloringsk. In a full version of the manuscript, the authors together with Garnero and Montealegre, answered the question in the negative: for every r3, the problem r-Fix does not admit a polynomial kernel unless . Independently of their work, we give an alternative proof of the theorem. Furthermore, we study the complexity of r-Swap, where the only difference from r-Fix is that instead ofk recolorings we have a budget ofk color swaps. We show that for every r3, the problem r-Swap is -hard whereas r-Fix is known to be FPT. Moreover, whenr is part of the input, we observe both Fix and Swap are -hard parameterized by the treewidth of the input graph. We also study promise variants of the problems, where we are guaranteed that a proper r-coloringc is indeed obtainable fromc by some finite number of swaps. For instance, we prove that for r=3, the problems r-Fix-Promise and r-Swap-Promise are -hard for planar graphs. As a consequence of our reduction, the problems cannot be solved in 2o(n) time unless the Exponential Time Hypothesis fails.

关键词： Graph coloring Computational complexity parameterized complexity Combinatorial reconfiguration Local search

来源：评论

学校读者我要写书评

暂无评论

Finding Cuts of Bounded Degree: complexity, FPT and Exact Algorithms, and Kernelization

引用

ALGORITHMICA 2021年第6期83卷 1677-1706页

作者： Gomes, Guilherme C. M. Sau, Ignasi Univ Fed Minas Gerais Dept Ciencia Comp Belo Horizonte MG Brazil Univ Montpellier LIRMM Montpellier France Univ Montpellier CNRS LIRMM Montpellier France

A matching cut is a partition of the vertex set of a graph into two sets A and B such that each vertex has at most one neighbor in the other side of the cut. The Matching Cut problem asks whether a graph has a matching cut, and has been intensively studied in the literature. Motivated by a question posed by Komusiewicz et al. [Discrete Applied Mathematics, 2020], we introduce a natural generalization of this problem, which we call d -Cut: for a positive integer d, a d-cut is a bipartition of the vertex set of a graph into two sets A and B such that each vertex has at most d neighbors across the cut. We generalize (and in some cases, improve) a number of results for the Matching Cut problem. Namely, we begin with an NP-hardness reduction for d -Cut on (2d + 2)-regular graphs and a polynomial algorithm for graphs of maximum degree at most d + 2. The degree bound in the hardness result is unlikely to be improved, as it would disprove a long-standing conjecture in the context of internal partitions. We then give FPT algorithms for several parameters: the maximum number of edges crossing the cut, treewidth, distance to cluster, and distance to co-cluster. In particular, the treewidth algorithm improves upon the running time of the best known algorithm for Matching Cut. Our main technical contribution, building on the techniques of Komusiewicz et al. [DAM, 2020], is a polynomial kernel for d -Cut for every positive integer d, parameterized by the vertex deletion distance of the input graph to a cluster graph. We also rule out the existence of polynomial kernels when parameterizing simultaneously by the number of edges crossing the cut, the treewidth, and the maximum degree. Finally, we provide an exact exponential algorithm slightly faster than the naive brute force approach running in time O*(2(n)).

关键词： Matching cut Bounded degree cut parameterized complexity FPT algorithm Polynomial kernel Distance to cluster

来源：评论

学校读者我要写书评

暂无评论

parameterized Domination in Circle Graphs

引用

THEORY OF COMPUTING SYSTEMS 2014年第1期54卷 45-72页

作者： Bousquet, Nicolas Goncalves, Daniel Mertzios, George B. Paul, Christophe Sau, Ignasi Thomasse, Stephan CNRS LIRMM AlGCo Project Team Montpellier France Univ Durham Sch Engn & Comp Sci Durham England UCBL CNRS ENS Lyon Lab LIPU LyonINRIA Lyon France

A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Appl. Math., 42(1):51-63, 1993] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-complete in circle graphs. To the best of our knowledge, nothing was known about the parameterized complexity of these problems in circle graphs. In this paper we prove the following results, which contribute in this direction Dominating Set, Independent Dominating Set, Connected Dominating Set, Total Dominating Set, and Acyclic Dominating Set are W[1]-hard in circle graphs, parameterized by the size of the solution. Whereas both Connected Dominating Set and Acyclic Dominating Set are W[1]-hard in circle graphs, it turns out that Connected Acyclic Dominating Set is polynomial-time solvable in circle graphs. If T is a given tree, deciding whether a circle graph G has a dominating set inducing a graph isomorphic to T is NP-complete when T is in the input, and FPT when parameterized by t=|V(T)|. We prove that the FPT algorithm runs in subexponential time, namely , where n=|V(G)|.

关键词： Circle graphs Domination problems parameterized complexity parameterized algorithms Dynamic programming Constrained domination

来源：评论

学校读者我要写书评

暂无评论

The complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number

引用

THEORY OF COMPUTING SYSTEMS 2009年第4期45卷 822-848页

作者： Fellows, Michael Lokshtanov, Daniel Misra, Neeldhara Mnich, Matthias Rosamond, Frances Saurabh, Saket Univ Newcastle Callaghan NSW 2308 Australia Univ Bergen Bergen Norway Inst Math Sci Madras 600113 Tamil Nadu India Tech Univ Eindhoven NL-5600 MB Eindhoven Netherlands

In the framework of parameterized complexity, exploring how one parameter affects the complexity of a different parameterized (or unparameterized problem) is of general interest. A well-developed example is the investigation of how the parameter treewidth influences the complexity of (other) graph problems. The reason why such investigations are of general interest is that real-world input distributions for computational problems often inherit structure from the natural computational processes that produce the problem instances (not necessarily in obvious, or well-understood ways). The max leaf number ml(G) of a connected graph G is the maximum number of leaves in a spanning tree for G. Exploring questions analogous to the well-studied case of treewidth, we can ask: how hard is it to solve 3-COLORING, HAMILTON PATH, MINIMUM DOMINATING SET, MINIMUM BANDWIDTH or many other problems, for graphs of bounded max leaf number? What optimization problems are W[1]-hard under this parameterization? We do two things: (1) We describe much improved FPT algorithms for a large number of graph problems, for input graphs G for which ml(G) <= k, based on the polynomial-time extremal structure theory canonically associated to this parameter. We consider improved algorithms both from the point of view of kernelization bounds, and in terms of improved fixed-parameter tractable (FPT) runtimes O*(f(k)). (2) The way that we obtain these concrete algorithmic results is general and systematic. We describe the approach, and raise programmatic questions.

关键词： parameterized complexity Max-leaf Bandwidth Well-quasiordering Kernelization

来源：评论

学校读者我要写书评

暂无评论

KERNELIZATION OF CYCLE PACKING WITH RELAXED DISJOINTNESS CONSTRAINTS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2018年第3期32卷 1619-1643页

作者： Agrawal, Akanksha Lokshtanov, Daniel Majumdar, Diptapriyo Mouawad, Amer E. Saurabh, Saket Univ Bergen Dept Informat Bergen Norway HBNI Inst Math Sci Madras Tamil Nadu India

A key result in the field of kernelization, a subfield of parameterized complexity, states that the classic DISJOINT CYCLE PACKING problem, i.e., finding k vertex disjoint cycles in a given graph G, admits no polynomial kernel unless NP subset of coNP/poly. However, very little is known about this problem beyond the aforementioned kernelization lower bound (within the parameterized complexity framework). In the hope of clarifying the picture and better understanding the types of constraints that separate kernelizable from nonkernelizable variants of DISJOINT CYCLE PACKINg, we investigate two relaxations of the problem. The first variant, which we call ALMOST DISJOINT CYCLE PACKING, introduces a global relaxation parameter t. That is, given a graph G and integers k and t, the goal is to find at least k distinct cycles such that every vertex of G appears in at most t of the cycles. The second variant, PAIRWISE DISJOINT CYCLE PACKING, introduces a local relaxation parameter, and we seek at least k distinct cycles such that every two cycles intersect in at most t vertices. While the PAIRWISE DISJOINT CYCLE Packing problem admits a polynomial kernel for all t >= 1, the kernelization complexity of ALMOST DISJOINT CYCLE PACKING reveals an interesting spectrum of upper and lower bounds. In particular, for t = k/c, where c could be a function of k, we obtain a kernel of size O(2(c2) k(7+c) log(3) k) whenever c is an element of o(root k). Thus the kernel size varies from being subexponential when c is an element of o(root k), to quasi-polynomial when c is an element of o(log(l) k), l is an element of R+, and polynomial when c is an element of O(1). We complement these results for ALMOST DISJOINT CYCLE PACKING by showing that the problem does not admit a polynomial kernel whenever t is an element of O(k(epsilon)) for any 0 <= epsilon < 1, unless NP subset of coNP/poly.

关键词： parameterized complexity cycle packing kernelization lower bounds relaxation

来源：评论

学校读者我要写书评

暂无评论

TARGET SET SELECTION IN DENSE GRAPH CLASSES

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2022年第1期36卷 536-572页

作者： Dvorak, Pavel Knop, Dusan Toufar, Tomas Charles Univ Prague Inst Comp Sci Prague 11636 Czech Republic Czech Tech Univ Fac Informat Technol Prague 16000 Czech Republic Charles Univ Prague Fac Math & Phys Prague 11636 Czech Republic

In this paper, we study the TARGET SET SELECTION problem from a parameterized complexity perspective. Here for a given graph and a threshold for each vertex, the task is to find a set of vertices (called a target set) that activates the whole graph during the following iterative process. A vertex outside the active set becomes active if the number of so far activated vertices in its neighborhood is at least its threshold. We give two parameterized algorithms for a special case where each vertex has the threshold set to half of its neighbors (the so-called MAJORITY TARGET SET SELECTION problem) for parameterizations by the neighborhood diversity and the twin cover number of the input graph. We complement these results from the negative side. We give a hardness proof for the MAJORITY TARGET SET SELECTION problem when parameterized by (a restriction of) the modular-width -a natural generalization of both previous structural parameters. We also show the TARGET SET SELECTION problem parameterized by the neighborhood diversity or by the twin cover number is W[1]-hard when there is no restriction on the thresholds.

关键词： parameterized complexity target set selection dense graphs opinion diffusion

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：