Source author record

Marta Piecyk

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity math.CO

Catalog footprint

Research overview

2works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Computing homomorphisms in hereditary graph classes: the peculiar case of the 5-wheel and graphs with no long claws

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 \geq 1$ , by $S_{a,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 \geq 5$ , by $W_k$ we denote the graph obtained from the $k$ -cycle by adding a universal vertex. As our main algorithmic result we show that $W_5$ -ColoringExt is polynomial-time solvable in $S_{2,1,1}$ -free graphs. This result exhibits an interesting non-monotonicity of $H$ -ColoringExt with respect to taking induced subgraphs of $H$ . Indeed, $W_5$ contains a triangle, and $K_3$ -Coloring, i.e., classical 3-coloring, is NP-hard already in claw-free (i.e., $S_{1,1,1}$ -free) graphs. Our algorithm is based on two main observations: 1. $W_5$ -ColoringExt in $S_{2,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 $S_{2,1,1}$ -free graphs. We complement this algorithmic result with several negative ones. In particular, we show that $W_5$ -ColoringExt is NP-hard in $S_{3,3,3}$ -free graphs. This is again uncommon, as usually problems that are NP-hard in $S_{a,b,c}$ -free graphs for some constant $a,b,c$ are already hard in claw-free graphs.

preprint2020arXiv

Full complexity classification of the list homomorphism problem for bounded-treewidth 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 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 \in V(G)$ it holds that $h(v) \in 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 $k^{t} \cdot n^{\mathcal{O}(1)}$ , provided that the input graph is given along with a tree decomposition of width $t$ , * cannot be solved in time $(k-\varepsilon)^{t} \cdot n^{\mathcal{O}(1)}$ , for any $\varepsilon >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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.