Search

A balanced transferable utility game (N, v) has a stable core if its core is externally stable, that is, if each imputation that is not in the core is dominated by some core element. Given two payoff allocations x and y, we say that xoutvotesy via some coalition S of a feasible set if x dominates y via S and x allocates at least v(T) to any feasible T that is not contained in S. It turns out that outvoting is transitive and the set M of maximal elements with respect to outvoting coincides with the core if and only if the game has a stable core. By applying the duality theorem of linear programming twice, it is shown that M coincides with the core if and only if a certain nested balancedness condition holds. Thus, it can be checked in finitely many steps whether a balanced game has a stable core. We say that the game has a super-stable core if each payoff vector that allocates less than v(S) to some coalition S is dominated by some core element and prove that core super-stability is equivalent to vital extendability, requiring that each vital coalition is extendable. [ABSTRACT FROM AUTHOR]

A graph G(V, E) is claw-free if no vertex has three pairwise non-adjacent neighbours. The maximum weight stable set (MWSS) problem in a claw-free graph is a natural generalization of the matching problem and has been shown to be polynomially solvable by Minty and Sbihi in 1980. In a remarkable paper, Faenza, Oriolo and Stauffer have shown that, in a two-step procedure, a claw-free graph can be first turned into a quasi-line graph by removing strips containing all the irregular nodes and then decomposed into {claw, net}-free strips and strips with stability number at most three. Through this decomposition, the MWSS problem can be solved in O (| V | (| V | log | V | + | E |)) time. In this paper, we describe a direct decomposition of a claw-free graph into {claw, net}-free strips and strips with stability number at most three which can be performed in O (| V | 2) time. In two companion papers we showed that the MWSS problem can be solved in O (| E | log | V |) time in claw-free graphs with α (G) ≤ 3 and in O (| V | | E |) time in {claw, net}-free graphs with α (G) ≥ 4 . These results prove that the MWSS problem in a claw-free graph can be solved in O (| V | 2 log | V |) time, the same complexity of the best and long standing algorithm for the MWSS problem in line graphs. [ABSTRACT FROM AUTHOR]

The "exact subgraph" approach was recently introduced as a hierarchical scheme to get increasingly tight semidefinite programming relaxations of several NP-hard graph optimization problems. Solving these relaxations is a computational challenge because of the potentially large number of violated subgraph constraints. We introduce a computational framework for these relaxations designed to cope with these difficulties. We suggest a partial Lagrangian dual, and exploit the fact that its evaluation decomposes into several independent subproblems. This opens the way to use the bundle method from non-smooth optimization to minimize the dual function. Finally computational experiments on the Max-Cut, stable set and coloring problem show the excellent quality of the bounds obtained with this approach. [ABSTRACT FROM AUTHOR]

In this paper we show how to solve the Maximum Weight Stable Set Problem in a claw-free graph G( V, E) with $$\alpha (G) \le 3$$ in time $$\mathcal{O}(|E|\log |V|)$$ . More precisely, in time $$\mathcal{O}(|E|)$$ we check whether $$\alpha (G) \le 3$$ or produce a stable set with cardinality at least 4; moreover, if $$\alpha (G) \le 3$$ we produce in time $$\mathcal{O}(|E|\log |V|)$$ a maximum weight stable set of G. This improves the bound of $$\mathcal{O}(|E||V|)$$ due to Faenza, Oriolo and Stauffer. [ABSTRACT FROM AUTHOR]

We discuss the use of semidefinite programming for combinatorial optimization problems. The main topics covered include (i) the Lovász theta function and its applications to stable sets, perfect graphs, and coding theory, (ii) the automatic generation of strong valid inequalities, (iii) the maximum cut problem and related problems, and (iv) the embedding of finite metric spaces and its relationship to the sparsest cut problem. [ABSTRACT FROM AUTHOR]

Let G=( V, E) be an undirected graph and c any vector in ℤ V( G) +. Denote by χ( G c) (resp. η( G c)) the chromatic number (resp. fractional chromatic number) of G with respect to c. We study graphs for which χ( G c)−[ η( G c)]⩽1. We show that for the class of graphs satisfying χ( G c)=[ η( G c)] (a class generalizing perfect graphs), an analogue of the Duplication Lemma does not hold. We also describe a 2-vertex cut decomposition procedure related to the integer decomposition property. We use this procedure to show that χ( G c)=[ η( G c)] for series-parallel graphs and χ( G c)⩽[ η( G c)]+1 for graphs that do not have the 4-wheel as a minor. [ABSTRACT FROM AUTHOR]

The problem of finding a minimum cardinality set of nodes in a graph which meet every edge is of considerable theoretical as well as practical interest. Because of the difficulty of this problem, a linear relaxation of an integer programming model is sometimes used as a heuristic. In fact Nemhauser and Trotter showed that any variables which receive integer values in an optimal solution to the relaxation can retain the same values in an optimal solution to the integer program. We define 2-bicritical graphs and give several characterizations of them. One characterization is that they are precisely the graphs for which an optimal solution to the linear relaxation will have no integer valued variables. Then we show that almost all graphs are 2-bicritical and hence the linear relaxation almost never helps for large random graphs. [ABSTRACT FROM AUTHOR]