Linear degree extractors and the inapproximability of max clique and chromatic number
From MaRDI portal
Publication:2931428
DOI10.1145/1132516.1132612zbMath1301.68152OpenAlexW2126186592WikidataQ56210451 ScholiaQ56210451MaRDI QIDQ2931428
Publication date: 25 November 2014
Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1132516.1132612
Analysis of algorithms and problem complexity (68Q25) Other combinatorial number theory (11B75) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
On the ordered list subgraph embedding problems, On the complexity of minimum \(q\)-domination partization problems, Acyclic Matching in Some Subclasses of Graphs, A review on algorithms for maximum clique problems, Scheduling with conflicts: Online and offline algorithms, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms, Inapproximability of the lid-chromatic number, A CPU-GPU local search heuristic for the maximum weight clique problem on massive graphs, An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy, The complexity of restricted star colouring, Eternal dominating sets on digraphs and orientations of graphs, Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming, On comparing algorithms for the maximum clique problem, A Wide Branching Strategy for the Graph Coloring Problem, A note on anti-coordination and social interactions, Reoptimization of maximum weight induced hereditary subgraph problems, Self-improved gaps almost everywhere for the agnostic approximation of monomials, Hadwiger Number of Graphs with Small Chordality, Strong Inapproximability of the Shortest Reset Word, On the Complexity of Wafer-to-Wafer Integration, Approximability of Two Variants of Multiple Knapsack Problems, Locally identifying coloring of graphs with few P4s, Inapproximability of Maximum Weighted Edge Biclique and Its Applications, On maximum ratio clique relaxations, Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error, Acyclic matching in some subclasses of graphs, Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms, Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation, Hardness and approximation of multiple sequence alignment with column score, Injective colorings with arithmetic constraints, Cliques in Regular Graphs and the Core-Periphery Problem in Social Networks, Security-aware database migration planning, Near-linear convergence of the random Osborne algorithm for matrix balancing, CLIQUE CENTRALITY AND GLOBAL CLIQUE CENTRALITY IN THE JOIN AND CORONA OF GRAPHS, A polyhedral study of lifted multicuts, Scheduling with machine conflicts, Domination and convexity problems in the target set selection model, Maximum subset intersection, The \textsc{max quasi-independent set} problem, Dual parameterization and parameterized approximability of subset graph problems, Factor models on locally tree-like graphs, Local search with edge weighting and configuration checking heuristics for minimum vertex cover, Online vector scheduling and generalized load balancing, The complexity of König subgraph problems and above-guarantee vertex cover, Approximability of the two-stage stochastic knapsack problem with discretely distributed weights, The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number, Hardness of optimal spaced seed design, Computationally-feasible truthful auctions for convex bundles, A Much Faster Branch-and-Bound Algorithm for Finding a Maximum Clique, Why Is Maximum Clique Often Easy in Practice?, Maximum disjoint paths on edge-colored graphs: approximability and tractability, Inapproximability results for graph convexity parameters, Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs, On the max min vertex cover problem, Inapproximability results related to monophonic convexity, How to Cut a Graph into Many Pieces, Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge, Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring, Approximating maximum satisfiable subsystems of linear equations of bounded width, Approximability of clausal constraints, Unnamed Item, Approximating maximum weight \(K\)-colorable subgraphs in chordal graphs, Approximating Independent Set and Coloring in Random Uniform Hypergraphs, Optimal pricing of capacitated networks, On multi-path routing for reliable communications in failure interdependent complex networks, Reoptimization of Weighted Graph and Covering Problems, Approximation of min coloring by moderately exponential algorithms, On the complexity of distributed graph coloring with local minimality constraints, Unnamed Item, A note on the fine-grained complexity of MIS on regular graphs, Extended formulations for vertex cover, Stabbing pairwise intersecting disks by five points, Community detection in dense random networks, “Rent-or-Buy” Scheduling and Cost Coloring Problems, On the approximability of time disjoint walks, \(\ell_1\)-sparsity approximation bounds for packing integer programs, Lower bounds for the happy coloring problems, Lyapunov Exponent of Rank-One Matrices: Ergodic Formula and Inapproximability of the Optimal Distribution, Multitasking Capacity: Hardness Results and Improved Constructions, A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem, New Tools for Graph Coloring, Scheduling Resources for Throughput Maximization, How to extract useful randomness from unreliable sources, Unnamed Item, An incremental search heuristic for coloring vertices of a graph, Auto-G-Computation of Causal Effects on a Network, Finding colorful paths in temporal graphs, Introduction to the Maximum Solution Problem, Worst-case analysis of clique MIPs, Lower bounds on approximating some variations of vertex coloring problem over restricted graph classes, The chromatic discrepancy of graphs, Non-malleability against polynomial tampering, On the hardness of learning queries from tree structured data, The maximum clique problem in multiple interval graphs, Large clique is hard on average for resolution
