Hardness of fully dense problems

DOI10.1016/j.ic.2007.02.006zbMath1121.68054OpenAlexW2001866149WikidataQ56486199 ScholiaQ56486199MaRDI QIDQ2643075

Nir Ailon, Noga Alon

Publication date: 23 August 2007

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2007.02.006

zbMATH Keywords

NP-hardnessdense problems

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

A survey on the linear ordering problem for weighted or unweighted tournaments, Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique, On Random Betweenness Constraints, Unnamed Item, Voting Procedures, Complexity of, An updated survey on the linear ordering problem for weighted or unweighted tournaments, New results on optimizing rooted triplets consistency, Efficient algorithms for measuring the funnel-likeness of DAGs, Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems, On Random Ordering Constraints, Unnamed Item, Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs, On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
• Quick approximation to matrices and applications
• Approximating minimum feedback sets and multicuts in directed graphs
• Packing directed circuits fractionally
• Additive approximation for edge-deletion problems
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• Random sampling and approximation of MAX-CSP problems
• Tensor decomposition and approximation schemes for constraint satisfaction problems
• A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
• Total Ordering Problem
• A Geometric Approach to Betweenness
• MAX-CUT has a randomized approximation scheme in dense graphs
• Ranking Tournaments
• Aggregating inconsistent information
• Polynomial time approximation schemes for some dense instances of NP-hard optimization problems