Abstracts of contributed papers

Papers are listed below in the order they were received.

Three classes of minimal circular-imperfect graphs

by  Arnaud Pêcher, Annegret K. Wagler, Xuding Zhu

Abstract: Circular perfect graphs form a natural superclass of perfect graphs: on the one hand due to their definition by means of a more general coloring concept, on the other hand as an important class of χ-bound graphs with the smallest non-trivial χ-binding function χ ≤ ω+1. The Strong Perfect Graph Conjecture, recently settled by Chudnovsky et al., provides a characterization of perfect graphs by means of forbidden subgraphs. It is, therefore, natural to ask for an analogous conjecture for circular perfect graphs, that is for a characterization of all minimal circular imperfect graphs. The present paper partially answers this question in the negative by providing three classes of minimal circular imperfect graphs which appear to be very different from a structural point of view: the first one is a subclass of partitionable graphs, the second one a subclass of planar graphs, the third one consists in all odd wheels and odd antiwheels.

Topics: graph theory

Upper bound on the non-colorability threshold of the 2+p-COL problem

by  Roberto Cruz

Abstract: The 2+p-COL problem, introduced by Walsh, smoothly interpolates between P and NP by mixing together the polynomial 2-coloring problem and the NP complete 3-coloring problem. A natural upper bound on the non colorability of the 2+p-COL problem is min{r2/(1–p), r3}, where r2 and r3 are the upper bounds on 2-COL and 3-COL threshold respectively. In this paper we improve this upper bound for each 0.73 ≤ p ≤ 1. This means that for p ≥ 0.73 the 2+p-COL problem does not behave like 2-COL problem. We use the method developed by Kaporis et al, which combines the concept of legal rigid colorings introduced by Achlioptas and Molloy with the occupancy problem for random allocations of balls into bins.

Topics: combinatorial optimization, complexity

Searching for geodetic boundary vertex sets

by  J. Cáceres, M. L. Puertas, C. Hernando, M. Mora, I. M. Pelayo, C. Seara

Abstract: A vertex v is a boundary vertex of a connected graph G if there exists a vertex u such that no neighbor of v is further away from u than v.  We obtain a number of properties involving different types of boundary vertices: peripheral, contour and eccentric vertices, including a realization theorem that not only corrects a wrong statement detected in a paper by Chartrand, Erwin, Johns, and Zhang ("Boundary vertices in graphs", 2003), but also improves it. We also prove that the boundary vertex set \partial(G) of any graph G is geodetic, that is, every vertex in G lies on some shortest path joining two boundary vertices. A vertex v belongs to the contour Ct(G) of G if no neighbor of v has an eccentricity greater than those of v. We investigate the geodeticity of the contour Ct(G) and other related sets.

Topics: graph theory

Building PQR trees in almost-linear time

by  Guilherme P. Telles, João Meidanis

Abstract: The problem of finding permutations that keep consecutive the elements in certain given sets S1, S2, . . . , Sm appears frequently, for example in DNA physical mapping, interval graph recognition and data retrieval. Such permutations are called valid. When there are valid permutation for the given sets, a PQR tree stores them all compactly. When there are no valid permutations, the R nodes of a PQR tree point out subsets responsible for the failure. This feature is interesting for problems whose input data may have errors, such as DNA physical mapping. In this paper we present an almost-linear time algorithm for PQR tree construction. Our algorithm replaces the pattern matching scheme of PQ trees, the predecessor of PQR trees, with simpler code that is easier to implement.

Topics: algorithms and data structures, analysis of algorithms

A multistart constructive heuristic for sequencing by hybridization using adaptive memory

by  Eraldo R. Fernandes, Celso C. Ribeiro

Abstract: We propose a new multistart constructive heuristic for sequencing by hybridization, based on learning from an adaptive memory. Computational results show that this heuristic obtains systematically better solutions than more involving and time consuming techniques such as tabu search and genetic algorithms. The memory-based strategy is able to significantly improve the performance of memoryless construction procedures and is particularly suitable for scheduling problems whose best solutions are in most cases built by blocks of elements that appear together very often.

Topics: approximation algorithms, combinatorial optimization, computational biology

(p,k)-coloring problems in line graphs

by  Marc Demange, Tinaz Ekim, Dominique de Werra

Abstract: The (p,k)-coloring problems generalize the usual coloring problem by replacing independent sets by cliques and independent sets. Complexities of many variations of (p,k)-coloring problems are studied in line graphs; polynomial algorithms or NP-hardness proofs are provided according to the complexity status. Finally, upper bounds on the optimal values are derived in general graphs.

Topics: approximation algorithms, complexity, graph theory

On the local splitting theorem

by  Zoltán Szigeti

Abstract: Let G = (V+s, E) be a 2-edge-connected graph. A pair of edges (rs, st) is called admissible if splitting off these edges (replacing rs and st by rt) preserves the local edge-connectivity (the maximum number of pairwise edge disjoint paths) between each pair of vertices in V.   The operation splitting off is very useful in graph theory, it is especially powerful in the solution of the edge-connectivity augmentation problem as it was showed by Frank ("Augmenting graphs to meet edge-connectivity requirements").   Mader ("A reduction method for edge-connectivity in graphs") proved that if the degree of s is different from three then there exists an admissible pair incident to s.   First we generalize Mader's result by showing that if d(s) ≥ 4 then there exists an edge incident to s that belongs to at least  floor(d(s)/3)  admissible pairs. An infinite family of graphs shows that this is best possible.   Second we generalize Frank's result ("On a theorem of Mader") by characterizing when an edge belongs to no admissible pairs. It provides a new proof for Mader's theorem.

Topics: combinatorial optimization, graph theory

The combinatorial stages of chromatic scheduling polytopes

by  Javier Marenco, Annegret Wagler

Abstract: Chromatic scheduling polytopes arise as solution spaces of the bandwidth allocation problem in certain radio access networks, the Point-to-Multipoint systems. The aim of this kind of radio systems is to supply wireless access to voice/data communication networks for customers with individual communication demands. To maintain the links, only frequencies from a certain spectrum can be used, which typically causes capacity problems. Hence it is, on the one hand, necessary to reuse frequencies, but, on the other hand, no interference must be caused thereby. This leads to the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-hard, and there exist no polynomial time algorithms with a fixed approximation ratio for these problems.   As algorithms based on cutting planes have shown to be successful for many other combinatorial optimization problems, the goal is to apply such methods to the bandwidth allocation problem. For that, knowledge on the associated polytopes is required. The present paper contributes to this issue, exploring the combinatorial structure of chromatic scheduling polytopes for increasing frequency spans. We observe that the polytopes pass through various stages — emptyness, non-emptyness but low-dimensionality, full-dimensionality but combinatorial instability, combinatorial stability — as the frequency span increases. We discuss here the thresholds for this increasing "quantity" giving rise to a new combinatorial "quality" of the polytopes, and we prove bounds on these thresholds.

Topics: combinatorial optimization, polyhedral combinatorics

The Helly property on subhypergraphs

by  Mitre C. Dourado, Fábio Protti, Jayme L. Szwarcfiter

Abstract: The celebrated theorem by Helly (1923) motivated the study of p-Helly hypergraphs. In this context, Golumbic and Jamison introduced the notion of strong p-Helly hypergraphs (1985). In this paper, we characterize strong p-Helly hypergraphs. This characterization leads to an algorithm for recognizing such hypergraphs. The algorithm terminates within polynomial time, whenever p is fixed. In contrast, we show that the recognition problem is co-NP-complete, for arbitrary p. Further, we apply the concept of strong p-Helly hypergraphs to the cliques of a graph, leading to the class of strong p-clique-Helly graphs. We describe a characterization for this class and obtain an algorithm for recognizing such graphs. Again, the algorithm has polynomial-time complexity for p fixed, and we show the corresponding recognition problem to be NP-hard, for arbitrary p.

Topics: complexity, graph theory

On the computational complexity of partial covers of Theta graphs

by  Jiří Fiala, Jan Kratochvíl, Attila Pór

Abstract: By use of elementary geometric arguments we prove the existence of a special integral solution of a system of linear equations. The existence of such a solution yields then the NP-hardness of the decision problem on the existence of locally injective homomorphisms to Theta graphs.

Topics: computational complexity, graph homomorphisms, Theta graphs

Generating all the cubic graphs that have a 6-cycle double cover

by  Rodrigo S. C. Leão, Valmir C. Barbosa

Abstract: A cycle double cover (CDC) of an undirected graph is a collection of the graph's cycles such that every edge of the graph belongs to exactly two cycles. We describe a constructive method for generating all the cubic graphs that have a 6-CDC (a CDC in which every cycle has length 6). We also prove that all such graphs have a Hamiltonian cycle.

Topics: graph theory

Partial characterizations of clique-perfect graphs

by  Flavia Bonomo, Maria Chudnovsky, Guillermo Durán

Abstract: A clique-transversal of a graph G is a subset of vertices that meets all the cliques of G. A clique-independent set is a collection of pairwise vertex-disjoint cliques. The clique-transversal number and clique-independence number of G are the sizes of a minimum clique-transversal and a maximum clique-independent set of G, respectively. A graph G is clique-perfect if the sizes of a minimum clique-transversal and a maximum clique-independent set are equal for every induced subgraph of G. It is not known whether there exists a characterization of clique-perfect graphs by forbidden subgraphs. In this paper, we present partial characterizations of this class of graphs, that is, we characterize clique-perfect graphs by forbidden subgraphs when the graph belongs to a certain class.

Topics: graph theory

The node-edge weighted 2-edge connected subgraph problem: linear relaxation, facets and separation

by  Mourad Baïou, José R. Correa

Abstract: Let G be an undirected k-edge connected graph with weights on edges and nodes. The minimum 2-edge connected subgraph problem, 2ECSP for short, is to find minimum weight 2-edge connected subgraph of G. This problem generalizes the well-known Steiner 2-edge connected subgraph problem. In this paper we study the convex hull of the incidence vectors corresponding to feasible solutions of 2ECSP. First, a natural integer programming formulation is given and it is shown that its linear relaxation is not suffcient to describe the underlying polytope, even if G is series-parallel. After studying the dimension of 2ECSP, we introduce two families of new valid inequalities and provide suffcient conditions for them to be facet-defining. Later, we concentrate on separation routines; finding polynomial time algorithms to separate important subclasses of the newly introduced inequalities. As consequence of the previous results we conclude that the separation of these new inequalities is polynomially solvable if G is series-parallel.

Topics: combinatorial optimization, polyhedral combinatorics

On bags and bugs

by  Pierre Hansen, Dragan Stevanović

Abstract: Usual graph classes, such as complete graphs, paths, cycles and stars, frequently appear as extremal graphs in graph theory problems. Here we want to turn the reader's attention to two novel, simply defined, graph classes that appear as extremal graphs in a number of graph theory problems. We call them bags and bugs. As examples of problems where bags and bugs appear, we show that balanced bugs maximize the index of graphs with fixed number of vertices and diameter, while odd bags maximize the index of graphs with fixed number of vertices and radius.

Topics: graph theory

Between coloring and list-coloring: \mu-coloring

by  Flavia Bonomo, Mariano Cecowski

Abstract: A new variation of the coloring problem, μ-coloring, is defined in this paper. Given a graph G and a function μ, a μ-coloring is a coloring where each vertex v of G must receive a color at most μ(v). It is proved that μ-coloring lies between coloring and list-coloring, in the sense of generalization of problems and computational complexity. The notion of perfection is extended for μ-coloring, defining M-perfect graphs and characterizing them by forbidden subgraphs. Finally, a polynomial time algorithm to solve μ-coloring for M-perfect graphs is shown.

Topics: combinatorial optimization complexity graph theory

A Gray code for binary subtraction

by  Joe Sawada

Abstract: A solution to the Binary Subtraction Problem (BSP) is a representation of an integer N as the difference of two binary numbers where the total number of bits is minimized. We describe a 3-close Gray code for listing all solutions to the BSP for a given N. In addition, we identify precisely the values for N that produce the maximal number of solutions given that the binary representation of N requires b bits.

Topics: algorithms and data structures, analysis of algorithms, enumerative combinatorics

An all-substrings common subsequence algorithm

by  C. E. R. Alves, E. N. Cáceres, S. W. Song

Abstract: Given two strings A and B of lengths na and nb, respectively, the all-substrings longest common subsequence (ALCS) problem obtains, for every substring B' of B, the length of the longest string that is a subsequence of both A and B'. The ALCS problem has many applications, such as finding approximate tandem repeats in strings, solving the circular alignment of two strings and finding the alignment of one string with several others that have a common substring. We present an algorithm for this problem that takes O(na nb) time and O(nb) space. To our knowledge, this is the first algorithm in the literature for the ALCS problem.

Topics: algorithms and data structures

Randomized mechanisms for limited supply multi-item auctions

by  Claudson F. Bornstein, Eduardo Sany Laber, Marcelo A. F. Más

Abstract: This paper studies a multiple item, limited supply auction problem in which each consumer can purchase at most one from a set of k items. Assuming an ordering among the items valuations, we obtain a randomized truthful mechanism that, under reasonable conditions, attains an expected competitive ratio of  O(log² k)  with high probability. Furthermore, we show that a wide class of truthful mechanisms, which includes all the presented mechanisms, cannot achieve a  o(log k / log log k)  competitive ratio.

Topics: analysis of algorithms, approximation algorithms, randomized algorithms

Non-separating cocircuits in matroids

by  Manoel Lemos, T. R. B. Melo

Abstract: For a 3-connected binary matroid M, let dimA(M) be the dimension of the subspace of the cocycle space spanned by the non-separating cocircuits of M avoiding A, where A is a subset of E(M). When A is empty, Bixby and Cunningham, in 1979, showed that dimA(M) = r(M). In 2004, when |A| = 1, Lemos proved that dimA(M) = r(M) – 1. Recently Lemos and Melo proved that if M is a 3-connected regular matroid and A is a 2-subset of E(M), then 2·dimA(M) ≥ r(M) – 3. In this paper, we show that if M is a 3-connected binary matroid and A is any subset of E(M) such that M | A has no coloop, then dimA(M) ≥ r(M) – (2^|A| – |A| – 1). We also show that when A is a triangle of a 3-connected binary matroid M, then dimA(M) = r(M) – 2.

Topics: enumerative combinatorics

On the Hadwiger number of hypercubes and its generalizations

by  L. Sunil Chandran, Naveen Sivadasan

Abstract: The Hadwiger number Had(G) of a graph G is the largest integer such that any graph G' with at most Had(G) nodes is a minor of G. We show (almost) sharp bounds on the Hadwiger number for the well known class of d-dimensional Hypercubes Hd. In particular, we show that 2^(floor((d–1)/2) ≤ Had(Hd) ≤ 2^((d–1)/2) · sqrt(d). Hypercubes are a special case of graph (Cartesian) products. The product of graph G taken d times is denoted by G^d. Under this notation, Hd is isomorphic to (K2)^d, where K2 is a single edge. We extend our results to obtain similar bounds for the Hadwiger number of graph products. As a consequence, we derive bounds for the Hadwiger number for important classes of graph products like Hamming graphs and d-dimensional grids. We also derive similar bounds for the products of almost all graphs with n nodes and at least n log n edges. The well-known Hadwiger conjecture states that Had(G) ≥ χ(G), where χ(G) is the chromatic number of G. As an important consequence of our results, we show that if G is isomorphic to F^d for some graph F then Had(G) ≥ χ(G)^(floor((d–1)/2)). (In fact, we show a stronger lower bound but involving a more complicated expression.) It follows that, if d ≥ 3 then Hadwiger conjecture holds for G.

Topics: graph theory

The distribution of the path edge-covering numbers for random trees

by  Alois Panholzer

Abstract: We study for various tree families the distribution of the number of edge-disjoint paths required to cover the edges of a random tree of size n. For all tree families considered we can show a central limit theorem with expectation  ~μn and variance  ~νn  with constants μ and ν depending on the specific tree family.

Topics: enumerative combinatorics, graph theory

Improved bounds on acyclic edge colouring

by  Rahul Muthu, Narayanan N., C. R. Subramanian

Abstract: A proper colouring of the edges of a graph G is called acyclic if there is no two-coloured cycle in G. The acyclic chromatic index of G, denoted a'(G), is the least number of colours required for an acyclic edge colouring of G. It is known that a'(G) ≤ 16 Δ for all graphs G where Δ is the maximum degree of G. We prove that a'(G) < 6 Δ for all graphs with girth at least 9. We extend the same method to obtain a bound of 4.52 Δ with the girth requirement g ≥ 220. We also give a relation between g and a'(G).

Topics: graph theory

Globally bounded local edge colourings of hypergraphs

by  Mathias Schacht, Anusch Taraz

Abstract: We consider edge colourings of K(n,r) — the complete r-uniform hypergraph on n vertices. Our main question is: how 'colourful' can such a colouring be if we restrict the number of colours locally? The local restriction is formulated as follows: for a fixed hypergraph H and an integer k we call a colouring (H,k)-local, if every copy of H in the complete hypergraph K(n,r) picks up at most k different colours. We will investigate the threshold of k which guarantees that every (H,k)-local colouring must have a bounded global number of colours as n tends to infinity.

Topics: graph theory

Search locally to arrange cyclically

by  Murali K. Ganapathy, Sachin P. Lodha

Abstract: The minimum Directed Circular Arrangement (DCA) problem, requires one to find an embedding of a given weighted directed graph into a discrete circle which minimizes the total weighted arc length. While DCA does not admit a PTAS (unless P=NP), it does have a O(log n log log n)-approximation algorithm. In this paper, we propose and investigate the performance of some local search based practical heuristics. For an interesting class of graphs (which includes random graphs), we show that any algorithm generates a constant approximation to the optimal solution.

Topics: algorithms and data structures, combinatorial optimization, graph theory

Probe interval bigraphs

by  Gerard Jennhwa Chang, Ton Kloks, Sheng-Lung Peng

Abstract: Given a graph class G, a graph is a probe graph of G if its vertices can be partitioned into two sets, probes and non-probes, where the set of non-probes is an independent set, such that the graph can be embedded into a graph of G by adding certain edges between non-probes. We show that the recognition problem of probe interval bigraphs is in P.

Topics: algorithms and data structures

On some applications of randomized memory

by  Vince Grolmusz

Abstract: We define Probabilistic Memory Cells (PMC's), and show how to encode n bits into n PMC's, transform n PMC's to n^o(1) PMC's (we call this form Hyperdense Coding), and we show how one can transform back these n^o(1) PMC's to n PMC's, and from these we can get back the original bits, while from the hyperdense form we could have got back only n^o(1) bits. We also show that n×n matrices can be converted to n^o(1) × n^o(1) matrices and from these tiny matrices we can retrieve original ones, also with linear transformations, using PMC's.

Topics: algorithms and data structures

A general approach to L(h,k)-label interconnection networks

by  Tiziana Calamoneri, Saverio Caminiti, Rossella Petreschi

Abstract: Given two non negative integers h and k, an L(h,k)-labeling of a graph G = (V,E) is a function from the set V to a set of colors, such that adjacent nodes take colors at distance at least h and nodes connected by a 2 length path take colors at distance at least k. The aim of the L(h,k)-labeling problem is to minimize the greatest used color. Since the decisional version of this problem is NP-complete, it is important to investigate particular classes of graphs for which the problem can be efficiently solved. In this work the L(h,k)-labeling problem for a new class of graphs, called (l × n)-multistage graphs, is studied. These graphs are characterized to have nodes organized as a matrix and they include the most common interconnection topologies, such as Butterfly-like, Beneš, CCC, Trivalent Cayley networks. The general algorithm presented in this paper leads to an efficient L(2,1)-labeling scheme for Butterfly and CCC networks.

Topics: algorithms and data structures, graph theory

Lehman's equation on near-ideal clutters

by  G. Argiroffo, S. Bianchi, G. Nasini

Abstract: In this paper we study the Lehman's equation on 0-1 matrices associated to near-ideal clutters. Since minimal nonideal clutters can be characterized as near-ideal clutters whose blockers also are near-ideal, Lehman's equation results on the cores of minimally nonideal clutters has been extended.

Topics: polyhedral combinatorics

Optimal flow distribution among multiple channels with unknown capacities

by  Richard Karp, Till Nierhoff, Till Tantau

Abstract: Consider a simple network flow problem in which there are n channels directed from a source to a sink. The channel capacities are unknown and we wish to determine a feasible network flow of value D. Flow problems with unknown capacities arise naturally in numerous applications, including inter-domain traffic routing in the Internet, bandwidth allocation for sending files in peer-to-peer networks, and the distribution of physical goods like newspapers among different points of sale. We study protocols that probe the network by attempting to send a flow of at most D units through the network. If the flow is not feasible, the protocol is told on which channels the capacity was exceeded (binary feedback) and possibly also how many units of flow were successfully send on these channels (throughput feedback). For the latter, more informative, type of feedback we present optimal protocols for minimizing the number of rounds needed to find a feasible flow and for minimizing the total amount of wasted flow. For binary feedback, we show that one can exploit the fact that network capacities are often larger than the demand D: We present a protocol for this situation that is asymptotically optimal and finds a solution more quickly than the generalized binary search protocol previously proposed in the literature. For the special case of two channels we present a protocol that is optimal and outperforms binary search.

Topics: algorithms and data structures, analysis of algorithms, combinatorial optimization

Detecting flows congesting a target network link

by  D. Barth, P. Berthomé, M. Diallo

Abstract: In this paper, we deal with the analysis of network links saturation. Given a network, we target one of its links and provide an interesting analysis that allows to detect all vertex pairs for which any maximum flow always saturates the targeted link. The whole analysis complexity remains around O(n) maximum-flow/minimum-cut computations using Gomory and Hu cut-trees.

Topics: combinatorial optimization, graph theory

Computing the integrality gap of the asymmetric travelling salesman problem

by  Sylvia Boyd, Paul Elliott-Magwood

Abstract: This extended abstract outlines the results of our investigations into the integrality gap of the Asymmetric Travelling Salesman Problem for small values of n. Specifically, we have computed the exact integrality gap for n = 4, 5, 6, and 7 and we have found a lower bound on the integrality gap for all n between 8 and 15. Furthermore we have created a new family of extreme points based on our data for which the integrality gaps approach 2 as n increases.

Topics: combinatorial optimization

Advances in packing directed joins

by  Aaron M. Williams, Bertrand Guenin

Abstract: Edmonds and Giles conjectured that the maximum number of disjoint directed joins is equal to the smallest weight of a directed cut, in every weighted directed graph. The conjecture is true in several special cases, and is also true if the roles of directed joins and directed cuts are reversed, by the Lucchesi-Younger Theorem. Schrijver disproved the conjecture in general by providing the first counterexample. Twenty years later, Cornuéjols and Guenin discovered two more counterexamples by computer search. Despite its great potential significance, little progress has been made towards compiling a complete list of minimal counterexamples. One obstacle is the apparent complexity of the known counterexamples. In this paper, we offer a simple framework for understanding these counterexamples, and we use this framework to construct several new counterexamples. Then we prove that minimal counterexamples have a particular structure, and we use this structure to show that every "smallest" minimal counterexamples has now been found. In addition, we introduce an NP-completeness result for a more difficult problem.

Topics: graph theory

Degree constrained subgraphs

by  L. Addario-Berry, K. Dalal, B. A. Reed

Abstract: In this paper, we present new structural results about the existence of a subgraph where the degrees of the vertices are pre-specified. Further, we use these results to prove that for any graph G there is a 16-edge-weighting (an assignment of weights from the set {1,...,16} to the edges of G) so that the weighted degrees of the vertices induce a proper colouring. This is substantial progress toward proving a conjecture by Karonski.

Topics: graph theory

Planar graph bipartization in linear time

by  Samuel Fiorini, Nadia Hardy, Bruce Reed, Adrian Vetta

Abstract: For each constant k, we present a linear time algorithm that, given a planar graph G, either finds a minimum odd cycle vertex transversal in G or guarantees that there is no transversal of size at most k.

Topics: combinatorial optimization, graph theory

Faster algorithms for feedback vertex set

by  Venkatesh Raman, Saket Saurabh, C. R. Subramanian

Abstract: We give a  O(((12 log k)/(log log k) + 6)^k · n^ω)  time algorithm for testing whether an undirected graph on n vertices has a feedback vertex set (fvs) of size at most k. Here n^ω is the complexity of the best matrix multiplication algorithm. This improves the previous fastest algorithms by roughly a factor of (log log k)^k. The main technical theorem we use to obtain faster algorithms is that if an undirected graph on n vertices with minimum degree ≥ 3 has a fvs of size at most (1/3) n^(1–ε), with 0<ε<1, then the girth (length of the shortest cycle) of the graph is at most 6/ε. We also investigate the fixed parameter complexity of weighted fvs problem in undirected graphs.

Topics: analysis of algorithms

A forbidden subgraph characterization of path graphs

by  Silvia B. Tondato, Marisa Gutierrez, Jayme L. Szwarcfiter

Abstract: A path graph is the intersection graph of paths of a tree. An open problem mentioned in the literature is to describe a characterization of path graph by forbidden induced subgraphs. In this paper, we propose a solution to this problem, by describing the family of fifteen forbidden subgraphs for path graphs.

Topics: graph theory

Non loop graphs with induced cycles

by  Liliana Alcón, Márcia R. Cerioli, Celina M. H. de Figueiredo, Marisa Gutierrez, João Meidanis

Abstract: Loop Graphs were introduced to model problems involving DNA taking into account the repeat structure of its molecules. We consider the recognition problem and a family of minimal forbidden configurations for the class of Loop Graphs. In a previous work we solved the problem for the particular case of trees by characterizing Tree Loop Graphs. The characterization gave all minimal forbidden configurations for Tree Loop Graphs, and consequently, all minimal forbidden configurations containing no cycles for the class of Loop Graphs. In the present work we further study minimal forbidden configurations for Loop Graphs by considering forbidden configurations containing induced cycles. We obtain new necessary conditions for the class of Loop Graphs which consequently give new infinite forbidden families.

Topics: computational biology, graph theory

Fractionally total colouring G(n,p)

by  Conor Meagher, Bruce Reed

Abstract: We give a characterization of what the value of X^(Tf(G(n,p)) asymptotically almost surely is, based solely on the value of p except for (i) when  p = (c + o(1))n^(–2)  or  p = (c + o(1))n^(–3/2)  for some constant c, or (ii) when n is even and  p ≥ 1 – log(n)/(3n).  In case (i) our characterization is based on whether Δ(G(n,p)) = 1 or not. In case (ii) our characterization is based on the size of the largest fractional matching of the graphs complement and can be computed in O(n^3) time.

Topics: algorithms and data structures, combinatorial optimization, graph theory

Forbidden subgraph characterization of split graphs that are UEH

by  M. R. Cerioli, P. Petito

Abstract: A graph is called a UEH graph if it is the edge intersection graph of a family of paths in a tree satisfying the Helly property. A graph is a Split graph if there is a partition of its vertex set into an independent set and a complete set. We present the forbidden subgraph characterization of the graph that are UEH and Split. This characterization is based on the clique separator theory.

Topics: graph theory

Two- and three-dimensional parametric packing

by  F. K. Miyazawa, Y. Wakabayashi

Abstract: We present asymptotic approximation algorithms for the two-dimensional bin packing, the three-dimensional strip packing and the three-dimensional bin packing problems. We consider the special case where each of the dimensions of the items to be packed is at most 1/m of the corresponding dimension of the recipient, where m is a positive integer. We show that the asymptotic performance bounds of these algorithms are better than the bounds already known for each of these parametric cases.

Topics: approximation algorithms, combinatorial optimization

Large k-independent sets of random regular graphs

by  Mihalis Beis, William Duckworth, Michele Zito

Abstract: A k-independent set in a graph is a set of vertices at distance at least k+1 from each other. The maximum k-independent set problem (or MkIS) is that of finding a k-independent set of maximum cardinality in the given graph. We prove both constructive lower bounds and combinatorial upper bounds on the size of the optimal solutions in random r-regular graphs for each fixed integer k ≥ 2 and each fixed r ≥ 3.

Topics: analysis of algorithms, graph theory, randomized algorithms

A one-dimensional bin packing problem with shelf divisions

by  E. C. Xavier, F. K. Miyazawa

Abstract: The class constrained shelf bin packing (CCSBP) problem is a generalization of the bin packing problem, where items must be packed into the minimum number of bins, and items in a same bin must be partitioned into compartments. The items in a same compartment must have a same class and a maximum total size. Subsequent compartments must be separated by non-null shelf divisors. We present an asymptotic approximation scheme when the number of classes is bounded by a constant. To our knowledge, this is the first approximation result where shelf divisions of non-null size are used in packing problems.

Topics: analysis of algorithms, approximation algorithms, combinatorial optimization

On the asymmetric representatives formulation for the vertex coloring problem

by  Manoel Campêlo, Victor Campos, Ricardo Corrêa

Abstract: In this work, the representatives formulation for the vertex coloring problem is revisited to remove symmetry and new versions of facets derived from the substructures of G are presented. In addition, we show a new facet derived from independent sets of G. Finally, a comparison with the independent sets formulation is provided.

Topics: combinatorial optimization, polyhedral combinatorics

Local cutpoints and iterated clique graphs

by  M. E. Frías-Armenta, F. Larrión, V. Neumann-Lara, M. A. Pizaña

Abstract: The clique graph K(G) of a graph G is the intersection graph of all its (maximal) cliques. Here we are interested in the effect of operations like edge contraction, edge removal and others on the dynamical behaviour of a graph under the iteration of the clique operator K. As a consequence of this study, we can now prove clique divergence for graphs for which no previously known technique would yield the result, in particular, we prove that every clique divergent graph is a spanning subgraph of a clique divergent graph with diameter 2.

Topics: graph theory

On hereditary Helly self-clique graphs

by  F. Larrión, A. Pizaña

Abstract: A graph is clique-Helly if any family of mutually intersecting (maximal) cliques has non-empty intersection, and it is hereditary clique-Helly (abbreviated HCH) if its induced subgraphs are clique-Helly. The clique graph of a graph G is the intersection graph of its cliques, and G is self-clique if it is connected and isomorphic to its own clique graph. We show that every HCH graph is an induced subgraph of a self-clique HCH graph, and give a characterization of self-clique HCH graphs in terms of their constructibility starting from certain digraphs with some forbidden subdigraphs. We also specialize these results to involutive HCH graphs, i.e. self-clique HCH graphs whose vertex-clique bipartite graphs admit a part-switching involution.

Topics: graph theory

A new family of K-divergent graphs

by  Martín Matamala, José Zamora

Abstract: A graph G is K-divergent if the sequence |V(Kn(G))| tends to infinity with n, where Kn+1(G) is defined by Kn+1(G) = K(Kn(G)) for n > 0 and K(G) is the intersection graph of the cliques of G. An affine graph is a pair (G,σ) where σ is an automorphism assigning to each vertex of G one of its neighbor. An admissible coloring of (G,σ) is a pair (c,π), where c is a vertex coloring of G with colors in a set S and π is a permutation of S satisfying c ° σ = π ° c. It is locally bijective if each color of S appears exactly once in the closed neighborhood of each vertex of G. In this work we obtain a structural decomposition of any affine graph (G,σ) in term of the orbits of σ. We also prove the following: if an affine graph (G,σ) has an admissible locally bijective coloring then \overline(G) is K-divergent. Using this result we construct new families of K-divergent graphs including the cartesian product (C2k+1)^k, for any k ≥ 2, where C2k+1 is the cycle of length 2k+1.

Topics: graph theory

Alignment with non-overlapping inversions in O(n³ log n) time

by  Carlos E. R. Alves, Alair Pereira do Lago, Augusto F. Vellozo

Abstract: Alignment of sequences is widely used for biological sequence comparisons, and only biological events like mutations, insertions and deletions are considered. Other biological events like inversions are not automatically detected by the usual alignment algorithms, thus some alternative approaches have been tried in order to include inversions or other kind of rearrangements. Despite many important results in the last decade, the complexity of the problem of alignment with inversions is still unknown. In 1992, Schöniger and Waterman proposed the simplification hypothesis that the inversions do not overlap. They also presented an O(n^6) exact solution for the alignment with non-overlapping inversions problem, and introduced a heuristic for it that brings the running-time complexity down. In this paper, n denotes the maximal length of the two aligned sequences. In 2003, two independ works presented an exact algorithm for the simplified problem. They presented algorithms with O(n^4)-time and O(n^2)-space complexity for alignments with non-overlapping inversions. In this present extended abstract, we announce we have an algorithm that solves the problem in O(n^3 log n)-time and O(n^2)-space.

Topics: algorithms and data structures, analysis of algorithms, computational biology

A new refinement procedure for graph isomorphism algorithms

by  Mateus de Oliveira Oliveira, Fabíola Greve

Abstract: Two vertices of a graph are said to be similar if there exists a graph automorphism mapping one of them into the other. Procedures aiming to separate vertices of a graph into equivalence classes accordingly to their similarities are the basis of many isomorphism testing algorithms. In practice, these refinement procedures are used to efficiently reduce the search space of backtracking based techniques. In this article we present a new refinement procedure that associates to each pair of vertices isomorphic invariant sequences which augments the possibilities of distinguishing non similar vertices in different classes.

Topics: graph theory

Two aspects of the pallet loading problem

by  Walter F. Mascarenhas

Abstract: We present two new ideas about the Pallet Loading Problem. One idea uses elementary number theory to analyze the structure of the filled parts of optimal solutions. The other uses duality bounds to constrain the regions of the pallet that can be empty in optimal solutions. Using these ideas, we propose a new exact algorithm to solve the Pallet Loading Problem.

Topics: combinatorial optimization

Stabilized branch-and-cut-and-price for the generalized assignment problem

by  Alexandre Pigatti, Marcus Poggi de Aragão, Eduardo Uchoa

Abstract: The Generalized Assignment Problem (GAP) is a classic scheduling problem with many applications. We propose a branch-and-cut-and-price for that problem featuring a stabilization mechanism to accelerate column generation convergence. We also propose ellipsoidal cuts, a new way of transforming the exact algorithm into a powerful heuristic, in the same spirit of the cuts recently proposed by Fischetti and Lodi. The improved solutions found by this heuristic can, in turn, help the task of the exact algorithm. The resulting algorithms showed a very good performance and were able to solve three among the last five open instances from the OR-Library.

Topics: combinatorial optimization

The 3-colored Ramsey number of odd cycles

by  Yoshiharu Kohayakawa, Miklós Simonovits, Jozef Skokan

Abstract: For graphs G1, ..., Gk, the Ramsey number R(G1, ..., Gk) is the minimum integer N satisfying that for any coloring of edges of the complete graph KN on N vertices by k colors there exists a color i for which the corresponding color class contains Gi as a subgraph. In 1973, Bondy and Erdös conjectured that if n is odd then R(Cn,Cn,Cn) = 4n–3, where Cn denotes the cycle on n vertices. In this paper we confirm this conjecture for n sufficiently large.

Topics: graph theory

Algorithms for the degree-constrained minimum spanning tree problem

by  Alexandre Salles da Cunha, Abilio Lucena

Abstract: In this paper, two different approaches are used to obtain upper and lower bounds to the Degree Constrained Minimum Spanning Tree Problem. To the best of our knowledge, this is the very first time in which blossom inequalities are used to reinforce lower bounds to that problem. One approach is based on (Lagrangian) Relax-and-Cut while the other is a cutting plane algorithm. Preliminary computational results indicate that both approaches may lead to exact solution algorithms and heuristics that are competitive with the best in the literature.

Topics: combinatorial optimization, polyhedral combinatorics

Perfect subgraph/supergraph

by  Murilo V. G. da Silva, André L. P. Guedes

Abstract: In this work it is defined four parameters that can measure how imperfect a graph is. These parameters are denoted ρ1, ρ2, ρ3 and ρ4. The defined parameters are related to some operations that can be applied to a graph to make it perfect. The following operations are considered: edge deletion (ρ1), edge insertion (ρ2), both deletion and insertion of edges (ρ3) and, finally, vertex deletion (ρ4). It is shown that for any graph it holds that ρ4 ≤ ρ3 ≤ ρ1 and ρ4 ≤ ρ3 ≤ ρ2. It is also shown examples of graphs where such inequalities are strict. Finally, some lower bounds and upper bounds for these parameters are shown. As a consequence of a lower bound for ρ4, the author shows that there are "highly" imperfect graphs. More precisely, there are graphs with n vertices where ρ4 ≥ n/log(2n) – log(2n).

Topics: analysis of algorithms, complexity, graph theory