Zobrazeno 1 - 10
of 33
pro vyhledávání: '"FOCKE, JACOB"'
Autor:
Focke, Jacob, Frei, Fabian, Li, Shaohua, Marx, Dániel, Schepper, Philipp, Sharma, Roohani, Węgrzycki, Karol
We study a general family of problems that form a common generalization of classic hitting (also referred to as covering or transversal) and packing problems. An instance of X-HitPack asks: Can removing k (deletable) vertices of a graph G prevent us
Externí odkaz:
http://arxiv.org/abs/2402.14927
It is known for many algorithmic problems that if a tree decomposition of width $t$ is given in the input, then the problem can be solved with exponential dependence on $t$. A line of research by Lokshtanov, Marx, and Saurabh [SODA 2011] produced low
Externí odkaz:
http://arxiv.org/abs/2402.07331
The Multicut problem asks for a minimum cut separating certain pairs of vertices: formally, given a graph $G$ and demand graph $H$ on a set $T\subseteq V(G)$ of terminals, the task is to find a minimum-weight set $C$ of edges of $G$ such that wheneve
Externí odkaz:
http://arxiv.org/abs/2312.11086
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity
We study the problem of counting answers to unions of conjunctive queries (UCQs) under structural restrictions on the input query. Concretely, given a class C of UCQs, the problem #UCQ(C) provides as input a UCQ Q in C and a database D and the proble
Externí odkaz:
http://arxiv.org/abs/2311.10634
Autor:
Focke, Jacob, Marx, Dániel, Inerney, Fionn Mc, Neuen, Daniel, Sankar, Govind S., Schepper, Philipp, Wellnitz, Philip
For a well-studied family of domination-type problems, in bounded-treewidth graphs, we investigate whether it is possible to find faster algorithms. For sets $\sigma,\rho$ of non-negative integers, a $(\sigma,\rho)$-set of a graph $G$ is a set $S$ of
Externí odkaz:
http://arxiv.org/abs/2306.03640
Autor:
Focke, Jacob, Marx, Dániel, Inerney, Fionn Mc, Neuen, Daniel, Sankar, Govind S., Schepper, Philipp, Wellnitz, Philip
We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets $\sigma,\rho$ of non-negative integers, a $(\sigma,\rho)$-set of a graph $G$ is a set $S$ of vertices such that $|N(u
Externí odkaz:
http://arxiv.org/abs/2211.04278
The goal of this paper is to investigate a family of optimization problems arising from list homomorphisms, and to understand what the best possible algorithms are if we restrict the problem to bounded-treewidth graphs. For a fixed $H$, the input of
Externí odkaz:
http://arxiv.org/abs/2210.10677
Autor:
Focke, Jacob, Roth, Marc
We study the computational complexity of the problem $\#\text{IndSub}(\Phi)$ of counting $k$-vertex induced subgraphs of a graph $G$ that satisfy a graph property $\Phi$. Our main result establishes an exhaustive and explicit classification for all h
Externí odkaz:
http://arxiv.org/abs/2111.02277
The goal of this work is to give precise bounds on the counting complexity of a family of generalized coloring problems (list homomorphisms) on bounded-treewidth graphs. Given graphs $G$, $H$, and lists $L(v)\subseteq V(H)$ for every $v\in V(G)$, a {
Externí odkaz:
http://arxiv.org/abs/2107.06889
We study the complexity of approximating the number of answers to a small query $\varphi$ in a large database $\mathcal{D}$. We establish an exhaustive classification into tractable and intractable cases if $\varphi$ is a conjunctive query with diseq
Externí odkaz:
http://arxiv.org/abs/2103.12468