We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets σ, ρ of non-negative integers, a (σ, ρ)-set of a graph G is a set S of vertices ...
详细信息
We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets σ, ρ of non-negative integers, a (σ, ρ)-set of a graph G is a set S of vertices such that |N(u) ∩S| ∈ σ for every u ∈ S, and |N(v) ∩S| ∈ ρ for every v ∉ S. The problem of finding a (σ, ρ)-set (of a certain size) unifies standard problems such as Independent Set, Dominating Set, Independent Dominating Set, and many others. For all pairs of finite or cofinite sets (σ, ρ), we determine (under standard complexity assumptions) the best possible value cσ,ρ such that there is an algorithm that counts (σ, ρ)sets in time ctwσ,ρ · nO(1) (if a tree decomposition of width tw is given in the input). Let stop denote the largest element of σ if σ is finite, or the largest missing integer +1 if σ is cofinite;rtop is defined analogously for ρ. Surprisingly, cσ,ρ is often significantly smaller than the natural bound stop + rtop + 2 achieved by existing algorithms [van Rooij, 2020]. Toward defining cσ,ρ, we say that (σ, ρ) is m-structured if there is a pair (α, β) such that every integer in σ equals α mod m, and every integer in ρ equals β mod m. Then, setting • cσ,ρ = stop + rtop + 2 if (σ, ρ) is not m-structured for any m ≥ 2, • cσ,ρ = max{stop, rtop}+ 2 if (σ, ρ) is 2-structured, but not m-structured for any m ≥ 3, and stop = rtop is even, and • cσ,ρ = max{stop, rtop} + 1, otherwise, we provide algorithms counting (σ, ρ)-sets in time ctwσ,ρ · nO(1). For example, for the Exact Independent Dominating Set problem (also known as Perfect Code) corresponding to σ = algorithms and ρ = algorithms, this improves the 3tw · nO(1) algorithm of van Rooij to 2tw · nO(1). Despite the unusually delicate definition of cσ,ρ, an accompanying paper shows that our algorithms are most likely optimal, that is, for any pair (σ, ρ) of finite or cofinite sets where the problem is non-trivial, and any Ε > 0, a (cσ,ρ−Ε)tw ·nO(1)-algorithm counting the number of (σ, ρ)-sets would violate the C
We continue the study of the area requirement of convex straight-line grid drawings of 3-connected plane graphs, which has been intensively investigated in the last decades. Motivated by applications, such as graph ed...
A unit disk intersection representation (UDR) of a graph G represents each vertex of G as a unit disk in the plane, such that two disks intersect if and only if their vertices are adjacent in G. A UDR with interior-di...
详细信息
The problem of extending partial geometric graph representations such as plane graphs has received considerable attention in recent years. In particular, given a graph G, a connected subgraph H of G and a drawing H of...
详细信息
We study two "above guarantee" versions of the classical Longest Path problem on undirected and directed graphs and obtain the following results. In the first variant of Longest Path that we study, called Lo...
详细信息
Motivated by a game of Battleship, we consider the problem of efficiently hitting a ship of an uncertain shape within a large playing board. Formally, we fix a dimension d ϵ {1, 2}. A ship is a subset of d. Given a fa...
详细信息
The page-number of a directed acyclic graph (a DAG, for short) is the minimum k for which the DAG has a topological order and a k-coloring of its edges such that no two edges of the same color cross, i.e., have altern...
详细信息
A k-page book embedding of a graph G draws the vertices of G on a line and the edges on k half-planes (called pages) bounded by this line, such that no two edges on the same page cross. We study the problem of determi...
详细信息
A map graph is a graph admitting a representation in which vertices are nations on a spherical map and edges are shared curve segments or points between nations. We present an explicit fixed-parameter tractable algori...
详细信息
We consider edge modification problems towards block and strictly chordal graphs, where one is given an undirected graph G = (V, E) and an integer k ∈ N and seeks to edit (add or delete) at most k edges from G to obt...
详细信息
暂无评论