On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments

DOI10.1016/j.dam.2015.01.032zbMath1311.05076MaRDI QIDQ2345613

Anthony Perez

Publication date: 22 May 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.01.032

zbMATH Keywords

dense instances; parameterized complexity; kernelization algorithms; ranking CSP

Mathematics Subject Classification ID

05C85: Graph algorithms (graph-theoretic aspects)

05C20: Directed graphs (digraphs), tournaments

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On making directed graphs transitive
• Kernels for feedback arc set in tournaments
• A kernelization algorithm for \(d\)-hitting set
• On problems without polynomial kernels
• A general method to speed up fixed-parameter-tractable algorithms
• Two edge modification problems without polynomial kernels
• Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
• Hardness of fully dense problems
• A 4 k ² kernel for feedback vertex set
• Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
• Conflict Packing Yields Linear Vertex-Kernels for k -FAST, k -dense RTI and a Related Problem
• Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• Fast FAST
• Kernelization: New Upper and Lower Bound Techniques
• Kernelization Lower Bounds by Cross-Composition
• Ranking Tournaments
• Ordering by weighted number of wins gives a good ranking for weighted tournaments