Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Maximum Acyclic Subgraph:
TR07-104 | 15th September 2007
Moses Charikar, Konstantin Makarychev, Yury Makarychev

On the Advantage over Random for Maximum Acyclic Subgraph

In this paper we present a new approximation algorithm for the MAX ACYCLIC SUBGRAPH problem. Given an instance where the maximum acyclic subgraph contains (1/2 + delta) fraction of all edges, our algorithm finds an acyclic subgraph with (1/2 + Omega(delta/ log n)) fraction of all edges.

more >>>

TR19-004 | 11th January 2019
Amey Bhangale, Subhash Khot

UG-hardness to NP-hardness by Losing Half

Revisions: 1

The $2$-to-$2$ Games Theorem of [KMS-1, DKKMS-1, DKKMS-2, KMS-2] implies that it is NP-hard to distinguish between Unique Games instances with assignment satisfying at least $(\frac{1}{2}-\varepsilon)$ fraction of the constraints $vs.$ no assignment satisfying more than $\varepsilon$ fraction of the constraints, for every constant $\varepsilon>0$. We show that the reduction ... more >>>

TR21-064 | 5th May 2021
Noah Singer, Madhu Sudan, Santhoshini Velusamy

Streaming approximation resistance of every ordering CSP

An ordering constraint satisfaction problem (OCSP) is given by a positive integer $k$ and a constraint predicate $\Pi$ mapping permutations on $\{1,\ldots,k\}$ to $\{0,1\}$. Given an instance of OCSP$(\Pi)$ on $n$ variables and $m$ constraints, the goal is to find an ordering of the $n$ variables that maximizes the number ... more >>>

ISSN 1433-8092 | Imprint