Loading...
Please wait, while we are loading the content...
Similar Documents
Sparsification Upper and Lower Bounds for Graph Problems and Not-All-Equal SAT
| Content Provider | Semantic Scholar |
|---|---|
| Author | Nederlof, Jesper Westenberg, Michel A. |
| Copyright Year | 2015 |
| Abstract | Many problems we care for are known to be NP-complete. Therefore, we do not think they can be solved in polynomial time, so only an exponential time algorithm is known. To speed up the search for a solution, we want to start by preprocessing an input instance. You can try to make the input instance smaller in polynomial time, without changing the answer. After doing so, we can run the slow algorithm on a smaller input. This thesis investigated whether there exist such algorithms that reduce the number of edges in graph problems, and the number of clauses for logical formulas. Such an algorithm is called a sparsification. We will show that for a number of decision problems on graphs, polynomial-time algorithms cannot compress instances of such problems to equivalent instances, of a possibly different problem, whose encoding size is sub-quadratic in the number of vertices. Here we only want to maintain the solution (YES/NO), therefore P = NP would imply that any NP-complete problem can be compressed in polynomial time to a single bit, indicating whether it was a YESor a NO-instance. For example look at the 4-colorability problem, which asks if we can color all vertices in a graph in such a way that the endpoints of any edge in the graph have distinct colors. Assuming that NP is not contained in coNP/poly, we show that instances of 4-COLORING cannot be compressed to a sub-quadratic encoding in polynomial time. We obtain similar results for a number of other graph problems. Finally we consider NOT-ALL-EQUAL SAT (NAE-SAT). This is a variant of the well-known satisfiability problem, that plays a central role in the theory of NPcompleteness. We show that an instance of NAE-SAT with n variables and d literals per clause can not be compressed to an equivalent instance of size O(nd−1−ε) for any ε > 0, unless NP ⊆ coNP/poly. Furthermore we present a generalized kernel that matches this lower bound. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://pure.tue.nl/ws/files/47037004/799516-1.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
