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

On the Complexity of Finding Large Odd Induced Subgraphs and Odd Colorings

algorithmICA 2021年第8期83卷 2351-2373页

作者： Belmonte, Remy Sau, Ignasi Univ Electrocommun Chofu Tokyo Japan Univ Montpellier CNRS LIRMM Montpellier France

We study the complexity of the problems of finding, given a graph G, a largest induced subgraph of G with all degrees odd (called an odd subgraph), and the smallest number of odd subgraphs that partition V(G). We call these parameters (G) and chi(odd)(G), respectively. We prove that deciding whether chi(odd)(G) <= q is polynomial-time solvable if q = 2, and NP-complete otherwise. We provide algorithms in time 2O(rw) center dot nO(1) and 2O(q center dot rw) center dot nO(1) to compute chi(odd)(G) and to decide whether chi(odd)(G) = q on n-vertex graphs of rank-width at most rw, respectively, and we prove that the dependency on rank-width is asymptotically optimal under the ETH. Finally, we give some tight bounds for these parameters on restricted graph classes or in relation to other parameters.

关键词： Odd subgraph Odd coloring Rank-width Parameterized complexity single-exponential algorithm exponential time hypothesis

来源：评论

学校读者我要写书评

暂无评论

On the Complexity of Finding Large Odd Induced Subgraphs and Odd Colorings 1

引用

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

作者： Belmonte, Remy Sau, Ignasi Univ Electrocommun Chofu Japan Univ Montpellier CNRS LIRMM Montpellier France

ISBN: (数字)9783030604400

ISBN: (纸本)9783030604394;9783030604400

We study the complexity of the problems of finding, given a graph G, a largest induced subgraph of G with all degrees odd (called an odd subgraph), and the smallest number of odd subgraphs that partition V (G). We call these parameters mos(G) and chi(odd)(G), respectively. We prove that deciding whether chi(odd)(G) <= q is polynomial-time solvable if q <= 2, and NP-complete otherwise. We provide algorithms in time 2(O(rw)).n(O(1)) and 2(O(***)).n(O(1)) to compute mos(G) and to decide whether chi(odd)(G) <= q on n-vertex graphs of rank-width at most rw, respectively, and we prove that the dependency on rank-width is asymptotically optimal under the ETH. Finally, we give some tight bounds for these parameters on restricted graph classes or in relation to other parameters.

关键词： Odd subgraph Odd coloring Rank-width Parameterized complexity single-exponential algorithm exponential Time Hypothesis

来源：评论

学校读者我要写书评

暂无评论

Parameterized Complexity Dichotomy for (r, a)-Vertex Deletion

引用

THEORY OF COMPUTING SYSTEMS 2017年第3期61卷 777-794页

作者： Baste, Julien Faria, Luerbio Klein, Sulamita Sau, Ignasi LIRMM CNRS AlGCo Project Team Montpellier France Univ Estado Rio de Janeiro FFP Rio De Janeiro Brazil Univ Fed Rio de Janeiro Rio De Janeiro Brazil

For two integers r, a"" 0, a graph G = (V, E) is an (r, a"")-graph if V can be partitioned into r independent sets and a"" cliques. In the parameterized (r, a"")-Vertex Deletion... 详细信息

For two integers r, a"" 0, a graph G = (V, E) is an (r, a"")-graph if V can be partitioned into r independent sets and a"" cliques. In the parameterized (r, a"")-Vertex Deletion problem, given a graph G and an integer k, one has to decide whether at most k vertices can be removed from G to obtain an (r, a"")-graph. This problem is NP-hard if r + a"" 1 and encompasses several relevant problems such as Vertex Cover and Odd Cycle Transversal. The parameterized complexity of (r, a"")-Vertex Deletion was known for all values of (r, a"") except for (2,1), (1,2), and (2,2). We prove that each of these three cases is FPT and, furthermore, solvable in single-exponential time, which is asymptotically optimal in terms of k. We consider as well the version of (r, a"")-Vertex Deletion where the set of vertices to be removed has to induce an independent set, and provide also a parameterized complexity dichotomy for this problem.

关键词： Graph modification problem Parameterized complexity Iterative compression FPT-algorithm single-exponential algorithm

来源：评论

学校读者我要写书评

暂无评论

HITTING AND HARVESTING PUMPKINS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2014年第3期28卷 1363-1390页

作者： Joret, Gwenael Paul, Christophe Sau, Ignasi Saurabh, Saket Thomasse, Stephan Univ Libre Bruxelles Dept Informat Brussels Belgium CNRS LIRMM AlGCo Project Team Montpellier France Univ Lyon Lab LIP CNRS ENS LyonINRIAUCBL Lyon France Inst Math Sci Madras 600113 Tamil Nadu India

The c-pumpkin is the graph with two vertices linked by c >= 1 parallel edges. A c-pumpkin-model in a graph G is a pair {A, B} of disjoint subsets of vertices of G, each inducing a connected subgraph of G, such that there are at least c edges in G between A and B. We focus on hitting and packing c-pumpkin-models in a given graph in the realm of approximation algorithms and parameterized algorithms. We give a fixed-parameter tractable (FPT) algorithm running in time 2(O(k))n(O(1)) deciding, for any fixed c >= 1, whether all c-pumpkin-models can be hit by at most k vertices. This generalizes known single-exponential FPT algorithms for Vertex Cover and Feedback Vertex Set, which correspond to the cases c = 1, 2 respectively. Finally, we present an O(log n)-approximation algorithm for both the problems of hitting all c-pumpkin-models with a smallest number of vertices and packing a maximum number of vertex-disjoint c-pumpkin-models.

关键词： hitting and packing parameterized complexity approximation algorithm single-exponential algorithm iterative compression graph minors

来源：评论

学校读者我要写书评

暂无评论

Hitting and Harvesting Pumpkins

引用

19th Annual European Symposium on algorithms (ESA)

作者： Joret, Gwenael Paul, Christophe Sau, Ignasi Saurabh, Saket Thomasse, Stephan Univ Libre Bruxelles Dept Informat Brussels Belgium LIRMM CNRS AlGCo project team Montpellier France UCBL INRIA ENS Lyon Laboratoire LIPU LyonCNRS Madras Tamil Nadu India

ISBN: (纸本)9783642237195

The c-pumpkin is the graph with two vertices linked by c >= 1 parallel edges. A c-pumpkin-model in a graph G is a pair {A, B} of disjoint subsets of vertices of G, each inducing a connected subgraph of G, such that there are at least c edges in G between A and B. We focus on hitting and packing c-pumpkin-models in a given graph: On the one hand, we provide an FPT algorithm running in time 2(O(k))n(O(1)) deciding, for any fixed c >= 1, whether all c-pumpkin-models can be hit by at most k vertices. This generalizes the single-exponential FPT algorithms for VERTEX COVER and FEEDBACK VERTEX SET, which correspond to the cases c = 1, 2 respectively. For this, we use a combination of iterative compression and a kernelization-like technique. On the other hand, we present an O(log n)-approximation algorithm for both the problems of hitting all c-pumpkin-models with a smallest number of vertices, and packing a maximum number of vertex-disjoint c-pumpkin-models. Our main ingredient here is a combinatorial lemma saying that any properly reduced n-vertex graph has a c-pumpkin-model of size at most f(c) log n, for a function f depending only on c.

关键词： Hitting and packing parameterized complexity approximation algorithm single-exponential algorithm iterative compression graph minors

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：