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

35th International Symposium on Algorithms and Computation, ISAAC 2024

作者： Jacob, Ashwin Majumdar, Diptapriyo Zehavi, Meirav National Institute of Technology Calicut Kozhikode India Indraprastha Institute of Information Technology Delhi New Delhi India Ben-Gurion University of The Negev Beersheba Israel

ISBN: (纸本)9783959773546

The class of graph deletion problems has been extensively studied in theoretical computer science, particularly in the field of parameterized complexity. Recently, a new notion of graph deletion problems was introduced, called deletion to scattered graph classes, where after deletion, each connected component of the graph should belong to at least one of the given graph classes. While fixed-parameter algorithms were given for a wide variety of problems, little progress has been made on the kernelization complexity of any of them. Here, we present the first non-trivial polynomial kernel for one such deletion problem, where, after deletion, each connected component should be a clique or a tree - that is, as dense as possible or as sparse as possible (while being connected). We develop a kernel of O(k5) vertices for the same. © Ashwin Jacob, Diptapriyo Majumdar, and Meirav Zehavi.

关键词： Cliques or Trees Vertex Deletion Kernelization New Expansion Lemma parameterized complexity Scattered Graph Classes

来源：评论

学校读者我要写书评

暂无评论

Counting Induced Subgraphs: An Algebraic Approach to #W-Hardness

引用

ALGORITHMICA 2022年第2期84卷 379-404页

作者： Doerfler, Julian Roth, Marc Schmitt, Johannes Wellnitz, Philip Saarland Informat Campus Grad Sch Comp Sci Saarbrucken Germany Univ Oxford Dept Comp Sci Oxford England Univ Oxford Merton Coll Oxford England Saarland Informat Campus Cluster Excellence MMCI Saarbrucken Germany Swiss Fed Inst Technol Zurich Switzerland Univ Bonn Math Inst Bonn Germany Saarland Informat Campus Max Planck Inst Informat Saarbrucken Germany

We study the problem #INDSuB(Phi) of counting all induced subgraphs of size k in a graph G that satisfy the property Phi. It is shown that, given any graph property Phi that distinguishes independent sets from bicliques, #INDSuB(Phi) is hard for the class #W[1], i.e., the parameterized counting equivalent of NP. Under additional suitable density conditions on (1), satisfied e.g. by non-trivial monotone properties on bipartite graphs, we strengthen #W[1]-hardness by establishing that #INDSuB(Phi) cannot be solved in time f(k) . n degrees((k)) for any computable function f, unless the Exponential Time Hypothesis fails. Finally, we observe that our results remain true even if the input graph G is restricted to be bipartite and counting is done modulo a fixed prime.

关键词： Counting complexity Edge-transitive graphs Graph homomorphisms Induced subgraphs parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

ON TREEWIDTH AND STABLE MARRIAGE: parameterized ALGORITHMS AND HARDNESS RESULTS (COMPLETE CHARACTERIZATION)

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2022年第1期36卷 596-681页

作者： Gupta, Sushmita Saurabh, Saket Zehavi, Meirav HBNI Inst Math Sci Chennai Tamil Nadu India Ben Gurion Univ Negev Beer Sheva Israel

STABLE MARRIAGE is a fundamental problem to both computer science and economics. Four well-known NP-hard optimization versions of this problem are the SEX-EQUAL STABLE MARRIAGE (SESMI), BALANCED STABLE MARRIAGE (BSMI), MAX-STABLE MARRIAGE WITH TIES (MAX-SMTI), and MIN-STABLE MARRIAGE WITH TIES (MIN-SMTI) problems. In this paper, we analyze these problems from the viewpoint of parameterized complexity. We conduct the first study of these problems in particular, and of problems related to STABLE MARRIAGE in general, with respect to the parameter treewidth. The motivation behind the choice of treewidth is threefold. First, several problems in social choice theory have already been studied with respect to treewidth. The networks relevant to these problems (say, social networks) are clearly also relevant to STABLE MARRIAGE. Thus, the motivation underlying these studies directly extends to our study. Second, empirical studies of the treewidth of several types of networks relevant to STABLE MARRIAGE have also already been undertaken, identifying that some of these networks indeed have a treelike structure. Third, treewidth is the most well studied structural parameter in parameterized complexity. We design optimal parameterized algorithms for all four problems under the treewidth of both their primal graphs and rotation digraphs. First, we study the treewidth tw of the primal graph. We establish that all four problems are W[1]-hard. In particular, while it is easy to show that all four problems admit algorithms that run in time n(O(tw)), we prove that unless the exponential-time hypothesis is false, all of these algorithms are optimal. Next, we study the treewidth tw of the rotation digraph. In this context, MAx-SMTI and MIN-SMTI are not defined. For both SESMI and BSMI, we design (highly nontrivial) algorithms that run in time 2(tw)n(O)(1). Then, for both SESMI and BSMI, we prove that unless the strong exponential-time hypothesis is false, algorithms that run in time (2 -

关键词： stable marriage treewidth parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Is FFT Fast Enough for Beyond 5G Communications? A Throughput-complexity Analysis for OFDM Signals

引用

IEEE ACCESS 2022年 10卷 104436-104448页

作者： Queiroz, Saulo Vilela, Joao P. Monteiro, Edmundo Fed Univ Technol UTFPR Acad Dept Informat BR-84017220 Ponta Grossa PR Brazil Univ Porto Fac Sci Dept Comp Sci CRACS INESCTECCISUC P-4169007 Porto Portugal Univ Coimbra Ctr Informat & Syst Univ Coimbra CISUC Dept Informat Engn P-3030290 Coimbra Portugal

In this paper, we study the impact of computational complexity on the throughput limits of the fast Fourier transform (FFT) algorithm for orthogonal frequency division multiplexing (OFDM) waveforms. Based on the spectro-computational complexity (SC) analysis, we verify that the complexity of an N-point FFT grows faster than the number of bits in the OFDM symbol. Thus, we show that FFT nullifies the OFDM throughput on N unless the N -point discrete Fourier transform (DFT) problem verifies as Omega(N) , which remains a "fascinating" open question in theoretical computer science. Also, because FFT demands N to be a power of two 2(i) (i > 0), the spectrum widening leads to an exponential complexity on i , i.e. O (2(i)i) . To overcome these limitations, we consider the alternative frequency-time transform formulation of vector OFDM (V-OFDM), in which an N -point FFT is replaced by N/L (L > 0) smaller L-point FFTs to mitigate the cyclic prefix overhead of OFDM. Building on that, we replace FFT by the straightforward DFT algorithm to release the V-OFDM parameters from growing as powers of two and to benefit from flexible numerology (e.g., L = 3 , N = 156). Besides, by setting L to Theta (1) , the resulting solution can run linearly on N (rather than exponentially on i) while sustaining a non null throughput as N grows.

关键词： Fast fourier transform computational complexity throughput spectro-computational analysis vector OFDM parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On the threshold of intractability

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2022年 124卷 1-25页

作者： Drange, Pal Gronas Dregi, Markus Sortland Lokshtanov, Daniel Sullivan, Blair D. Univ Bergen Bergen Norway Univ Calif Santa Barbara Santa Barbara CA 93106 USA Univ Utah Salt Lake City UT 84112 USA

The computational complexity of the graph modification problems THRESHOLD EDITING and CHAIN EDITING has been an important open question in computational graph theory for more than 15 years. These problems consist of adding and deleting the fewest possible edges to transform a graph into a threshold or chain graph. We show that both problems are NP-hard, resolving a conjecture by Natanzon, Shamir, and Sharan from 2001. On the positive side, we show both problems admit quadratic vertex kernels and give subexponential time parameterized algorithms solving both problems in 2(O(root klogk)) + n(O(1)) time. Few natural problems are known to be in this complexity class. These results also extend to the completion and deletion variants of both problems, and threshold/chain graphs are the only known graph classes for which all three versions-completion, deletion, and editing-are both NP-complete and solvable in subexponential parameterized time. (C) 2021 Elsevier Inc. All rights reserved.

关键词： Edge editing Threshold graphs parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Faster algorithm for pathwidth one vertex deletion

引用

THEORETICAL COMPUTER SCIENCE 2022年 921卷 63-74页

作者： Tsur, Dekel Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

In the PATHWIDTH ONE VERTEX DELETION (POVD) problem the input is a graph G and an integer k, and the goal is to decide whether there is a set of at most k vertices whose removal from G results in a graph with pathwidth at most 1. In this paper we give an algorithm for POVD whose running time is O* (3.888(k)). (c) 2022 Elsevier B.V. All rights reserved.

关键词： Graph algorithms parameterized complexity Branching algorithms

来源：评论

学校读者我要写书评

暂无评论

Revising Johnson's table for the 21st century

引用

DISCRETE APPLIED MATHEMATICS 2022年 323卷 184-200页

作者： de Figueiredo, Celina M. H. de Melo, Alexsander A. Sasaki, Diana Silva, Ana Univ Fed Rio de Janeiro Rio De Janeiro Brazil Univ Estado Rio De Janeiro Rio De Janeiro Brazil Univ Fed Ceara Fortaleza Ceara Brazil

What does it mean today to study a problem from a computational point of view? We focus on parameterized complexity and on Column 16 "Graph Restrictions and Their Effect"of D.S. Johnson's Ongoing guide, where several puzzles were proposed in a summary table with 30 graph classes as rows and 11 problems as columns. Several of the 330 entries remain unclassified into Polynomial or NP-complete after 35 years. We provide a full dichotomy for the STEINER TREE column by proving that the problem is NP-complete when restricted to UNDIRECTED PATH graphs. We revise Johnson's summary table according to the granularity provided by the parameterized complexity for NP-complete problems.(c) 2021 Elsevier B.V. All rights reserved.

关键词： Computational complexity parameterized complexity NP-complete Steiner tree Dominating set

来源：评论

学校读者我要写书评

暂无评论

Fast Exact Algorithms Using Hadamard Product of Polynomials

引用

ALGORITHMICA 2022年第2期84卷 436-463页

作者： Arvind, V Chatterjee, Abhranil Datta, Rajit Mukhopadhyay, Partha Inst Math Sci HBNI Chennai Tamil Nadu India Chennai Math Inst Chennai Tamil Nadu India

Let C be an arithmetic circuit of size s, given as input that computes a polynomial f is an element of F[x(1), x(2), ..., x(n)], where F is a finite field or the field of rationals. Using the Hadamard product of polynomials, we obtain new algorithms for the following two problems first studied by Koutis and Williams (Faster algebraic algorithms for path and packing problems, 2008, https://***/10.1007/978-3-540-70575-8_47;ACM Trans Algorithms 12(3):31:1-31:18, 2016, https://***/ 10.1145/2885499;Inf Process Lett 109(6):315-318, 2009, https:// ***/10.1016/***.2008.11.004): (k,n)-MLC: is the problem of computing the sum of the coefficients of all degree-k multilinear monomials in the polynomial f. We obtain a deterministic algorithm of running time (n down arrow k/2).n(O(log k)) . s(O(1).) This improvement over the O(n(k)) time brute-force search algorithm answers positively a question of Koutis and Williams (2016). As applications, we give exact counting algorithms, faster than brute-force search, for counting the number of copies of a tree of size k in a graph, and also the problem of exact counting of m-dimensional k-matchings. k-MMD: is the problem of checking if there is a degree-k multilinear monomial in the polynomial f with non-zero coefficient. We obtain a randomized algorithm of running time O(4.32(k) . n(O(1))). Additionally, our algorithm is polynomial space bounded. Other results include fast deterministic algorithms for (k,n)-MLC and k-MMD problems for depth three circuits.

关键词： parameterized complexity Multilinear monomial detection Multilinear monomial counting Arithmetic circuits

来源：评论

学校读者我要写书评

暂无评论

On the tractability of hard scheduling problems with generalized due-dates with respect to the number of different due-dates

引用

JOURNAL OF SCHEDULING 2022年第5期25卷 577-587页

作者： Mosheiov, Gur Oron, Daniel Shabtay, Dvir Hebrew Univ Jerusalem Sch Business Adm Jerusalem Israel Univ Sydney Sch Business Sydney NSW 2006 Australia Ben Gurion Univ Negev Dept Ind Engn & Management Beer Sheva Israel

We study two NP-hard single-machine scheduling problems with generalized due-dates. In such problems, due-dates are associated with positions in the job sequence rather than with jobs. Accordingly, the job that is assigned to position j in the job processing order (job sequence), is assigned with a predefined due-date, delta(j). In the first problem, the objective consists of finding a job schedule that minimizes the maximal absolute lateness, while in the second problem, we aim to maximize the weighted number of jobs completed exactly at their due-date. Both problems are known to be strongly NP-hard when the instance includes an arbitrary number of different due-dates. Our objective is to study the tractability of both problems with respect to the number of different due-dates in the instance, nu(d). We show that both problems remain NP-hard even when nu(d) = 2, and are solvable in pseudo-polynomial time when the value of nu(d) is upper bounded by a constant. To complement our results, we show that both problems are fixed parameterized tractable (FPT) when we combine the two parameters of number of different due-dates (nu(d)) and number of different processing times (nu(p)).

关键词： Scheduling Single machine Generalized due-dates NP-hard Pseudo-polynomial time algorithm parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

W-hardness of the k-center problem parameterized by the skeleton dimension

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第4期44卷 2762-2781页

作者： Blum, Johannes Univ Konstanz Univ Str 10 D-78457 Constance Germany

We study the k-CENTER problem, where the input is a graph G = ( V, E) with positive edge weights and an integer k, and the goal is to select k center vertices C subset of V such that the maximum distance from any vertex to the closest center vertex is minimized. In general, this problem is NP-hard and cannot be approximated within a factor less than 2. Typical applications of the k-CENTER problem can be found in logistics or urban planning and hence, it is natural to study the problem on transportation networks. Common characterizations of such networks are graphs that are (almost) planar or have low doubling dimension, highway dimension or skeleton dimension. It was shown by Feldmann and Marx that k-CENTER is W[1]-hard on planar graphs of constant doubling dimension when parameterized by the number of centers k, the highway dimension hd and the pathwidth pw (Feldmann and Marx 2020). We extend their result and show that even if we additionally parameterize by the skeleton dimension kappa, the k-CENTER problem remains W[1]-hard. Moreover, we prove that under the Exponential Time Hypothesis there is no exact algorithm for k-CENTER that has runtime f (k, hd, pw, kappa) . vertical bar V vertical bar(o(pw+kappa+root k+hd)) for any computable function f.

关键词： k-Center Skeleton dimension Highway dimension parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：