BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We prove that for every fixed integer s and every planar graph H, the class of H-induced-minor-free and K1,s-induced-subgraph-free graphs has polylogarithmic tree-independence number. This is a weakening of a conjecture of Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht.
In the Feedback Vertex Set problem, we aim to find a small set S of vertices in a graph intersecting every cycle. The Subset Feedback Vertex Set problem requires S to intersect only those cycles that include a vertex of some specified set T. We also consider the Weighted Subset Feedback Vertex Set problem, where each vertex u has weight w(u)>0 and we ask that S has small weight. By combining known NP-hardness results with new polynomial-time results we prove full complexity dichotomies for Subset Feedback Vertex Set and Weighted Subset Feedback Vertex Set for H-free graphs, that is, graphs that do not contain a graph H as an induced subgraph.
A homomorphism from a graph G to a graph H is an edge-preserving mapping from V(G) to V(H). For a fixed graph H, in the list homomorphism problem, denoted by LHom(H), we are given a graph G, whose every vertex v is equipped with a list L(v)⊆V(H). We ask if there exists a homomorphism f from G to H, in which f(v)∈L(v) for every v∈V(G). Feder, Hell, and Huang [JGT~2003] proved that LHom(H) is polynomial time-solvable if H is a bi-arc-graph, and NP-complete otherwise. We are interested in the complexity of the LHom(H) problem in graphs excluding a copy of some fixed graph F as an induced subgraph. It is known that if F is connected and is not a path nor a subdivided claw, then for every non-bi-arc graph the LHom(H) problem is NP-complete and cannot be solved in subexponential time, unless the ETH fails. We consider the remaining cases for connected graphs F. If F is a path, we exhibit a full dichotomy. We define a class called predacious graphs and show that if H is not predacious, then for every fixed t the LHom(H) problem can be solved in quasi-polynomial time in Pt-free graphs. On the other hand, if H is predacious, then there exists t, such that LHom(H) cannot be solved in subexponential time in Pt-free graphs. If F is a subdivided claw, we show a full dichotomy in two important cases: for H being irreflexive (i.e., with no loops), and for H being reflexive (i.e., where every vertex has a loop). Unless the ETH fails, for irreflexive H the LHom(H) problem can be solved in subexponential time in graphs excluding a fixed subdivided claw if and only if H is non-predacious and triangle-free. If H is reflexive, then LHom(H) cannot be solved in subexponential time whenever H is not a bi-arc graph.
For graphs G and H, an H-coloring of G is an edge-preserving mapping from V(G) to V(H). In the H-Coloring problem the graph H is fixed and we ask whether an instance graph G admits an H-coloring. A generalization of this problem is H-ColoringExt, where some vertices of G are already mapped to vertices of H and we ask if this partial mapping can be extended to an H-coloring. We study the complexity of variants of H-Coloring in F-free graphs, i.e., graphs excluding a fixed graph F as an induced subgraph. For integers a,b,c≥1, by Sa,b,c we denote the graph obtained by identifying one endvertex of three paths on a+1, b+1, and c+1 vertices, respectively. For odd k≥5, by Wk we denote the graph obtained from the k-cycle by adding a universal vertex. As our main algorithmic result we show that W5-ColoringExt is polynomial-time solvable in S2,1,1-free graphs. This result exhibits an interesting non-monotonicity of H-ColoringExt with respect to taking induced subgraphs of H. Indeed, W5 contains a triangle, and K3-Coloring, i.e., classical 3-coloring, is NP-hard already in claw-free (i.e., S1,1,1-free) graphs. Our algorithm is based on two main observations: 1. W5-ColoringExt in S2,1,1-free graphs can be in polynomial time reduced to a variant of the problem of finding an independent set intersecting all triangles, and 2. the latter problem can be solved in polynomial time in S2,1,1-free graphs. We complement this algorithmic result with several negative ones. In particular, we show that W5-ColoringExt is NP-hard in S3,3,3-free graphs. This is again uncommon, as usually problems that are NP-hard in Sa,b,c-free graphs for some constant a,b,c are already hard in claw-free graphs.
A homomorphism from a graph G to a graph H is an edge-preserving mapping from V(G) to V(H). Let H be a fixed graph with possible loops. In the list homomorphism problem, denoted by \textsc{LHom}(H), the instance is a graph G, whose every vertex is equipped with a subset of V(H), called list. We ask whether there exists a homomorphism from G to H, such that every vertex from G is mapped to a vertex from its list. We study the complexity of the \textsc{LHom}(H) problem in intersection graphs of various geometric objects. In particular, we are interested in answering the question for what graphs H and for what types of geometric objects, the \textsc{LHom}(H) problem can be solved in time subexponential in the number of vertices of the instance. We fully resolve this question for string graphs, i.e., intersection graphs of continuous curves in the plane. Quite surprisingly, it turns out that the dichotomy exactly coincides with the analogous dichotomy for graphs excluding a fixed path as an induced subgraph [Okrasa, Rzążewski, STACS 2021]. Then we turn our attention to subclasses of string graphs, defined as intersections of fat objects. We observe that the (non)existence of subexponential-time algorithms in such classes is closely related to the size mrc(H) of a maximum reflexive clique in H, i.e., maximum number of pairwise adjacent vertices, each of which has a loop. We study the maximum value of mrc(H) that guarantees the existence of a subexponential-time algorithm for \textsc{LHom}(H) in intersection graphs of (i) convex fat objects, (ii) fat similarly-sized objects, and (iii) disks. In the first two cases we obtain optimal results, by giving matching algorithms and lower bounds. Finally, we discuss possible extensions of our results to weighted generalizations of \textsc{LHom}(H).
We prove new complexity results for Feedback Vertex Set and Even Cycle Transversal on H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. In particular, we prove that for every s≥1, both problems are polynomial-time solvable for sP3-free graphs and (sP1+P5)-free graphs; here, the graph sP3 denotes the disjoint union of s paths on three vertices and the graph sP1+P5 denotes the disjoint union of s isolated vertices and a path on five vertices. Our new results for Feedback Vertex Set extend all known polynomial-time results for Feedback Vertex Set on H-free graphs, namely for sP2-free graphs [Chiarelli et al., TCS 2018], (sP1+P3)-free graphs [Dabrowski et al., Algorithmica 2020] and P5-free graphs [Abrishami et al., SODA 2021]. Together, the new results also show that both problems exhibit the same behaviour on H-free graphs (subject to some open cases). This is in part due to a new general algorithm we design for finding in a (sP3)-free or (sP1+P5)-free graph G a largest induced subgraph whose blocks belong to some finite class C of graphs. We also compare our results with the state-of-the-art results for the Odd Cycle Transversal problem, which is known to behave differently on H-free graphs.
For graphs G and H, we say that G is H-free if it does not contain H as an induced subgraph. Already in the early 1980s Alekseev observed that if H is connected, then the \textsc{Max Weight Independent Set} problem (MWIS) remains \textsc{NP}-hard in H-free graphs, unless H is a path or a subdivided claw, i.e., a graph obtained from the three-leaf star by subdividing each edge some number of times (possibly zero). Since then determining the complexity of MWIS in these remaining cases is one of the most important problems in algorithmic graph theory. A general belief is that the problem is polynomial-time solvable, which is witnessed by algorithmic results for graphs excluding some small paths or subdivided claws. A more conclusive evidence was given by the recent breakthrough result by Gartland and Lokshtanov [FOCS 2020]: They proved that MWIS can be solved in quasipolynomial time in H-free graphs, where H is any fixed path. If H is an arbitrary subdivided claw, we know much less: The problem admits a QPTAS and a subexponential-time algorithm [Chudnovsky et al., SODA 2019]. In this paper we make an important step towards solving the problem by showing that for any subdivided claw H, MWIS is polynomial-time solvable in H-free graphs of bounded degree.
We study the \textsc{Max Partial H-Coloring} problem: given a graph G, find the largest induced subgraph of G that admits a homomorphism into H, where H is a fixed pattern graph without loops. Note that when H is a complete graph on k vertices, the problem reduces to finding the largest induced k-colorable subgraph, which for k=2 is equivalent (by complementation) to \textsc{Odd Cycle Transversal}. We prove that for every fixed pattern graph H without loops, \textsc{Max Partial H-Coloring} can be solved: ∙ in {P5,F}-free graphs in polynomial time, whenever F is a threshold graph; ∙ in {P5,bull}-free graphs in polynomial time; ∙ in P5-free graphs in time nO(ω(G)); ∙ in {P6,1-subdivided claw}-free graphs in time nO(ω(G)3). Here, n is the number of vertices of the input graph G and ω(G) is the maximum size of a clique in~G. Furthermore, combining the mentioned algorithms for P5-free and for {P6,1-subdivided claw}-free graphs with a simple branching procedure, we obtain subexponential-time algorithms for \textsc{Max Partial H-Coloring} in these classes of graphs. Finally, we show that even a restricted variant of \textsc{Max Partial H-Coloring} is NP-hard in the considered subclasses of P5-free graphs, if we allow loops on H.
For graphs G and H, a \emph{homomorphism} from G to H is an edge-preserving mapping from the vertex set of G to the vertex set of H. For a fixed graph H, by \textsc{Hom(H)} we denote the computational problem which asks whether a given graph G admits a homomorphism to H. If H is a complete graph with k vertices, then \textsc{Hom(H)} is equivalent to the k-\textsc{Coloring} problem, so graph homomorphisms can be seen as generalizations of colorings. It is known that \textsc{Hom(H)} is polynomial-time solvable if H is bipartite or has a vertex with a loop, and NP-complete otherwise [Hell and Nešetřil, JCTB 1990]. In this paper we are interested in the complexity of the problem, parameterized by the treewidth of the input graph G. If G has n vertices and is given along with its tree decomposition of width tw(G), then the problem can be solved in time ∣V(H)∣tw(G)⋅nO(1), using a straightforward dynamic programming. We explore whether this bound can be improved. We show that if H is a \emph{projective core}, then the existence of such a faster algorithm is unlikely: assuming the Strong Exponential Time Hypothesis (SETH), the \textsc{Hom(H)} problem cannot be solved in time (∣V(H)∣−ε)tw(G)⋅nO(1), for any ε>0. This result provides a full complexity characterization for a large class of graphs H, as almost all graphs are projective cores. We also notice that the naive algorithm can be improved for some graphs H, and show a complexity classification for all graphs H, assuming two conjectures from algebraic graph theory. In particular, there are no known graphs H which are not covered by our result. In order to prove our results, we bring together some tools and techniques from algebra and from fine-grained complexity.
A homomorphism from a graph G to a graph H is an edge-preserving mapping from V(G) to V(H). Let H be a fixed graph with possible loops. In the list homomorphism problem, denoted by LHom(H), we are given a graph G, whose every vertex v is assigned with a list L(v) of vertices of H. We ask whether there exists a homomorphism h from G to H, which respects lists L, i.e., for every v∈V(G) it holds that h(v)∈L(v). The complexity dichotomy for LHom(H) was proven by Feder, Hell, and Huang [JGT 2003]. We are interested in the complexity of the problem, parameterized by the treewidth of the input graph. This problem was investigated by Egri, Marx, and Rzążewski [STACS 2018], who obtained tight complexity bounds for the special case of reflexive graphs H. In this paper we extend and generalize their results for \emph{all} relevant graphs H, i.e., those, for which the LHom{H} problem is NP-hard. For every such H we find a constant k=k(H), such that LHom(H) on instances with n vertices and treewidth t * can be solved in time kt⋅nO(1), provided that the input graph is given along with a tree decomposition of width t, * cannot be solved in time (k−ε)t⋅nO(1), for any ε>0, unless the SETH fails. For some graphs H the value of k(H) is much smaller than the trivial upper bound, i.e., ∣V(H)∣. Obtaining matching upper and lower bounds shows that the set of algorithmic tools we have discovered cannot be extended in order to obtain faster algorithms for LHom(H) in bounded-treewidth graphs. Furthermore, neither the algorithm, nor the proof of the lower bound, is very specific to treewidth. We believe that they can be used for other variants of LHom(H), e.g. with different parameterizations.
A hole in a graph is an induced cycle of length at least 4. A hole is long if its length is at least 5. By Pt we denote a path on t vertices. In this paper we give polynomial-time algorithms for the following problems: the Maximum Weight Independent Set problem in long-hole-free graphs, and the Feedback Vertex Set problem in P5-free graphs. Each of the above results resolves a corresponding long-standing open problem. An extended C5 is a five-vertex hole with an additional vertex adjacent to one or two consecutive vertices of the hole. Let C be the class of graphs excluding an extended C5 and holes of length at least 6 as induced subgraphs; C contains all long-hole-free graphs and all P5-free graphs. We show that, given an n-vertex graph G∈C with vertex weights and an integer k, one can in time $n^{\Oh(k)}$ find a maximum-weight induced subgraph of G of treewidth less than k. This implies both aforementioned results.
Contact representations of graphs have a long history. Most research has focused on problems in 2D, but 3D contact representations have also been investigated, mostly concerning fully-dimensional geometric objects such as spheres or cubes. In this paper we study contact representations with convex polygons in 3D. We show that every graph admits such a representation. Since our representations use super-polynomial coordinates, we also construct representations on grids of polynomial size for specific graph classes (bipartite, subcubic). For hypergraphs, we represent their duals, that is, each vertex is represented by a point and each edge by a polygon. We show that even regular and quite small hypergraphs do not admit such representations. On the other hand, the two smallest Steiner triple systems can be represented.
We investigate the List H-Coloring problem, the generalization of graph coloring that asks whether an input graph G admits a homomorphism to the undirected graph H (possibly with loops), such that each vertex v∈V(G) is mapped to a vertex on its list L(v)⊆V(H). An important result by Feder, Hell, and Huang [JGT 2003] states that List H-Coloring is polynomial-time solvable if H is a so-called bi-arc graph, and NP-complete otherwise. We investigate the NP-complete cases of the problem from the perspective of polynomial-time sparsification: can an n-vertex instance be efficiently reduced to an equivalent instance of bitsize O(n2−ε) for some ε>0? We prove that if H is not a bi-arc graph, then List H-Coloring does not admit such a sparsification algorithm unless NP⊆coNP/poly. Our proofs combine techniques from kernelization lower bounds with a study of the structure of graphs H which are not bi-arc graphs.
A connected path decomposition of a simple graph G is a path decomposition (X1,…,Xl) such that the subgraph of G induced by X1∪⋯∪Xi is connected for each i∈{1,…,l}. The connected pathwidth of G is then the minimum width over all connected path decompositions of G. We prove that for each fixed k, the connected pathwidth of any input graph can be computed in polynomial-time. This answers an open question raised by Fedor V. Fomin during the GRASTA 2017 workshop, since connected pathwidth is equivalent to the connected (monotone) node search game.
We study the {\sc Clique} problem in classes of intersection graphs of convex sets in the plane. The problem is known to be NP-complete in convex-set intersection graphs and straight-line-segment intersection graphs, but solvable in polynomial time in intersection graphs of homothetic triangles. We extend the latter result by showing that for every convex polygon P with sides parallel to k directions, every n-vertex graph which is an intersection graph of homothetic copies of P contains at most nk inclusion-wise maximal cliques. We actually prove this result for a more general class of graphs, the so called kDIR−CONV, which are intersection graphs of convex polygons whose sides are parallel to some fixed k directions. Moreover, we provide some lower bounds on the numbers of maximal cliques, discuss the complexity of recognizing these classes of graphs and present a relationship with other classes of convex-set intersection graphs. Finally, we generalize the upper bound on the number of maximal cliques to intersection graphs of higher-dimensional convex polytopes in Euclidean space.
Motion planning is an important and well-studied field of robotics. A typical approach to finding a route is to construct a {\em cell graph} representing a scene and then to find a path in such a graph. In this paper we present and analyze parallel algorithms for constructing the cell graph on a SIMD-like GPU processor. Additionally, we present a new implementation of the dictionary data type on a GPU device. In the contrary to hash tables, which are common in GPU algorithms, it uses a search tree in which all values are kept in leaves. With such a structure we can effectively perform dictionary operations on a set of long vectors over a limited alphabet.
The generalized list T-coloring is a common generalization of many graph coloring models, including classical coloring, L(p,q)-labeling, channel assignment and T-coloring. Every vertex from the input graph has a list of permitted labels. Moreover, every edge has a set of forbidden differences. We ask for such a labeling of vertices of the input graph with natural numbers, in which every vertex gets a label from its list of permitted labels and the difference of labels of the endpoints of each edge does not belong to the set of forbidden differences of this edge. In this paper we present an exact algorithm solving this problem, running in time O∗((τ+2)n), where τ is the maximum forbidden difference over all edges of the input graph and n is the number of its vertices. Moreover, we show how to improve this bound if the input graph has some special structure, e.g. a bounded maximum degree, no big induced stars or a perfect matching.
For graphs G and H, a homomorphism from G to H is a function φ:V(G)→V(H), which maps vertices adjacent in G to adjacent vertices of H. A homomorphism is locally injective if no two vertices with a common neighbor are mapped to a single vertex in H. Many cases of graph homomorphism and locally injective graph homomorphism are NP-complete, so there is little hope to design polynomial-time algorithms for them. In this paper we present an algorithm for graph homomorphism and locally injective homomorphism working in time O∗((b+2)∣V(G)∣), where b is the bandwidth of the complement of H.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.