Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials

Abstract:
The theory of kernelization can be used to rigorously analyze data reduction for graph coloring problems. Here, the aim is to reduce a q-Coloring input to an equivalent but smaller input whose size is provably bounded in terms of structural properties, such as the size of a minimum vertex cover. In this paper we settle two open problems about data reduction for q-Coloring. First, we obtain a kernel of bitsize $${\\mathcal {O}}(k^{q-1}\\log {k})$$O(kq-1logk) for q-Coloring parameterized by Vertex Cover for any $$q\\ge 3$$q≥3. This size bound is optimal up to\xa0$$k^{o(1)}$$ko(1) factors assuming\xa0$$\\mathsf {NP} \\not \\subseteq \\mathsf {coNP/poly}$$NP⊈coNP/poly, and improves on the previous-best kernel of size\xa0$${\\mathcal {O}}(k^q)$$O(kq). We generalize this result for deciding q-colorability of a graph G, to deciding the existence of a homomorphism from G to an arbitrary fixed graph H. Furthermore, we can replace the parameter vertex cover by the less restrictive parameter twin-cover. We prove that H-Coloring parameterized by Twin-Cover has a kernel of size $${\\mathcal {O}}(k^{\\varDelta (H)}\\log k)$$O(kΔ(H)logk). Our second result shows that 3-Coloring does not admit non-trivial sparsification: assuming $$\\mathsf {NP} \\not \\subseteq \\mathsf {coNP/poly}$$NP⊈coNP/poly, the parameterization by the number of vertices\xa0n admits no (generalized) kernel of size\xa0$${\\mathcal {O}}(n^{2-\\varepsilon })$$O(n2-ε) for any $$\\varepsilon > 0$$ε>0. Previously, such a lower bound was only known for coloring with $$q \\ge 4$$q≥4 colors.
Author Listing： Bart M. P. Jansen;Astrid Pieterse
Volume： None
Pages： 1-25
DOI： 10.1007/s00453-019-00578-5
Language： English
Journal： Algorithmica

ALGORITHMICA

ALGORITHMICA

影响因子：0.9 是否综述期刊：否 是否OA：否 是否预警：不在预警名单内 发行时间：1986 ISSN：0178-4617 发刊频率：Monthly 收录数据库：SCIE/Scopus收录 出版国家/地区：UNITED STATES 出版社：Springer US

期刊介绍

Algorithmica is an international journal which publishes theoretical papers on algorithms that address problems arising in practical areas, and experimental papers of general appeal for practical importance or techniques. The development of algorithms is an integral part of computer science. The increasing complexity and scope of computer applications makes the design of efficient algorithms essential.Algorithmica covers algorithms in applied areas such as: VLSI, distributed computing, parallel processing, automated design, robotics, graphics, data base design, software tools, as well as algorithms in fundamental areas such as sorting, searching, data structures, computational geometry, and linear programming.In addition, the journal features two special sections: Application Experience, presenting findings obtained from applications of theoretical results to practical situations, and Problems, offering short papers presenting problems on selected topics of computer science.

Algorithmica（英语：Algorithmica）是一份国际性期刊，发表关于算法的理论论文，解决实际领域中出现的问题，以及具有实际重要性或技术的实验论文。算法的发展是计算机科学的一个组成部分。随着计算机应用的复杂性和范围的不断扩大，设计有效的算法变得越来越重要。算法学涵盖了以下应用领域的算法：超大规模集成电路、分布式计算、并行处理、自动化设计、机器人、图形学、数据库设计、软件工具，以及诸如排序、搜索、数据结构、计算几何和线性规划等基础领域的算法。此外，该杂志还设有两个特别部分：应用经验，介绍从理论结果到实际情况的应用中获得的发现，和问题，提供简短的论文，介绍计算机科学的选定主题的问题。

年发文量 106
国人发稿量 8
国人发文占比 7.55%
自引率 11.1%
平均录取率 容易
平均审稿周期 偏慢,4-8周
版面费 US$2890
偏重研究方向 工程技术-计算机：软件工程
期刊官网 https://www.springer.com/453/?utm_medium=display&utm_source=letpub&utm_content=text_link&utm_term=null&utm_campaign=MPSR_00453_AWA1_CN_CNPL_letpb_mp
投稿链接 https://www.editorialmanager.com/algo/

质量指标占比

研究类文章占比 OA被引用占比 撤稿占比 出版后修正文章占比
100.00% 39.29% 0.00% 1.40%

相关指数

{{ relationActiveLabel }}
{{ item.label }}

期刊预警不是论文评价，更不是否定预警期刊发表的每项成果。《国际期刊预警名单（试行）》旨在提醒科研人员审慎选择成果发表平台、提示出版机构强化期刊质量管理。

预警期刊的识别采用定性与定量相结合的方法。通过专家咨询确立分析维度及评价指标，而后基于指标客观数据产生具体名单。

具体而言，就是通过综合评判期刊载文量、作者国际化程度、拒稿率、论文处理费（APC）、期刊超越指数、自引率、撤稿信息等，找出那些具备风险特征、具有潜在质量问题的学术期刊。最后，依据各刊数据差异，将预警级别分为高、中、低三档，风险指数依次减弱。

《国际期刊预警名单（试行）》确定原则是客观、审慎、开放。期刊分区表团队期待与科研界、学术出版机构一起，夯实科学精神，打造气正风清的学术诚信环境！真诚欢迎各界就预警名单的分析维度、使用方案、值得关切的期刊等提出建议！

预警情况 查看说明

时间 预警情况
2024年02月发布的2024版 不在预警名单中
2023年01月发布的2023版 不在预警名单中
2021年12月发布的2021版 不在预警名单中
2020年12月发布的2020版 不在预警名单中

JCR分区 WOS分区等级：Q3区

版本 按学科 分区
WOS期刊SCI分区
WOS期刊SCI分区是指SCI官方（Web of Science）为每个学科内的期刊按照IF数值排 序，将期刊按照四等分的方法划分的Q1-Q4等级，Q1代表质量最高，即常说的1区期刊。
（2021-2022年最新版）
MATHEMATICS, APPLIED Q3
COMPUTER SCIENCE, SOFTWARE ENGINEERING Q3

关于2019年中科院分区升级版（试行）

分区表升级版（试行）旨在解决期刊学科体系划分与学科发展以及融合趋势的不相容问题。由于学科交叉在当代科研活动的趋势愈发显著，学科体系构建容易引发争议。为了打破学科体系给期刊评价带来的桎梏，“升级版方案”首先构建了论文层级的主题体系，然后分别计算每篇论文在所属主题的影响力，最后汇总各期刊每篇论文分值，得到“期刊超越指数”，作为分区依据。

分区表升级版（试行）的优势：一是论文层级的主题体系既能体现学科交叉特点，又可以精准揭示期刊载文的多学科性；二是采用“期刊超越指数”替代影响因子指标，解决了影响因子数学性质缺陷对评价结果的干扰。整体而言，分区表升级版（试行）突破了期刊评价中学科体系构建、评价指标选择等瓶颈问题，能够更为全面地揭示学术期刊的影响力，为科研评价“去四唯”提供解决思路。相关研究成果经过国际同行的认可，已经发表在科学计量学领域国际重要期刊。

《2019年中国科学院文献情报中心期刊分区表升级版（试行）》首次将社会科学引文数据库（SSCI）期刊纳入到分区评估中。升级版分区表（试行）设置了包括自然科学和社会科学在内的18个大类学科。基础版和升级版（试行）将过渡共存三年时间，推测在此期间各大高校和科研院所仍可能会以基础版为考核参考标准。 提示：中科院分区官方微信公众号“fenqubiao”仅提供基础版数据查询，暂无升级版数据，请注意区分。

中科院分区 查看说明

版本 大类学科 小类学科 Top期刊 综述期刊
计算机科学
4区
MATHEMATICS, APPLIED
应用数学
3区
COMPUTER SCIENCE, SOFTWARE ENGINEERING
计算机：软件工程
4区
 否 否
2021年12月
基础版
工程技术
4区
MATHEMATICS, APPLIED
应用数学
4区
COMPUTER SCIENCE, SOFTWARE ENGINEERING
计算机：软件工程
4区
 否 否
2021年12月
升级版
计算机科学
4区
MATHEMATICS, APPLIED
应用数学
4区
COMPUTER SCIENCE, SOFTWARE ENGINEERING
计算机：软件工程
4区
 否 否
2020年12月
旧的升级版
计算机科学
4区
MATHEMATICS, APPLIED
应用数学
4区
COMPUTER SCIENCE, SOFTWARE ENGINEERING
计算机：软件工程
4区
 否 否
2022年12月
最新升级版
计算机科学
4区
MATHEMATICS, APPLIED
应用数学
4区
COMPUTER SCIENCE, SOFTWARE ENGINEERING
计算机：软件工程
4区
 否 否
翻译 润色 隐私声明 期刊介绍 SCI论文润色 SCI论文投稿
科研顾问
官方微信公众号