**Abstracts of the talks of GROW 2013**** (download the abstracts as a .pdf file)**

**1. Susanne Albers**: *Algorithms for Online Bipartite Matching*

**Abstract**: We study the online version of the classical bipartite matching problem. In this setting one vertex set of a bipartite graph is given initially. The vertices of the second set arrive online. Each incoming vertex may be matched to an eligible partner vertex immediately upon arrival. The framework was initially introduced by Karp, Vazirani and Vazirani (STOC 1990) and has recently received considerable research interest due to its relevance in online advertising. In this talk we survey important contributions that have been developed in the algorithms community over the past years. The results address the standard problem setting as well as budgeted versions and scenarios with stochastic input.

**2. Andreas Brandstädt**: *On the complexity of some packing and covering problems in graphs and hypergraphs*

**Abstract**: Packing and covering problems in graphs and hypergraphs and their relationships belong to the most fundamental topics in combinatorics and graph algorithms and have a wide spectrum of applications in computer science, operations research and many other fields. Recently, there has been an increasing interest in graph and hypergraph problems combining packing and covering properties, and the NP-complete Exact Cover problem on hypergraphs is a good example. Closely related graph problems are the Efficient Domination and Efficient Edge Domination problems. We give a survey on existing results, describe some connections to other problems such as Maximum Weight Independent Set and Minimum Weight Dominating Set, consider some new cases where the problems are efficiently solvable by using structural properties of graph classes and using closure properties under the square operation, and we also extend the graph problems to hypergraphs.

**3. Bruno Courcelle**: Graph algorithms based on infinite automata: logical descriptions and usable constructions

Abstract: The FPT algorithms that check MSO (Monadic Second-Order) properties of graphs of bounded tree-width or clique-width are based on finite automata that process terms representing (in a Universal Algebra setting) the relevant hierarchical decompositions. Although finite, these automata are in most cases much too large to be built. We call* fly-automaton* (FA) an automaton whose states are described (and not listed) and whose transitions are described by programs and computed only when needed. Such automata can have infinitely many states : a state may include a finite set of counters, among other finite information. Such automata can be used for checking graph properties that are not *MSO*, for example the regularity of a graph (all vertices have same degree), and for computing functions, for example the number of answers to an MSO query, or the minimal or maximal size of such an answer. Many *optimization functions* can be handled in this setting: the minimal size of a set of vertices whose deletion yields a p-colorable graph , or more generally, a graph satisfying a property defined by a constructed FA (in particular any MSO property). For another example, if the graph can be partitioned into two regular induced subgraphs, we may wish to compute the minimum number of edges not in any of two such subgraphs. From logical descriptions of problems and already constructed FA for basic properties and functions, the *running system AUTOGRAPH* (work by Irène Durand, LaBRI) can build the corresponding automata. Our basic automata process clique-width terms (so they also work for graphs of bounded tree-width). We also analyse whether the newly built FA yield polynomial-time, FPT, XP or non XP algorithms. First-order constructions yield FPT algorithms from basic FPT automata. Monadic second-order ones, as one may guess, need detailed analysis of the search spaces corresponding to existential quantifications. This work can be seen as a theory of (some aspects of ) *dynamic programming.*

**4. Marek Cygan**: Improved approximation for 3-dimensional matching via bounded pathwidth local search

Abstract: One of the most natural optimization problems is the k-Set Packing problem, where given a family of sets of size at most k one should select a maximum size subfamily of pairwise disjoint sets. A special case of 3-Set Packing is the well known 3-Dimensional Matching problem. Both problems belong to the Karp`s list of 21 NP-complete problems. The best known polynomial time approximation ratio for k-Set Packing is (k + ε)/2 and goes back to the work of Hurkens and Schrijver [SIDMA'89], which gives (1.5 + ε)-approximation for 3-Dimensional Matching. Those results are obtained by a simple local search algorithm, that uses constant size swaps. The main result of the paper is a new approach to local search for k-Set Packing where only a special type of swaps is considered, which we call swaps of bounded pathwidth. We show that for a fixed value of k one can search the space of r-size swaps of constant pathwidth in c^r poly(|F|) time. Moreover we present an analysis proving that a local search maximum with respect to O(log |F|)-size swaps of constant pathwidth yields a polynomial time (k + 1 + ε)/3-approximation algorithm, improving the best known approximation ratio for k-Set Packing. In particular we improve the approximation ratio for 3-Dimensional Matching from 3/2 + ε to 4/3 + eps. The manuscript is available on arxiv: http://arxiv.org/abs/1304.1424.

**5. Jiří Fiala**: Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree

A homomorphism from a graph G to a graph H is locally bijective, surjective, or injective if its restriction to the neighborhood of every vertex of G is bijective, surjective, or injective, respectively. We prove that the problems of testing whether a given graph G allows a homomorphism to a given graph H that is locally bijective, surjective, or injective, respectively, are NP-complete, even in the restricted case where G has pathwidth 5, 4 or 2, respectively, or when both G and H have maximum degree 3. We complement these hardness results by showing that the three problems are polynomial-time solvable if G has bounded treewidth and in addition G or H has bounded maximum degree.

**6. Robert Ganian**: Meta-Kernelization with Structural Parameters

Meta-kernelization theorems are general results that provide polynomial kernels for large classes of parameterized problems. The known meta-kernelization theorems, in particular the results of Bodlaender et al. (FOCS'09) and of Fomin et al. (FOCS'10), apply to problems parameterized by *solution size*. We present meta-kernelization theorems that use \emph{structural parameters} of the input and not the solution size. Let $\cal C$ be a graph class. We define the \emph{$\cal C$-cover number} of a graph to be a the smallest number of modules the vertex set can be partitioned into such that each module induces a subgraph that belongs to the class $\cal C$. We show that each graph problem that can be expressed in Monadic Second Order (MSO) logic has a polynomial kernel with a linear number of vertices when parameterized by the $\cal C$-cover number for any fixed class $\cal C$ of bounded rank-width (or equivalently, of bounded clique-width, or bounded Boolean width). Many graph problems such as \textsc{Independent Dominating Set}, \textsc{$c$-Coloring}, and \textsc{$c$-Domatic Number} are covered by this meta-kernelization result. Our second result applies to MSO expressible optimization problems, such as \textsc{Minimum Vertex Cover}, \textsc{Minimum Dominating Set}, and \textsc{Maximum Clique}. We show that these problems admit a polynomial annotated kernel with a linear number of vertices.

**7. Alexander Grigoriev**: Bidimensionality on geometric intersection graphs

Let ${\cal B}$ be a finite collection of geometric (not necessarily convex) bodies in the plane. Clearly, this class of geometric objects naturally generalizes the class of disks, polylines, ellipsoids and even convex polyhedra. We consider geometric intersection graphs $G_{\cal B}$ where each body of the collection ${\cal B}$ is represented by a vertex, and two vertices of $G_{\cal B}$ are adjacent if the intersection of the corresponding bodies is non-empty. For such graph classes and under natural restrictions on their maximum degree or subgraph exclusion, we prove that the relation between their treewidth and the maximum size of a grid minor is linear. These combinatorial results vastly extend the applicability of all the meta-algorithmic results of the bidimensionality theory to geometrically defined graph classes.

**8. Qianping Gu**: Practical algorithms for branch-decompositions and grid-minors of planar graphs

Branch-decompositions and grid-minors of graphs have important algorithmic applications. A graph $G$ of small branchwidth admits efficient algorithms for many NP-hard problems in $G$. These algorithms have two major steps: (1) compute a branch-decomposition $T$ of $G$ and (2) solve a problem by dynamic programming based on the branch-decomposition $T$. These algorithms usually run in exponential time in the width of $T$. The ratio of the branchwidth of $G$ over the largest size of the grid minor of $G$ typically appears in the exponent of the running time of these algorithms as well. It is critical to compute a branch-decomposition of small width and a grid minor of large size for a given graph in the practical applications of these algorithms. It is known that an optimal branch-decomposition of planar graphs can be computed in $O(n^3)$ time by the edge-contraction algorithm. In this talk, we give a summary on the practical performance of the edge-contraction algorithm and the heuristics for improving the algorithm. We also give a summary on computational studies for the grid minors of planar graphs and some branch-decomposition based algorithms.

**9. Michel Habib**: Graph Searches and cocomparability graphs

A comparability graph is a graph that admits a transitive orientation, and a cocomparability graph is simply the complement of a comparability graph. Both classes comparability and cocomparability graphs are well studied subclasses of perfect graphs. Cocomparability graphs generalize interval graphs, and we generalize for cocomparability graphs some algorithmic results already obtained for interval graphs \cite{CDH11}. For a total ordering $\tau$ of the set of vertices of an undirected graph $G=(V, E)$, an *umbrella* is a triple of vertices $a, b, c \in V$ such that: $a <_{\tau} b <_{\tau} c$ and $ac \in E$ and $ab, bc \notin E$. A cocomparability (*cocomp* for short) ordering is an umbrella-free total ordering of the vertices of $G$. As noticed, $G$ is a cocomparability graph iff it admits a cocomp ordering. A cocomp ordering is a linear extension of some transitive orientation $P= (V, \leq)$ of the complement of $\overline{G}=(V, \overline{E})$. In fact, given a cocomp ordering $\tau$ there is a unique transitive orientation of $\overline{G}=(V, \overline{E})$ compatible with $\tau$. We introduce a general framework to describe graph searches and within this framework we characterize the searches which preserve cocomp orderings, when used as a `+' sweep where ties are broken using a previous ordering. Such searches include BFS, DFS, LBFS, LDFS. This allows us to present a toolbox of different graph searches and a framework to solve various problems on comparability graphs or partial orders. In particular we describe two very simple certifying algorithms for maximum independent set and permutation graph recognition. This study is deeply involved in the relationships between cocomparability graphs and partial orders. For partial orders we will employ the following basic terminology. A {\it partial order} $P =(V, \leq_{P})$ is a finite set $V$, the *ground set* of $P$, formed by ordered pairs of vertices in $V$, satisfying reflexivity, anti-symmetry and transitivity. For $x,y \in V$, if $x \leq_{P} y $ or $y \leq_{P} x $ then $x,y$ are comparable, otherwise they are incomparable denoted by $x || y$. A chain (resp. antichain) in a partial order is of subset of vertices in which all pairs of elements are comparable (resp. incomparable). As defined, the set of maximal (under inclusion) antichains of a given partial order $P$ denoted by $MA(P)$ is a lattice when equipped with the following ordering: For $A, B$ maximal antichains, $A \leq_{MA(P)} B$ if $\forall y \in B$, $\exists x \in A$ with $x \leq_{P} y$. This *Maximal Antichain* lattice was also studied elsewere and in particular it is well-known that: $P$ is an interval order iff $MA(P)$ is a chain. Using this combinatorial structure we characterize cocomparability graphs in terms of a lattice structure acting on its maximal cliques and present some efficient algorithmic applications of this characterization including finding minimal clique cutsets and simplicial vertices.

**10. Frédéric Havet**: Finding a subdivision of a digraph

One of the results of treewidth theory is that the k-Linkage problem can be solved in polynomial time. This implies that for any fixed graph F, deciding if a graph contains a subdivision of F is polynomial-time solvable. In contrast, for a fixed digraph F, the F-Subdivision problem of deciding if a given digraph contains a subdivision of F, can be NP-complete or polynomial-time solvable. On the one hand, Fortune, Hopcroft and Wyllie proved that the Directed 2-Linkage problem is NP-complete; this allows us to prove that F-subdivision is NP-complete for many digraphs. On the other hand, a conjecture of Seymour motivated by directed treewidth asserts if if F is planar and every vertex has either indegree and outdegree at most 2 and total degree at most 3, then F-subdivision can be solved in polynomial time. We shall survey all results and conjectures on F-subdivision and in particular show that Seymour's conjecture holds for digraphs of order at most 4. This a joint work with J. Bang-Jensen, A.-K. Maia and B. Mohar.

**11. Mamadou Kanté**: On the linear rank-width of trees

We show that linear rank-width and path-width coincide in trees. We also show that linear clique-width of a tree equals its path-width plus two (provided the tree contains a path of length three). A tree $T$ is a minimal excluded acyclic vertex-minor to linear rank-width $k$ if $T$ has linear rank-width $k+1$ and every proper vertex-minor of $T$ that is a tree has linear rank-width $k$. We provide minimal excluded acyclic vertex-minor to linear rank-width $k$. Joint work with Isolde Adler.

**12. Stavros Kolliopoulos**: Integrality gaps for strengthened LP relaxations of Capacitated and Lower-Bounded Facility Location

**13. Chun-Hung Liu**: Structural theorems and well-quasi-ordering

Motivated by well-quasi-ordering problems, we prove structure theorems for excluding a fixed graph H as a weak immersion or a topological subgraph, improving upon earlier results of Grohe and Marx, Dvorak, and Wollan. For topological minors our ultimate goal is an old conjecture of Robertson that for every integer k graphs with no topological minor isomorphic to the graph obtained from a path of length k by doubling every edge are well-quasi-ordered by the topological minor relation. We are able to prove the conjecture for graphs of bounded tree-width and reduce the general problem to graphs that possess certain kind of tree-decomposition. We expect that our proof for graphs of bounded tree-width will generalize to graphs possessing said decomposition, but the details of that have not yet been worked out at the time of submission.

**14. Daniel Lokshtanov**: Independent Set in P_5-Free Graphs in Polynomial Time

The Independent Set problem is NP-hard in general, however polynomial time algorithms exist for the problem on various specific graph classes. Over the last couple of decades there has been a long sequence of papers exploring the boundary between the NP-hard and polynomial time solvable cases. In particular the complexity of Independent Set on P5-free graphs has received significant attention, and there has been a long list of results showing that the problem becomes polynomial time solvable on sub-classes of P5-free graphs. We give the first polynomial time algorithm for Independent Set on P5-free graphs. Our algorithm also works for the Weighted Independent Set problem.

**15. Vadim Lozin**: Minimal classes of graphs of unbounded clique-width

The celebrated theorem of Robertson and Seymour states that in the family of minor-closed graph classes the planar graphs constitute a unique minimal class of unbounded tree-width. In the study of tree-width the restriction to minor-closed graph classes is justified by the fact that the tree-width of a graph is never smaller than the tree-width of any of its minors. With respect to clique-width, this restriction is not justified, as the clique-width of a graph can be (much) smaller than the clique-width of its minor. However, the clique-width of a graph is never smaller than the clique-width of any of its induced subgraphs, which allows us to restrict ourselves to hereditary classes, i.e. those closed under taking induced subgraphs. The first two minimal hereditary classes of graphs of unbounded clique-width were discovered in [V.Lozin, Minimal classes of graphs of unbounded clique-width, Annals of Combinatorics, 15 (2011) 707-722]. In the present talk we reveal new minimal hereditary classes of unbounded clique-width. Our approach combines various techniques and involves various notions such as geometric intersection graphs, universal graphs, pivoting procedure developed by Sand-il Oum to study rank-width of graphs, etc. This is a joint work with Juraj Stacho.

**16. George Mertzios**: The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial

Intersection graphs of geometric objects have been extensively studied, both due to their interesting structure and their numerous applications; prominent examples include interval graphs and permutation graphs. In this paper we study a natural graph class that generalizes both interval and permutation graphs, namely *imple-triangle* graphs. Simple-triangle graphs - also known as \emph{*PI* graphs (for Point-Interval) - are the intersection graphs of triangles that are defined by a point on a line $L_{1}$ and an interval on a parallel line $L_{2}$. They lie naturally between permutation and trapezoid graphs, which are the intersection graphs of line segments between $L_{1}$ and $L_{2}$ and of trapezoids between $L_{1}$ and $L_{2}$, respectively. Although various efficient recognition algorithms for permutation and trapezoid graphs are well known to exist, the recognition of simple-triangle graphs has remained an open problem since their introduction by Corneil and Kamula three decades ago. In this paper we resolve this problem by proving that simple-triangle graphs can be recognized in polynomial time. As a consequence, our algorithm also solves a longstanding open problem in the area of partial orders, namely the recognition of *linear-interval orders*, i.e. of partial orders $P=P_{1}\cap P_{2}$, where $P_{1}$ is a linear order and $P_{2}$ is an interval order. This is one of the first results on recognizing partial orders $P$ that are the intersection of orders from two different classes $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$. In contrast, partial orders $P$ which are the intersection of orders from the same class $\mathcal{P}$ have been extensively investigated, and in most cases the complexity status of these recognition problems has been established.

**17. Martin Milanič**: Graphs of Power-Bounded Clique-Width

Clique-width is a graph parameter with many algorithmic applications. A $k$-th power of a graph $G$ is the graph with the same vertex set as $G$, in which two distinct vertices are adjacent if and only if they are at distance at most $k$ in $G$. Many graph algorithmic problems can be expressed in terms of graph powers. We introduce and study the notion of graph classes of *power-bounded clique-width*. A graph class is of power-bounded clique-width if there exists an integer $k$ such that the $k$-th powers of graphs in the class form a class of bounded clique-width. We identify several graph classes of power-unbounded clique-width, and give a sufficient condition for clique-width to be power-bounded. Based on this condition, we characterize graph classes of power-bounded clique-width among classes defined by two connected forbidden induced subgraphs. Joint work with Flavia Bonomo, Luciano Grippo and Martín Darío Safe.

**18. Christophe Paul**: Explicit Linear Kernels via Dynamic Programming

Several algorithmic meta-theorems on kernelization have appeared in the last years, starting with the result of Bodlaender et al. [FOCS 2009] on graphs of bounded genus. Typically, these results guarantee the existence of linear or polynomial kernels on sparse graph classes for problems satisfying some generic conditions but, manly due to their generality, it is hard to derive from them constructive kernels with explicit constants. In this article we make a step toward a fully constructive meta-kernelization theory on sparse graphs. Our approach is based on a more explicit protrusion replacement machinery that instead of expressibility in CMSO logic uses dynamic programming, which allows us to find an explicit upper bound on the size of the derived kernels. We demonstrate the usefulness of our techniques by providing the first explicit linear kernels for $r$-Dominating Set and $r$-Scattered Set on apex-minor-free graphs, and for Planar-$\mc{F}$-Deletion and Planar-$\mc{F}$-Packing on graphs excluding a fixed (topological) minor in the case where all the graphs in $\mc{F}$ are connected.

**19. Marcin Pilipczuk**: The planar directed k-Vertex Disjoint Paths problem is fixed-parameter tractable

Given a graph G and k pairs of vertices (s_1,t_1), ..., (s_k,t_k), the k-Vertex-Disjoint Paths problem asks for pairwise vertex-disjoint paths P_1, ..., P_k such that P_i goes from s_i to t_i. Schrijver [SICOMP'94] proved that the k-Vertex-Disjoint Paths problem on planar directed graphs can be solved in time n^{O(k)}. We give an algorithm with running time 2^{2^{O(k^2)}} n^{O(1)} for the problem, that is, we show the fixed-parameter tractability of the problem. The algorithm consists of two main parts: an irrelevant vertex rule for a large number of concentric cycles of alternating direction, and a specific bounded-alternation decomposition, computable if the irrelevant vertex rule is not applicable, together with its algorithmic usage. Joint work with Marek Cygan, Dániel Marx and Michał Pilipczuk.

**20. Michał Pilipczuk**: Topological problems on tournaments

A theory of topological containment for tournaments was developed recently by Chudnovsky, Fradkin, Kim, Scott, and Seymour. It appears that the natural containment notions in this setting form well-quasi-orderings, and correspond to two natural width measures, namely pathwidth and cutwidth. This creates possibilities for many algorithmic applications, including XP and FPT algorithms. During the talk, I would like to survey the status of algorithmic results on topological problems on tournaments, with a particular focus on applications in fixed-parameter tractability. The material covered will be based on the work of Chudnovsky, Fradkin, Kim, Scott, and Seymour, as well as on more recent results obtained together with Fedor V. Fomin.

**21. Leonidas Pitsoulis**: Decomposition of Binary Signed-Graphic Matroids

Tutte's theory of bridges is extended to derive a decomposition theorem for binary matroids arising from signed graphs. The proposed decomposition differs from previous decomposition results on matroids that have appeared in the literature in the sense that it is not based on $k$-sums, but rather on the operation of deletion of a cocircuit. A sketch of a recognition algorithm as well as an excluded minor characterization of the building blocks of the aforementioned decomposition will also be presented.

**22. Maadapuzhi Sridharan Ramanujan**: Cuts on Skew-Symmetric Graphs and Linear Time FPT algorithms

A skew-symmetric graph (D=(V,A),\sigma) is a directed graph D with an involution \sigma on the set of vertices and arcs. We will introduce the following problem where we are given a skew-symmetric graph $D$, a family $\cal T$ of $d$-sized subsets of vertices and an integer $k$. The objective is to decide if there is a set $X\subseteq A$ of $k$ arcs such that every set $J$ in the family has a vertex $v$ such that $v$ and $\sigma(v)$ are in different strongly connected components of $(V,A\setminus (X\cup \sigma(X))$. This problem, termed the $d$-skew symmetric multicut problem, is a problem that generalizes numerous well studied classical problems including Odd Cycle Transversal and 2-SAT deletion. In this talk, we will see an algorithm for the $d$-skew symmetric multicut problem which runs in time $O((4d)^{k}(m+n+\ell))$, where $m$ is the number of arcs in the graph, $n$ the number of vertices and $\ell$ the length of the family given in the input. As corollaries of this algorithm, we obtain the first linear time FPT algorithm for Odd Cycle Transversal which runs in time $O(4^kk^4(m+n))$ and the first linear time FPT algorithm for 2-SAT deletion which runs in time $O(4^kk^4\ell)$. The first algorithm resolves an open problem of Reed, Smith and Vetta [Operations Research Letters, 2003] and improves upon the earlier almost linear time algorithm of Kawarabayashi and Reed [SODA, 2010]. his is joint work with Saket Saurabh.

**23. Νicola Santoro**: Graph Search with Immunity

Our understanding of the links between classic graph parameters and graph search problems has been stimulated and enriched by the investigations of the *intruder capture* problem (and its equivalent formulation of *network decontamination*) started in 2002 in the application domain of distributed computing by mobile agents. Since then, in the application domain, the problem has been generalized into two quite different but related directions, both focusing on the "re-contamination" rules. These new problems generate new definitions of basic concepts, including *monotonicity*; they have been studied in the application domain but there is no investigation so far on their relationship with graph parameters. Aim of this talk is to stimulate such a study.

**24. Saket Saurabh**: *Matroids, Randomness and FPT Algorithms*

This talk will be dedicated to the recent developments in designing randomized paramterized algorithms using techniques and tools from matroid theory.

**25. Ingo Schiermeyer**: Rainbow connection and forbidden subgraphs

A connected edge-colored graph G is rainbow-connected if any two distinct vertices of G are connected by a path whose edges have pairwise distinct colors; the rainbow connection number rc(G) of G is the minimum number of colors such that G is rainbow-connected. We consider families F of connected graphs for which there is a constant κ_F such that, for every connected F-free graph G, rc(G)\leq diam(G)+ κ_{F}$, where diam(G) is the diameter of G. In this paper, we give a complete answer for $|F|\in {1,2}.

**26. Stefan Szeider**: A SAT Approach to Clique-Width

We present a new method for computing the clique-width of graphs based on an encoding to propositional satisfiability (SAT) which is then evaluated by a SAT solver. Our encoding is based on a reformulation of clique-width in terms of partitions that utilizes an efficient encoding of cardinality constraints. Our SAT-based method is the first to discover the exact clique-width of various small graphs, including famous graphs from the literature as well as random graphs of various density. With our method we determined the smallest graphs that require a small pre-described clique-width. Joint work with Marijn J. H. Heule, The University of Texas at Austin, USA. Preprint available at http://arxiv.org/abs/1304.5498

**27. Nicolas Trotignon**: The stable set problem is FPT in bull-free graphs

The bull is the graph obtained from the triangle by adding two pendant non-adjacent edges. A graph is bull-free if it does not contain a bull as an induced subgraph. Finding a maximum stable set in a bull-free graph is a NP-hard problem. We prove that this problem is FPT. Our proof relies on the decompostion theorem for bull-free graph due to Maria Chudnovsky. This is a joint work with Stéphan Thomassé and Krisitina Vušković

**28. Antonios Varvitsiotis**: On the rank constrained Grothendieck constant of graphs and a new tree-width-like graph parameter

Let $G=([n],E)$ be a simple and loopless graph and let $w=(w_{ij}) \in \mathbb{R}^E$. For any fixed integer $r\ge 1$ consider the rank constrained semidefinite program {\rm sdp}_r(G,w)=\max \left\{ \sum_ {ij \in E}w_{ij} u_i^{\sf T}u_j : u_1,\ldots,u_n \in \mathbb{S}^{r-1} \right\}, where $\mathbb{S}^{r-1}$ denotes the unit sphere in $\mathbb{R}^r$. The study of such programs is motivated by their relevance to statistical mechanics and more specifically to the computation of the Hamiltonian and of the ground states of various vector models that describe the interaction of particles in spin glasses. Solving problems of this form is in general computationally challenging. Indeed, for $r=1$ this program models the max-cut problem (in $\pm 1$ variables) and thus it is NP-hard. This motivates the study of tractable relaxations of \eqref{eq1} and we will be focusing on its canonical semidefinite programming relaxation given by ${\rm sdp}(G,w)=\max \left\{ \sum_ {ij \in E}w_{ij} u_i^{\sf T} u_j : u_1,\ldots,u_n \in \mathbb{S}^{n-1} \right\}.$ The quality of this relaxation is measured by its integrality gap, i.e., the ratio \kappa(r,G):=\sup_{w \in \mathbb{R}^E} \frac{{\rm sdp}(G,w)}{{\rm sdp}_r(G,w)}, known as the {\em rank-$r$ Grothendieck constant} of the graph $G$. As problems of the form \eqref{eq1} are in general hard, it is important to identify specific graph classes for which they can be solved efficiently. In this talk we focus on graphs that satisfy $\kappa(r,G)=1$ for some fixed integer $r\ge 1$. We show that for any fixed $r\ge 1$ the family of graphs satisfying $\kappa(r,G)=1$ is closed under taking minors. For $r=1$ these graphs are the forests. Our main result is the forbidden minor characterization for the graphs that satisfy $\kappa(2,G)=1$. Additionally, for any graph $G$ one can ask for the smallest integer $r\ge 1$ for which $\kappa(r,G)=1$. This graph parameter is well defined since $\kappa(n,G)=1$ and we call it the {\em extreme Gram dimension} of a graph. We introduce a new a tree-width-like graph parameter, denoted by ${\rm la}_{\boxtimes}(\cdot)$, which we call the {\em strong largeur d'arborescence}. The parameter ${\rm la}_{\boxtimes}(G)$ is defined as the smallest integer $r\ge 1$ such that $G$ is a minor of the strong graph product $T\boxtimes K_r $, where $T$ is a tree and $K_r$ denotes the complete graph on $r$ vertices. The name of the parameter is derived from the parameter {\em largeur d'arborescence}, denoted by ${\rm la}_{\square}(\cdot),$ introduced by Colin de Verdi\'ere, where the strong graph product is replaced by the Cartesian product of graphs. This parameter is closely related to the tree-width of a graph as it satisfies ${\rm tw}(G) \le {\rm la}_{\square}(G)\le {\rm tw}(G)+1.$ Our second main result is to show that ${\rm la}_{\boxtimes}(\cdot)$ is an upper bound for the extreme Gram dimension. Lastly, we give the forbidden minor characterization for the graphs satisfying ${\rm la}_{\boxtimes}(G)\le 2$.