WG 2019 Accepted Papers with Abstracts

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.

Abstract: The $k^{th}$-power of a graph $G$ is obtained by adding an edge between every two distinct vertices at a distance $\leq k$ in $G$. We call $G$ a {\em $k$-Steiner power} if it is an induced subgraph of the $k^{th}$-power of some tree $T$. In particular, $G$ is a {\em $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, {\it ISAAC'00}) for $k=1,2$ and (Chang and Ko, {\it 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. We expect several components of this new framework to be further used in the recognition of $k$-leaf powers, $k$-Steiner powers and related graph classes.

Abstract: Dirac’s theorem (1952) is a classical result of graph theory, stating that an n-vertex graph (n >= 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 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.

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 include a sub-divided 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.

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.

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 $\tfrac12$ 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 \emph{deterministic} distributed algorithms for {\sc 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 $\tfrac1{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 $\tfrac1{d}+\epsilon$ (with $\epsilon>0$) can run in a constant number of rounds. We also prove results of a similar flavour for the {\sc 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.

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=|V|$ 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.

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 log_2(3)*n+O((log n)^2) bits of working memory.

Abstract: For a fixed family of graphs F, the F-Minor-Free Deletion problem takes as input a graph G and integer l and asks whether there exists a set X⊆V(G) of size at most l such that G-X is F-minor-free. For F={K_2} and 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 F containing a planar graph but no forests.
In this paper we show that F-Minor-Free Deletion parameterized by feedback vertex number is MK[2]-hard when F contains a forest but no P_3-subgraph-free graph. This rules out the existence of a polynomial kernel assuming NP ⊈ coNP/poly, and also gives evidence that the problem does not admit a polynomial Turing kernel. Our hardness result generalizes to any F not containing a P_3-subgraph-free graph, using as parameter the vertex-deletion distance to treewidth mintw(F), where mintw(F) denotes the minimum treewidth of the graphs in F.
For the other case, where F contains a P_3-subgraph-free graph, we present a polynomial Turing kernelization. Our results extend to F-Subgraph-Free Deletion.

Abstract: Flip graphs are a ubiquitous class of graphs, which encode relations induced on a set of combinatorial objects 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.

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.

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 a complement of the classical Multiway Cut problem.
Due to their fundamental role in theory and practice, clusterization and cut problems have attracted a lot of attention recently.
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'18, Aravind et al.'16, Choudhari and Reddy'18, Misra and Reddy'18.

Abstract: Imagine that unlabelled tokens are placed on the edges forming a matching of a graph. A token can be moved to another edge if the edges containing tokens remain a matching. The \emph{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 both matchings are maximal then the problem admits no polynomial-time sublogarithmic-factor approximation algorithm unless P = NP. On the positive side, we show that for matchings of bipartite graphs the problem is fixed-parameter tractable when parameterized by the size d of the symmetric difference of the two given configurations. Furthermore, we obtain a d^epsilon-factor approximation algorithm for the distance of two maximum matchings of bipartite graphs for every epsilon > 0. The proofs of our positive results are constructive and can hence be turned into
algorithms that output shortest transformations. Finally, we show that determining the exact distance between two configurations is complete for the class D^P, and determining the maximum distance between any two configurations of a given graph is D^P-hard.

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 NP-hard for these restricted graphs. For TSP we show NP-hardness for graphs of highway dimension 6, which answers an open problem posed in [Feldmann et al. ICALP 2015].

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.

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 realization in the dichotomous setting.

Abstract: We provide an $O(n \log n)$ algorithm computing the linear maximum induced matching width of a tree.

Abstract: A \emph{string} graph is an intersection graph of simple curves on the plane. For $k\geq 0$, \emph{$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\geq 0$, \emph{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$.

\hspace{0.5cm}In this article, we show that the \textsc{Minimum Dominating
Set} (\textsc{MDS}) problem for unit $B_k$-VPG graphs is NP-Hard for all $k \geq 1$
and provide an $O(k^4)$-approximation algorithm for all $k\geq 0$.
Furthermore, we also provide an $8$-approximation for the \textsc{MDS} problem for the \emph{vertically-stabbed \textsc{L}-graphs}, intersection graphs of
\textsc{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 \emph{stabbing segment with rays} (\textsc{SSR}) problem introduced and studied by Katz et al. (Comput. Geom. 2005).

Abstract: In this paper, we consider the problem of computing an optimal matching in a bipartite graph where
elements of one side of the bipartition specify preferences over the other side, and
one or both sides can have capacities and classifications.
The input instance is a bipartite graph G=(A U P,E), where A is a set of applicants, P is a set of posts, and
each applicant ranks its neighbors in an order of preference, possibly involving ties. Moreover, each vertex v in A U P
has a quota q(v) denoting the maximum number of partners it can have in any allocation of applicants to posts - referred to
as a {\em matching} in this paper.
A classification for a vertex u is a collection of subsets of neighbors of u. Each subset (class)
has an upper quota denoting the maximum number of vertices from the class 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 in multiple flow networks.
We use the fact that, in any flow network, w.r.t. any max-flow the vertices can be decomposed
into three disjoint sets and this decomposition is invariant of the flow. This simple fact turns out to be surprisingly useful
in the design of our combinatorial algorithms.
We believe that our technique of flow networks provides a unified
framework for capacitated rank-maximal matchings (Paluch CIAC-13) and capacitated house allocation problem (Manlove and Sng ESA-06) and will find further applications
in capacitated matching problems with preferences.

Abstract: Theta-six 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. Babu et al. (2014) conjectured that any theta-six graph has a 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 theta-six graphs to the minimum size of a blocking set. Every edge of a theta-six 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 1/2 beta(n) where beta(n) is the minimum, over all theta-six 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) >= 3n/4 − 2.

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.

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 of 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 TAR, TJ, and TS. The result under TAR resolves an open problem posed by Bonsma [WG 2014, JGT 2016].

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 λ, 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.

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.

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, \emph{flip} and \emph{transpose}, while remaining in the family of $1$-complex Hamiltonian cycles throughout the reconfiguration. Operations \emph{flip} and \emph{transpose} are local in $G$. We give a reconfiguration algorithm that uses $O(|G|)$ operations.

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 Hom(T,G) from T to G is equal to the corresponding number 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 Hom(B,G) = 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.

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.

Abstract: Many graph parameters can be expressed as homomorphism counts to fixed target graphs H; 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, starting a line of research that culminated in a full dichotomy for (weighted) counting versions of Constraint Satisfaction Problems. In this paper, we significantly shorten the proof of the Dyer-Greenhill theorem, which also allows us to obtain a starker complexity dichotomy under the exponential-time hypothesis. We similarly strengthen the complexity dichotomies by Focke, Goldberg, and Živný (SODA 2018) for counting surjective homomorphisms to fixed graphs H, and shorten their proofs. The main new ingredient in our proofs is that we make explicit use of Lovász' notion of quantum graphs and the literature surrounding it (Colloquium Publications 2012).

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 polyno-
mially 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 dened by small forbidden induced subgraphs have a polyno-
mially 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.