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 dene 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 specic type of decomposition of Hshows that there are graphs Hwhere LHomED(H)

can be solved signicantly more eciently 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 aliated 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.

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 seloops), 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 satises 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 reexive [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 dened 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 satises f(v)∈L(v)for every v∈V(G)

and satises f(u)f(v)∈E(H)for the maximum number of edges uv of G. The vertex-deletion vari-

ant LHomVD(H)is dened 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

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

•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 seloops. 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 seloops. 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,. . . ,vcseloops. 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-dened

family of problems. Earlier results in this area typically focused on specic problems or relatively minor

variants of a specic 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 specic 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

loopless vertex in Hand hence we can expect polynomial-time algorithms only for reexive graphs

Theorem 1.1. The LHomVD(H)problem is polynomial-time solvable if His reexive 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 dicult to characterize. This is also true in our case:

for LHomED(H), the graph Hdoes not have to be reexive to make the problem polynomial-time

solvable, hence the proof of the classication result becomes signicantly more complicated as graphs

with both reexive (i.e., looped) and irreexive (i.e., non-looped) vertices must be handled as well. We

need the following denition 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 reex-

ive vertices then they have private neighbors. Co-private neighbors are dened similarly, but i=j

is replaced by i̸=j. In particular, if {v1, v2, v3}are pairwise adjacent irreexive vertices, then they

have co-private neighbors. Finally, we say an edge is irreexive if both of its endpoints are irreexive

vertices.

Theorem 1.2. The LHomED(H)problem is polynomial time solvable if Hdoes not contain any of the

following:

1. an irreexive 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 classication

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

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Listhomomorphismsbydeletingedgesandvertices:tightcomplexityboundsforbounded-treewidthgraphsBarışCanEsmer∗JacobFocke∗DánielMarx∗PawełRzążewski†AbstractThegoalofthispaperistoinvestigateafamilyofoptimizationproblemsarisingfromlistho-momorphisms,andtounderstandwhatthebestpossiblealgorithmsareifwerestric...

展开>> 收起<<

List homomorphisms by deleting edges and vertices tight complexity bounds for bounded-treewidth graphs Barış Can EsmerJacob FockeDániel MarxPaweł Rzążewski.pdf

共55页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

List homomorphisms by deleting edges and vertices tight complexity bounds for bounded-treewidth graphs Barış Can EsmerJacob FockeDániel MarxPaweł Rzążewski

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: