# inapproximability_of_treewidth_and_related_problems__9451d043.pdf

Journal of Artiﬁcial Intelligence Research 49 (2014) 569-600 Submitted 04/2013; published 04/2014

Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems

Yu (Ledell) Wu wuyu@cs.toronto.edu Per Austrin austrin@cs.toronto.edu Toniann Pitassi toni@cs.toronto.edu David Liu liudavid@cs.toronto.edu Department of Computer Science University of Toronto, Ontario, Canada

Graphical models, such as Bayesian Networks and Markov networks play an important role in artiﬁcial intelligence and machine learning. Inference is a central problem to be solved on these networks. This, and other problems on these graph models are often known to be hard to solve in general, but tractable on graphs with bounded Treewidth. Therefore, ﬁnding or approximating the Treewidth of a graph is a fundamental problem related to inference in graphical models. In this paper, we study the approximability of a number of graph problems: Treewidth and Pathwidth of graphs, Minimum Fill-In, One Shot Black (and Black-White) pebbling costs of directed acyclic graphs, and a variety of diﬀerent graph layout problems such as Minimum Cut Linear Arrangement and Interval Graph Completion. We show that, assuming the recently introduced Small Set Expansion Conjecture, all of these problems are NP-hard to approximate to within any constant factor in polynomial time.

1. Introduction

Graphical models provide a computational framework for eﬃciently manipulating probability distributions over high dimensional spaces, often involving hundreds of thousands of variables. This framework has found applications in an enormous range of domains including: medical and fault diagnosis, image understanding, speech recognition, web search, coding theory, and statistical physics (Koller & Friedman, 2009). A graphical model is an eﬃcient representation of a joint distribution over some set of n random variables. Even if the random variables are binary, it is well known that an arbitrary joint distribution requires the speciﬁcation of 2n probabilities. Luckily, in the real world, there is often structure in the distribution that allows one to express it more succinctly. A graphical model represents such a joint probability distribution by a graph where the vertices represent the random variables, and the dependences are modeled by the graph structure. Associated with each vertex of the graph is a conditional probability table, which speciﬁes the conditional probabilities of this random variable, conditioned on its neighboring vertices. The two most common types of graphical models are Bayesian networks (also called belief networks), where the underlying graph is directed, and Markov networks (also called Markov random ﬁelds), where the underlying graph is undirected. The most basic problem in graphical models is the inference problem, which is the problem of computing the posterior marginal

c 2014 AI Access Foundation. All rights reserved.

Wu, Austrin, Pitassi, & Liu

distribution of a variable at some vertex. Unfortunately, inference in general is well-known to be NP-hard to compute exactly as well as to approximate (Roth, 1996). Despite this intractability, an important class of bounded Treewidth instances of probabilistic inference has been identiﬁed and shown to be exactly computable in polynomial time. The Treewidth of a graph (Robertson & Seymour, 1984, 1986) is a fundamental parameter of a graph that measures how close the graph is to being a tree. Treewidth is very closely related to the other notions in machine learning such as Branch-width, Clique-width and Elimination-width (for an overview of Treewidth and related notions, see Bodlaender, Gilbert, Hafsteinsson, & Kloks, 1995). On graphs with small Treewidth and where the tree decomposition is known, a dynamic programming algorithm yields a polynomial-time algorithm. Particular algorithms for probabilistic inference on bounded Treewidth graphs are the junction-tree method, variable elimination and clique trees (e.g. see Koller & Friedman, 2009, ch. 9, 10). These algorithms runs in time exponential in the Treewidth of the tree decomposition and polynomial in the size of the graph. Thus for graphs where a tree decomposition of bounded Treewidth is given, inference is polynomial-time computable. The same ideas also yield polynomial-time algorithms and often even linear time algorithms for small Treewidth instances for an astonishing variety of other NP-hard problems, including: satisﬁability, counting satisfying assignments, constraint satisfaction, vertex cover, maximum independent set, Hamiltonian circuit, query optimization, matrix decomposition, and more generally all problems deﬁnable in monadic second-order logic. (See the excellent survey Bodlaender, 2005 for motivation, including theoretical as well as practical applications of Treewidth.) One catch is that for all of these problems, the algorithm must begin by ﬁnding a tree decomposition, and then use the decomposition to solve the problem. Given the tree decomposition, the algorithm is typically exponential in the width of the underlying tree decomposition. Thus there is a need for eﬃcient algorithms to actually compute the Treewidth of a given graph, and to ﬁnd tree decompositions with optimal or close to optimal width. Unfortunately, while there are many good heuristics for ﬁnding a good tree decomposition, it is NP-hard in general to determine the Treewidth of a graph (Arnborg, Corneil, & Proskurowski, 1987). However, Bodlaender et al. (1995) obtained an O(log n) factor approximation algorithm for Treewidth. In fact, they actually show that if there is a factor c approximation algorithm for vertex separator, then there is an O(c) approximation algorithm for Treewidth. And if there is a factor b approximation algorithm for Treewidth then there is an O(b log n) approximation algorithm for the related Pathwidth problem. The best currently known approximation factor for vertex separator is O( log n) (Feige, Hajiaghayi, & Lee, 2005) and thus the best algorithm for Treewidth ﬁnds a tree decomposition that is within an O( p

log n) factor of the optimal width, and an O(( log n)(log n)) factor approximation algorithm for Pathwidth. It is a longstanding open question whether or not there is a constant factor approximation algorithm for Treewidth. Such an algorithm would lead to faster algorithms to ﬁnd good tree-decompositions for all of the problems mentioned above. The current best known algorithm that achieves a constant factor approximation for Treewidth runs in time 2O(w)O(n), where w is the Treewidth of the underlying graph, and achieves a factor 5 approximation (Bodlaender, 2007) (Earlier approximation algorithms with similar runtimes are Reed, 1992; Amir, 2001). In a book devoted to Treewidth Kloks (1994, p. 62) states:

Inapproximability of Treewidth and Related Problems

We feel this is one of the biggest open problems in the research dealing with Treewidth and Pathwidth at the moment. If the fast algorithms for solving NPhard problems for graphs with bounded Treewidth are ever to become of practical importance, it is undoubtedly of importance to ﬁnd good tree-decompositions for these graphs. Since the (current best) approximations do not make many of these algorithms practical, it is of great interest to know whether approximations with a small constant exist.

Nearly twenty years later, it is still an open problem whether or not there is a polynomialtime algorithm to approximate Treewidth to within a constant factor. Similarly, the approximability of many related graph layout problems is also unresolved, including Minimum Cut Linear Arrangement and Interval Graph Completion. In this paper, we make an important step to resolve this problem by showing that Treewidth, Pathwidth, and a host of related graph layout problems are hard to approximate to within any constant factor, under the Small Set Expansion (SSE) conjecture (Raghavendra & Steurer, 2010). The SSE conjecture is a strengthened version of the conjecture that P is diﬀerent from NP and warrants some explanation. In the next subsection (Section 1.1), we explain the SSE conjecture, and how it relates to the P versus NP question and to related conjectures. We then state our main hardness results for Treewidth, pebbling problems and graph layout problems (Sections 1.2, 1.4, and 1.5), and discuss related results in Section 1.6.

1.1 The Small Set Expansion Conjecture

The P versus NP problem is the most important and intriguing open problem in the ﬁeld of computational complexity theory. Many decision problems in theory and practice have been proven to be NP-hard, which indicates that they are impossible to compute in polynomial time, under the widely believed conjecture that P = NP. The discovery of the PCP theorem in the late 80 s (Arora, Lund, Motwani, Sudan, & Szegedy, 1998; Arora & Safra, 1998) made it possible to prove that for many optimization problems, approximating the optimal value to within a certain factor is as hard as computing the exact optimal value. In other words, under the conjecture that P = NP, it is not possible to approximate certain optimization problems within some factor that depends on the problem. Celebrated results show that it is NP-hard to approximate MAX-3SAT within a ratio of 7

8 + ϵ for any ϵ > 0 (H astad, 2001), which gives the optimal lower bound, since there is a simple algorithm that achieves an approximation ratio of 7

8. Also, it is NP-hard to approximate clique to within a n1 ϵ

factor for any ϵ > 0 (H astad, 1999). Despite this success, for many important problems, the hardness of approximation results obtained through the PCP theorem have not matched the best approximation algorithms known. For example, there are still signiﬁcant gaps in our understanding of the optimal approximability factor for important problems such as: Vertex Cover, Max-Cut, Bipartite Clique, and Kernel Clustering. The formulation of the Unique Games Conjecture (UGC) due to Khot (2002) was intended to clarify the approximability of many optimization problems. The conjecture postulates that the problem of determining the value of a certain type of game, known as a unique game, is NP-hard. The conjecture has inspired a remarkable body of work since its formulation. Under UGC, many of the known algorithms in approximation are proven to be tight (for an excellent survey on this topic, see Khot & Vishnoi, 2005). For instance, under

Wu, Austrin, Pitassi, & Liu

the UGC, the Vertex Cover problem is NP-hard to approximate within a factor of 2 ϵ, for any ϵ > 0 (Khot & Regev, 2008). Perhaps most strikingly, Raghavendra (2008) proved that under the UGC, the semi-deﬁnite programming (SDP) approximation algorithm for a large class of constraint satisfaction problems (CSP) are essentially the best one can hope for. More speciﬁcally, he showed that every maximum constraint satisfaction problem (Max CSP) has an associated sharp approximation threshold τ: for every ϵ > 0, one can achieve a τ ϵ approximation in polynomial time using SDP, but obtaining a τ + ϵ approximation is NP-hard. Thus, the UGC has become the central open problem in inapproximability and encapsulates the barrier of designing better polynomial time approximation algorithms for a large class of problems.

Despite this tremendous progress, still there remain important yet stubborn problems such as Treewidth, Balanced Separator, Minimum Linear Arrangement (MLA), and many other graph layout problems whose approximation status remains unresolved even assuming the UGC. Intuitively this is because the hard instances for these problems seem to require a certain global structure such as expansion. (Expansion is a graph property that is akin to high connectivity, and requires that every subset of vertices that is not too large has a large boundary.) Typical reductions for these problems are gadget reductions which preserve global properties of the unique games instance, such as the lack of expansion. Therefore, barring radically new types of reductions that do not preserve global properties, proving hardness for these problems seems to require a stronger version of UGC, where the instance is guaranteed to have certain expansion properties.

In the work of Raghavendra and Steurer (2010), the Small Set Expansion (SSE) Conjecture was introduced, and it was shown that it implies the UGC, and that the SSE Conjecture follows if one assumes that the UGC is true for somewhat expanding graphs. In follow-up work by Raghavendra et al. (2012), it was shown that the SSE Conjecture is in fact equivalent to the UGC on somewhat expanding graphs, and that the SSE Conjecture implies NP-hardness of approximation for balanced separator and MLA. In this light, the Small Set Expansion conjecture serves as a natural uniﬁed conjecture that yields all of the implications of UGC and also hardness for expansion-like problems that could not be resolved with the UGC.

Our main contribution in this paper is to prove that a wide range of other graph layout problems are SSE-hard to approximate to within any constant factor. For these problems, no evidence of hardness of approximation was known prior to our results. Moreover, we show that Treewidth, Pathwidth, and Minimum Fill-In are SSE-hard to approximate within any constant factor. This is the ﬁrst result giving hardness of (relative) approximation for these problems, and gives evidence that no constant factor approximation algorithm exists for them.

It should be noted that the status of the SSE conjecture is very open at this point. In particular, recent results (Arora, Barak, & Steurer, 2010; Barak, Raghavendra, & Steurer, 2011; Guruswami & Sinop, 2011) give subexponential-time algorithms for small set expansion. Still despite this recent progress providing evidence against the SSE conjecture, it remains open. Our SSE-hardness results for Treewidth and related problems may therefore be viewed as establishing a new connection between a fundamental conjecture in complexity theory, and the approximability of a ubiquitous problem in artiﬁcial intelligence.

Inapproximability of Treewidth and Related Problems

1.2 Width Parameters of Graphs

As mentioned earlier, determining the exact Treewidth of a graph and producing an associated optimal tree decomposition (see Deﬁnition 2.1) is known to be NP-hard (Arnborg et al., 1987), and a central open problem is to determine whether or not there exists a polynomial time constant factor approximation algorithm for Treewidth (see e.g., Bodlaender et al., 1995; Feige et al., 2005; Bodlaender, 2005). The current best polynomial time approximation algortihm for Treewidth (Feige et al., 2005), computes the Treewidth tw(G) within a factor O( p

log tw(G)). On the other hand, the only hardness result to date for Treewidth shows that it is NP-hard to compute Treewidth within an additive error of nϵ

for some ϵ > 0 (Bodlaender et al., 1995). No hardness of approximation is known and not even the possibility of a polynomial-time approximation scheme for Treewidth has been ruled out. In many important special classes of graphs, such as planar graphs (Seymour & Thomas, 1994), asteroidal triple-free graphs (Bouchitt e & Todinca, 2003), and H-minor-free graphs (Feige et al., 2005), constant factor approximations are known, but the general case has remained elusive. On the positive side, there is a large body of literature developing ﬁxed-parameter algorithms for Treewidth. Exactly determining the Treewidth is ﬁxed-parameter tractable: there is a linear time algorithm for computing the (exact) Treewidth for graphs of constant treewidth (Bodlaender, 1996). More speciﬁcally this exact algorithm runs in time 2poly(k)poly(n). Constant factor approximation algorithms achieve better dependence on the treewidth, k, and n, with the best such algorithm running in time 2O(k)O(n) (Bodlaender, 2007). A related graph parameter is the so-called Pathwidth, which can be viewed as measuring how close G is to a path. The Pathwidth pw(G) is always at least tw(G), but can be much larger. The current state of aﬀairs here is similar as for Treewidth; though the current best approximation algorithm only has an approximation ratio of O( p

log pw(G) log n) (Feige et al., 2005), the best hardness result is NP-hardness of additive nϵ error approximation. Using the recently proposed Small Set Expansion (SSE) Conjecture (Raghavendra & Steurer, 2010) discussed earlier, we show that both tw(G) and pw(G) are hard to approximate within any constant factor. In fact, we show something stronger: it is hard to distinguish graphs with small Pathwidth from graphs with large Treewidth. Speciﬁcally:

Theorem 1.1. For every α > 1 there is a c > 0 such that given a graph G = (V, E) it is SSE-hard to distinguish between the case when pw(G) c |V | and the case when tw(G) α c |V |. In particular, both Treewidth and Pathwidth are SSE-hard to approximate within any constant factor.

This is the ﬁrst result giving hardness of (relative) approximation for these problems, and gives evidence that no constant factor approximation algorithm exists for either of them.

1.3 Minimum Fill-In

A closely related graph theoretic property is the Minimum Fill-In of a graph, the minimum number of edges required to add to a graph to triangulate it (i.e., make it chordal).

Wu, Austrin, Pitassi, & Liu

This property has important applications with sparse matrix computations (and in particular Gaussian elimination) and artiﬁcial intelligence (see the excellent survey in Heggernes, 2006). Minimum Fill-in has been known to be ﬁxed parameter tractable since 1994, when Kaplan et al. (1994) gave an O(|E|16k) algorithm, where k is the number of edges required. From there, several improvements to the running time have been given, with the most recent in 2012 by Fomin and Villanger (2012), who gave the ﬁrst subexponential parameterized algorithm, running in time O(2O(

k log k) + k2|V | |E|). In the work of Natanzon et al. (1998), a polynomial time approximation algorithm was presented, which computed a value at most 8k2, where k is the optimal solution. For graphs with degree bounded by d, their algorithm achieves an approximation ratio of O(d2.5 log4(kd)). This remains the best polynomial time approximation algorithm known to date. In particular, it has remained an open question whether a polynomial time constant factor approximation algorithm exists. In this paper, we show that this is not possible, assuming the SSE Conjecture.

Theorem 1.2. It is SSE-hard to approximate the Minimum Fill-In of a graph to within a constant factor.

1.4 Pebbling Problems

Graph pebbling is a rich and relatively mature topic in theoretical computer science. Pebbling is a game deﬁned on a directed acyclic graph (DAG), where the goal is to pebble the sink nodes of the DAG according to certain rules, using the minimum number of pebbles. The rules for pebbling are as follows. A black pebble can be placed on a node if all of the node s immediate predecessors contain pebbles, and can always be removed. A white pebble can always be placed on a node, but can only be removed if all of the node s immediate predecessors contain pebbles. A pebbling strategy is a process of pebbling the sink nodes in a graph according to the above rules. The pebbling cost of a pebbling strategy is the maximum number of pebbles used in the strategy. The Black-White pebbling cost of a DAG is the minimum pebbling cost of all possible pebbling strategies. The black pebbling cost is the minimum pebbling cost over all pebbling strategies that only use black pebbles. Pebbling games were originally devised for studying programming languages and compiler construction, but have later found a broad range of applications in computational complexity theory. Pebbling is a tool for studying the relationship between computation time and space by means of a game played on directed acyclic graphs. It was employed to model register allocation, and to analyze the relative power of time and space as Turing machine resources. For a comprehensive recent survey on graph pebbling, see the work of Nordstr om (2010). Apart from the cost of a pebbling, another important measure is the pebbling time, which is the number of steps (pebble placements/removals) performed. In the context of measuring memory used by computations, this corresponds to computation time, and hence keeping the pebbling time small is a natural priority. The extreme case of this is what we refer to as One-Shot Pebbling, also known as progressive pebbling, considered in the literature (e.g., Sethi, 1973; Lengauer, 1981; Kirousis & Papadimitriou, 1986). In One-Shot Pebbling, we

Inapproximability of Treewidth and Related Problems

have the restriction that each node can receive a pebble only once. Note that this restriction can cause a huge increase in the pebbling cost of the graph (Lengauer & Tarjan, 1982). The One-Shot Pebbling problem is easier to analyze for the following reasons. In the original pebbling problem, in order to achieve the minimum pebbling number, the pebbling time might be required to be exponentially long, which becomes impractical when n is large. On the other hand, the One-Shot Pebbling problem is more amenable to complexity theoretic analysis as it minimizes the space used in a computation subject to the execution time being minimum. In particular, the decision problem for One-Shot Pebbling is in NP (whereas the unrestricted pebbling problems are PSPACE-complete). The One-Shot Black Pebbling problem and One-Shot Black-White Pebbling problems admit an O( log n log n) approximation ratio. We show that they are SSE-hard to approximate to within any constant factor. For black pebbling we show that this holds for single sink DAGs with in-degree 2, which is the canonical setting for pebbling games (it seems plausible that the black-white hardness can be shown to hold for this case as well, though we have not attempted to prove this).

Theorem 1.3. It is SSE-hard to approximate the One-Shot Black Pebbling problem within any constant factor, even in DAGs with a single sink and maximum in-degree 2.

Theorem 1.4. It is SSE-hard to approximate the One-Shot Black-White Pebbling problem within any constant factor.

No hardness of approximation result of any form was known for One-Shot Pebbling problems. We believe that these results can be extended to obtain hardness for more relaxed versions of bounded time pebbling costs as well. We are currently working on this, and have some preliminary results.

1.5 The Connection: Layout Problems

The graph width and One-Shot Pebbling problems discussed in the previous sections may at ﬁrst glance appear to be unrelated. However, both sets of problems are instances of a general family of problems, known as graph layout problems. In a graph layout problem (also known as an arrangement problem, or a vertex ordering problem), the goal is to ﬁnd an ordering of the vertices, optimizing some condition on the edges, such as adjacent pairs being close. Layout problems are an important class of problems that have applications in many areas such as VLSI circuit design. A classic example is the Minimum Cut Linear Arrangement problem (MCLA). In this problem, the objective is to ﬁnd a permutation π of the vertices V of an undirected graph G = (V, E), such that the largest number of edges crossing any point,

max i |{(u, v) E|π(u) i < π(v)}|, (1)

is minimized. MCLA is closely related to the Minimum Linear Arrangement problem (MLA), in which the max in (1) is replaced by a sum. The MCLA problem can be approximated to within a factor O(log n log n). To the best of our knowledge, there is no hardness of approximation for MCLA in the literature. Its cousin MLA was recently proved SSE-hard to approximate within any constant factor

Wu, Austrin, Pitassi, & Liu

(Raghavendra et al., 2012), and we observe that the same hardness applies to the MCLA problem.

Theorem 1.5. It is SSE-hard to approximate the Minimum Cut Linear Arrangement problem within any constant factor.

Another example of graph layout is the Interval Graph Completion Problem (IGC). In this problem, the objective is to ﬁnd a supergraph G = (V, E ) of G with the same vertex set V , such that G is an interval graph (i.e., the intersection graph of a set of intervals on the real line) and having minimum number of edges. While not immediately appearing to be a layout problem, using a simple structural characterization of interval graphs (Ramalingam & Rangan, 1988) one can show that IGC can be reformulated as ﬁnding a permutation of the vertices that minimizes the sum over the longest edges going out from each vertex, i.e., minimizing X

u V max (u,v) E max{π(v) π(u), 0}. (2)

See, for example, the work of Charikar et al. (2010). The current best approximation algorithm for IGC achieves a ratio of O( log n log log n) (Charikar et al., 2010). It turns out that the SSE Conjecture can be used to prove super-constant hardness for this problem as well.

Theorem 1.6. It is SSE-hard to approximate the Interval Graph Completion problem within any constant factor.

There is a distinction in IGC of whether one counts the number of edges in the ﬁnal interval graph this is the most common deﬁnition or whether one only counts the number of edges added to make G an interval graph (which makes the problem harder from an approximability viewpoint). Our result holds for the common deﬁnition and therefore applies also to the harder version. Note that Interval Graph Completion is well connected to Pathwidth: the pathwidth of a graph G is one less than the smallest clique number of an interval graph that contains G as a subgraph. Theorems 1.5 and 1.6 are just two examples of layout problems that we prove hardness of approximation for. By varying the precise objective function and also considering directed acyclic graphs, in which case the permutation π must be a topological ordering of the graph, one can obtain a wide variety of graph layout problems. We consider a set of eight such problems, generated by three natural variations (see Section 2.3 for precise details), and show super-constant SSE-based hardness for all of them in a uniﬁed way. This set of problems includes MLA, MCLA, and IGC, but not problems such as Bandwidth (but on the other hand, strong NP-hardness inapproximability results for Bandwidth are already known Dubey, Feige, & Unger, 2011). See Table 1 in Section 2.3 for a complete list of problems covered.

Theorem 1.7. Assuming the SSE Conjecture, all problems listed in Table 1 (see page 581) are NP-hard to approximate to within any constant factor.

Let us now return to the problems discussed in the previous sections. It should not be surprising that the One-Shot Black Pebbling problem is equivalent to a graph layout

Inapproximability of Treewidth and Related Problems

problem: the one-shot constraint reduces the problem to determining in which order to pebble the vertices; such an ordering induces a pebbling strategy in an obvious way. (Given a graph layout ordering, the vertices can be black pebbled in that order, with each black pebble removed as soon as that vertex is no longer be needed. Conversely, any black pebbling sequence induces the corresponding ordering on the vertices.) For the black-white case, it is known that the One-Shot Black-White Pebbling cost of D is interreducible with a layout problem on an undirected graph G. Both of these layout problems are included in the set of problems we show hardness for, so Theorems 1.3 and 1.4 follow immediately from Theorem 1.7.

Turning to the width parameters, Treewidth is equivalent to a graph layout problem called elimination width. Here the objective function is somewhat more intricate than in the set of basic layout problems we consider in Theorem 1.7, but we are able to extend those results to hold also for elimination width. Pathwidth is also known to be equivalent to a certain graph layout problem, and in fact is equivalent to the layout problem which One-Shot Black-White Pebbling reduces to. We use these connections to prove the hardness of approximation for both Treewidth and Pathwidth, thereby obtaining Theorem 1.1.

1.6 Previous Work

As the reader may have noticed, for all the problems mentioned, the best current algorithms achieve similar poly-logarithmic approximation ratios. Given their close relation, this is of course not surprising. Most of the algorithms are obtained by recursively applying some algorithm for the c-balanced separator problem, in which the objective is to ﬁnd a bipartition of the vertices of a graph such that both sides contain at least a c fraction of vertices, and the number of edges crossing the partition is minimized.

In the pioneering work on separators by Leighton and Rao (1999), an O(log n) approximation algorithm for c-balanced separator was given, which was used to design O(log2 n) approximation algorithm for a number of graph layout problems such as MLA, MCLA, and Register Suﬃciency. Later, Rao and Richa (1998) improved the approximation algorithm for MLA to a ratio O(log n log log n), using a spreading metric method. In the groundbreaking work of Arora et al. (2009), semideﬁnite programming was used to give an improved approximation ratio of O( log n) for c-balanced separator. Using their ideas, improved algorithms for ordering problems have been found, such as the O( log n log log n) approximation algorithm for IGC and MLA (Charikar et al., 2010), the O( log n) approximation algorithm for Treewidth (Feige et al., 2005) and the O( log n log n) approximation algorithm for Pathwidth (Feige et al., 2005).

It is known that the Register Suﬃciency problem (also known as One-Shot Black Pebbling) admits a O(log2 n) approximation algorithm (Ravi, Agrawal, & Klein, 1991). We observe that by plugging in the improved approximation algorithm for direct vertex separator (Agarwal, Charikar, Makarychev, & Makarychev, 2005) into the algorithm by Ravi et al. (1991), one can improve this to an O( log n log n) approximation algorithm.

Again, in these algorithms, the approximation algorithm for c-balanced separator plays a key role. An improved algorithm for c-balanced separator will also improve the approximation algorithms for the other problems. On the other hand, hardness of approximating

Wu, Austrin, Pitassi, & Liu

c-balanced separator (Raghavendra et al., 2012) does not necessarily imply hardness of approximating layout problems. On the hardness side, our work builds upon the work by Raghavendra et al. (2012), which showed that the SSE Conjecture implies superconstant hardness of approximation for MLA (and for c-balanced separator). The only other hardness of relative approximation that we are aware of for these problems is a result of the work of Amb uhl et al. (2007), showing that MLA does not have a PTAS unless NP has randomized subexponential time algorithms.

1.7 Organization

The outline for the rest of the paper is as follows. In Section 2, we formally deﬁne the layout problems studied as well as Treewidth, Pathwidth, and Minimum Fill-In. After giving an overview of the reductions used in Section 3 we give the full proof of Theorem 1.7 in Section 4. Then, in Section 5 we give the lower bound on Treewidth which combined with the results from Section 4 gives Theorem 1.1. In Section 6 we give the lower bound on Minimum Fill-In. Finally in Section 7 we give some additional reductions for our pebbling instances in order to achieve indegree 2 and single sinks, as promised in Theorem 1.3. We end with some concluding remarks in Section 8.

2. Deﬁnitions and Preliminaries

For an undirected graph G = (V, E), and subsets S, S V , E(S, S ) denotes the set of edges that go between S and S . In other words, E(S, S ) is the set of edges (u, v) E such that u S and v S .

2.1 Treewidth, Elimination Width, and Pathwidth

Deﬁnition 2.1 (Tree decomposition, Treewidth). Let G = (V, E) be a graph, T a tree, and let V = (Vt)t T be a family of vertex sets Vt V indexed by the vertices t of T. The pair (T, V) is called a tree decomposition of G if it satisﬁes the following three conditions:

(T1) V = t T Vt;

(T2) for every edge e E, there exists a t T such that both endpoints of e lie in Vt;

(T3) for every vertex v V , {t T | v Vt} is a subtree of T .

The width of (T, V) is the number max{|Vt| 1 | t T}, and the Treewidth of G, denoted tw(G), is the minimum width of any tree decomposition of G.

Deﬁnition 2.2. Let G = (V, E) be a graph, and let v1, . . . , vn be some ordering of its vertices. Consider the following process: for each vertex vi in order, add edges to turn the neighborhood of vi into a clique, and then remove vi from G. This is an elimination ordering of G. The width of an elimination ordering is the maximum over all vi of the degree of vi when vi is eliminated. The elimination width of G is the minimum width of any elimination order.

Inapproximability of Treewidth and Related Problems

Theorem 2.3 (See e.g., Bodlaender, 2007). For every graph G, the elimination width of G equals tw(G).

Thus Treewidth is another example of a layout problem. In principle this layout problem can be formulated in the framework of Section 2.3, but the choice of cost function is now more involved than the vertexand edge-counting considered there.

Deﬁnition 2.4 (Path decomposition, Pathwidth). Given a graph G, we say that (T, V) is a path decomposition of G if it is a tree decomposition of G and T is a path. The Pathwidth of G, denoted pw(G), is the minimum width of any path decomposition of G.

As claimed earlier, Pathwidth is in fact equivalent with a graph layout problem. (See the next section for the formal deﬁnition of layout.)

Theorem 2.5 (Kinnersley, 1992). For every graph G, we have pw(G) = Layout(G; V, max).

2.2 Minimum Fill-In

Deﬁnition 2.6 (Chordal, Triangulation). A graph G is chordal if and only if every cycle of length at least 4 has a chord. For any (possibly non-chordal) graph G, a triangulation of G is a supergraph of G which is chordal.

Deﬁnition 2.7 (Minimum Fill-In). The Minimum Fill-In of a graph G is the minimum number of edges required to add to G to triangulate it; i.e., so that the resulting supergraph is chordal.

The problem of determining the Minimum Fill-In of a graph is sometimes called the Chordal Graph Completion problem. A perfect elimination ordering of G is an elimination ordering such that no edges are ever added to G. Put another way, for each vertex vi, its neighbours appearing after it in the ordering form a clique.

Theorem 2.8 (Fulkerson & Gross, 1965). A graph G is chordal if and only if it has a perfect elimination ordering.

Treewidth and Minimum Fill-In are related through the following theorem.

Theorem 2.9 (Folklore). Suppose G is a graph with Treewidth k. Then every triangulation of G has a clique of size k + 1.

2.3 Graph Layout Problems

In this subsection, we describe the set of graph layout problems that we consider. A problem from the set is described by three parameters, giving rise to several diﬀerent problems. These three parameters are by no means the only interesting graph layout problems (and some of the settings give rise to more or less uninteresting layout problems). However, they are suﬃcient to capture the problems we are interested in except Treewidth, which in principle could be incorporated as well though we refrain from doing so in order to keep the deﬁnitions simple (see Section 2.1 for more details).

Wu, Austrin, Pitassi, & Liu

First a word on notation. Throughout the paper, G = (V, E) denotes an undirected graph, and D = (V, E) denotes a directed (acyclic) graph. Letting n denote the number of vertices of the graph, we are interested in bijective mappings π : V [n]. We say that an edge (u, v) E crosses point i [n] (with respect to the permutation π, which will always be clear from context), if π(u) i < π(v). We consider the following variations:

1. Undirected or directed acyclic: In the case of an undirected graph G, any ordering π of the vertices is a feasible solution. In the case of a DAG D, only the topological orderings of D are feasible solutions.

2. Counting edges or vertices: for a point i [n] of the ordering, we are interested in the set Ei(π) of edges crossing this point. When counting edges, we use the cardinality of Ei as our basic measure. When counting vertices, we only count the set of vertices Vi to the left of i that are incident upon some edge crossing i. In other words, Vi is the projection of Ei(π) to the left-hand side vertices. Formally:

Ei(π) = {e E | π(u) i < π(v) where e = (u, v)}

Vi(π) = {u V | π(u) i < π(v) for some (u, v) E}

We refer to |Ei(π)| or |Vi(π)| (depending on whether we are counting edges or vertices) as the cost of π at i.

3. Aggregation by sum or max: given an ordering π, we aggregate the costs of each point i [n], by either summation or by taking the maximum cost.

Given these choices, the objective is to ﬁnd a feasible ordering π that minimizes the aggregated cost.

Deﬁnition 2.10. (Layout value) For a graph H (either an undirected graph G or a DAG D), a cost function C (either E or V ), and an aggregation function agg : R R (either Σ or max), we deﬁne Layout(H; C, agg) as the minimum aggregated cost over all feasible orderings of H. Formally:

Layout(H; C, agg) = min feasible π agg i [n] |Ci(π)|.

Example 2.11. Layout(G; E, max) = min π max i [n] |Ei(π)|,

where π ranges over all orderings of V (G). This we recognize from Section 1.5 as the Minimum Cut Linear Arrangement value of G.

Example 2.12. Layout(D; V, max) = min π max i [n] |Vi(π)|,

where π ranges over all topological orderings of the DAG D. As we shall see in Section 2.4, this is precisely the One-Shot Black Pebbling cost of D.

Inapproximability of Treewidth and Related Problems

Problem Also known as / Equivalent with undir. edge sum Minimum/Optimal Linear Arrangement undir. edge max Minimum Cut Linear Arrangement Cut Width undir. vertex sum Interval Graph Completion Sum Cut undir. vertex max Pathwidth One-Shot Black-White Pebbling DAG edge sum Minimum Storage-Time Sequencing Directed MLA/OLA DAG edge max DAG vertex sum DAG vertex max One-Shot Black Pebbling Register Suﬃciency

Table 1: Taxonomy of Layout Problems

Combining the diﬀerent choices gives rise to a total of eight layout problems (some more natural than others). Several of these appear in the literature under one or more names, and some turn out to be equivalent1 to problems that at ﬁrst sight appear to be diﬀerent. We summarize some of these names in Table 1. In some cases the standard deﬁnitions of these problems look somewhat diﬀerent than the deﬁnition given here (e.g., for Pathwidth, One-Shot Pebbling, and Interval Graph Completion). For the Pebbling and Pathwidth problems, we discuss these equivalences of deﬁnitions in the following two sections. For Interval Graph Completion, recall from Section 1.5 that the objective is to minimize X

u V max (u,v) E max{π(v) π(u), 0}.

In other words, we are counting the longest edge going to the right from each point i. If the length of this edge is l then the edge contributes 1 to Vi(π), . . . , Vi+l 1(π) and hence the objective can be rewritten as X

u V |Vi(π)|,

so that Interval Graph Completion is precisely Layout(G; V, Σ).

2.4 Pebbling Problems

In this section we deﬁne pebbling problems and their one-shot versions.

Deﬁnition 2.13. (Pebbling Conﬁgurations) Let D = (V, E) be a directed acyclic graph (DAG). A pebbling conﬁguration of D is a pair (B, W) of (disjoint) subsets of vertices (representing the set B of vertices that have black pebbles, and the set W of vertices that have white pebbles on them).

1. Here, we consider two optimization problems equivalent if there are reductions between them that change the objective values by at most an additive constant.

Wu, Austrin, Pitassi, & Liu

Deﬁnition 2.14. (Black and Black-White Pebbling Strategies) Let D = (V, E) be a directed acyclic graph. A Black-White Pebbling strategy for D is a sequence of pebble conﬁgurations P = {P0, . . . , Pτ} such that:

(i) the ﬁrst and last conﬁgurations contain no pebbles; that is P0 = Pτ = ( , ).

(ii) each sink vertex u of D is pebbled at least once, i.e., there is some Pt = (Bt, Wt) such that u Bt Wt.

(iii) each conﬁguration follows from the previous conﬁguration by one of the following rules:

(a) A black pebble can be removed from a vertex.

(b) A black pebble can be placed on a pebble-free vertex v if all of the immediate predecessors of v are pebbled.

(c) A white pebble can be placed on a pebble-free vertex.

(d) A white pebble can be removed from a vertex v if all of the immediate predecessors of v are pebbled.

A Black Pebbling Strategy for G is a Black-White Pebbling strategy in which no white pebbles are used.

The cost of a pebbling strategy is cost(P) = max0 t τ{|Bt Wt|}. The Black-White Pebbling cost of D is the minimum cost of any Black-White Pebbling strategy of D, and similarly the Black Pebbling cost of D is the minimum cost of any Black Pebbling Strategy of D.

Deﬁnition 2.15. (One-Shot Black and One-Shot Black-White Pebbling) A One-Shot Black (resp. Black-White) pebbling strategy is a Black (resp. Black-White) Pebbling strategy in which each node is only pebbled once. The One-Shot Black (resp. Black-White) pebbling cost of D, denoted BP1s(D) (resp. BWP1s(D)) is the minimum cost of any One-Shot Black (resp. Black-White) Pebbling strategy of D.

As mentioned in Table 1, One-Shot Pebbling problems can be formulated as Layout problems.

Lemma 2.16. For every DAG D = (V, E), we have BP1s(D) = Layout(D, V, max).

Proof. Suppose π is the optimal ordering of Layout(D, V, max), we pebble the vertices according to π. We remove a pebble from vertex u if and only if all of the successors of u are pebbled. Since π is a topological order of D, this is a valid pebbling strategy. It is easy to verify that after pebbling π(i), the number of pebbles on the graph is |Vi(π)|. Therefore the number of pebbles used in the above strategy is Layout(D, V, max). On the other hand, suppose Γ is the optimal pebbling strategy, let σ be the ordering of vertices to receive a pebble in Γ. We consider the number of pebbles on the graph after pebbling the i-th vertex in σ. For any vertex u that has a pebble, if the vertex has a successor that has not yet been pebbled, then the pebble on u cannot be removed, since u cannot be pebbled again. Therefore the number of pebbles on the graph is at least |Vi(σ)|. Thus BP1s(D) maxi [n] |Vi(σ)| Layout(D, V, max).

Inapproximability of Treewidth and Related Problems

For One-Shot Black-White Pebbling, we have the following reductions by Lengauer (1981), showing that One-Shot Black-White Pebbling is equivalent to the undirected Max Vertex Layout Problem.

Lemma 2.17 (Lengauer, 1981). For a given DAG D = (V, E), let GD = (V, ED) be an undirected graph with ED = {(v, w) | (v, w) E} {(v, w) | u, (v, u), (w, u) E}. Then

BWP1s(D) = Layout(GD, V, max) 1.

Lemma 2.18 (Lengauer, 1981). For an undirected graph G = (V, E), let DG = (V E, EG) be a DAG with EG = {(v, e) | e E, v V, v e}. Then

Layout(G, V, max) = BWP1s(DG) + 2.

2.5 Small Set Expansion Conjecture

In this section we deﬁne the SSE Conjecture. Let G = (V, E) be an undirected d-regular graph. For a set S V of vertices, we write ΦG(S) for the (normalized) edge expansion of S,

ΦG(S) = |E(S, V \ S)|

d|S| The Small Set Expansion Problem with parameters η and δ, denoted SSE(η, δ), asks if G has a small set S which does not expand or whether all small sets are highly expanding.

Deﬁnition 2.19 (SSE(η, δ)). Given a d-regular graph G = (V, E) 2, SSE(η, δ) is the problem of distinguishing between the following two cases:

Yes There is an S V with |S| = δ|V | and ΦG(S) η.

No For every S V with |S| = δ|V | it holds that ΦG(S) 1 η.

This problem was introduced by Raghavendra and Steurer (Raghavendra & Steurer, 2010), who conjectured that the problem is hard.

Conjecture 2.20 (Small Set Expansion Conjecture). For every η > 0, there is a δ > 0 such that SSE(η, δ) is NP-hard.

As has become common for a conjecture like this (such as the Unique Games Conjecture), we say that a problem is SSE-hard if it is as hard to solve as the SSE problem. Formally, a decision problem P (e.g., a gap version of some optimization problem) is SSE-hard if there is some η > 0 such that for every δ > 0, SSE(η, δ) polynomially reduces to P. Subsequently, Raghavendra et al. (2012) showed that the SSE Problem can in turn be reduced to a quantitatively stronger form of itself. To state this stronger version, we need to ﬁrst deﬁne Gaussian noise stability.

Deﬁnition 2.21. Let ρ [ 1, 1]. We deﬁne Γρ : [0, 1] [0, 1] by

Γρ(µ) = Pr X Φ 1(µ) Y Φ 1(µ)

where Φ 1 is inverse function of normal distribution, and X and Y are jointly normal

random variables with mean 0 and covariance matrix 1 ρ ρ 1

2. d is a constant

Wu, Austrin, Pitassi, & Liu

The only property we shall need of Γρ is the following well-known fact on the asymptotic behaviour for ρ close to 1 and µ bounded away from 0.

Fact 2.22. (Raghavendra et al., 2012) There is a constant c > 0 such that for all suﬃciently small ϵ and all µ [1/10, 1/2],

Γ1 ϵ(µ) µ(1 c ϵ).

We can now state the strong form of the SSE Conjecture.

Conjecture 2.23 (SSE Conjecture, Equivalent Formulation). For every integer q > 0 and ϵ, γ > 0, it is NP-hard to distinguish between the following two cases for a given d-regular graph G = (V, E)

Yes There is a partition of V into q equi-sized sets S1, . . . , Sq such that ΦG(Si) 2ϵ for every 1 i q.

No For every S V , letting µ = |S|/|V |, it holds that ΦG(S) 1 (Γ1 ϵ/2(µ) + γ)/µ.

For future reference, let us make two remarks about the strong form of the conjecture.

Remark 2.24. In the Yes case of Conjecture 2.23, the number of edges leaving Si is at most |E(Si, V \ Si)|3 = ΦG(Si)d|S| 4ϵ|E|/q.

In particular, the total number of edges that are not contained in one of the Si s is at most

i |E(Si, V \ Si)| 2ϵ|E|.

Remark 2.25. Using Fact 2.22 we see that, in the No case of Conjecture 2.23, we have

for some constant c > 0, provided µ [1/10, 1/2] and setting γ ϵ. In particular, for every |V |/10 |S| 9|V |/10, we have |E(S, V \ S)| c ϵ|E| (switching roles of S and V \ S for |S| > |V |/2), for some constant c > 0 (not the same constant as in Fact 2.22).

3. Brief Overview of Reductions

In this section, we give a very brief overview of the reductions used to prove that the layout problems of Table 1 are SSE-hard to approximate within any constant factor. The full details of these reductions can be found in Section 4. For the two undirected edge problems (i.e., MLA and MCLA), the hardness follows immediately from the strong form of the SSE Conjecture (Conjecture 2.23) for the case of MLA this was proved in the work of Raghavendra et al. (2012) and the proof for MCLA is similar. This is our starting point for the remaining problems. Unfortunately, the results do

3. E(S1, S2) indicates the number of edges between vertex set S1 and S2

Inapproximability of Treewidth and Related Problems

SSE Problem

Undirected Edge Problems (MLA/MCLA) with expansion

Directed Problems

Undirected Vertex Problems

Nice Pebbling Instances

Figure 1: Overview of Reductions. Dashed arrows indicate that the reduction is obtained by the identity mapping, whereas solid arrows indicate a nontrivial transformation from one problem to the other.

not follow from hardness for MLA/MCLA in a black-box way; for the soundness analyses we end up having to use the expansion properties of the original SSE instance. We then give a reduction from MLA/MCLA to the four directed problems. This reduction simply creates the bipartite graph where the vertex set is the union of the edges and vertices of the original graph G, with directed arcs from an edge e to the vertices incident upon e in G. The use of direction here is crucial: it essentially ensures that both the vertex and edge counts of any feasible ordering corresponds very closely to the number of edges crossing the point in the induced ordering of G. To obtain hardness for the remaining two undirected problems, we perform a similar reduction as for the directed case, creating the bipartite graph of edge-vertex incidences. However, since we are now creating an undirected graph, we can no longer force the edges to be chosen before the vertices upon which they are incident, which was a key property in the reduction for the directed case. In order to overcome this, we duplicate each original vertex a large number of times. This gives huge penalties to orderings which do not essentially obey the desired direction of the edges, and makes the reduction work out. The results for Treewidth, which are presented in Section 5, follows from an additional analysis of the instances produced by the reduction for undirected vertex problems. Finally, the reduction for directed problems, implying hardness for One-Shot Black Pebbling, does not produce the kind of nice instances promised by Theorem 1.3. In Section 7, we give some additional transformation to achieve these properties. Figure 1 gives a high-level overview of these reductions.

4. Hardness For Layout Problems

In this section, we show that all of the layout problems deﬁned in Section 2.3 are SSEhard to approximate within any constant factor. This also shows that Pathwidth and the One-Shot Pebbling problems are hard to approximate within any constant.

4.1 Hardness for MCLA and MLA

In this section, we recall the proof in the work of Raghavendra et al. (2012) for MLA, and observe that it applies to MCLA as well. For an undirected graph G, let us write MCLA(G)

Wu, Austrin, Pitassi, & Liu

(resp., MLA(G)) for the MCLA value (resp., MLA value) of G, i.e.,

MLA(G) = Layout(G; E, Σ) = min π

i [n] |Ei(π)|

MCLA(G) = Layout(G; E, max) = min π max i [n] |Ei(π)|.

Theorem 4.1. For every ϵ > 0, given a graph G = (V, E), it is SSE-hard to distinguish between:

Yes MLA(G) O(ϵ |V | |E|) and MCLA(G) O(ϵ|E|)

No For every S V with |V |/10 |S| 9|V |/10, it holds that |E(S, V \ S)| Ω( ϵ|E|). In particular, MLA(G) Ω( ϵ |V | |E|) and MCLA(G) Ω( ϵ|E|).

Proof. We use the instances for Conjecture 2.23 with q = 1/ϵ. Let G = (V, E) be an instance for Conjecture 2.23. In the Yes case, we have disjoint sets S1, . . . , Sq and for each set Sj, |Sj| = n/q = ϵn, ΦG(Sj) 2ϵ. We give an ordering π : V [1, .., n] of the vertices such that maxi [n] |Ei(π)| 3ϵ|E| as follows. Order the vertices as S1, . . . , Sq (with the order within each Sj chosen arbitrary) and let this order be π. For any i [n], we show that |Ei(π)| 3ϵ|E|. Suppose π 1(i) is a vertex in Sj. Each edge in Ei(π) either has both end-points inside Sj, or its endpoints in two diﬀerent Sk s. The total number of edges inside Sj is at most ϵdn/2 = ϵ|E|. Moreover, by Remark 2.24, the total number of edges with end-points in two diﬀerent Sk s is at most 2ϵ|E|. Therefore, MCLA(G) maxi |Ei(π)| 3ϵ|E|. The MLA value can be bounded similarly. The property of the No instance is the same as in Conjecture 2.23 (via Remark 2.25), and the implications for the MLA and MCLA values are immediate.

4.2 Reduction To Directed Graphs

Given an undirected graph G = (V, E), we construct a directed graph D = (V , E ) as follows. In order to distinguish the elements of V and E from the elements of V and E , we refer to elements of V as vertices, elements of E as edges, elements of V as nodes, and elements of E as arcs. There is a node in D for each vertex and for each edge of G, i.e., V = V E. The graph D is bipartite with bipartition V, E, and there is an arc in D from e E to v V if e is incident upon v. Formally,

E = {(e, v) | e E, v V, v e}.

See also Figure 2. The remainder of this section is devoted to analyzing the reduction. First, it is easy to give an upper bound on the four Layout values of D in terms of the MLA and MCLA values of G.

Inapproximability of Treewidth and Related Problems

(u, w) (u, v)

Figure 2: The reduction from G to D.

Lemma 4.2. The DAG D constructed from G as above satisﬁes the following:

Layout(D; E, Σ) (MLA(G) + O(|E|)) (d + 1)

Layout(D; E, max) MCLA(G) + d.

Note that, for the purposes of applying this to the graphs of Theorem 4.1 the error term of |E| (resp. d) is insignifcant compared to the MLA (resp. MCLA) value of G.

Proof. Consider an ordering π of V . For a set of vertices S of V , let uπ(S) S denote the vertex of S that comes ﬁrst in the ordering π. We extend π to an ordering π of V by inserting each edge e = (u, v) immediately before the vertex uπ(e). It is easy to see that for each node z V ,

|Ez(π )| |Euπ(z)(π)| + d

where Ev(π) for a vertex v is an abbreviation for Eπ(v)(π). This immediately implies

Layout(D; E, max) max z V |Ez(π )| max u V |Eu(π)| + d,

Setting π to be an optimal MCLA ordering of G, we obtain the second claim of the Lemma. Similarly, using that |u 1 π (v)| d + 1 for every v V , we get

Layout(D; E, Σ) X

z V |Ez(π )| = X

z V uπ(z)=v

|Ez(π )| (d + 1) X

v V |Ev(π)| + d|V |,

Setting π to be an optimal MLA ordering of G and using |V | = O(|E|), we obtain the ﬁrst claim of the Lemma.

Next we use Theorem 4.1 to argue the converse direction.

Lemma 4.3. Let 0 ϵ < 1. Suppose G has the property that for every |V |/10 |S| 9|V |/10 we have |E(S, V \ S)| Ω( ϵ|E|). Then,

Layout(D; V, Σ) Ω( ϵ|E|2)

Layout(D; V, max) Ω( ϵ|E|)

Wu, Austrin, Pitassi, & Liu

Proof. Let π be any ordering of V . Using the expansion property of Theorem 4.1, we ll show that this ordering must have high cost. For a point i [N], let Si be the set of vertices of V that appear after i in π . The bound on Layout(D; V, max) is immediate: consider a point i [N] such that |Si| = |V |/2. By the expansion property |E(Si, V \ Si)| Ω( ϵ|E|), and since each such edge e has one of its endpoints before or at point i, the node e itself must appear before point i and thus |Vi(π )| |E(Si, V \ Si)| Ω( ϵ|E|). Let us then turn to Layout(D; V, Σ). Write ci for the fraction of edges e that appear before (or at) point i in π . We shall show that whenever 1/5 ci 4/5, we have |Vi(π )| Ω( ϵ|E|), giving a total of Layout(D; V, Σ) Ω( ϵ|E|2). By a simple counting argument, we have

d|Si| 2(1 ci)|E|,

implying |Si| (1 ci)|V | which for ci 4/5 is at least a 1/5 fraction of vertices. If in addition |Si| 9|V |/10, the argument above gives |Vi(π )| Ω( ϵ|E|). The remaining case is that |Si| 9|V |/10. But then Si is incident upon at least a 9/10 fraction of edges. This implies that the number of edges incident upon Si, appearing before i in π , are at least |E|(ci 1/10) which for ci 1/5 is Ω( ϵ|E|).

Combining Lemma 4.2 and Lemma 4.3, with Theorem 4.1, and using the fact that edge costs are always larger than the corresponding vertex costs, we immediately obtain the following theorem.

Theorem 4.4. Given a DAG D, Layout(D; E, max), Layout(D; E, Σ), Layout(D; V, max), and Layout(D; V, Σ) are all SSE-hard to approximate within any constant factor, even in DAG s with maximum path length 1 (i.e., every vertex is a source or a sink).

Proof. Given a graph G, Theorem 4.1 says that it is SSE-hard to distinguish between

Yes MLA(G) O(ϵ |V | |E|) and MCLA(G) O(ϵ|E|)

No For every S V with |V |/10 |S| 9|V |/10, it holds that |E(S, V \ S)| Ω( ϵ|E|). In particular, MLA(G) Ω( ϵ |V | |E|) and MCLA(G) Ω( ϵ|E|).

Applying the reduction to directed graphs, Lemma 4.2 tells us that the Yes case becomes

Layout(D; E, Σ) (d + 1)O(ϵ|V ||E| + |E|) = O(ϵ|E|2)

Layout(D; E, max) O(ϵ|E|),

and Lemma 4.3 tells us that the No case becomes

Layout(D; V, Σ) Ω( ϵ|E|2)

Layout(D; V, max) Ω( ϵ|E|).

thereby establishing a hardness factor of Ω(1/ ϵ) for each of the four problems (using that Layout(D; V, ) Layout(D; E, )).

Inapproximability of Treewidth and Related Problems

(u, w) (u, v)

v1, . . . , vr w1, . . . , wr

u1, . . . , ur u

Figure 3: The reduction from G to G , illustrated for r = 3.

Remark 4.5. In fact we see that, as in Theorem 4.1, the four hardness results apply to the same instance, so that it is SSE-hard to distinguish all of the four Layout values being high from all of them being low.

As the One-Shot Black Pebbling problem is precisely Layout(D; V, max), we obtain hardness for One-Shot Black Pebbling as an immediate corollary. However, the instances are not single-sink DAGs with maximum indegree 2, as promised in Theorem 1.3. In Section 7 we show how to transform the instances further to obtain such DAGs.

4.3 Undirected Vertex Problems

The reduction for undirected vertex problems is very similar to the reduction for directed problems given in the previous section. As before, we introduce nodes for every edge of G. As in the directed case, we are interested in orderings where an edge appears before its two endpoints, but we cannot use direction to force this anymore. Instead, we ensure that orderings that are not like this incur a high cost by replicating each node corresponding to a vertex of G many times. Given an undirected graph G = (V, E), we construct a new graph G = (V , E ) as follows. There are r nodes in G for each vertex and one node for each edge of G, i.e., V = V [r] E. For a vertex u V we write u1, . . . , ur to denote the r copies of u and refer to each such set of r nodes as a vertex group. The graph G is bipartite with bipartition V [r], E, and there is an edge in G between e E and vi V [r] if e is incident upon v. Formally,

V = {vi | v V, i [r]} {e | e E}

E = {(e, vi) | e E, v V, v e, i [r]}.

See also Figure 3.

Wu, Austrin, Pitassi, & Liu

Lemma 4.6. The graph G constructed from G as above satisﬁes the following:

Layout(G ; V, Σ) (d + r) MLA(G)

Layout(G ; V, max) MCLA(G).

Proof. We proceed as in the proof of Lemma 4.2. An ordering π of V naturally induces an ordering π of V : put all r copies of u V consecutively, with vertices of V appearing in the same order as in π, and insert each edge e E immediately before its ﬁrst vertex. Again, for an edge e E, let uπ(e) denote the endpoint of e that appears ﬁrst in π. Similarly, for a copy vi V of v V , let uπ(vi) = v. It is easy to see that the constructed ordering π

|Vz(π )| |Euπ(z)(π)|

for every z V . This immediately implies

Layout(G ; V, max) max z V |Vz(π )| max u V |Eu(π)|,

Similarly, as in Lemma 4.2 we use that |u 1 π (π)| d + r and get

Layout(G ; V, Σ) X

z V |Vz(π )| (d + r) X

v V |Ev(π)|.

Lemma 4.7. Let 0 ϵ < 1. Suppose G has the property that for every |V |/10 |S| 9|V |/10 we have |E(S, V \ S)| Ω( ϵ|E|). Then, if r |V | |E|, we have

Layout(G ; V, Σ) Ω( ϵ r |V | |E|)

Layout(G ; V, max) Ω( ϵ|E|)

Proof. Let π be an ordering of V . First we have the following simple claim, establishing that for good orderings, most vertices appear after their edges.

Claim 4.8. Suppose that for some vertex u V , at least r/2 of the copies of u in G appear before some edge e = (u, v) E adjacent upon u. Then

max i [N] |Vi(π )| r/4 Ω( ϵ |E|) X

i [N] |Vi(π )| (r/4)2 Ω( ϵ r |V | |E|).

Proof. Let I1 be the ﬁrst half of the positions where copies of u appear before e, and I2 the second half. Thus, |I1|, |I2| r/4. Then each element of I1 contributes to Vi(π ) for each i I2, giving the claimed bounds.

Thus we may without loss of generality assume that for each vertex u of V , at least r/2 of its r copies in G appear after all edges adjacent upon u. From now on, let us discard all the r/2 bad copies of each vertex of V that appear before some of its edges. This only decreases the cost of π , and there are still r|V |/2 vertex nodes left. Let i1 be the (ﬁrst) point of π such that r|V |/10 vertex nodes are to the left of i1, and i2 the (last) point of π such that r|V |/10 vertex nodes are to the right of i2.

Inapproximability of Treewidth and Related Problems

Claim 4.9. For any point i between i1 and i2, we have |Vi(π )| Ω( ϵ|E|).

Proof. Let S V (resp. T V ) be the set of vertices u such that some copy of u appears before i (resp. after i). We then have |S|, |T| r|V |/10

r/2 |V |/5, and S T = V . Thus we can partition V into S S, T T such that |S |, |T | 4|V |/5. By the expansion property of G we have |E(S , T )| Ω( ϵ|E|). Further, we also have |Vi(π )| |E(S , T )| as each e E(S , T ) must appear before i in π (because one of their endpoints is in S) but have an edge crossing i (because the other of their endpoints is in T).

From Claim 4.9, the proof of the lemma follows immediately.

As in the previous section, we can now combine Lemma 4.6 and Lemma 4.7, with Theorem 4.1, to obtain:

Theorem 4.10. Given a graph G, Layout(G; V, max), Layout(G; V, Σ) are both SSE-hard to approximate within any constant factor, even in bipartite graphs.

As the Pathwidth problem is precisely Layout(G; V, max), we obtain hardness for Pathwidth as an immediate corollary. In the next section, we ll show the stronger soundness required for Theorem 1.1.

5. Hardness For Treewidth

In this section we shall complete our proof of Theorem 1.1 by showing that the hard instances for Pathwidth from Theorem 4.10 also have large Treewidth.

Lemma 5.1. Let 0 ϵ < 1. Let G = (V, E) be an undirected graph with the property that for every |V |/10 |S| 9|V |/10 we have |E(S, V \S)| Ω( ϵ|E|), and let G be the graph obtained by applying the reduction of Section 4.3 to G. Then, if r |V | |E|, we have

tw(G ) Ω( ϵ|E|)

To prove Lemma 5.1, we shall use the fact that the Treewidth of a graph is closely related to an expansion-like property called the 1/2-separator number, deﬁned in the work of Bodlaender et al. (1995).

Deﬁnition 5.2 (1/2-vertex separator, 1/2-separator number). Let G = (V, E) be an undirected graph. For W V , a 1/2-vertex separator of W in G is a set S V of vertices such that every connected component of the graph G[V S] contains at most |W|/2 vertices of W. Let ψG(1/2, W) denote the minimum size of a 1/2-vertex separator of W in G. We deﬁne the 1/2-separator number K1/2(G) to be

K1/2(G) = max W V ψG(1/2, W).

Lemma 5.3 (Bodlaender et al., 1995). For every graph G = (V, E), it holds that tw(G) K1/2(G) 1.

Using this, it is now straightforward to prove the lower bound on the Treewidth.

Wu, Austrin, Pitassi, & Liu

Proof of Lemma 5.1. We ll show that ψG (1/2, V ) Ω( ϵ|E|) (i.e. we choose W = V ). Suppose C is an optimal 1/2-vertex separator of V and it separates V \ C into l sets V 1, . . . , V l , each of size at most |V |/2. We can merge two sets in V 1, . . . , V l by combining the vertex set of them. By merging diﬀerent V i we may assume that we only have two sets V 1 and V 2, both of size at least |V |/5 (this can be achieved by always merging the two sets with smallest number of vertices, whever there are more than two sets left). Now, similarly to the proof of Claim 4.9, let S V (resp. T V ) be the set of vertices v such that some copy of V appears in V 1 (resp. V 2). As |V 1|, |V 2| r|V |/5, this implies that both |S|, |T| are at least |V |/5, and furthermore S T = V (since otherwise all r copies of some vertex are in C, implying |C| r Ω( ϵ|E|)). We can thus choose a balanced partition S , T such that S S, T T, and we have |E(S , T )| Ω( ϵ|E|). But every edge e = (u, v) such that u S and v T must belong to C, since it is connected (in G ) to every copy of u and v.

6. Hardness for Minimum Fill-In

In this section, we use the previous construction and results for Treewidth to prove the inapproximability of Minimum Fill-In. Speciﬁcally, we will show that applying the construction to the SSE No instances produces graphs with high Minimum Fill-In, while Yes instances yields graphs with low Minimum Fill-In.

Lemma 6.1. Let 0 ϵ < 1. Let G = (V, E) be an undirected graph with the property that for every |V |/10 |S| 9|V |/10 we have |E(S, V \ S)| Ω( ϵ|E|), and let G be the graph obtained by applying the reduction of Section 4.3 to G. Then, if r |V | |E|, at least Ω(ϵ|E|2) edges must be added to triangulate G .

Proof. We use the observation that G is bipartite. Consider a minimum triangulation of G, which must have a clique of size tw(G ) + 1. By Lemma 5.1, one set of of the bipartition of G must have Ω( ϵ|E|) vertices in this clique, and since these vertices are independent in G , Ω(ϵ|E|2) edges must be added.

Note that this lemma holds independently of the choice of q. Now we prove a good upper bound on Yes instances.

Lemma 6.2. Let ϵ > 0 and q = 1/ϵ2. Let G = (V, E) be a d-regular graph, and suppose there is a partition of V into q equi-sized sets S1, . . . , Sq such that ΦG(Si) 2ϵ for every 1 i q. Let G = (V , E ) be the graph obtained by applying the reduction of Section 4.3 to G. Then G has a triangulation with |E | + O(ϵ2|E|2) edges. Suppose G = (V, E) is a Yes instance of Conjecture 2.23 with parameters q, ϵ, with q = 1/ϵ2, and apply the previous construction with r |V | |E| to get a graph G = (V , E ). Then G has a triangulation with |E | + O(ϵ2|E|2) edges.

Proof. Note that it suﬃces to ﬁnd a good ordering of the vertices of G which is close to being a perfect elimination ordering, i.e., that requires few additional edges to turn it into a perfect elimination ordering. For each i, we deﬁne the set

Ei = {(u, v) E | u, v Si}.

Inapproximability of Treewidth and Related Problems

Also deﬁne the set of cut edges Ec = {(u, v) E | u Si, v Sj, i = j}. Clearly, the Ei together with Ec form a partition of E. Further deﬁne subsets of Ec by Ei c = E(Si, V \Si), the set of cut edges of Si. By the deﬁnition of the Si, ΦG(Si) 2ϵ, and hence |Ei c| 4ϵ|E|/q = 4ϵ3|E|. We ll identify the Ei and Ec as subsets of Y in the constructed graph. Now let π be an ordering of V such that all r|V | of the vertex copies appear ﬁrst (in any order), followed by the sets E1, . . . , Eq, Ec in that order, where within each set the vertex order is arbitrary. Now consider the following supergraph H of G obtained by:

making each set Ei Ei c a clique

making Ec a clique/

Claim 1: This only adds O(ϵ2|E|2) edges.

Note that |Ei Ei c| d|Si| = d|V |

2 . Thus making Ei Ei c a clique requires O(ϵ4|E|2) edges. Since there are q = 1 ϵ2 of these cliques in total, this requires O(ϵ2|E|2) edges total. Finally, by Remark 2.24, |Ec| 2ϵ|E|, so making this a clique takes O(ϵ2|E|2) edges as well. Claim 2: Adding these edges makes π a perfect elimination ordering for H. Consider a vertex copy vk X. Its neighbours in H are the edges which are incident with v; if v Si, then these edges must all be in Ei Ei c. So every vertex in X satisﬁes the perfect elimination property. Now consider (u, v) Ei Y . Its edge neighbours are all in Ei or Ei c. Finally, for every edge vertex (u, v) Ec, its only neighbours that appear after it with respect to π are also in Ec. Putting these two claims together yields the desired result.

Combining these two lemmas prove Theorem 1.2.

7. Nicer Pebbling Instances

In this section we show how to transform our hard instances for One-Shot Black Pebbling so as to have in-degree bounded by 2 and single sinks.

Lemma 7.1. Given a DAG D = (V, E) we can in polynomial time construct a DAG D = (V , E ) such that D has a single sink and

BP1s(D) BP1s(D ) BP1s(D) + s + 1,

where s is the number of sinks in D. Furthermore, the maximum in-degree in D is no larger than the maximum in-degree in D, provided this quantity is at least 2.

Proof. Construct D by adding a binary tree with s leaves to D, and identifying the leaves of the tree with the sinks of D. That is, D consists of a binary tree with s leaves on top of a copy of D where the leaves of the binary tree are identiﬁed with the sinks of D. The number of vertices of D is equal to |D| + |s| 1. Note that any binary tree with s leaves will suﬃce. The properties of D are easily veriﬁed. Since D is a super-DAG of D, its pebbling cost must be at least BP1s(D). Conversely, a valid pebbling of D can be obtained by using a One-Shot Pebbling of D but without removing pebbles from the sinks, and then pebbling the tree.

Wu, Austrin, Pitassi, & Liu

Figure 4: Pyramid of size 4

For the in-degree, we prove the following.

Lemma 7.2. Given a DAG D = (V, E) we can in polynomial time construct a DAG D = (V , E ) such that every node of D has in-degree at most 2 and

BP1s(D) BP1s(D ) BP1s(D) + d,

where d is the maximum in-degree of D. Furthermore, if D has a single sink then so does D .

Before proving Lemma 7.2, let us see how to use the two Lemmas to derive Theorem 1.3.

Proof of Theorem 1.3. By (the proof of) Theorem 4.4, there is a reduction which takes an instance (G = (V, E) for Conjecture 2.23 and produces a dag D such that BP1s(D) = Layout(D; V, max) = O(ϵ|E|) if G is a Yes instance, and BP1s(D) = Ω( ϵ|E|) if G is a No instance. The number of sinks in D is |V | = 2|E|/d, which is much smaller than O(ϵ|E|) provided d 1/ϵ (which may be assumed without loss of generality). The maximum indegree in D is the maximum degree of G which is d = O(1). Applying the reduction of Lemma 7.1 and then the reduction of Lemma 7.2 we obtain a dag D with a single sink and in-degree 2 such that BP1s(D) BP1s(D ) BP1s(D) + d + 2|E|/d. Since d + 2|E|/d O(ϵ|E|) BP1s(D), we conclude that it is SSE-hard to distinguish between BP1s(D ) O(ϵ|E|) and BP1s(D ) Ω( ϵ|E|).

7.1 Lemma 7.2

In this section we prove Lemma 7.2. First, recall the deﬁnition of a pyramid graph.

Deﬁnition 7.3. A pyramid graph of size d is a layered graph of indegree two, with d layers, labelled 0, 1, . . . , d 1. Layer zero (the input layer) consists of d vertices, and layer i contains d i vertices. Call the vertices at layer i v1 i , . . . vd i i . For all i, 1 i d 1, 1 j d i, Vertex vj i has incoming edges from vertices vj i 1 and vj+1 i 1 . See Figure 4.

The reduction of Lemma 7.2 to produce DAGs of indegree 2 is as follows. Construct D

by replacing each vertex u by a pyramid Pu of size d(u) (here, d(u) denotes the indegree of u), where the d(u) vertices at layer 0 of Pu are identiﬁed with the predecessors of u, and u is identiﬁed with the vertex at layer d(u) 1 of Pu. See Figure 5.

Inapproximability of Treewidth and Related Problems

v1 v1 v2 v2 v3 v3 v4 v4 v5 v5 v6 v6 v7 v7

u1 u2 u1 u2

Figure 5: Reduction to DAGs of indegree 2

To prove the lemma we need to show that D constructed this way satisﬁes

BP1s(D) BP1s(D ) BP1s(D) + d,

where d is the maximum indegree of any vertex u of D. In what follows whenever we say pebbling strategy of D or D we always refer to a One-Shot Black Pebbling strategy of D or D . The upper bound on BP1s(D ) is trivial: if S is a valid pebbling strategy for D, then clearly we can create a corresponding pebbling strategy for D by pebbling through the pyramid whenever D pebbles the sink of the pyramid. This takes at most d additional pebbles. In the other direction, we want to show that a pebbling strategy for D can be converted into a pebbling strategy for D. We ﬁrst show that D can be assumed to be in a particular normal form, and then using this normal form, we show how to simulate the pebbling.

Deﬁnition 7.4. Let S be a pebbling strategy of D . That is, S is a sequence of conﬁgurations, where each conﬁguration is a set of black pebble placements, and such that the sequence of conﬁgurations follows the black pebbling rules. We say that conﬁguration c S is saturated with respect to a pyramid Pu if c is the ﬁrst time in S that there is a black pebble path cutting the sink of Pu from all of the sources of Pu. (The cut does not include any sources or the sink of Pu.) Note that this cut has size d 1.

Claim 7.5. Let S be a pebbling strategy for D . We can assume without loss of generality that S has the following normal form. For each conﬁguration c S , if c is saturated with respect to pyramid Pu, then the subsequent moves of S pebble the sink of Pu (in the obvious way), removing all other black pebbles on the internal nodes of Pu.

Proof Sketch. We show that any pebbling strategy can be converted into a normal form strategy of the same pebbling cost. At a saturated conﬁguration c , there must be d 1 pebbles on internal nodes of Pu. If we subsequently pebble the sink of p, we never use more than d 1 pebbles on internal nodes of p, and all other pebbles on the graph stay as they were. Thus the normal form does not use more pebbles than the original strategy. Furthermore, since the internal nodes of a pyramid are only used to pebble the sink of this pyramid, we have not lost anything by pebbling through to the sink and removing the other internal black pebbles.

Wu, Austrin, Pitassi, & Liu

From now on we assume that the pebbling S of D has the above normal form. That is, if a conﬁguration is saturated (with respect to a pyramid Pu), the next thing that happens in S is to pebble the sink of Pu. (After pebbling the sink, we will have not touched whatever pebbles were on the source nodes of Pu, and we will have a pebble on the sink node of Pu, and no other internal pebbles on Pu.) Our strategy for constructing a pebbling, S, of D, given a normal form pebbling, S of D is as follows. For each node v of D, pebble v whenever it is ﬁrst pebbled in S , and remove the pebble from v as soon as all successors of v (in the original graph D) are pebbled. We want to argue that the cost of the pebbling strategy S is not greater than that of S . To see this, we use the following Lemma.

Lemma 7.6. In any minimal-length One-Shot Black Pebbling of a size d pyramid, the number of pebbles on the pyramid at any point in time, up until all sources are pebbled, must be at least the number of sources in that pyramid that have been pebbled so far.

Assuming the above Lemma it is clear that if S is a normal form pebbling of D , then for any pyramid Pu in D , and any conﬁguration c , if there are k pebbles on Pu at c , then in the corresponding conﬁguration c of D, there are at most k pebbles on source nodes of Pu. To see this, ﬁrst notice that by the above Lemma, any time a pyramid is being pebbled in D up until the time when all source nodes of the pyramid are pebbled for the ﬁrst time, the number of pebbles on the pyramid will be at least as large as the number of source nodes in D that contain pebbles. Then by the normal form property of D , as soon as all source nodes of D are pebbled for the ﬁrst time, the strategy pebbles the sink of D , and thus again the number of corresponding pebbles on D is never greater than the number of pebbles on D .

Proof of Lemma 7.6. Let P be a size d pyramid graph, and let S be a One-Shot Black Pebbling of P. Let c be a conﬁguration occurring in S such that the set of source nodes that have been pebbled up to c are the source nodes of P , where P is a size d subpyramid of P. We want to argue that c must contain at least d pebbles. Assume without loss of generality that P is the leftmost sub-pyramid of P, of size d < d (with source vertices v1 0, . . . , vd 0 .) Consider the outer rightmost vertices of P those vertices with labels v1 d 1, v2 d 2, . . . , vd 1 1 , vd 0 . Relabel these outer rightmost vertices of P by vd 1, ..., v0, where vd 1 is the sink vertex of P , and for all i < d 1, vi is the rightmost vertex in P at level i. Corresponding to each named vertex vi is a diagonal set of vertices, diag(vi), beginning at vi and travelling southwest to a source vertex of P . Note that the sets diag(vi) are pairwise disjoint. We will argue that for each i, 0 i d 1, at least one vertex from diag(vi) must appear in c. To see this, ﬁrst notice that for each vi, there is a vertex v i that is an immediate successor of vi and that lies outside of P . This vertex v i must be pebbled at some point, and furthermore it must be pebbled at some time after conﬁguration c, since pebbling v i requires pebbling a source vertex of P that is not in P , and the only source vertices that have been pebbled so far are the source vertices of P . But in order to pebble v i in the future, if S is a minimal-length pebbling, then there must be a black pebble on some vertex in diag(vi) in c. (In a minimal-length pebbling of graph G, if any set of conﬁgurations is removed from the pebbling, what results is no longer a black pebbling of G.) Thus, we have shown that if c is any conﬁguration in S such that d < d source vertices are pebbled thus far, then there must be d vertices pebbled in c.

Inapproximability of Treewidth and Related Problems

8. Conclusion and Open Problems

We proved SSE-hardness of approximation for a variety of graph problems. Most importantly we obtained the ﬁrst inapproximability result for the Treewidth problem and Minimum Fill-In. Some remarks are in order. The status of the SSE conjecture is, at this point in time, very uncertain, and our results should therefore not be taken as absolute evidence that there is no polynomial time approximation algorithm for (e.g.) Treewidth. However, at the very least, our results do give an indication of the diﬃculty involved in obtaining such an algorithm for Treewidth, and builds a connection between these two important problems. We also ﬁnd it remarkable how simple our reductions and proofs are. We leave the choice of whether to view this as a healthy sign of strength of the SSE Conjecture, or whether to view it as an indication that the conjecture is too strong, to the reader. There are many important open questions and natural avenues for further work, including:

1. It seems plausible that these results can be extended to a wider range of graph layout problems. For instance, our two choices of aggregators max and Σ can be viewed as taking ℓ and ℓ1 norms, and it seems likely that the results would apply for any ℓp norm (though we are not aware of any previous literature studying such variants).

2. It would be nice to obtain hardness of approximation result for our problems based on a weaker hardness assumption such as UGC. It is conjectured in the work of Raghavendra et al. (2012) that the SSE conjecture is equivalent to UGC. Alternatively, it would be nice to show that hardness of some of our problems imply hardness for the SSE Problem.

3. For pebbling, it would be very interesting to obtain results for the unrestricted pebbling problems (for which ﬁnding the exact pebbling cost is even PSPACE-hard). As far as we are aware, nothing is known for these problems, not even, say, whether one can obtain a non-trivial approximation in NP. As mentioned in the introduction, we are currently working on extending our One-Shot Pebbling results to bounded time pebblings. We have some preliminary progress there and are hopeful that we can relax the pebbling results to a much larger class of pebblings.

Acknowledgments

Research supported by NSERC.

Agarwal, A., Charikar, M., Makarychev, K., & Makarychev, Y. (2005). O( logn) approximation algorithms for min Un Cut, min 2CNF deletion, and directed cut problems. In Proceedings of the thirty-seventh annual ACM Symposium on Theory of computing, STOC 05, pp. 573 581, New York, NY, USA. ACM.

Wu, Austrin, Pitassi, & Liu

Ambuhl, C., Mastrolilli, M., & Svensson, O. (2007). Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 07, pp. 329 337, Washington, DC, USA. IEEE Computer Society.

Amir, E. (2001). Eﬃcient approximation for triangulation of minimum treewidth. In Proceedings of the 17th Conference on Uncertainty in Artiﬁcial Intelligence, pp. 7 15. Morgan Kaufmann Publishers.

Arnborg, S., Corneil, D. G., & Proskurowski, A. (1987). Complexity of ﬁnding embeddings in a k-tree. SIAM J. Algebraic Discrete Methods, 8, 277 284.

Arora, S., Barak, B., & Steurer, D. (2010). Subexponential algorithms for unique games and related problems. In Annual Symposium on Foundations of Computer Science, FOCS 10, pp. 563 572.

Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M. (1998). Proof veriﬁcation and the hardness of approximation problems. J. ACM, 45(3), 501 555.

Arora, S., Rao, S., & Vazirani, U. (2009). Expander ﬂows, geometric embeddings and graph partitioning. J. ACM, 56, 5:1 5:37.

Arora, S., & Safra, S. (1998). Probabilistic checking of proofs: a new characterization of np. J. ACM, 45(1), 70 122.

Barak, B., Raghavendra, P., & Steurer, D. (2011). Rounding semideﬁnite programming hierarchies via global correlation. ECCC Report TR11-065.

Bodlaender, H. L., Gilbert, J. R., Hafsteinsson, H., & Kloks, T. (1995). Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. Journal of Algorithms, 18(2), 238 255.

Bodlaender, H. (2007). Treewidth: Structure and algorithms. In Prencipe, G., & Zaks, S. (Eds.), Structural Information and Communication Complexity, Vol. 4474 of Lecture Notes in Computer Science, pp. 11 25. Springer Berlin / Heidelberg. 10.1007/978-3540-72951-8 3.

Bodlaender, H. L. (1996). A linear-time algorithm for ﬁnding tree-decompositions of Small Treewidth. SIAM Journal on Computing, 25(6), 1305 1317.

Bodlaender, H. L. (2005). Discovering treewidth. In SOFSEM, pp. 1 16.

Bouchitt e, V., & Todinca, I. (2003). Approximating the treewidth of at-free graphs. Discrete Applied Mathematics, 131(1), 11 37.

Charikar, M., Hajiaghayi, M., Karloﬀ, H., & Rao, S. (2010). l2 2 spreading metrics for vertex ordering problems. Algorithmica, 56, 577 604.

Dubey, C. K., Feige, U., & Unger, W. (2011). Hardness results for approximating the bandwidth. J. Comput. Syst. Sci., 77(1), 62 90.

Feige, U., Hajiaghayi, M., & Lee, J. R. (2005). Improved approximation algorithms for minimum-weight vertex separators. In Proceedings of the thirty-seventh annual ACM Symposium on Theory of computing, STOC 05, pp. 563 572, New York, NY, USA. ACM.

Inapproximability of Treewidth and Related Problems

Fomin, F. V., & Villanger, Y. (2012). Subexponential parameterized algorithm for minimum ﬁll-in. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 12, pp. 1737 1746. SIAM.

Fulkerson, D. R., & Gross, O. A. (1965). Incidence matrices and interval graphs. Paciﬁc Journal of Mathematics, 15, 835 855.

Guruswami, V., & Sinop, A. K. (2011). Lasserre hierarchy, higher eigenvalues, and approximation schemes for quadratic integer programming with psd objectives..

H astad, J. (1999). Clique is hard to approximate withinn 1ε. Acta Mathematica, 182(1), 105 142.

H astad, J. (2001). Some optimal inapproximability results. J. ACM, 48(4), 798 859.

Heggernes, P. (2006). Minimal triangulations of graphs: A survey. Discrete Mathematics.

Kaplan, H., Shamir, R., & Tarjan, R. E. (1994). Tractability of parameterized completion problems on chordal and interval graphs: Minimum ﬁll-in and physical mapping (extended abstract). SIAM J. Comput, 28, 780 791.

Khot, S., & Regev, O. (2008). Vertex cover might be hard to approximate to within 2ε. Journal of Computer and System Sciences, 74(3), 335 349.

Khot, S., & Vishnoi, N. (2005). On the unique games conjecture. In Annual Symposium on Foundations of Computer Science, Vol. 46 of FOCS 05, p. 3. IEEE COMPUTER SOCIETY PRESS.

Khot, S. (2002). On the power of unique 2-prover 1-round games. In Proceedings of the thiry-fourth annual ACM Symposium on Theory of Computing, STOC 02, pp. 767 775, New York, NY, USA. ACM.

Kinnersley, N. G. (1992). The vertex separation number of a graph equals its path-width. Information Processing Letters, 42(6), 345 350.

Kirousis, L. M., & Papadimitriou, C. H. (1986). Searching and pebbling. Theor. Comput. Sci., 47, 205 218.

Kloks, T. (1994). Treewidth: computations and approximations, Vol. 842. Springer.

Koller, D., & Friedman, N. (2009). Probabilistic Graphical Models: Principles and Techniques. MIT press.

Leighton, T., & Rao, S. (1999). Multicommodity max-ﬂow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46, 787 832.

Lengauer, T. (1981). Black-white pebbles and graph separation. Acta Informatica, 16, 465 475. 10.1007/BF00264496.

Lengauer, T., & Tarjan, R. E. (1982). Asymptotically tight bounds on time-space trade-oﬀs in a pebble game. J. ACM, 29, 1087 1130.

Natanzon, A., Shamir, R., & Sharan, R. (1998). A polynomial approximation algorithm for the minimum ﬁll-in problem. In Proceedings of the thirtieth annual ACM Symposium on Theory of Computing, STOC 98, pp. 41 47, New York, NY, USA. ACM.

Nordstr om, J. (2010). New wine into old wineskins: A survey of some pebbling classics with supplemental results. Draft manuscript.

Wu, Austrin, Pitassi, & Liu

Raghavendra, P. (2008). Optimal algorithms and inapproximability results for every csp?. In Proceedings of the 40th annual ACM Symposium on Theory of computing, pp. 245 254. ACM.

Raghavendra, P., & Steurer, D. (2010). Graph expansion and the unique games conjecture. In Proceedings of the 42nd ACM Symposium on Theory of computing, STOC 10, pp. 755 764, New York, NY, USA. ACM.

Raghavendra, P., Steurer, D., & Tulsiani, M. (2012). Reductions Between Expansion Problems. IEEE Conference on Computational Complexity.

Ramalingam, G., & Rangan, C. P. (1988). A uniﬁed approach to domination problems on interval graphs. Inf. Process. Lett., 27, 271 274.

Rao, S., & Richa, A. W. (1998). New approximation techniques for some ordering problems. In Proceedings of the ninth annual ACM-SIAM Symposium on Discrete Algorithms, SODA 98, pp. 211 218, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics.

Ravi, R., Agrawal, A., & Klein, P. (1991). Ordering problems approximated: single-processor scheduling and interval graph completion. In Albert, J., Monien, B., & Artalejo, M. (Eds.), Automata, Languages and Programming, Vol. 510 of Lecture Notes in Computer Science, pp. 751 762. Springer Berlin / Heidelberg. 10.1007/3-540-54233-7180.

Reed, B. A. (1992). Finding approximate separators and computing tree width quickly. In Proceedings of the Twenty-fourth Annual ACM Symposium on Theory of Computing, STOC 92, pp. 221 228, New York, NY, USA. ACM.

Robertson, N., & Seymour, P. D. (1984). Graph minors. III. Planar tree-width. J. Comb. Theory, Ser. B, 36(1), 49 64.

Robertson, N., & Seymour, P. D. (1986). Graph minors. II. Algorithmic aspects of treewidth. Journal of Algorithms, 7(3), 309 322.

Roth, D. (1996). On the hardness of approximate reasoning. Artiﬁcial Intelligence, 82(1), 273 302.

Sethi, R. (1973). Complete register allocation problems. In Proceedings of the ﬁfth annual ACM Symposium on Theory of computing, STOC 73, pp. 182 195, New York, NY, USA. ACM.

Seymour, P. D., & Thomas, R. (1994). Call routing and the ratcatcher. Combinatorica, 14(2), 217 241.