Subexponential algorithms for variants of homomorphism problem in string graphs

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.

The 4-Steiner Root Problem

Hamiltonicity below Dirac’s condition

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.

Maximum Independent Sets in Subcubic Graphs: New Results

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.

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

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.

Local approximation of the Maximum Cut in regular graphs

Fixed-parameter tractability of counting small minimum (S,T)-cuts

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.

Fast Breadth-First Search in Still Less Space

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.

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

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.

Flip distances between graph orientations

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.

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.

On Happy Colorings, Cuts, and Structural Parameterizations

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.

Shortest Reconfiguration of Matchings

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.

Travelling on Graphs with Small Highway Dimension

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

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.

Geometric Representations of Dichotomous Ordinal Data

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.

Linear MIM-width of Trees

Approximating Minimum Dominating Set on String graphs

\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).

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

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.

Maximum Matchings and Minimum Blocking Sets in Theta-6 Graphs

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.

A polynomial-time algorithm for the independent set problem in $\{P_{10},C_4,C_6\}$-free 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.

Independent Set Reconfiguration Parameterized by Modular-Width

Counting independent sets in graphs with bounded bipartite pathwidth

Intersection Graphs of Non-Crossing Paths

Reconfiguring Hamiltonian Cycles in L-Shaped Grid Graphs

Color Refinement, Homomorphisms, and Hypergraphs

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.

3-colorable planar graphs have an intersection segment representation using 3 slopes

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.

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

Minimal separators in graph classes defined by small forbidden induced subgraphs

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.