## Abstract

The linkage of a graph is defined to be the maximum min-degree of any of its subgraphs. It is known that the linkage of a graph is equal to its width: for an arbitrary linear ordering of the vertices of the graph, consider the maximum, with respect to any vertex v, of the number of vertices connected with v and preceding it in the ordering; the width of the graph is the minimum of these maxima over all possible linear orderings. Width has been used in artificial intelligence in the context of constraint satisfaction problems (CSPs). A more general notion is defined by considering not the number of vertices preceding and connected with v but rather the least number of vertices preceding and connected with any cluster of at most j consecutive vertices extending to the right up to v (j is a given integer). The graph parameter thus defined is called j-width. No efficient algorithm was known for computing the j-width. In this paper, we introduce a graph parameter depending on j that refers to the subgraphs of the graph and generalizes the notion of linkage. We prove the min-max theorem that this graph parameter, which we call j-linkage, is equal to j-width, and we then give a polynomial-time algorithm for computing it (for constant j). We also find tight lower and upper bounds for the j-linkage (equivalently, the j-width) of graphs with given numbers of vertices and edges. It is interesting to note that a lower bound for the width of a graph had been found by Erdös; as we show, however, that bound is not tight. Moreover, we prove that our lower bound for width is also a tight lower bound for treewidth, pathwidth, and bandwidth, graph parameters that may be arbitrarily larger than width. Finally, we show that computing the j-linkage is a P-complete problem, whereas we prove that approximating it is a threshold problem: it is in NC for approximation factors < 1/(2j), and it is P-complete for approximation factors > 1/2.

Original language | English (US) |
---|---|

Pages (from-to) | 626-647 |

Number of pages | 22 |

Journal | SIAM Journal on Computing |

Volume | 25 |

Issue number | 3 |

DOIs | |

State | Published - Jun 1996 |

## Keywords

- Algorithms in NC
- Backtrack-free search
- Extremal graph properties
- Linkage of a graph
- P-complete problems
- Width parameters of a graph

## ASJC Scopus subject areas

- General Computer Science
- General Mathematics