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

Multistage s-t Path: Confronting Similarity with Dissimilarity

ALGORITHMICA 2023年第7期85卷 2028-2064页

作者： Fluschnik, Till Niedermeier, Rolf Schubert, Carsten Zschoche, Philipp Tech Univ Berlin Fac 4 Algorithm & Computat Complex Berlin Germany

Addressing a quest by Gupta et al. (in: Proceedings of the 41st international colloquium on automata, languages, and programming (ICALP 2014), vol 8572 of LNCS. Springer, pp 563-575, 2014), we provide a first, comprehensive study of finding a short s-t path in the multistage graph model, referred to as the MULTISTAGE s-t PATH problem. Herein, given a sequence of graphs over the same vertex set but changing edge sets, the task is to find short s-t paths in each graph ("snapshot") such that in the found path sequence the consecutive s-t paths are "similar". We measure similarity by the size of the symmetric difference of either the vertex set (vertex-similarity) or the edge set (edge-similarity) of any two consecutive paths. We prove that these two variants of MULTISTAGE s-t PATH are already NP-hard for an input sequence of only two snapshots and maximum vertex degree four. Motivated by this fact and natural applications of this scenario e.g. in traffic route planning, we perform a parameterized complexity analysis. Among other results, for both variants, vertex-and edge-similarity, we prove parameterized hardness (W[1]-hardness) regarding the parameter path length (solution size). As a further conceptual investigation, we then modify the multistage model by asking for dissimilar consecutive paths. As one of the main technical results (employing so-called representative sets known from non-temporal settings), we prove that dissimilarity allows for fixed-parameter tractability for the parameter solution size, contrasting with our W[1]-hardness proof of the corresponding similarity case. We also provide partially positive results concerning efficient and effective data reduction (kernelization).

关键词： Temporal graphs Shortest paths parameterized complexity Kernelization Representative sets in temporal graphs

来源：评论

学校读者我要写书评

暂无评论

Even More Effort Towards Improved Bounds and Fixed-Parameter Tractability for Multiwinner Rules

引用

ALGORITHMICA 2023年第12期85卷 3717-3740页

作者： Gupta, Sushmita Jain, Pallavi Saurabh, Saket Talmon, Nimrod HBNI Inst Math Sci Chennai India Indian Inst Technol Jodhpur Jodhpur India Univ Bergen Bergen Norway Ben Gurion Univ Negev Beer Sheva Israel

Multiwinner elections have proven to be a fruitful research topic with many real world applications. We contribute to this line of research by improving the state of the art regarding the computational complexity of computing good committees. More formally, given a set of candidates C, a set of voters V-each ranking the candidates according to their preferences, and an integer k;a multiwinner voting rule identifies a k-sized committee, based on these given voter preferences. In this paper we consider several utilitarian and egailitarian ordered weighted average scoring rules, which are an extensively-researched family of rules (and a subfamily of the family of committee scoring rules). First, we improve the result of Betzler et al. (JAIR 47:475-519, 2013), which gave a O(n(n)) algorithm for computing winner under the Chamberlin-Courant rule, where n is the number of voters;to a running time of O(2(n)), which is optimal. Furthermore, we study the parameterized complexity of the Pessimist voting rule and describe a few tractable and intractable cases. Apart from such utilitarian voting rules, we extend our study and consider egalitarian median and egalitarian mean (both committee scoring rules), showing some tractable and intractable results, based on nontrivial structural observations.

关键词： Multiwinner election parameterized complexity Chamberlin Courant

来源：评论

学校读者我要写书评

暂无评论

Efficient parameterized algorithms for computing all-pairs shortest paths

引用

DISCRETE APPLIED MATHEMATICS 2023年第1期341卷 102-119页

作者： Kratsch, Stefan Nelles, Florian Humboldt Univ Unter Linden 6 D-10099 Berlin Germany

Computing for all pairs of vertices the shortest paths in a graph is a fundamental and much-studied problem with many applications. Unfortunately, despite intense study, there are still no significantly faster algorithms for it than the O(n(3)) time algorithm due to Floyd and Warshall (1962). Somewhat faster algorithms exist for the vertex-weighted version if fast matrix multiplication may be used. Yuster (SODA 2009) gave an algorithm running in time O(n(2.842)), but no combinatorial, truly subcubic algorithm is known. Motivated by the recent framework of efficient parameterized algorithms (or '' FPT in P ''), we investigate the influence of the graph parameters clique-width (cw) and modular-width (mw) on the running times of algorithms for solving vertex-weighted all-pairs shortest paths. We obtain efficient (and combinatorial) parameterized algorithms of times O(cw(2)n(2)), resp. O(mw(2)n + n(2)). If fast matrix multiplication is allowed then the latter can be improved to O(mw(1.842)n+ n(2)) using the algorithm of Yuster as a black box. The algorithm relative to modular-width is adaptive, meaning that the running time matches the best unparameterized algorithm for parameter value mw equal to n, and outperforms it already for mw epsilon O(n(1-epsilon)) for any epsilon > 0. (c) 2023 Elsevier B.V. All rights reserved.

关键词： All-pairs shortest paths Efficient parameterized algorithms parameterized complexity Clique-width Modular-width

来源：评论

学校读者我要写书评

暂无评论

Efficient Isomorphism for Sd-Graphs and T-Graphs

引用

ALGORITHMICA 2023年第2期85卷 352-383页

作者： Agaoglu Cagirici, Deniz Hlineny, Petr Masaryk Univ Brno Czech Republic

An H-graph is one representable as the intersection graph of connected subgraphs of a suitable subdivision of a fixed graph H, introduced by Biro et al. (Discrete Mathematics 100:267-279, 1992). An H-graph is proper if the representing subgraphs of H can be chosen incomparable by the inclusion. In this paper, we focus on the isomorphism problem for S-d-graphs and T-graphs, where S-d is the star with d rays and T is an arbitrary fixed tree. Answering an open problem of Chaplick et al. (2016, personal communication), we provide an FPT-time algorithm for testing isomorphism and computing the automorphism group of S-d-graphs when parameterized by d, which involves the classical group-computing machinery by Furst et al. (in Proceedings of 11th southeastern conference on combinatorics, graph theory, and computing, congressum numerantium 3, 1980). We also show that the isomorphism problem of S-d-graphs is at least as hard as the isomorphism problem of posets of bounded width, for which no efficient combinatorial-only algorithm is known to date. Then we extend our approach to an XP-time algorithm for isomorphism of T-graphs when parameterized by the size of T. Lastly, we contribute an FPT-time combinatorial algorithm for isomorphism testing in the special case of proper S-d - and T-graphs.

关键词： Intersection graph Isomorphism testing Chordal graph H-graph parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On computing the Hamiltonian index of graphs

引用

THEORETICAL COMPUTER SCIENCE 2023年第PartA期940卷 149-179页

作者： Philip, Geevarghese Rani, M. R. Subashini, R. Chennai Math Inst Chennai India Govt Engn Coll Sreekrishnapuram Dept Informat Technol Palakkad India Natl Inst Technol Dept Comp Sci & Engn Calicut India

For an integer r >= 0 the r-th iterated line graph L-r(G) of a graph G is defined by: (i) L-0(G) = G and (ii) L-r(G) = L(L((r-1))(G)) for r > 0, where L(G) denotes the line graph of G. The Hamiltonian Index h(G) of G is the smallest r such that Lr(G) has a Hamiltonian cycle [Chartrand, 1968]. Checking if h(G) = k is NP-hard for any fixed integer k >= 0 even for subcubic graphs G [Ryjacek et al., 2011]. We study the parameterized complexity of this problem with the parameter treewidth, tw(G), and show that we can find h(G) in time(1) O-star((1 +2((w+3)))(tw(G))) where w is the matrix multiplication exponent. Prior work on computing h(G) includes various O-star(2(O(tw(G))))-time algorithms for checking if h(G) = 0 holds;i.e., whether G has a Hamiltonian Cycle [Cygan et al., FOCS 2011;Bodlaender et al., Inform. Comput., 2015;Fomin et al., JACM 2016];an O-star(tw(G)(O(tw(G))))-time algorithm for checking if h(G) =1 holds;i.e., whether L(G) has a Hamiltonian Cycle [Lampis et al., Discrete Appl. Math., 2017];and, most recently, an O*((1 +2(()w(+3)))(tw(G)))-time algorithm for checking if h(G) =1 holds [Misra et al., CSR 2019]. Our algorithm for computing h(G) generalizes these results. The NP-hard EULERIAN STEINER SUBGRAPH problem takes as input a graph G and a specified subset K of terminal vertices of G and asks if G has an Eulerian2 subgraph H containing all the terminals. A key ingredient of our algorithm for finding h(G) is an algorithm which solves EULERIAN STEINER SUBGRAPH in O-star((1 +2(w(+3))tw(G))) time. To the best of our knowledge this is the first FPT algorithm for EULERIAN STEINER SUBGRAPH. Prior work on the special case of finding a spanning Eulerian subgraph (i.e., with K = V(G)) includes a polynomial-time algorithm for series-parallel graphs [Richey et al., 1985] and an O*(2(O(root n)))-time algorithm for planar graphs on n vertices [Sau and Thilikos, 2010]. Our algorithm for EULERIAN STEINER SUBGRAPH generalizes both these results. (c) 2022 Elsevier B.V

关键词： Hamiltonian index Supereulerian graphs Iterated line graphs parameterized complexity Fixed-parameter tractability Eulerian Steiner subgraphs Spanning Eulerian subgraphs Treewidth

来源：评论

学校读者我要写书评

暂无评论

The complexity of Routing Problems in Forbidden-Transition Graphs and Edge-Colored Graphs

引用

ALGORITHMICA 2023年第5期85卷 1202-1250页

作者： Bellitto, Thomas Li, Shaohua Okrasa, Karolina Pilipczuk, Marcin Sorge, Manuel Sorbonne Univ CNRS LIP6 Paris France Warsaw Univ Technol Fac Math & Informat Sci Warsaw Poland Univ Warsaw Fac Math & Informat & Mech Warsaw Poland

The notion of forbidden-transition graphs allows for a robust generalization of walks in graphs. In a forbidden-transition graph, every pair of edges incident to a common vertex is permitted or forbidden;a walk is compatible if all pairs of consecutive edges on the walk are permitted. Forbidden-transition graphs and related models have found applications in a variety of fields, such as routing in optical telecommunication networks, road networks, and bio-informatics. A widely-studied special case are edge-colored graphs, where a compatible walk is forbidden to take two edges of the same color in a row. We initiate the study of fundamental problems on finding paths, cycles and walks in forbidden-transition graphs from the point of view of parameterized complexity, including an in-depth study of tractability with regards to various graph-width parameters. Among several results, we prove that finding a simple compatible path between given endpoints in a forbidden-transition graph is W[1]-hard when parameterized by the vertex-deletion distance to a linear forest (so it is also hard when parameterized by pathwidth or treewidth). On the other hand, we show an algebraic trick that yields tractability when parameterized by treewidth for finding a compatible Hamiltonian cycle in the edge-colored graph setting.

关键词： Graph algorithms Fixed-parameter tractability parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Envy-freeness and relaxed stability for lower-quotas: A parameterized perspective

引用

DISCRETE APPLIED MATHEMATICS 2023年第1期337卷 288-302页

作者： Limaye, Girija Indian Inst Technol Madras Chennai India

We consider the problem of assigning agents to resources under the two-sided pref-erence list setting where resources specify an upper-quota and a lower-quota, that is, respectively the maximum and minimum number of agents that can be assigned to it. Different notions of optimality including envy-freeness and relaxed stability are investigated for this setting. Krishnaa et al. (2020) show that in this setting, the problem of computing a maximum size envy-free matching (MAXEFM) or a maximum size relaxed stable matching (MAXRSM) that satisfies lower quotas is not approximable within a certain constant factor unless P = *** this work, we investigate the parameterized complexity of MAXEFM and MAXRSM. We show that MAXEFM is W[1]-hard and MAXRSM is para-NP-hard when parame-terized on several natural parameters derived from the instance. We present kernel-ization results and FPT algorithms for both problems parameterized on other relevant parameters.& COPY;2023 Elsevier B.V. All rights reserved.

关键词： Matchings under two-sided preferences Lower-quota Envy-freeness Relaxed stability parameterized complexity Kernelization Fixed-parameter tractability

来源：评论

学校读者我要写书评

暂无评论

Edge Exploration of Temporal Graphs

引用

ALGORITHMICA 2023年第3期85卷 688-716页

作者： Bumpus, Benjamin Merlin Meeks, Kitty TU Eindhoven Math & Comp Sci Groene Loper MetaForum BldgPOB 513 NL-5600 MB Eindhoven Netherlands Univ Glasgow Sch Comp Sci Sir Alwyn Williams Bldg Glasgow G12 8RZ Lanark Scotland

We introduce a natural temporal analogue of Eulerian circuits and prove that, in contrast to the static case, it is NP-hard to determine whether a given temporal graph is temporally Eulerian even if strong restrictions are placed on the structure of the underlying graph and each edge is active at only three times. However, we do obtain an FPT-algorithm with respect to a new parameter called interval-membership-width which restricts the times assigned to different edges;we believe that this parameter will be of independent interest for other temporal graph problems. Our techniques also allow us to resolve two open questions of Akrida, Mertzios and Spirakis [CIAC 2019] concerning a related problem of exploring temporal stars.

关键词： Temporal graphs Dynamic networks parameterized complexity Width measures

来源：评论

学校读者我要写书评

暂无评论

Faster parameterized algorithms for two vertex deletion problems

引用

THEORETICAL COMPUTER SCIENCE 2023年第PartA期940卷 112-123页

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

In the l-PATH VERTEX COVER problem (resp., the l-COMPONENT ORDER CONNECTIVITY problem) the input is an undirected graph G and an integer k. The goal is to decide whether there is a set of vertices of size at most k whose deletion from G results in a graph that does not contain a path with l vertices (resp., does not contain a connected component with at least l vertices). In this paper we give a parameterized algorithm for l-PATH VERTEX COVER when l = 5, 6, 7, whose running times are O*(3.945k), O*(4.947k), and O*(5.951k), respectively. We also give an algorithm for l-COMPONENT ORDER CONNECTIVITY whose running time is O *((l - 1 - El)k) for every l > 4, where El > 0 for every l. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Graph algorithms parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Structural Parameterizations for Equitable Coloring: complexity, FPT Algorithms, and Kernelization

引用

ALGORITHMICA 2023年第7期85卷 1912-1947页

作者： Gomes, Guilherme C. M. Guedes, Matheus R. dos Santos, Vinicius F. Univ Fed Minas Gerais Dept Cencia Computacao Belo Horizonte Brazil

An n-vertex graph is equitably k-colorable if there is a proper coloring of its vertices such that each color is used either [n/k] or [n/k] times. While classic VERTEX COLORING is fixed parameter tractable under well established parameters such as pathwidth and feedback vertex set, equitable coloring is W[1]-hard. We present an extensive study of structural parameterizations of EQUITABLE COLORING, tackling both tractability and kernelization questions. We begin by showing that the problem is fixed parameter tractable when parameterized by distance to cluster or by distance to co-cluster-improving on the FPT algorithm of Fiala et al. (Theor Comput Sci 412(23):2513-2523, 2011) parameterized by vertex cover-and also when parameterized by distance to disjoint paths of bounded length. To justify the latter result, we adapt a proof of Fellows et al. (Inf Comput 209(2):143-153, 2011) to show that EQUITABLE COLORING is W[1]-hard when simultaneously parameterized by distance to disjoint paths and number of colors. In terms of kernelization, on the positive side we present a linear kernel for the distance to clique parameter and a cubic kernel when parameterized by the maximum leaf number;on the other hand, we show that, unlike VERTEX COLORING, EQUITABLE COLORING does not admit a polynomial kernel when jointly parameterized by vertex cover and number of colors, unless NP subset of coNP/poly. We also revisit the literature and derive other results on the parameterized complexity of the problem through minor reductions or other observations.

关键词： Equitable coloring parameterized complexity FPT algorithm Polynomial kernel Cross-composition

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：