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

Kernels for feedback arc set in tournaments

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2011年第6期77卷 1071-1078页

作者： Bessy, Stephane Fomin, Fedor V. Gaspers, Serge Paul, Christophe Perez, Anthony Saurabh, Saket Thomasse, Stephan Univ Montpellier 2 LIRMM CNRS F-34932 Montpellier France Univ Bergen Dept Informat N-5020 Bergen Norway Univ Chile CMM Santiago 8370459 Chile Inst Math Sci Madras 600113 Tamil Nadu India

A tournament T = (V, A) is a directed graph in which there is exactly one arc between every pair of distinct vertices. Given a digraph on n vertices and an integer parameter k, the FEEDBACK ARC SET problem asks whether the given digraph has a set of k arcs whose removal results in an acyclic digraph. The FEEDBACK ARC SET problem restricted to tournaments is known as the k-FEEDBACK ARC SET IN TOURNAMENTS (k-FAST) problem. In this paper we obtain a linear vertex kernel for k-FAST. That is, we give a polynomial time algorithm which given an input instance T to k-FAST obtains an equivalent instance T' on O(k) vertices. In fact, given any fixed epsilon > 0, the kernelized instance has at most (2 + epsilon)k vertices. Our result improves the previous known bound of O(k(2)) on the kernel size for k-FAST. Our kernelization algorithm solves the problem on a subclass of tournaments in polynomial time and uses a known polynomial time approximation scheme for k-FAST. (C) 2010 Elsevier Inc. All rights reserved.

关键词： Feedback arc set Tournaments Kernelization parameterized algorithms Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient computation of the oriented chromatic number of recursively defined digraphs

引用

INTERNATIONAL JOURNAL OF CARDIOLOGY 2021年 343卷 16-35页

作者： Gurski, Frank Komander, Dominique Lindemann, Marvin Heinrich Heine Univ Inst Comp Sci Algorithm Hard Problems Grp D-40225 Dusseldorf Germany

In this paper we consider colorings of oriented graphs, i.e. digraphs without cycles of length 2. Given some oriented graph G = (V, E), an oriented r-coloring for G is a partition of the vertex set V into r independent sets, such that all the arcs between two of these sets have the same direction. The oriented chromatic number of G is the smallest integer r such that G permits an oriented r-coloring. Deciding whether an acyclic digraph has an oriented 4-coloring is NP-hard, which motivates to consider the problem on special graph classes. In this paper we consider the Oriented Chromatic Number problem on classes of recursively defined oriented graphs. Oriented co-graphs (short for oriented complement reducible graphs) can be recursively defined from the single vertex graph by applying the disjoint union and order composition. This recursive structure allows to compute an optimal oriented coloring and the oriented chromatic number in linear time. We generalize this result using the concept of perfect orderable graphs. Therefore, we show that for acyclic transitive digraphs every greedy coloring along a topological ordering leads to an optimal oriented coloring. Msp-digraphs (short for minimal series-parallel digraphs) can be defined from the single vertex graph by applying the parallel composition and series composition. We prove an upper bound of 7 for the oriented chromatic number for msp-digraphs and we give an example to show that this is bound best possible. We apply this bound and the recursive structure of msp-digraphs to obtain a linear time solution for computing the oriented chromatic number of msp-digraphs. In order to generalize the results on computing the oriented chromatic number of special graph classes, we consider the parameterized complexity of the Oriented Chromatic Number problem by so-called structural parameters, which are measuring the difficulty of decomposing a graph into a special tree-structure. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Oriented graphs Msp-digraphs Oriented co-graphs Oriented coloring Efficient algorithms Directed clique-width parameterized algorithms CLIQUE-WIDTH GRAPHS COLORINGS PLANAR RECOGNITION COMPLEXITY BOUNDS

来源：评论

学校读者我要写书评

暂无评论

Vertex deletion on split graphs: Beyond 4-hitting set

引用

THEORETICAL COMPUTER SCIENCE 2020年 845卷 21-37页

作者： Choudhary, Pratibha Jain, Pallavi Krithika, R. Sahlot, Vibha Indian Inst Technol Jodhpur Jodhpur Rajasthan India HBNI Inst Math Sci Chennai Tamil Nadu India Indian Inst Technol Palakkad Palakkad India

Vertex deletion problems on graphs involve finding a set of minimum number of vertices whose deletion results in a graph with some specific property. In a recent study on vertex deletion problems on split graphs, it was shown that transforming a split graph to a block graph or a threshold graph using minimum number of vertex deletions isNP-hard. We call the decision version of these problems asSplit to Block Vertex Deletion(SBVD) andSplit to Threshold Vertex Deletion(STVD), respectively. In this paper, we study the parameterized complexity of these problems with the number of vertex deletions, k, as a parameter. These problems are implicit 4-HITTING SET and thus admit an algorithm with running time O* (3.0755(k)), a kernel with O(k(3)) vertices, and a 4-approximation algorithm. In this paper, we exploit the structural properties of the concerned graph classes and obtain a kernel forSBVDwith O(k(2)) vertices and FPT algorithms for SBVD and STVD with running times O* (2.3028(k)) and O*(2.7913(k)), respectively. We further give improved approximation algorithms for SBVD and STVD. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Vertex deletion problems Split graphs parameterized algorithms Kernelization Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

A Quadratic Vertex Kernel for Feedback Arc Set in Bipartite Tournaments

引用

ALGORITHMICA 2015年第1期71卷 87-97页

作者： Xiao, Mingyu Guo, Jiong Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 610054 Peoples R China Univ Saarland D-66123 Saarbrucken Germany

The k-feedback arc set problem is to determine whether there is a set F of at most k arcs in a directed graph G such that the removal of F makes G acyclic. The k-feedback arc set problems in tournaments and bipartite tournaments (k-FAST and k-FASBT) have applications in ranking aggregation and have been extensively studied from the viewpoint of parameterized complexity. By introducing a new concept called "bimodule", we provide a problem kernel with O(k (2)) vertices for k-FASBT, which improves the previous result by a factor of k.

关键词： Kernelization Feedback arc set Bipartite tournament Graph algorithms parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Assigning times to minimise reachability in temporal graphs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2021年 115卷 169-186页

作者： Enright, Jessica Meeks, Kitty Skerman, Fiona Univ Glasgow Sch Comp Sci Glasgow Lanark Scotland Uppsala Univ Dept Math Uppsala Sweden

Temporal graphs (in which edges are active at specified times) are of particular relevance for spreading processes on graphs, e.g. the spread of disease or dissemination of information. Motivated by real-world applications, modification of static graphs to control this spread has proven a rich topic for previous research. Here, we introduce a new type of modification for temporal graphs: the number of active times for each edge is fixed, but we can change the relative order in which (sets of) edges are active. We investigate the problem of determining an ordering of edges that minimises the maximum number of vertices reachable from any single starting vertex;epidemiologically, this corresponds to the worst-case number of vertices infected in a single disease outbreak. We study two versions of this problem, both of which we show to be NP-hard, and identify cases in which the problem can be solved or approximated efficiently. (C) 2020 The Author(s). Published by Elsevier Inc.

关键词： Graph modification Graph contagion Influence spreading Temporal paths parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

BIDIMENSIONALITY AND KERNELS

引用

SIAM JOURNAL ON COMPUTING 2020年第6期49卷 1397-1422页

作者： Fomin, Fedor, V Lokshtanov, Daniel Saurabh, Saket Thilikos, Dimitrios M. Univ Bergen Dept Informat N-5020 Bergen Norway Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA Inst Math Sci TCS Chennai 600113 Tamil Nadu India Univ Montpellier CNRS LIRMM F-34000 Montpellier France

Bidimensionality theory was introduced by [E. D. Demaine et al., T. ACM, 52 (2005), pp. 866-893] as a tool to obtain subexponential time parameterized algorithms on H-minor-free graphs. In [E. D. Demaine and M. Hajiaghayi, Bidimensionality: New connections between FPT algorithms and PTASs, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete algorithms (SODA), SIAM, Philadelphia, 2005, pp. 590-601] this theory was extended in order to obtain polynomial time approximation schemes (PTASs) for bidimensional problems. In this work, we establish a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of linear kernels for parameterized problems. In particular, we prove that every minor (resp., contraction) bidimensional problem that satisfies a separation property and is expressible in Countable Monadic Second Order Logic (CMSO) admits a linear kernel for classes of graphs that exclude a fixed graph (resp., an apex graph) H as a minor. Our results imply that a multitude of bidimensional problems admit linear kernels on the corresponding graph classes. For most of these problems no polynomial kernels on H-minor-free graphs were known prior to our work.

关键词： kernelization parameterized algorithms treewidth bidimensionality

来源：评论

学校读者我要写书评

暂无评论

List-coloring - Parameterizing from triviality

引用

THEORETICAL COMPUTER SCIENCE 2020年 821卷 102-110页

作者： Arora, Pranav Banik, Aritra Paliwal, Vijay Kumar Raman, Venkatesh Media Net Bengaluru Karnataka India HBNI Natl Inst Sci Educ & Res Bhubaneswar India DE Shaw India Private Ltd Hyderabad India HBNI Inst Math Sci Chennai Tamil Nadu India

The classical graph coloring problem is given an undirected graph and the goal is to color the vertices of the graph with the minimum number of colors so that endpoints of each edge gets different colors. In list-coloring, each vertex is given a list of allowed colors with which it can be colored. Most versions of the problems are hard in several paradigms including approximation and parameterized complexity. We consider a few versions of the problems that are polynomial time solvable and try to extend the notion of feasible algorithms by parameterizing suitably in the paradigm of parameterized complexity. In particular, we provide extensions of these polynomial time solvable coloring problems that belong to the extreme ends of the parameterized complexity hierarchy including fixed-parameter tractable (FPT) class or the complexity class XP or W[1]-hard or PARA-NP-hard (i.e. NP-hard even for constant values of the parameter). Specifically, we consider generalizations of odd cycle transversal and edge bipartization in the context of list-coloring and show them fixed-parameter tractable. We also look at LIST COLORING where each list has n - k colors and the goal is to color the vertices respecting the list. We show that the problem is in the parameterized complexity class XP, when parameterized by k. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Graph coloring List coloring parameterized algorithms FPT

来源：评论

学校读者我要写书评

暂无评论

Finding Temporal Paths Under Waiting Time Constraints

引用

ALGORITHMICA 2021年第9期83卷 2754-2802页

作者： Casteigts, Arnaud Himmel, Anne-Sophie Molter, Hendrik Zschoche, Philipp Univ Bordeaux Bordeaux INP CNRS LaBRI Bordeaux France Tech Univ Berlin Algorithm & Computat Complex Berlin Germany

Computing a (short) path between two vertices is one of the most fundamental primitives in graph algorithmics. In recent years, the study of paths in temporal graphs, that is, graphs where the vertex set is fixed but the edge set changes over time, gained more and more attention. A path is time-respecting, or temporal, if it uses edges with non-decreasing time stamps. We investigate a basic constraint for temporal paths, where the time spent at each vertex must not exceed a given duration Delta, referred to as Delta-restless temporal paths. This constraint arises naturally in the modeling of real-world processes like packet routing in communication networks and infection transmission routes of diseases where recovery confers lasting resistance. While finding temporal paths without waiting time restrictions is known to be doable in polynomial time, we show that the "restless variant" of this problem becomes computationally hard even in very restrictive settings. For example, it is W[1]-hard when parameterized by the distance to disjoint path of the underlying graph, which implies W[1]-hardness for many other parameters like feedback vertex number and pathwidth. A natural question is thus whether the problem becomes tractable in some natural settings. We explore several natural parameterizations, presenting FPT algorithms for three kinds of parameters: (1) output-related parameters (here, the maximum length of the path), (2) classical parameters applied to the underlying graph (e.g., feedback edge number), and (3) a new parameter called timed feedback vertex number, which captures finer-grained temporal features of the input temporal graph, and which may be of interest beyond this work.

关键词： Temporal graphs Disease spreading Waiting-time policies Restless temporal paths Timed feedback vertex set NP-hard problems parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Computations by fly-automata beyond monadic second-order logic

引用

THEORETICAL COMPUTER SCIENCE 2016年 619卷 32-67页

作者： Courcelle, Bruno Durand, Irene CNRS LaBRI 351 Cours Liberat F-33405 Talence France Bordeaux Univ 351 Cours Liberat F-33405 Talence France

The validity of a monadic-second order (MS) expressible property can be checked in linear time on graphs of bounded tree-width or clique-width given with appropriate decompositions. This result is proved by constructing from the MS sentence expressing the property and an integer that bounds the tree-width or clique-width of the input graph, a finite automaton intended to run bottom-up on the algebraic term representing a decomposition of the input graph. As we cannot construct practically the transition tables of these automata because they are huge, we use fly-automata whose states and transitions are computed "on the fly", only when needed for a particular input. Furthermore, we allow infinite sets of states and we equip automata with output functions. Thus, they can check properties that are not MS expressible and compute values, for example, the number of p-colorings of a graph. We obtain XP and FPT graph algorithms, parameterized by tree width or clique-width. We show how to construct easily such algorithms by combining predefined automata for basic functions and properties. These combinations reflect the structure of the MS formula that specifies the property to check or the function to compute. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Monadic second-order logic Graph algorithms Infinite automata parameterized algorithms Tree-width Clique-width Dynamic programming Model-checking Data complexity Algorithmic meta-theorems

来源：评论

学校读者我要写书评

暂无评论

Between Treewidth and Clique-Width

引用

ALGORITHMICA 2016年第1期75卷 218-253页

作者： Saether, Sigve Hortemo Telle, Jan Arne Univ Bergen Dept Informat N-5008 Bergen Norway

Many hard graph problems can be solved efficiently when restricted to graphs of bounded treewidth, and more generally to graphs of bounded clique-width. But there is a price to be paid for this generality, exemplified by the four problems MaxCut, Graph Coloring, Hamiltonian Cycle and Edge Dominating Set that are all FPT parameterized by treewidth but none of which can be FPT parameterized by clique-width unless FPT = W[1], as shown by Fomin et al. (Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms, pp 493-502, 2010a;SIAM J Comput 39(5):1941-1956, 2010b). We therefore seek a structural graph parameter that shares some of the generality of clique-width without paying this price. Based on splits, branch decompositions and the work of Vatshelle (New width parameters of graphs. The University of Bergen, 2012) on maximum matching-width, we consider the graph parameter sm-width which lies between treewidth and clique-width. Some graph classes of unbounded treewidth, like distance-hereditary graphs, have bounded sm-width. We show that MaxCut, Graph Coloring, Hamiltonian Cycle and Edge Dominating Set are all FPT parameterized by sm-width.

关键词： parameterized algorithms Width parameters of graphs Split decompositions

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：