Graph-Theoretic Concepts in Computer Science

Frontmatter

Subexponential Algorithms for Variants of Homomorphism Problem in String Graphs

Abstract

We consider the complexity of finding weighted homomorphisms from intersection graphs of curves (string graphs) with n vertices to a fixed graph H. We provide a complete dichotomy for the problem: if H has no two vertices sharing two common neighbors, then the problem can be solved in time \(2^{O(n^{2/3} \log n)}\), otherwise there is no algorithm working in time \(2^{o(n)}\), even in intersection graphs of segments, unless the ETH fails. This generalizes several known results concerning the complexity of computational problems in geometric intersection graphs.

Then we consider two variants of graph homomorphism problem, called locally injective homomorphism and locally bijective homomorphism, where we require the homomorphism to be injective or bijective on the neighborhood of each vertex. We show that for each target graph H, both problems can always be solved in time \(2^{O(\sqrt{n} \log n)}\) in string graphs. For the locally surjective homomorphism, defined analogously, the situation seems more complicated. We show the dichotomy theorem for simple connected graphs H with maximum degree 2. If H is isomorphic to \(P_3\) or \(C_4\), then the existence of a locally surjective homomorphism from a string graph with n vertices to H can be decided in time \(2^{O(n^{2/3} \log ^{3/2} n)}\), otherwise, assuming ETH, the problem cannot be solved in time \(2^{o(n)}\). As a byproduct, we obtain results concerning the complexity of variants of homomorphism problem in \(P_t\)-free graphs – in particular, the weighted homomorphism dichotomy, analogous to the one for string graphs.

Karolina Okrasa, Paweł Rzążewski

The 4-Steiner Root Problem

Abstract

The \(k^{th}\)-power of a graph G is obtained by adding an edge between every two distinct vertices at a distance \(\le k\) in G. We call G a k -Steiner power if it is an induced subgraph of the \(k^{th}\)-power of some tree \(T_{}\). In particular, G is a k -leaf power if all vertices in V(G) are leaf-nodes of \(T_{}\). Our main contribution is a polynomial-time recognition algorithm of 4-Steiner powers, thereby extending the decade-year-old results of (Lin, Kearney and Jiang, ISAAC’00) for \(k=1,2\) and (Chang and Ko, WG’07) for \(k=3\). As a byproduct, we give the first known polynomial-time recognition algorithm for 6-leaf powers. Our work combines several new algorithmic ideas that help us overcome the previous limitations on the usual dynamic programming approach for these problems.

Guillaume Ducoffe

Hamiltonicity Below Dirac’s Condition

Abstract

Dirac’s theorem (1952) is a classical result of graph theory, stating that an n-vertex graph (\(n \ge 3\)) is Hamiltonian if every vertex has degree at least n/2. Both the value n/2 and the requirement for every vertex to have high degree are necessary for the theorem to hold.

In this work we give efficient algorithms for determining Hamiltonicity when either of the two conditions are relaxed. More precisely, we show that the Hamiltonian Cycle problem can be solved in time \(c^k \cdot n^{O(1)}\), for a fixed constant c, if at least \(n-k\) vertices have degree at least n/2, or if all vertices have degree at least \(n/2 - k\). The running time is, in both cases, asymptotically optimal, under the exponential-time hypothesis (ETH).

The results extend the range of tractability of the Hamiltonian Cycle problem, showing that it is fixed-parameter tractable when parameterized below a natural bound. In addition, for the first parameterization we show that a kernel with O(k) vertices can be found in polynomial time.

Bart M. P. Jansen, László Kozma, Jesper Nederlof

Maximum Independent Sets in Subcubic Graphs: New Results

Abstract

We consider the complexity of the classical Independent Set problem on classes of subcubic graphs characterized by a finite set of forbidden induced subgraphs. It is well-known that a necessary condition for Independent Set to be tractable in such a class (unless P = NP) is that the set of forbidden induced subgraphs includes a subdivided star \(S_{k,k,k}\), for some k. Here, \(S_{k,k,k}\) is the graph obtained by taking three paths of length k and identifying one of their endpoints.

It is an interesting open question whether this condition is also sufficient: is Independent Set tractable on all hereditary classes of subcubic graphs that exclude some \(S_{k,k,k}\)? A positive answer to this question would provide a complete classification of the complexity of Independent Set on all classes of subcubic graphs characterized by a finite set of forbidden induced subgraphs. The best currently known result of this type is tractability for \(S_{2,2,2}\)-free graphs. In this paper we generalize this result by showing that the problem remains tractable on \(S_{2,k,k}\)-free graphs, for any fixed k. Along the way, we show that subcubic Independent Set is tractable for graphs excluding a type of graph we call an “apple with a long stem”, generalizing known results for apple-free graphs.

Ararat Harutyunyan, Michael Lampis, Vadim Lozin, Jérôme Monnot

Cyclewidth and the Grid Theorem for Perfect Matching Width of Bipartite Graphs

Abstract

A connected graph G is called matching covered if every edge of G is contained in a perfect matching. Perfect matching width is a width parameter for matching covered graphs based on a branch decomposition. It was introduced by Norine and intended as a tool for the structural study of matching covered graphs, especially in the context of Pfaffian orientations. Norine conjectured that graphs of high perfect matching width contain a large grid as a matching minor, similar to the result on treewidth by Robertson and Seymour.

In this paper we obtain the first results on perfect matching width since its introduction. For the restricted case of bipartite graphs, we show that perfect matching width is equivalent to directed treewidth and thus, the Directed Grid Theorem by Kawarabayashi and Kreutzer for directed treewidth implies Norine’s conjecture.

Meike Hatzel, Roman Rabinovich, Sebastian Wiederrecht

Local Approximation of the Maximum Cut in Regular Graphs

Abstract

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and achieves an approximation ratio of at least \(\tfrac{1}{2}\) in average. When the graph is d-regular and triangle-free, a slightly better approximation ratio can be achieved with a randomized algorithm running in a single round. Here, we investigate the round complexity of deterministic distributed algorithms for MaxCut in regular graphs. We first prove that if G is d-regular, with d even and fixed, no deterministic algorithm running in a constant number of rounds can achieve a constant approximation ratio. We then give a simple one-round deterministic algorithm achieving an approximation ratio of \(\tfrac{1}{d}\) for d-regular graphs with d odd. We show that this is best possible in several ways, and in particular no deterministic algorithm with approximation ratio \(\tfrac{1}{d}+\epsilon \) (with \(\epsilon >0\)) can run in a constant number of rounds. We also prove results of a similar flavour for the MaxDiCut problem in regular oriented graphs, where we want to maximize the number of arcs oriented from the left part to the right part of the cut.

Étienne Bamas, Louis Esperet

Fixed-Parameter Tractability of Counting Small Minimum (S, T)-Cuts

Abstract

The parameterized complexity of counting minimum cuts stands as a natural question because Ball and Provan showed its #P-completeness. For any undirected graph \(G=(V,E)\) and two disjoint sets of its vertices S, T, we design a fixed-parameter tractable algorithm which counts minimum edge (S, T)-cuts parameterized by their size p. Our algorithm operates on a transformed graph instance. This transformation, called drainage, reveals a collection of at most \(n=\left| V \right| \) successive minimum (S, T)-cuts \(Z_i\). We prove that any minimum (S, T)-cut X contains edges of at least one cut \(Z_i\). This observation, together with Menger’s theorem, allows us to build the algorithm counting all minimum (S, T)-cuts with running time \(2^{O(p^2)}n^{O(1)}\). Initially dedicated to counting minimum cuts, it can be modified to obtain an FPT sampling of minimum edge (S, T)-cuts.

Pierre Bergé, Benjamin Mouscadet, Arpad Rimmel, Joanna Tomasik

Fast Breadth-First Search in Still Less Space

Abstract

It is shown that a breadth-first search in a directed or undirected graph with n vertices and m edges can be carried out in \(O(n+m)\) time with \(n\log _2 3+O((\log n)^2)\) bits of working memory.

Torben Hagerup

A Turing Kernelization Dichotomy for Structural Parameterizations of -Minor-Free Deletion

Abstract

For a fixed finite family of graphs \(\mathcal {F}\), the \(\mathcal {F}\)-Minor-Free Deletion problem takes as input a graph G and an integer \(\ell \) and asks whether there exists a set \(X \subseteq V(G)\) of size at most \(\ell \) such that \(G-X\) is \(\mathcal {F}\)-minor-free. For \(\mathcal {F} =\{K_2\}\) and \(\mathcal {F} =\{K_3\}\) this encodes Vertex Cover and Feedback Vertex Set respectively. When parameterized by the feedback vertex number of G these two problems are known to admit a polynomial kernelization. Such a polynomial kernelization also exists for any \(\mathcal {F}\) containing a planar graph but no forests.

In this paper we show that \(\mathcal {F}\)-Minor-Free Deletion parameterized by the feedback vertex number is \(\mathsf {MK[2]}\)-hard for \(\mathcal {F} = \{P_3\}\). This rules out the existence of a polynomial kernel assuming \(\mathsf {NP}\not \subseteq \mathsf {coNP/poly}\), and also gives evidence that the problem does not admit a polynomial Turing kernel. Our hardness result generalizes to any \(\mathcal {F}\) not containing a \(P_3\)-subgraph-free graph, using as parameter the vertex-deletion distance to treewidth \(\min {{\,\mathrm{tw}\,}} (\mathcal {F})\), where \(\min {{\,\mathrm{tw}\,}} (\mathcal {F})\) denotes the minimum treewidth of the graphs in \(\mathcal {F}\). For the other case, where \(\mathcal {F}\) contains a \(P_3\)-subgraph-free graph, we present a polynomial Turing kernelization. Our results extend to \(\mathcal {F}\)-Subgraph-Free Deletion.

Huib Donkers, Bart M. P. Jansen

Flip Distances Between Graph Orientations

Abstract

Flip graphs are a ubiquitous class of graphs, which encode relations on a set of combinatorial objects induced by elementary, local changes. A natural computational problem to consider is the flip distance: Given two objects, what is the minimum number of flips needed to transform one into the other?

We consider flip graphs on so-called \(\alpha \)-orientations of a graph G, in which every vertex v has a specified outdegree \(\alpha (v)\), and a flip consists of reversing all edges of a directed cycle. We prove that deciding whether the flip distance between two \(\alpha \)-orientations of a planar graph G is at most 2 is NP-complete. This also holds in the special case of plane perfect matchings, where flips involve alternating cycles. We also consider the dual question of the flip distance between graph orientations in which every cycle has a specified number of forward edges, and a flip is the reversal of all edges in a minimal directed cut. In general, the problem remains hard, but if we only change sinks into sources, or vice-versa, then the problem can be solved in polynomial time.

Oswin Aichholzer, Jean Cardinal, Tony Huynh, Kolja Knauer, Torsten Mütze, Raphael Steiner, Birgit Vogtenhuber

Graph Functionality

Abstract

In the present paper, we introduce the notion of graph functionality, which generalizes simultaneously several other graph parameters, such as degeneracy or clique-width, in the sense that bounded degeneracy or bounded clique-width imply bounded functionality. Moreover, we show that this generalization is proper by revealing classes of graphs of unbounded degeneracy and clique-width, where functionality is bounded by a constant. We also prove that bounded functionality implies bounded VC-dimension, i.e. graphs of bounded VC-dimension extend graphs of bounded functionality, and this extension also is proper.

Bogdan Alecu, Aistis Atminas, Vadim Lozin

On Happy Colorings, Cuts, and Structural Parameterizations

Abstract

We study the Maximum Happy Vertices and Maximum Happy Edges problems. The former problem is a variant of clusterization, where some vertices have already been assigned to clusters. The second problem gives a natural generalization of Multiway Uncut, which is the complement of the classical Multiway Cut problem. Due to their fundamental role in theory and practice, clusterization and cut problems has always attracted a lot of attention. We establish a new connection between these two classes of problems by providing a reduction between Maximum Happy Vertices and Node Multiway Cut. Moreover, we study structural and distance to triviality parameterizations of Maximum Happy Vertices and Maximum Happy Edges. Obtained results in these directions answer questions explicitly asked in four works: Agrawal ’17, Aravind et al. ’16, Choudhari and Reddy ’18, Misra and Reddy ’17.

Ivan Bliznets, Danil Sagunov

Shortest Reconfiguration of Matchings

Abstract

Imagine that unlabelled tokens are placed on edges forming a matching of a graph. A token can be moved to another edge provided that the edges containing tokens remain a matching. The distance between two configurations of tokens is the minimum number of moves required to transform one into the other. We study the problem of computing the distance between two given configurations. We prove that if source and target configurations are maximal matchings, then the problem admits no polynomial-time sublogarithmic-factor approximation algorithm unless \(\mathsf{P}= \mathsf{NP}\). On the positive side, we show that for matchings of bipartite graphs the problem is fixed-parameter tractable parameterized by the size d of the symmetric difference of the two given configurations. Furthermore, we obtain a \(d^\varepsilon \)-factor approximation algorithm for the distance of two maximum matchings of bipartite graphs for every \(\varepsilon > 0\). The proofs of our positive results are constructive and can hence be turned into algorithms that output shortest transformations. Both algorithmic results rely on a close connection to the Directed Steiner Tree problem. Finally, we show that determining the exact distance between two configurations is complete for the class \(\mathsf{D}^\mathsf{P}\), and determining the maximum distance between any two configurations of a given graph is \(\mathsf{D}^\mathsf{P}\)-hard.

Nicolas Bousquet, Tatsuhiko Hatanaka, Takehiro Ito, Moritz Mühlenthaler

Travelling on Graphs with Small Highway Dimension

Abstract

We study the Travelling Salesperson (TSP) and the Steiner Tree problem (STP) in graphs of low highway dimension. This graph parameter was introduced by Abraham et al. [SODA 2010] as a model for transportation networks, on which TSP and STP naturally occur for various applications in logistics. It was previously shown [Feldmann et al. ICALP 2015] that these problems admit a quasi-polynomial time approximation scheme (QPTAS) on graphs of constant highway dimension. We demonstrate that a significant improvement is possible in the special case when the highway dimension is 1, for which we present a fully-polynomial time approximation scheme (FPTAS). We also prove that STP is weakly \(\mathsf {NP}\)-hard for these restricted graphs. For TSP we show \(\mathsf {NP}\)-hardness for graphs of highway dimension 6, which answers an open problem posed in [Feldmann et al. ICALP 2015].

Yann Disser, Andreas Emil Feldmann, Max Klimm, Jochen Könemann

The Power of Cut-Based Parameters for Computing Edge Disjoint Paths

Abstract

This paper revisits the classical Edge Disjoint Paths (EDP) problem, where one is given an undirected graph G and a set of terminal pairs P and asks whether G contains a set of pairwise edge-disjoint paths connecting every terminal pair in P. Our aim is to identify structural properties (parameters) of graphs which allow the efficient solution of EDP without restricting the placement of terminals in P in any way. In this setting, EDP is known to remain NP-hard even on extremely restricted graph classes, such as graphs with a vertex cover of size 3.

We present three results which use edge-separator based parameters to chart new islands of tractability in the complexity landscape of EDP. Our first and main result utilizes the fairly recent structural parameter treecut width (a parameter with fundamental ties to graph immersions and graph cuts): we obtain a polynomial-time algorithm for EDP on every graph class of bounded treecut width. Our second result shows that EDP parameterized by treecut width is unlikely to be fixed-parameter tractable. Our final, third result is a polynomial kernel for EDP parameterized by the size of a minimum feedback edge set in the graph.

Robert Ganian, Sebastian Ordyniak

Geometric Representations of Dichotomous Ordinal Data

Abstract

Motivated by the study of ordinal embeddings in machine learning and by the recognition of Euclidean preferences in computational social science, we study the following problem. Given a graph G, together with a set of relationships between pairs of edges, each specifying that an edge must be longer than another edge, is it possible to construct a straight-line drawing of G satisfying all these relationships?

We mainly consider a dichotomous setting, in which edges are partitioned into short and long, as otherwise there are simple (planar) instances that do not admit a solution. Since the problem is NP-hard even in this setting, we study under which conditions a solution always exists. We prove that degeneracy-2 graphs, subcubic graphs, double-wheels, and 4-colorable graphs in which the short edges induce a caterpillar always admit a realization. These positive results are complemented by negative instances, even when the input graph is composed of a maximal planar graph, namely a double-wheel graph, and an edge. We conjecture that planar graphs always admit a (not necessarily planar) realization in the dichotomous setting.

Patrizio Angelini, Michael A. Bekos, Martin Gronemann, Antonios Symvonis

Linear MIM-Width of Trees

Abstract

We provide an \(O(n \log n)\) algorithm computing the linear maximum induced matching width of a tree and an optimal layout.

Svein Høgemo, Jan Arne Telle, Erlend Raa Vågset

Approximating Minimum Dominating Set on String Graphs

Abstract

A string graph is an intersection graph of simple curves on the plane. For \(k\ge 0\), \(B_k\)-VPG graphs are intersection graphs of simple rectilinear curves having at most k cusps (bends). It is well-known that any string graph is a \(B_k\)-VPG graph for some value of k. For \(k\ge 0\), unit \(B_k\)-VPG graphs are intersection graphs of simple rectilinear curves having at most k cusps (bends) and each segment of the curve being unit length. Any string graph is a unit-\(B_k\)-VPG graph for some value of k.

In this article, we show that the Minimum Dominating Set (MDS) problem for unit \(B_k\)-VPG graphs is NP-Hard for all \(k \ge 1\) and provide an \(O(k^4)\)-approximation algorithm for all \(k\ge 0\). Furthermore, we also provide an 8-approximation for the MDS problem for the vertically-stabbed L-graphs, intersection graphs of L-paths intersecting a common vertical line. The same problem is known to be APX-Hard (MFCS, 2018). As a by-product of our proof, we obtained a 2-approximation algorithm for the stabbing segment with rays (SSR) problem introduced and studied by Katz et al. (Comput. Geom. 2005).

Dibyayan Chakraborty, Sandip Das, Joydeep Mukherjee

Classified Rank-Maximal Matchings and Popular Matchings – Algorithms and Hardness

Abstract

In this paper, we consider the problem of computing an optimal matching in a bipartite graph \(G=(A\cup P, E)\) where elements of A specify preferences over their neighbors in P, possibly involving ties, and each vertex can have capacities and classifications. A classification \(\mathcal {C}_u\) for a vertex u is a collection of subsets of neighbors of u. Each subset (class) \(C\in \mathcal {C}_u\) has an upper quota denoting the maximum number of vertices from C that can be matched to u. The goal is to find a matching that is optimal amongst all the feasible matchings, which are matchings that respect quotas of all the vertices and classes.

We consider two well-studied notions of optimality namely popularity and rank-maximality. The notion of rank-maximality involves finding a matching in G with maximum number of rank-1 edges, subject to that, maximum number of rank-2 edges and so on. We present an \(O(|E|^2)\)-time algorithm for finding a feasible rank-maximal matching, when each classification is a laminar family. We complement this with an NP-hardness result when classes are non-laminar even under strict preference lists, and even when only posts have classifications, and each applicant has a quota of one. We show an analogous dichotomy result for computing a popular matching amongst feasible matchings (if one exists) in a bipartite graph with posts having capacities and classifications and applicants having a quota of one.

To solve the classified rank-maximal and popular matchings problems, we present a framework that involves computing max-flows iteratively in multiple flow networks. Besides giving polynomial-time algorithms for classified rank-maximal and popular matching problems, our framework unifies several algorithms from literature [1, 10, 12, 15].

Meghana Nasre, Prajakta Nimbhorkar, Nada Pulath

Maximum Matchings and Minimum Blocking Sets in -Graphs

Abstract

\(\varTheta _6\)-graphs are important geometric graphs that have many applications especially in wireless sensor networks. They are equivalent to Delaunay graphs where empty equilateral triangles take the place of empty circles. We investigate lower bounds on the size of maximum matchings in these graphs. The best known lower bound is n/3, where n is the number of vertices of the graph, which comes from half-\(\varTheta _6\)-graphs that are subgraphs of \(\varTheta _6\)-graphs. Babu et al. (2014) conjectured that any \(\varTheta _6\)-graph has a (near-)perfect matching (as is true for standard Delaunay graphs). Although this conjecture remains open, we improve the lower bound to \((3n-8)/7\).

We also relate the size of maximum matchings in \(\varTheta _6\)-graphs to the minimum size of a blocking set. Every edge of a \(\varTheta _6\)-graph on point set P corresponds to an empty triangle that contains the endpoints of the edge but no other point of P. A blocking set has at least one point in each such triangle. We prove that the size of a maximum matching is at least \(\beta (n)/2\) where \(\beta (n)\) is the minimum, over all \(\varTheta _6\)-graphs with n vertices, of the minimum size of a blocking set. In the other direction, lower bounds on matchings can be used to prove bounds on \(\beta \), allowing us to show that \(\beta (n)\ge 3n/4-2\).

Therese Biedl, Ahmad Biniaz, Veronika Irvine, Kshitij Jain, Philipp Kindermann, Anna Lubiw

A Polynomial-Time Algorithm for the Independent Set Problem in -Free Graphs

Abstract

We consider the independent set problem, a classical NP-hard optimization problem that remains hard even under substantial restrictions on the input graphs. The complexity status of the problem is unknown for the classes of \(P_k\)-free graphs for all \(k\ge 7\) and for the class of even-hole-free graphs, that is, graphs not containing any even induced cycles. Using the technique of augmenting graphs we show that the independent set problem is solvable in polynomial time in the class of even-hole-free graphs not containing an induced path on 10 vertices. Our result is developed in the context of the more general class of \(\{P_{10},C_4,C_6\}\)-free graphs.

Edin Husić, Martin Milanič

Independent Set Reconfiguration Parameterized by Modular-Width

Abstract

Independent Set Reconfiguration is one of the most well-studied problems in the setting of combinatorial reconfiguration. It is known that the problem is PSPACE-complete even for graphs of bounded bandwidth. This fact rules out the tractability of parameterizations by most well-studied structural parameters as most of them generalize bandwidth. In this paper, we study the parameterization by modular-width, which is not comparable with bandwidth. We show that the problem parameterized by modular-width is fixed-parameter tractable under all previously studied rules \(\mathsf {TAR}\), \(\mathsf {TJ}\), and \(\mathsf {TS}\). The result under \(\mathsf {TAR}\) resolves an open problem posed by Bonsma [WG 2014, JGT 2016].

Rémy Belmonte, Tesshu Hanaka, Michael Lampis, Hirotaka Ono, Yota Otachi

Counting Independent Sets in Graphs with Bounded Bipartite Pathwidth

Abstract

The Glauber dynamics can efficiently sample independent sets almost uniformly at random in polynomial time for graphs in a certain class. The class is determined by boundedness of a new graph parameter called bipartite pathwidth. This result, which we prove for the more general hardcore distribution with fugacity \(\lambda \), can be viewed as a strong generalisation of Jerrum and Sinclair’s work on approximately counting matchings. The class of graphs with bounded bipartite pathwidth includes line graphs and claw-free graphs, which generalise line graphs. We consider two further generalisations of claw-free graphs and prove that these classes have bounded bipartite pathwidth.

Martin Dyer, Catherine Greenhill, Haiko Müller

Intersection Graphs of Non-crossing Paths

Abstract

We study graph classes modeled by families of non-crossing (NC) connected sets. Two classic graph classes in this context are disk graphs and proper interval graphs. We focus on the cases when the sets are paths and the host is a tree. Forbidden induced subgraph characterizations and linear time certifying recognition algorithms are given for intersection graphs of NC paths of a tree (and related subclasses). For intersection graphs of NC paths of a tree, the dominating set problem is shown to be solvable in linear time. Also, each such graph is shown to have a Hamiltonian cycle if and only if it is 2-connected, and to have a Hamiltonian path if and only if its block-cutpoint tree is a path.

Steven Chaplick

Reconfiguring Hamiltonian Cycles in L-Shaped Grid Graphs

Abstract

Given a pair of 1-complex Hamiltonian cycles C and \(C'\) in an L-shaped grid graph G, we show that one is reachable from the other under two operations, flip and transpose, while remaining in the family of 1-complex Hamiltonian cycles throughout the reconfiguration. Operations flip and transpose are local in G. We give a reconfiguration algorithm that uses O(|G|) operations.

Rahnuma Islam Nishat, Sue Whitesides

Color Refinement, Homomorphisms, and Hypergraphs

Abstract

Recent results show that the structural similarity of graphs can be characterized by counting homomorphisms to them: the Tree Theorem states that the well-known color-refinement algorithm does not distinguish two graphs G and H if and only if, for every tree T, the number of homomorphisms \(\mathsf {Hom}(T, G)\) from T to G is equal to the corresponding number \(\mathsf {Hom}(T, H)\) from T to H (Dell, Grohe, Rattan 2018). We show how this approach transfers to hypergraphs by introducing a generalization of color refinement. We prove that it does not distinguish two hypergraphs G and H if and only if, for every connected Berge-acyclic hypergraph B, we have \(\mathsf {Hom}(B, G) = \mathsf {Hom}(B, H)\). To this end, we show how homomorphisms of hypergraphs and of a colored variant of their incidence graphs are related to each other. This reduces the above statement to one about vertex-colored graphs.

Jan Böker

3-Colorable Planar Graphs Have an Intersection Segment Representation Using 3 Slopes

Abstract

In his PhD Thesis E.R. Scheinerman conjectured that planar graphs are intersection graphs of segments in the plane. This conjecture was proved with two different approaches. In the case of 3-colorable planar graphs E.R. Scheinerman conjectured that it is possible to restrict the set of slopes used by the segments to only 3 slopes. Here we prove this conjecture by using an approach introduced by S. Felsner to deal with contact representations of planar graphs with homothetic triangles.

Daniel Gonçalves

The Exponential-Time Complexity of Counting (Quantum) Graph Homomorphisms

Abstract

Many graph parameters can be expressed as homomorphism counts to fixed target graphs; this includes the number of independent sets and the number of k-colorings for any fixed k. Dyer and Greenhill (RSA 2000) gave a sweeping complexity dichotomy for such problems, classifying which target graphs render the problem polynomial-time solvable or \(\#\mathrm {P}\)-hard. In this paper, we give a new and shorter proof of this theorem, with previously unknown tight lower bounds under the exponential-time hypothesis. We similarly strengthen complexity dichotomies by Focke, Goldberg, and Živný (SODA 2018) for counting surjective homomorphisms to fixed graphs. Both results crucially rely on our main contribution, a complexity dichotomy for evaluating linear combinations of homomorphism numbers to fixed graphs. In the terminology of Lovász (Colloquium Publications 2012), this amounts to counting homomorphisms to quantum graphs.

Hubie Chen, Radu Curticapean, Holger Dell

Minimal Separators in Graph Classes Defined by Small Forbidden Induced Subgraphs

Abstract

Minimal separators in graphs are an important concept in algorithmic graph theory. In particular, many problems that are NP-hard for general graphs are known to become polynomial-time solvable for classes of graphs with a polynomially bounded number of minimal separators. Several well-known graph classes have this property, including chordal graphs, permutation graphs, circular-arc graphs, and circle graphs. We perform a systematic study of the question which classes of graphs defined by small forbidden induced subgraphs have a polynomially bounded number of minimal separators. We focus on sets of forbidden induced subgraphs with at most four vertices and obtain an almost complete dichotomy, leaving open only two cases.

Martin Milanič, Nevena Pivač

Backmatter