List homomorphisms by deleting edges and vertices tight complexity bounds for bounded-treewidth graphs Barış Can EsmerJacob FockeDániel MarxPaweł Rzążewski
2025-05-02
0
0
1.68MB
55 页
10玖币
侵权投诉
List homomorphisms by deleting edges and vertices:
tight complexity bounds for bounded-treewidth graphs
Barış Can Esmer∗Jacob Focke∗Dániel Marx∗Paweł Rzążewski†
Abstract
The goal of this paper is to investigate a family of optimization problems arising from list ho-
momorphisms, and to understand what the best possible algorithms are if we restrict the problem
to bounded-treewidth graphs. Given graphs G,H, and lists L(v)⊆V(H)for every v∈V(G), a
list homomorphism from (G, L)to His a function f:V(G)→V(H)that preserves the edges (i.e.,
uv ∈E(G)implies f(u)f(v)∈E(H)) and respects the lists (i.e., f(v)∈L(v)). The graph Hmay
have loops. For a xed H, the input of the optimization problem LHomVD(H)is a graph Gwith
lists L(v), and the task is to nd a set Xof vertices having minimum size such that (G−X, L)has
a list homomorphism to H. We dene analogously the edge-deletion variant LHomED(H), where
we have to delete as few edges as possible from Gto obtain a graph that has a list homomorphism.
This expressive family of problems includes members that are essentially equivalent to funda-
mental problems such as Vertex Cover,Max Cut,Odd Cycle Transversal, and Edge/Vertex
Multiway Cut.
For both variants, we rst characterize those graphs Hthat make the problem polynomial-
time solvable and show that the problem is NP-hard for every other xed H. Second, as our main
result, we determine for every graph Hfor which the problem is NP-hard, the smallest possible
constant cHsuch that the problem can be solved in time ct
H·nO(1) if a tree decomposition of
Ghaving width tis given in the input. Let i(H)be the maximum size of a set of vertices in H
that have pairwise incomparable neighborhoods. For the vertex-deletion variant LHomVD(H), we
show that the smallest possible constant is i(H)+1for every H:
•Given a tree decomposition of width tof G,LHomVD(H)can be solved in time (i(H) + 1)t·
nO(1).
•For any ε > 0and H, an (i(H)+1−ε)t·nO(1) algorithm would violate the Strong
Exponential-Time Hypothesis (SETH).
The situation is more complex for the edge-deletion version. For every H, one can solve
LHomED(H)in time i(H)t·nO(1) if a tree decomposition of width tis given. However, the exis-
tence of a specic type of decomposition of Hshows that there are graphs Hwhere LHomED(H)
can be solved signicantly more eciently and the best possible constant can be arbitrarily smaller
than i(H). Nevertheless, we determine this best possible constant and (assuming the SETH) prove
tight bounds for every xed H.
∗CISPA Helmholtz Center for Information Security. The rst author is also aliated with the Saarbrücken Graduate
School of Computer Science, Saarland Informatics Campus, Germany. Research of the third author is supported by the
European Research Council (ERC) consolidator grant No. 725978 SYSTEMATICGRAPH.
†Warsaw University of Technology, Faculty of Mathematics and Information Science and University of Warsaw, In-
stitute of Informatics, pawel.rzazewski@pw.edu.pl. Supported by the Polish National Science Centre grant no.
2018/31/D/ST6/00062.
1
arXiv:2210.10677v2 [cs.CC] 13 Feb 2024
Contents
1 Introduction 1
2 Technical Overview 6
2.1 Vertex-deletion version .................................... 7
2.2 Edge-deletion version ..................................... 9
3 Preliminaries 14
4 Complexity dichotomy for LHomVD(H)16
5 Tight results for LHomVD(H)18
5.1 Algorithm for LHomVD(H)................................. 18
5.2 Hardness for LHomVD(H).................................. 18
5.2.1 Constructing prohibitors ............................... 20
6 Complexity dichotomy for LHomED(H)22
6.1 NP-hardness .......................................... 23
6.2 Polynomial-time algorithm .................................. 24
6.2.1 Analyzing a geometric representation of H.................... 24
6.2.2 Solving LHomED(H)................................. 31
7 Tight results for LHomED(H)32
7.1 Algorithm for LHomED(H)................................. 33
7.2 Hardness for LHomED(H).................................. 34
7.2.1 Realizing relations .................................. 35
7.2.2 Main gadgets ..................................... 35
7.2.3 Proof of Theorem 1.7: Tight lower bound under the SETH ............ 37
7.2.4 Moving between 2-vertex incomparable sets .................... 38
7.2.5 Proof of Lemma 7.7: Constructing indicators .................... 47
8 An outlook regarding homomorphism deletion without lists 49
References 49
1 Introduction
Typical NP-hard graph problems are known to be solvable in polynomial time when the input graph is
restricted to be of bounded treewidth. In many cases, the problem is actually xed-parameter tractable
(FPT) parameterized by treewidth: given a tree decomposition of width t, the problem can be solved in
time f(t)·nO(1) for some function f[6,8,9]. While early work focused on just establishing this form
of running time, more recently there is increased interest in obtaining algorithms where the function
fis growing as slowly as possible. New techniques such as representative sets, cut-and-count, subset
convolution, and generalized convolution were developed to optimize the function f(t).
On the complexity side, a line of work started by Lokshtanov, Marx, and Saurabh [36] provides
tight lower bounds for many problems where ct·nO(1)-time algorithms were known. These type
of complexity results typically show the optimality of the base cof the exponent in the best known
ct·nO(1)-time algorithm, by proving that the existence of a (c−ε)t·nO(1)-algorithm for any ε > 0
would violate the Strong Exponential-Time Hypothesis (SETH) [2,4,5,11,19,20,31,37,38,41,42]. The
goal of this paper is to unify some of these lower bounds under the umbrella of list homomorphism with
deletion problems, obtaining tight lower bounds for an expressive family of optimization problems that
include members that are essentially equivalent to fundamental problems such a Vertex Cover,Max
Cut,Odd Cycle Transversal, and Edge/Vertex Multiway Cut.
Graph homomorphisms. Given graphs Gand H, a homorphism from Gto His a (not necessarily
injective) mapping f:V(G)→V(H)that preserves the edges of G, that is, if uv ∈E(G), then
f(u)f(v)∈E(H). For example, if His the complete graph Kcon cvertices, then the homomorphisms
from Gto Hcorrespond to the proper vertex c-colorings of G: adjacent vertices have to be mapped
to distinct vertices of H. For a xed graph H, the problem Hom(H)asks if the given graph Ghas a
homomorphism to H. Motivated by the connection to c-coloring when H=Kc, the problem is also
called H-coloring [21,24,26–28,39,40].
The list version of Hom(H)is the generalization of the problem where the possible image of each
v∈V(G)is restricted [1,7,10,11,13,15,16,20,25,29,41]. This generalization allows us to express a
wider range of problems and it makes complexity results more robust. Formally, for a xed undirected
graph H(possibly with seloops), the input of the LHom(H)problem consists of a graph Gand a list
assignment L:V(G)→2V(H), the task is to decide if there is a list homomorphism ffrom (G, L)to
H, that is, a homomorphism ffrom Gto Hthat satises f(v)∈L(v)for every v∈V(G). Note that
Hom(H)is trivial if Hhas a vertex with a loop, but loops may have a non-trivial role in the LHom(H)
problem as not every list may contain the same looped vertex. In fact, it is already non-trivial to
consider the special case where His reexive [13], that is, every vertex of Hhas a loop.
The main topic of the current paper is a further generalization of LHom(H)to an optimization
problem where we are allowed to delete some edges/vertices of G. The edge-deletion variant LHomED(H)
is dened the following way: given a graph Gand a list assignment L:V(G)→2V(H), the task is to
nd a minimum set X⊆E(G)of edges such that (G\X, L)has a list homomorphism to H. In other
words, we want to nd a mapping f:V(G)→V(H)that satises f(v)∈L(v)for every v∈V(G)
and satises f(u)f(v)∈E(H)for the maximum number of edges uv of G. The vertex-deletion vari-
ant LHomVD(H)is dened analogously: here the task is to nd a minimum size set Xof vertices such
that (G−X, L)has a list homomorphism to H. The LHomVD(H)problem was considered from the
viewpoint of FPT algorithms parameterized by the number of removed vertices [3,32].
While the Hom(H)and LHom(H)problems can be seen as generalizations of vertex coloring, the
framework of deletion problems we consider here can express a wide range of fundamental optimiza-
tion problems. We show below how certain problems can be reduced to LHomED(H)or LHomVD(H)
for some xed H. The reductions mostly work in the other direction as well (we elaborate on that
in Section 2), showing that this framework contains problems that are essentially equivalent to well-
studied basic problems.
•Vertex Cover: Let H=K1be a single vertex xwithout a loop. Then Vertex Cover can
1
be expressed by LHomVD(K1)with single-element lists: as vertex xis not adjacent to itself, it
follows that for every edge uv of G, at least one of uand vhas to be deleted.
•Independent Set: As Ghas an independent set of size kif and only if it has a vertex cover of
size |V(G)| − k, the same reduction can be used.
•Max Cut: Let H=K2be two adjacent vertices without loops. Then Max Cut can be expressed
by LHomED(H)with the list V(H)at every vertex: the task is to delete the minimum number
of edges to obtain a bipartition (X, Y ), that is, to maximize the number of edges between Xand
Y.
•Odd Cycle Transversal: Let H=K2be two adjacent vertices without loops. Then Odd Cycle
Transversal can be expressed by LHomVD(H)with the list V(H)at every vertex: the task is
to delete the minimum number of vertices to obtain a bipartite graph.
•s-tMin Cut: Let Hcontain two independent vertices vsand vtwith seloops. Then s-tMin
Cut can be expressed as LHomED(H)where L(s) = {vs},L(t) = {vt}, and the list is {vs, vt}
for all remaining vertices. It is clear that sand tcannot be in the same component after removing
the solution Xfrom G.
•Edge Multiway Cut with cterminals t1,. . . ,tc: Let Hbe cindependent vertices v1,. . . ,vc
with seloops. Then the problem can be expressed as LHomED(H)where L(ti) = {vi}and
non-terminals have list {v1, . . . , vc}. It is clear that if Xis a solution of LHomED(H), then each
component of G\Xcan contain at most one terminal.
•Vertex Multiway Cut with c(undeletable) terminals t1,. . . ,tc: Let Hbe cindependent vertices
v1,. . . ,vcseloops. First we modify the graph: if terminal tiis adjacent to a vertex w, then we
replace tiby n=|V(G)|degree-1 copies adjacent to w. Then the problem can be expressed as
LHomVD(H)where the list is {vi}for each copy of tiand {v1, . . . , vc}for each non-terminal
vertex. Observe that it does not make sense to delete a copy of any terminal. Therefore, the
optimal solution to LHomVD(H)is a set of vertices, disjoint from the terminals, that separates
the original terminals.
For every xed H, our results give tight lower bounds for LHomVD(H)and LHomED(H), param-
eterized by the width of the given tree decomposition problems. This comprehensive set of results
reprove earlier lower bounds on basic problems in a uniform way, extend them to new problems that
have not been considered before (e.g., Multiway Cut), and in fact fully investigate a large, well-dened
family of problems. Earlier results in this area typically focused on specic problems or relatively minor
variants of a specic problem. Compared to that, our results focus on a family of problems that include
a diverse set of optimization problems interesting on their own right. The tight characterization also
includes an algorithmic surprise: for some LHomED(H)problems, the obvious brute force algorithm
is not optimal on its own, one needs to consider a specic form of decomposition into subproblems to
achieve the best possible algorithm.
Polynomial-time cases. The seminal work of Nešetřil and Hell [24] characterized the polynomial-
time solvable cases of Hom(H): it can be solved in polynomial time if His bipartite or has a loop, and
it is NP-hard for every other xed H. For the more general list version, we need more restrictions:
Feder, Hell, and Huang [16] showed that the problem is polynomial-time solvable if His a bi-arc graph.
Given the amount of attention this type of problems received in the literature [1,7,10,13–18,23–25,
29,30], it is somewhat surprising that the polynomial-time solvability of the deletion versions have
not been systematically studied. Therefore, our rst contribution is a polynomial-time versus NP-hard
dichotomy for LHomED(H)and LHomVD(H). As expected, these more general problems remain
polynomial-time solvable only for an even more restricted class of graphs. In particular, the reduction
above from Vertex Cover shows that LHomVD(H)becomes NP-hard already when there is a single
2
loopless vertex in Hand hence we can expect polynomial-time algorithms only for reexive graphs
H.
Theorem 1.1. The LHomVD(H)problem is polynomial-time solvable if His reexive and does not
contain any of the following:
1. three pairwise non-adjacent vertices,
2. an induced four-cycle, or
3. an induced ve-cycle.
Otherwise, LHomVD(H)is NP-hard.
Edge-deletion problems are typically easier than their vertex-deletion counterparts, but the bound-
ary line between the easier and hard cases is more dicult to characterize. This is also true in our case:
for LHomED(H), the graph Hdoes not have to be reexive to make the problem polynomial-time
solvable, hence the proof of the classication result becomes signicantly more complicated as graphs
with both reexive (i.e., looped) and irreexive (i.e., non-looped) vertices must be handled as well. We
need the following denition to state the dichotomy result. We say that the three vertices v1,v2,v3
have private neighbors if there are vertices v′
1,v′
2,v′
3(not necessarily disjoint from {v1, v2, v3}) such
that viand v′
jare adjacent if and only if i=j. In particular, if {v1, v2, v3}are independent reex-
ive vertices then they have private neighbors. Co-private neighbors are dened similarly, but i=j
is replaced by i̸=j. In particular, if {v1, v2, v3}are pairwise adjacent irreexive vertices, then they
have co-private neighbors. Finally, we say an edge is irreexive if both of its endpoints are irreexive
vertices.
Theorem 1.2. The LHomED(H)problem is polynomial time solvable if Hdoes not contain any of the
following:
1. an irreexive edge,
2. a 3-vertex set Swith private neighbors, or
3. a 3-vertex set Swith co-private neighbors.
Otherwise, LHomED(H)is NP-hard.
The proof of Theorem 1.2 exploits a delicate interplay between the geometric bi-arc representation
(in the algorithm) and the characterization by forbidden subgraphs (for hardness). While the proofs of
these dichotomy results are non-trivial, we do not consider them to be the main results of the paper.
Clearly, understanding the easy and hard cases of the problem is a necessary prerequisite for the lower
bounds we are aiming at, hence we needed to prove these dichotomy results as they were not present
in the literature in this form. We remark that LHomED(H)can be formulated as a Valued Constraint
Satisfaction Problem (VCSP) with a single binary relation, hence the existence of a polynomial-time
versus NP-hard dichotomy should follow from known results on the complexity of VCSP [33,34,43].
However, we obtain in a self-contained way a compact statement of an easily checkable classication
property with purely graph-theoretic proofs and algorithms.
Bounded-treewidth graphs, vertex deletion. Let us rst consider the vertex-deletion version
LHomVD(H)and determine how exactly the complexity of the problem depends on treewidth. We
assume that the input contains a tree decomposition of Ghaving width t, we try to determine the
smallest csuch that the problem can be solved in time ct·nO(1). This question has been investigated
for Hom(H)[42], LHom(H)[11,41], and the counting version of LHom(H)[20].
Standard dynamic programming techniques show that LHomVD(H)can be solved in time (|V(H)|+
1)t·nO(1) if a tree decomposition of width tis given: each vertex has |V(H)|possible “states” corre-
sponding to where it is mapped to, plus one more state corresponding to deleting the vertex. For some
H, this naive algorithm can be improved the following way. First, if every vertex in Ghas a list of size
3
摘要：
展开>>
收起<<
Listhomomorphismsbydeletingedgesandvertices:tightcomplexityboundsforbounded-treewidthgraphsBarışCanEsmer∗JacobFocke∗DánielMarx∗PawełRzążewski†AbstractThegoalofthispaperistoinvestigateafamilyofoptimizationproblemsarisingfromlistho-momorphisms,andtounderstandwhatthebestpossiblealgorithmsareifwerestric...
声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！
相关推荐
-
公司营销部领导述职述廉报告VIP免费
2024-12-03 15 -
100套述职述廉述法述学框架提纲VIP免费
2024-12-03 15 -
20220106政府党组班子党史学习教育专题民主生活会“五个带头”对照检查材料VIP免费
2024-12-03 12 -
20220106县纪委监委领导班子党史学习教育专题民主生活会对照检查材料VIP免费
2024-12-03 16 -
A文秘笔杆子工作资料汇编手册（近70000字）VIP免费
2024-12-03 12 -
20220106县领导班子党史学习教育专题民主生活会对照检查材料VIP免费
2024-12-03 15 -
经济开发区党工委书记管委会主任述学述职述廉述法报告VIP免费
2024-12-03 54 -
20220106政府领导专题民主生活会五个方面对照检查材料VIP免费
2024-12-03 21 -
派出所教导员述职述廉报告6篇VIP免费
2024-12-03 18 -
民主生活会对县委班子及其成员批评意见清单VIP免费
2024-12-03 63
分类：图书资源
价格：10玖币
属性：55 页
大小：1.68MB
格式：PDF
时间：2025-05-02
渝公网安备50010702506394
