Abstract. A hole in a graph is an induced cycle of length at least 4. A hole is long if its length is at least 5. By [Formula: see text], we denote a path on [Formula: see text] vertices. In this paper, we give polynomial-time algorithms for the following problems: the maximum weight independent set problem in long-hole–free graphs and the feedback vertex set problem in [Formula: see text]-free graphs. Each of the above results resolves a corresponding long-standing open problem. An extended [Formula: see text] is a five-vertex hole with an additional vertex adjacent to one or two consecutive vertices of the hole. Let [Formula: see text] be the class of graphs excluding an extended [Formula: see text] and holes of length at least 6 as induced subgraphs; [Formula: see text] contains all long-hole–free graphs and all [Formula: see text]-free graphs. We show that, given an [Formula: see text]-vertex graph [Formula: see text] with vertex weights and an integer [Formula: see text], one can, in time, [Formula: see text] find a maximum-weight induced subgraph of [Formula: see text] of treewidth less than [Formula: see text]. This implies both aforementioned results. To achieve this goal, we extend the framework of potential maximal cliques (PMCs) to containers. Developed by Bouchitté and Todinca [ SIAM J. Comput., 31 (2001), pp. 212–232] and extended by Fomin, Todinca, and Villanger [ SIAM J. Comput., 44 (2015), pp. 54–87], this framework allows us to solve a wide variety of tasks, including finding a maximum-weight induced subgraph of treewidth less than [Formula: see text] for fixed [Formula: see text], in time polynomial in the size of the graph and the number of potential maximal cliques. Further developments, tailored to solve the maximum weight independent set problem within this framework (e.g., for [Formula: see text]-free [Lokshtanov, Vatshelle, and Villanger, SODA 2014, pp. 570–581] or [Formula: see text]-free graphs [Grzesik, Klimošová, Pilipczuk, and Pilipczuk, ACM Trans. Algorithms, 18 (2022), pp. 4:1–4:57]), enumerate only a specifically chosen subset of all PMCs of a graph. In all aforementioned works, the final step is an involved dynamic programming algorithm whose state space is based on the considered list of PMCs. Here, we modify the dynamic programming algorithm and show that it is sufficient to consider only a container for each PMC: a superset of the maximal clique that intersects the sought solution only in the vertices of the PMC. This strengthening of the framework not only allows us to obtain our main result but also leads to significant simplifications of the reasoning in previous papers.

Abstract. We prove that every connected [Formula: see text]-free graph has cop number at most two, solving a conjecture of Sivaraman. In order to do so, we first prove that every connected [Formula: see text]-free graph [Formula: see text] with independence number at least three contains a three-vertex induced path with vertices [Formula: see text] in order, such that every neighbor of [Formula: see text] is also adjacent to one of [Formula: see text].

Abstract. Fix [Formula: see text], and let [Formula: see text] be a graph, with vertex set partitioned into [Formula: see text] subsets (“blocks”) of approximately equal size. An induced subgraph of [Formula: see text] is “transversal” (with respect to this partition) if it has exactly one vertex in each block (and therefore it has exactly [Formula: see text] vertices). A “pure pair” in [Formula: see text] is a pair [Formula: see text] of disjoint subsets of [Formula: see text] such that either all edges between [Formula: see text] are present or none are; and in the present context we are interested in pure pairs [Formula: see text] where each of [Formula: see text] is a subset of one of the blocks, and not the same block. This paper collects several results and open questions concerning how large a pure pair must be present if various types of transversal subgraphs are excluded.

A pure pair in a graph $G$ is a pair $(Z_1,Z_2)$ of disjoint sets of vertices such that either every vertex in $Z_1$ is adjacent to every vertex in $Z_2$, or there are no edges between $Z_1$ and $Z_2$. With Maria Chudnovsky, we recently proved that, for every forest $F$, every graph $G$ with at least two vertices that does not contain $F$ or its complement as an induced subgraph has a pure pair $(Z_1,Z_2)$ with $|Z_1|,|Z_2|$ linear in $|G|$. Here we investigate what we can say about pure pairs in an ordered graph $G$, when we exclude an ordered forest $F$ and its complement as induced subgraphs. Fox showed that there need not be a linear pure pair; but Pach and Tomon showed that if $F$ is a monotone path, then there is a pure pair of size $c|G|/\log |G|$. We generalize this to all ordered forests, at the cost of a slightly worse bound: we prove that, for every ordered forest $F$, every ordered graph $G$ with at least two vertices that does not contain $F$ or its complement as an induced subgraph has a pure pair of size $|G|^{1-o(1)}$.

A hole in a graph is an induced cycle of length at least 4. A hole is long if its length is at least 5. By Pt we denote a path on t vertices. In this paper we give polynomial-time algorithms for the following problems: the Maximum Weight Independent Set problem in long-hole-free graphs, and the Feedback Vertex Set problem in P5-free graphs. Each of the above results resolves a corresponding long-standing open problem. An extended C5 is a five-vertex hole with an additional vertex adjacent to one or two consecutive vertices of the hole. Let be the class of graphs excluding an extended C5 and holes of length at least 6 as induced subgraphs; contains all long-hole-free graphs and all P5-free graphs. We show that, given an n-vertex graph G ∊ with vertex weights and an integer k, one can in time find a maximum-weight induced subgraph of G of treewidth less than k. This implies both aforementioned results. To achieve this goal, we extend the framework of potential maximal cliques (PMCs) to containers. Developed by Bouchitté and Todinca [SIAM J. Comput. 2001] and extended by Fomin, Todinca, and Villanger [SIAM J. Comput. 2015], this framework allows to solve high variety of tasks, including finding a maximum-weight induced subgraph of treewidth less than k for fixed k, in time polynomial in the size of the graph and the number of potential maximal cliques. Further developments, tailored to solve the Maximum Weight Independent Set problem within this framework (e.g., for P5-free [SODA 2014] or P6-free graphs [SODA 2019]), enumerate only a specifically chosen subset of all PMCs of a graph. In all aforementioned works, the final step is an involved dynamic programming algorithm whose state space is based on the considered list of PMCs. Here we modify the dynamic programming algorithm and show that it is sufficient to consider only a container for each potential maximal clique: a superset of the maximal clique that intersects the sought solution only in the vertices of the potential maximal clique. This strengthening of the framework not only allows us to obtain our main result, but also leads to significant simplifications of reasonings in previous papers.

An odd hole in a graph is an induced cycle with odd length greater than 3. In an earlier paper (with Sophie Spirkl), solving a longstanding open problem, we gave a polynomial-time algorithm to test if a graph has an odd hole. We subsequently showed that, for every t , there is a polynomial-time algorithm to test whether a graph contains an odd hole of length at least t . In this article, we give an algorithm that finds a shortest odd hole, if one exists.

We give a polynomial-time algorithm to test whether a graph contains an induced cycle with length more than three and odd.

Ramsey's theorem says that for every clique $H_1$ and for every graph $H_2$ with no edges, all graphs containing neither of $H_1,H_2$ as induced subgraphs have bounded order. What if, instead, we exclude a graph $H_1$ with a vertex whose deletion gives a clique, and the complement $H_2$ of another such graph? This no longer implies bounded order, but it implies tightly restricted structure that we describe. There are also several related subproblems (what if we exclude a star and the complement of a star? what if we exclude a star and a clique? and so on) and we answer a selection of these.

Hadwiger's conjecture asserts that if a simple graph $G$ has no $K_{t+1}$ minor, then its vertex set $V(G)$ can be partitioned into $t$ stable sets. This is still open, but we prove under the same hypothesis that $V(G)$ can be partitioned into $t$ sets $X_1,\ldots,X_t$, such that for $1\le i\le t$, the subgraph induced on $X_i$ has maximum degree at most a function of $t$. This is sharp, in that the conclusion becomes false if we ask for a partition into $t-1$ sets with the same property.

Reed's $\omega$, $\Delta$, $\chi$ conjecture proposes that every graph satisfies $\chi\leq \lceil\frac 12(\Delta+1+\omega)\rceil$; it is known to hold for all claw-free graphs. In this paper we consider a local strengthening of this conjecture. We prove the local strengthening for line graphs, then note that previous results immediately tell us that the local strengthening holds for all quasi-line graphs. Our proofs lead to polytime algorithms for constructing colorings that achieve our bounds: $O(n^2)$ for line graphs and $O(n^3m^2)$ for quasi-line graphs. For line graphs, this is faster than the best known algorithm for constructing a coloring that achieves the bound of Reed's original conjecture.

A graph $G$ is claw-free if no induced subgraph of it is isomorphic to the complete bipartite graph $K_{1,3}$, and it is prime if $|V(G)| \geq 4$ and there is no $X \subseteq V(G)$ with $1<|X|<|V(G)|$ such that every vertex of $V(G) \setminus X$ with a neighbor in $X$ is adjacent to every vertex of $X$. In particular, if $G$ is prime, then both $G$ and $G^c$ are connected. This paper has two main results. The first one is that if $G$ is a prime graph that is not a member of a particular family of exceptions, and $H$ is a prime induced subgraph of $G$, then (up to isomorphism) $G$ can be grown from $H$, adding one vertex at a time, in such a way that all the graphs constructed along the way are prime induced subgraphs of $G$. A simplicial clique in $G$ is a nonempty clique $K$ such that for every $k \in K$ the set of neighbors of $k$ in $V(G) \setminus K$ is a clique. Our second result is that a prime claw-free graph $G$ has at most $|V(G)|+1$ simplicial cliques, and we give an algorithm to find them all with running time $O(|V(G)|^4)$. In particular, this answers a question of Prasad Tetali [private communication] who asked if there is an efficient algorithm to test if a claw-free graph has a simplicial clique. Finally, we apply our results to claw-free graphs that are not prime. Such a graph may have exponentially many simplicial cliques, so we cannot list them all in polynomial time, but we can in a sense describe them.

Efficient operation of wireless networks and switches requires using simple (and in some cases distributed) scheduling algorithms. In general, simple greedy algorithms (known as Greedy Maximal Scheduling, or GMS) are guaranteed to achieve only a fraction of the maximum possible throughput (e.g., 50% throughput in switches). However, it was recently shown that in networks in which the Local Pooling conditions are satisfied, GMS achieves 100% throughput. Moreover, in networks in which the σ-Local Pooling conditions hold, GMS achieves σ% throughput. In this paper, we focus on identifying the specific network topologies that satisfy these conditions. In particular, we provide the first characterization of all the network graphs in which Local Pooling holds under primary interference constraints (in these networks, GMS achieves 100% throughput). This leads to a linear-time algorithm for identifying Local-Pooling-satisfying graphs. Moreover, by using similar graph-theoretical methods, we show that in all bipartite graphs (i.e., input-queued switches) of size up to 7 ×n, GMS is guaranteed to achieve 66% throughput, thereby improving upon the previously known 50% lower bound. Finally, we study the performance of GMS in interference graphs and show that in certain specific topologies, its performance could be very bad. Overall, the paper demonstrates that using graph-theoretical techniques can significantly contribute to our understanding of greedy scheduling algorithms.

Efficient operation of wireless networks and switches requires using simple (and in some cases distributed) scheduling algorithms. In general, simple greedy algorithms (known as Greedy Maximal Scheduling - GMS) are guaranteed to achieve only a fraction of the maximum possible throughput (e.g., 50% throughput in switches). However, it was recently shown that in networks in which the Local Pooling conditions are satisfied, GMS achieves 100% throughput. Moreover, in networks in which the ¿-Local Pooling conditions hold, GMS achieves ¿% throughput. In this paper, we focus on identifying the specific network topologies that satisfy these conditions. In particular, we provide the first characterization of all the network graphs in which Local Pooling holds under primary interference constraints (in these networks GMS achieves 100% throughput). This leads to a linear time algorithm for identifying Local Pooling-satisfying graphs. Moreover, by using similar graph theoretical methods, we show that in all bipartite graphs (i.e., input-queued switches) of size up to 7 × n, GMS is guaranteed to achieve 66% throughput, thereby improving upon the previously known 50% lower bound. Finally, we study the performance of GMS in interference graphs and show that in certain specific topologies its performance could be very bad. Overall, the paper demonstrates that using graph theoretical techniques can significantly contribute to our understanding of greedy scheduling algorithms.

Robertson and Seymour introduced branch-width as a new connectivity invariant of graphs in their proof of the Wagner conjecture. Decompositions based on this invariant provide a natural framework for implementing dynamic-programming algorithms to solve graph optimization problems. We describe a heuristic method for finding branch decompositions; the method is based on the eigenvector technique for finding graph separators. We use this as a tool to obtain high-quality tours for the traveling salesman problem by merging collections of tours produced by standard traveling salesman heuristics.

The following problem arose in the planning of optical communications networks which use bidirectional SONET rings. Traffic demands d i,j are given for each pair of nodes in an n-node ring; each demand must be routed one of the two possible ways around the ring. The object is to minimize the maximum load on the cycle, where the load of an edge is the sum of the demands routed through that edge. We provide a fast, simple algorithm which achieves a load that is guaranteed to exceed the optimum by at most 3/2 times the maximum demand, and that performs even better in practice. En route we prove the following curious lemma: for any x 1 ,..., x n in [0,1] there exist y 1 ,..., y n such that for each k, $|y_k|=x_k$ and $$ \left| \sum_{i=1}^k y_i - \sum_{i=k+1}^n y_i \right| \le 2. $$

We give a polynomial-time algorithm for the following problem of P61ya.Given an n x n O-1 matrix, either find a matrix obtained from it by changing some of the 1's to -1's in such a way that the determinant of the new matrix equals the permanent of the old one, or determine that no such matrix exists.This is equivalent to finding Pfafiian orientations of bipartite graphs and to the even circuit problem for directed graphs.The aigorithm is based on a structural characterization of bipartite graphs that admit a Pfaffian orientation.-

Article Free Access Share on Efficiently four-coloring planar graphs Authors: Neil Robertson Department of Mathematics, The Ohio State University, Columbus, Ohio Department of Mathematics, The Ohio State University, Columbus, OhioView Profile , Daniel P. Sanders Department of Mathematics, The Ohio State University, Columbus, Ohio Department of Mathematics, The Ohio State University, Columbus, OhioView Profile , Paul Seymour Bellcore, 445 South Street, Morristown, New Jersey Bellcore, 445 South Street, Morristown, New JerseyView Profile , Robin Thomas School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia School of Mathematics, Georgia Institute of Technology, Atlanta, GeorgiaView Profile Authors Info & Claims STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of ComputingJuly 1996 Pages 571–575https://doi.org/10.1145/237814.238005Published:01 July 1996Publication History 63citation2,172DownloadsMetricsTotal Citations63Total Downloads2,172Last 12 Months487Last 6 weeks60 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In the multiterminal cut problem one is given an edge-weighted graph and a subset of the vertices called terminals, and is asked for a minimum weight set of edges that separates each terminal from all the others. When the number k of terminals is two, this is simply the mincut, max-flow problem, and can be solved in polynomial time. It is shown that the problem becomes NP-hard as soon as $k = 3$, but can be solved in polynomial time for planar graphs for any fixed k. The planar problem is NP-hard, however, if k is not fixed. A simple approximation algorithm for arbitrary graphs that is guaranteed to come within a factor of ${{2 - 2} / k}$ of the optimal cut weight is also described.

The authors give a short proof of a theorem of Lipton and Tarjan, that, for every planar graph with $n > 0$ vertices, there is a partition $( A,B,C )$ of its vertex set such that $|A|,|B| < \frac{2}{3}n,|C| \leq 2( 2n )^{1/2} $, and no vertex in A is adjacent to any vertex in B Secondly, they apply the same technique more carefully to deduce that, in fact, such a partition $( A,B,C )$ exists with $|A|,|B| < \frac{2}{3}n$, and $|C| \leq \frac{3}{2}( 2n )^{1/2} $ ; this improves the best previously known result. An analogous result holds when the vertices or edges are weighted.

In the Multiway Cut problem we are given an edge-weighted graph and a subset of the vertices called terminals, and asked for a minimum weight set of edges that separates each terminal from all the others. When the number k of terminals is two, this is simply the min-cut, max-flow problem, and can be solved in polynomial time. We show that the problem becomes NP-hard as soon as k = 3, but can be solved in polynomial time for planar graphs for any fixed k. The planar problem is NP-hard, however, if k is not fixed. We also describe a simple approximation algorithm for arbitrary graphs that is guaranteed to come within a factor of 2–2/k of the optimal cut weight.

Let $D = ( V,A )$ be a directed planar graph, let $( r_1 ,s_1 ), \cdots , ( r_k ,s_k )$ be pairs of vertices on the boundary of the unbounded face, let $A_1 , \cdots ,A_k $ be subsets of A, and let H be a collection of unordered pairs from $\{ 1, \cdots ,k \}$. Given are necessary and sufficient conditions for the existence of a directed $r_i - s_i $ path $P_i $ in $( V,A_i )$ (for $i = 1, \cdots ,k$), such that $P_i $ and $P_j $ are vertex-disjoint whenever $\{ i, j \} \in H$.

corresponds to G in time 0(n3/2).We also describe Let G be an n-vertex graph with nonnegative weights whose sum is 1 assigned to its vertices, and with no minor isomorphic to a given h-vertex graph H.We prove that there is a set X of no more than h3/2nl/2 vertices of G whose deletion creates a graph in which the total weight of every connected component is at most 1/2.This extends significantly a well-known theorem of Lipton and Tarjan for planar graphs.We exhibit an algorithm which finds, given an n-vertex graph G with weights as above and an h-vertex graph H, either such a set X or a minor of G isomorphic to H.The algorithm runs in time O(hl/2nl/2m), where m is the number of edges of G plus the number of its vertices.Our results supply extensions of the many known applications of the Lipton-Tarjan separator theorem from the class of planar graphs (or that of graphs with bounded genus) to any class of graphs with an excluded minor.For example, it follows that for any fixed graph H, given a graph G with n vertices and with no H-minor one can approximate the size of the maximum independent set of G up to a relative error of 1/~/l-b-~ in polynomial time, find that size exactly and find the chromatic number of G in time 2 °(¢'~-) and solve any sparse system of n linear equations in n unknowns whose sparsity structure Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery.To copy otherwise, or to republish, requires a fee and/or specific

In this paper we describe a general technique which can be used to solve an old problem in analyzing self-organizing sequential search. We prove that the average time required for the move-to-front heuristic is no more than p/2 times that of the optimal order and this bound is best possible. Hilbert's inequalities will be used to derive large classes of inequalities some of which can be applied to obtain tight worst-case bounds for several self-organizing heuristics.

Abstract Suppose that s1, s2, s3, s4 are vertices of a graph, that each edge has a real‐valued capacity, and qii(1 ⩽ i < j ⩽ 4) are six demands. There exist flows from si to sj of value qij(1 ⩽ i < j ⩽ 4), such that the total flow through each edge does not exceed its capacity, if and only if the obvious connectivity requirements are satisfied. This result extends Hu's 2‐commodity flow theorem.