Graph-Theoretic Concepts in Computer Science

Frontmatter

Structures and Hyperstructures in Metabolic Networks

Introduction

There has been an increasing interest by the computational biology community in the study of chemical reactions within cells; indeed cells can be considered as chemical factories that manufacture the various products of the cells and the metabolic capacities of an organism are directly defined by the set of its possible biochemical reactions. The links between reactions and compounds (or metabolites) that are used and produced by such reactions constitute the metabolic network an organism.

Alberto Marchetti-Spaccamela

Important Separators and Parameterized Algorithms

Abstract

The notion of “important separators” and bounding the number of such separators turned out to be a very useful technique in the design of fixed-parameter tractable algorithms for multi(way) cut problems. For example, the recent breakthrough result of Chen et al.[3] on the Directed Feedback Vertex Set problem can be also explained using this notion. In my talk, I will overview combinatorial and algorithmic results that can be obtained by studying such separators.

Dániel Marx

Split Clique Graph Complexity

Abstract

A complete set of a graph G is a subset of vertices inducing a complete subgraph. A clique is a maximal complete set. Denote by \({ \mathcal{C}}(G)\) the clique family of G. The clique graph of G, denoted by K(G), is the intersection graph of \( {\mathcal{C}}(G)\). Say that G is a clique graph if there exists a graph H such that G = K(H). The clique graph recognition problem, a long-standing open question posed in 1971, asks whether a given graph is a clique graph and it was recently proved to be NP-complete even for a graph G with maximum degree 14 and maximum clique size 12. Hence, if P≠NP, the study of graph classes where the problem can be proved to be polynomial, or of more restricted graph classes where the problem remains NP-complete is justified. We present a proof that given a split graph G = (V,E) with partition (K,S) for V, where K is a complete set and S is a stable set, deciding whether there is a graph H such that G is the clique graph of H is NP-complete. As a byproduct, we prove that a problem about the Helly property on a family of sets is NP-complete. Our result is optimum in the sense that each vertex of the independent set of our split instance has degree at most 3, whereas when each vertex of the independent set has degree at most 2 the problem is polynomial, since it is reduced to check whether the clique family of the graph satisfies the Helly property. Additionally, we show three split graph subclasses for which the problem is polynomially solvable: the subclass where each vertex of S has a private neighbor, the subclass where |S| ≤ 3, and the subclass where |K| ≤ 4.

Liliana Alcón, Luerbio Faria, Celina M. H. de Figueiredo, Marisa Gutierrez

On Searching for Small Kochen-Specker Vector Systems

Abstract

Kochen-Specker (KS) vector systems are sets of vectors in ℝ³ with the property that it is impossible to assign 0s and 1s to the vectors in such a way that no two orthogonal vectors are assigned 0 and no three mutually orthogonal vectors are assigned 1. The existence of such sets forms the basis of the Kochen-Specker and Free Will theorems. Currently, the smallest known KS vector system contains 31 vectors. In this paper, we establish a lower bound of 18 on the size of any KS vector system. This requires us to consider a mix of graph-theoretic and topological embedding problems, which we investigate both from theoretical and practical angles. We propose several algorithms to tackle these problems and report on extensive experiments. At the time of writing, a large gap remains between the best lower and upper bounds for the minimum size of KS vector systems.

Felix Arends, Joël Ouaknine, Charles W. Wampler

Characterizations of Deque and Queue Graphs

Abstract

In graph layouts the vertices of a graph are processed according to a linear order and the edges correspond to items in a data structure inserted and removed at their end vertices. Graph layouts characterize interesting classes of planar graphs: A graph G is a stack graph if and only if G is outerplanar, and a graph is a 2-stack graph if and only if it is a subgraph of a planar graph with a Hamiltonian cycle [2]. Heath and Rosenberg [12] characterized all queue graphs as the arched leveled-planar graphs. In [1], we have introduced linear cylindric drawings (LCDs) to study graph layouts in the double-ended queue (deque) and have shown that G is a deque graph if and only if it permits a plane LCD.

In this paper, we show that a graph is a deque graph if and only if it is the subgraph of a planar graph with a Hamiltonian path. In consequence, we obtain that the dual of an embedded queue graph contains a Eulerian path. We also turn to the respective decision problem of deque graphs and show that it is \(\mathcal{NP}\)-hard by proving that the Hamiltonian path problem in maximal planar graphs is \(\mathcal{NP}\)-hard. Heath and Rosenberg state [12] that queue graphs are “almost” proper leveled-planar. We show that bipartiteness captures this “almost”: A graph is proper leveled-planar if and only if it is a bipartite queue graph.

Christopher Auer, Andreas Gleißner

Graph Classes with Structured Neighborhoods and Algorithmic Applications

Abstract

Boolean-width is a recently introduced graph width parameter. If a boolean decomposition of width w is given, several NP-complete problems, such as Maximum Weight Independent Set, k-Coloring and Minimum Weight Dominating Set are solvable in O ^*(2 ^O(w)) time [6]. In this paper we study graph classes for which we can compute a decomposition of logarithmic boolean-width in polynomial time. Since 2 ^O(logn) = n ^O(1), this gives polynomial time algorithms for the above problems on these graph classes. For interval graphs we show how to construct decompositions where neighborhoods of vertex subsets are nested. We generalize this idea to neighborhoods that can be represented by a constant number of vertices. Moreover we show that these decompositions have boolean-width O(logn). Graph classes having such decompositions include circular arc graphs, circular k-trapezoid graphs, convex graphs, Dilworth k graphs, k-polygon graphs and complements of k-degenerate graphs. Combined with results in [1,5], this implies that a large class of vertex subset and vertex partitioning problems can be solved in polynomial time on these graph classes.

Rémy Belmonte, Martin Vatshelle

Exact Algorithms for Kayles

Abstract

In the game of Kayles, two players select alternatingly a vertex from a given graph G, but may never choose a vertex that is adjacent or equal to an already chosen vertex. The last player that can select a vertex wins the game. In this paper, we give an exact algorithm to determine which player has a winning strategy in this game. To analyse the running time of the algorithm, we introduce the notion of a K-set: a nonempty set of vertices W ⊆ V is a K-set in a graph G = (V,E), if G[W] is connected and there exists an independent set X such that W = V − N[X], where N[X] is the union of X and the set of all vertices adjacent to at least one vertex of X. The running time of the algorithm is bounded by a polynomial factor times the number of K-sets in G. We show that the number of K-sets in a graph with n vertices is bounded by O(1.6052 ⁿ ), and thus we have an algorithm for Kayles with running time O(1.6052 ⁿ ). We also show that the number of K-sets in a tree is bounded by n ·3 ^n/3 and thus Kayles can be solved on trees in O(1.4423 ⁿ ) time. We show that apart from a polynomial factor, the number of K-sets in a tree is sharp.

Hans L. Bodlaender, Dieter Kratsch

The Cinderella Game on Holes and Anti-holes

Abstract

We investigate a two-player game on graphs, where one player (Cinderella) wants to keep the behavior of an underlying water-bucket system stable whereas the other player (the wicked Stepmother) wants to cause overflows. The bucket number of a graph G is the smallest possible bucket size with which Cinderella can win the game.

We determine the bucket numbers of all perfect graphs, and we also derive results on the bucket numbers of certain non-perfect graphs. In particular, we analyze the game on holes and (partially) on anti-holes for the cases where Cinderella sticks to a simple greedy strategy.

Marijke H. L. Bodlaender, Cor A. J. Hurkens, Gerhard J. Woeginger

On the Complexity of Planar Covering of Small Graphs

Abstract

The problem Cover(H) asks whether an input graph G covers a fixed graph H (i.e., whether there exists a homomorphism G → H which locally preserves the structure of the graphs). Complexity of this problem has been intensively studied. In this paper, we consider the problem PlanarCover(H) which restricts the input graph G to be planar.

PlanarCover(H) is polynomially solvable if Cover(H) belongs to P, and it is even trivially solvable if H has no planar cover. Thus the interesting cases are when H admits a planar cover, but Cover(H) is NP-complete. This also relates the problem to the long-standing Negami Conjecture which aims to describe all graphs having a planar cover. Kratochvíl asked whether there are non-trivial graphs for which Cover(H) is NP-complete but Planarcover(H) belongs to P.

We examine the first nontrivial cases of graphs H for which Cover(H) is NP-complete and which admit a planar cover. We prove NP-completeness of Planarcover(H) in these cases.

Ondřej Bílka, Jozef Jirásek, Pavel Klavík, Martin Tancer, Jan Volec

Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses

Abstract

In a modification of the classical model of housing market which includes duplicate houses, economic equilibrium might not exist. As a measure of approximation the value sat \(\mathcal(M)\) was proposed: the maximum number of satisfied agents in the market \(\mathcal(M)\), where an agent is said to be satisfied if, given a set of prices, he gets a most preferred house in his budget set. Clearly, market \(\mathcal(M)\) admits an economic equilibrium if sat(M) is equal to the total number n of agents, but sat\(\mathcal(M)\) is NP-hard to compute.

In this paper we give a 2-approximation algorithm for sat\(\mathcal(M)\) in the case of trichotomic preferences. On the other hand, we prove that sat\(\mathcal(M)\) is hard to approximate within a factor smaller than 21/19, even if each house type is used for at most two houses. If the preferences are not required to be trichotomic, the problem is hard to approximate within a factor smaller than 1.2. We also prove that, provided the Unique Games Conjecture is true, approximation is hard within a factor 1.25 for trichotomic preferences, and within a factor 1.5 in the case of general preferences.

Katarína Cechlárová, Eva Jelínková

Planarization and Acyclic Colorings of Subcubic Claw-Free Graphs

Abstract

We study methods of planarizing and acyclically coloring claw-free subcubic graphs. We give a polynomial-time algorithm that, given such a graph G, produces an independent set Q of at most n/6 vertices whose removal from G leaves an induced planar subgraph P (in fact, P has treewidth at most four). We further show the stronger result that in polynomial-time a set of at most n/6 edges can be identified whose removal leaves a planar subgraph (of treewidth at most four). From an approximability point of view, we show that our results imply 6/5- and 9/8-approximation algorithms, respectively, for the (NP-hard) problems of finding a maximum induced planar subgraph and a maximum planar subgraph of a subcubic claw-free graph, respectively.

Regarding acyclic colorings, we give a polynomial-time algorithm that finds an optimal acyclic vertex coloring of a subcubic claw-free graph. To our knowledge, this represents the largest known subclass of subcubic graphs such that an optimal acyclic vertex coloring can be found in polynomial-time. We show that this bound is tight by proving that the problem is NP-hard for cubic line graphs (and therefore, claw-free graphs) of maximum degree d ≥ 4. An interesting corollary to the algorithm that we present is that there are exactly three subcubic claw-free graphs that require four colors to be acyclically colored. For all other such graphs, three colors suffice.

Christine Cheng, Eric McDermid, Ichiro Suzuki

List Coloring in the Absence of a Linear Forest

Abstract

The k-Coloring problem is to decide whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. The List k -Coloring problem requires in addition that every vertex u must receive a color from some given set L(u) ⊆ {1,…,k}. Let P _n denote the path on n vertices, and G + H and rH the disjoint union of two graphs G and H and r copies of H, respectively. For any two fixed integers k and r, we show that List k -Coloring can be solved in polynomial time for graphs with no induced rP ₁ + P ₅, hereby extending the result of Hoàng, Kamiński, Lozin, Sawada and Shu for graphs with no induced P ₅. Our result is tight; we prove that for any graph H that is a supergraph of P ₁ + P ₅ with at least 5 edges, already List 5-Coloring is NP-complete for graphs with no induced H. We also show that List k -Coloring is fixed parameter tractable in k + r on graphs with no induced rP ₁ + P ₂, and that k-Coloring restricted to such graphs allows a polynomial kernel when parameterized by k. Finally, we show that List k -Coloring is fixed parameter tractable in k for graphs with no induced P ₁ + P ₃.

Jean-François Couturier, Petr A. Golovach, Dieter Kratsch, Daniël Paulusma

Parameterized Complexity of Eulerian Deletion Problems

Abstract

We study a family of problems where the goal is to make a graph Eulerian by a minimum number of deletions. We completely classify the parameterized complexity of various versions: undirected or directed graphs, vertex or edge deletions, with or without the requirement of connectivity, etc. Of particular interest is a randomized FPT algorithm for making an undirected graph Eulerian by deleting the minimum number of edges.

Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Ildikó Schlotter

Restricted Cuts for Bisections in Solid Grids: A Proof via Polygons

Abstract

The graph bisection problem asks to partition the n vertices of a graph into two sets of equal size so that the number of edges across the cut is minimum. We study finite, connected subgraphs of the infinite two-dimensional grid that do not have holes. Since bisection is an intricate problem, our interest is in the tradeoff between runtime and solution quality that we get by limiting ourselves to a special type of cut, namely cuts with at most one bend each (corner cuts). We prove that optimum corner cuts get us arbitrarily close to equal sized parts, and that this limitation makes us lose only a constant factor in the quality of the solution. We obtain our result by a thorough study of cuts in polygons and the effect of limiting these to corner cuts.

Andreas Emil Feldmann, Shantanu Das, Peter Widmayer

Maximum Independent Set in 2-Direction Outersegment Graphs

Abstract

An outersegment graph is the intersection graph of line-segments lying inside a disk and having one end-point on the boundary of the disk. We present a polynomial-time algorithm for the problem of computing a maximum independent set in outersegment graphs where every segment is either horizontally or vertically aligned. We assume that a geometric representation of the graph is given as input.

Holger Flier, Matúš Mihalák, Peter Widmayer, Anna Zych

Complexity of Splits Reconstruction for Low-Degree Trees

Abstract

Given a vertex-weighted tree T, the split of an edge xy in T is min{s _x , s _y } where s _x (respectively, s _y ) is the sum of all weights of vertices that are closer to x than to y (respectively, closer to y than to x) in T. Given a set of weighted vertices V and a multiset of splits S, we consider the problem of constructing a tree on V whose splits correspond to S. The problem is known to be NP-complete, even when all vertices have unit weight and the maximum vertex degree of T is required to be no more than 4. We show that

• the problem is strongly NP-complete when T is required to be a path. For this variant we exhibit an algorithm that runs in polynomial time when the number of distinct vertex weights is constant.We also show that
• the problem is NP-complete when all vertices have unit weight and the maximum degree of T is required to be no more than 3, and
• it remains NP-complete when all vertices have unit weight and T is required to be a caterpillar with unbounded hair length and maximum degree at most 3.

Finally, we shortly discuss the problem when the vertex weights are not given but can be freely chosen by an algorithm.

The considered problem is related to building libraries of chemical compounds used for drug design and discovery. In these inverse problems, the goal is to generate chemical compounds having desired structural properties, as there is a strong correlation between structural properties, such as the Wiener index, which is closely connected to the considered problem, and biological activity.

Serge Gaspers, Mathieu Liedloff, Maya Stein, Karol Suchan

Empires Make Cartography Hard: The Complexity of the Empire Colouring Problem

Abstract

We study the empire colouring problem (as defined by Percy Heawood in 1890) for maps containing empires formed by exactly r > 1 countries each. We prove that the problem can be solved in polynomial time using s colours on maps whose underlying adjacency graph has no induced subgraph of average degree larger than s/r. However, if s ≥ 3, the problem is NP-hard for forests of paths of arbitrary lengths (if s < r) for trees (if r ≥ 2 and s < 2r) and arbitrary planar graphs (if s < 7 for r = 2, and s < 6r − 3, for r ≥ 3). The result for trees shows a perfect dichotomy (the problem is NP-hard if 3 ≤ s ≤ 2r − 1 and polynomial time solvable otherwise). The one for planar graphs proves the NP-hardness of colouring with less than 7 colours graphs of thickness two and less than 6r − 3 colours graphs of thickness r ≥ 3.

Andrew R. A. McGrae, Michele Zito

Alternation Graphs

Abstract

A graph G = (V,E) is an alternation graph if there exists a word W over the alphabet V such that letters x and y alternate in W if and only if (x,y) ∈ E for each x ≠ y.

In this paper we give an effective characterization of alternation graphs in terms of orientations. Namely, we show that a graph is an alternation graph if and only if it admits a semi-transitive orientation defined in the paper. This allows us to prove a number of results about alternation graphs, in particular showing that the recognition problem is in NP, and that alternation graphs include all 3-colorable graphs.

We also explore bounds on the size of the word representation of the graph. A graph G is a k-alternation graph if it is represented by a word in which each letter occurs exactly k times; the alternation number of G is the minimum k for which G is a k-alternation graph. We show that the alternation number is always at most n, while there exist graphs for which it is n/2.

Magnús M. Halldórsson, Sergey Kitaev, Artem Pyatkin

Improved Bounds for Minimum Fault-Tolerant Gossip Graphs

Abstract

A k-fault-tolerant gossip graph is a (multiple) graph whose edges are linearly ordered such that for any ordered pair of vertices u and v, there are k + 1 edge-disjoint ascending paths from u to v. Let τ(n,k) denote the minimum number of edges in a k-fault-tolerant gossip graph with n vertices. In this paper, we present upper and lower bounds on τ(n,k) which improve the previously known bounds. In particular, from our upper bounds, it follows that \(\tau(n,k) \leq \frac{nk}{2} + O(n\log{n})\). Previously, it has been shown that this upper bound holds only for the case that n is a power of two.

Toru Hasunuma, Hiroshi Nagamochi

Parameterized Two-Player Nash Equilibrium

Abstract

We study the problem of computing Nash equilibria in a two-player normal form (bimatrix) game from the perspective of parameterized complexity. Recent results proved hardness for a number of variants, when parameterized by the support size. We complement those results, by identifying three cases in which the problem becomes fixed-parameter tractable. Our results are based on a graph-theoretic representation of a bimatrix game, and on applying graph-theoretic tools on this representation.

Danny Hermelin, Chien-Chung Huang, Stefan Kratsch, Magnus Wahlström

Counting Independent Sets in Claw-Free Graphs

Abstract

In this paper we give an algorithm for counting the number of all independent sets in a claw-free graph which works in time O ^*(1.08352 ⁿ ) for graphs with no vertices of degree larger than 3 and O ^*(1.23544 ⁿ ) for arbitrary claw-free graphs, where n is the number of vertices in the instance graph.

Konstanty Junosza-Szaniawski, Zbigniew Lonc, Michał Tuczyński

On the Independence Number of Graphs with Maximum Degree 3

Abstract

Let G be an undirected graph with maximum degree at most 3 such that G does not contain any of the three graphs shown in Figure [1] as a subgraph. We prove that the independence number of G is at least n(G)/3 + nt(G)/42, where n(G) is the number of vertices in G and nt(G) is the number of nontriangle vertices in G. This bound is tight as implied by the well-known tight lower bound of 5n(G)/14 on the independence number of triangle-free graphs of maximum degree at most 3. We then proceed to show some algorithmic applications of the aforementioned combinatorial result to the area of parameterized complexity. We present a linear-time kernelization algorithm for the independent set problem on graphs with maximum degree at most 3 that computes a kernel of size at most 140 k/47 < 3k, where k is the given parameter. This improves the known 3k upper bound on the kernel size for the problem, and implies a lower bound of 140k/93 on the kernel size for the vertex cover problem on graphs with maximum degree at most 3.

Iyad A. Kanj, Fenghui Zhang

On Computing an Optimal Semi-matching

Abstract

The problem of finding an optimal semi-matching is a generalization of the problem of finding classical matching in bipartite graphs. A semi-matching in a bipartite graph G = (U, V, E) with n vertices and m edges is a set of edges M ⊆ E, such that each vertex in U is incident to at most one edge in M. An optimal semi-matching is a semi-matching with degM(u) = 1 for all u ∈ U and the minimal value of \(\sum_{v \in V} \frac{deg_M(v).(deg_M(v)+1)}2\). We propose a schema that allows a reduction of the studied problem to a variant of the maximum bounded-degree semi-matching problem. The proposed schema yields to two algorithms for computing an optimal semi-matching. The first one runs in time \(O(\sqrt{n} \cdot m \cdot \log{n})\) that is the same as the time complexity of the currently best known algorithm. However, our algorithm uses a different approach that enables some improvements in practice (e.g. parallelization, faster algorithms for special graph classes). The second one is randomized and it computes an optimal semi-matching with high probability in O(n ^ω ·log^1 + o(1) n), where ω is the exponent of the best known matrix multiplication algorithm. Since ω ≤ 2.38, this algorithms breaks through O(n ^2.5) barrier for dense graphs.

František Galčík, Ján Katrenič, Gabriel Semanišin

Planar k-Path in Subexponential Time and Polynomial Space

Abstract

In the k-Path problem we are given an n-vertex graph G together with an integer k and asked whether G contains a path of length k as a subgraph. We give the first subexponential time, polynomial space parameterized algorithm for k-Path on planar graphs, and more generally, on H-minor-free graphs. The running time of our algorithm is \(O(2^{O(\sqrt{k}\log^2 k)}n^{O(1)})\).

Daniel Lokshtanov, Matthias Mnich, Saket Saurabh

Approximability of the Path-Distance-Width for AT-free Graphs

Abstract

The path-distance-width of a graph measures how close the graph is to a path. We consider the problem of determining the path-distance-width for graphs with chain-like structures such as k-cocomparability graphs, AT-free graphs, and interval graphs. We first show that the problem is NP-hard even for a very restricted subclass of AT-free graphs. Next we present simple approximation algorithms with constant approximation ratios for graphs with chain-like structures. For instance, our algorithm for AT-free graphs has approximation factor 3 and runs in linear time. We also show that the problem is solvable in polynomial time for the class of cochain graphs, which is a subclass of the class of proper interval graphs.

Yota Otachi, Toshiki Saitoh, Katsuhisa Yamanaka, Shuji Kijima, Yoshio Okamoto, Hirotaka Ono, Yushi Uno, Koichi Yamazaki

Hanani-Tutte and Monotone Drawings

Abstract

A drawing of a graph is x-monotone if every edge intersects every vertical line at most once and every vertical line contains at most one vertex. Pach and Tóth showed that if a graph has an x-monotone drawing in which every pair of edges crosses an even number of times, then the graph has an x-monotone embedding in which the x-coordinates of all vertices are unchanged. We give a new proof of this result and strengthen it by showing that the conclusion remains true even if adjacent edges are allowed to cross oddly. This answers a question posed by Pach and Tóth. Moreover, we show that an extension of this result for graphs with non-adjacent pairs of edges crossing oddly fails even if there exists only one such pair in a graph.

Radoslav Fulek, Michael J. Pelsmajer, Marcus Schaefer, Daniel Štefankovič

On Collinear Sets in Straight-Line Drawings

Abstract

We consider straight-line drawings of a planar graph G with possible edge crossings. The untangling problem is to eliminate all edge crossings by moving as few vertices as possible to new positions. Let fix G denote the maximum number of vertices that can be left fixed in the worst case among all drawings of G. In the allocation problem, we are given a planar graph G on n vertices together with an n-point set X in the plane and have to draw G without edge crossings so that as many vertices as possible are located in X. Let fit G denote the maximum number of points fitting this purpose in the worst case among all n-point sets X. As fix G ≤ fit G, we are interested in upper bounds for the latter and lower bounds for the former parameter.

For any ε > 0, we construct an infinite sequence of graphs with fit G = O(n ^σ + ε ), where σ < 0.99 is a known graph-theoretic constant, namely the shortness exponent for the class of cubic polyhedral graphs. On the other hand, we prove that \(fix G\ge\sqrt{n/30}\) for any graph G of tree-width at most 2. This extends the lower bound obtained by Goaoc et al. [Discrete and Computational Geometry 42:542–569 (2009)] for outerplanar graphs. Our results are based on estimating the maximum number of vertices that can be put on a line in a straight-line crossing-free drawing of a given planar graph.

Alexander Ravsky, Oleg Verbitsky

From Few Components to an Eulerian Graph by Adding Arcs

Abstract

Eulerian Extension (EE) is the problem to make an arc-weighted directed multigraph Eulerian by adding arcs of minimum total cost. EE is NP-hard and has been shown fixed-parameter tractable with respect to the number of arc additions. Complementing this result, on the way to answering an open question, we show that EE is fixed-parameter tractable with respect to the combined parameter “number of connected components in the underlying undirected multigraph” and “sum of indeg(v) - outdeg(v) over all vertices v in the input multigraph where this value is positive.” Moreover, we show that EE is unlikely to admit a polynomial-size problem kernel for this parameter combination and for the parameter “number of arc additions”.

Manuel Sorge, René van Bevern, Rolf Niedermeier, Mathias Weller

Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid

Abstract

We investigate graphs that can be represented as vertex intersections of horizontal and vertical paths in a grid, known as B ₀-VPG graphs. Recognizing these graphs is an NP-hard problem. In light of this, we focus on their subclasses. In the paper, we describe polynomial time algorithms for recognizing chordal B ₀-VPG graphs, and for recognizing B ₀-VPG graphs that have a representation on a grid with 2 rows.

Steven Chaplick, Elad Cohen, Juraj Stacho

A Polynomial Time Algorithm for Bounded Directed Pathwidth

Abstract

We give a polynomial time algorithm for bounded directed pathwidth. Given a positive integer k and a digraph G with n vertices and m edges, it runs in O(m n ^k + 1) time and constructs a directed path-decomposition of G of width at most k if one exists and otherwise reports the non-existence.

Hisao Tamaki

Backmatter