An Effective Upperbound on Treewidth Using Partial Fill-in of Separators
Partitioning a graph using graph separators, and particularly clique separators, are well-known techniques to decompose a graph into smaller units which can be treated independently. It was previously known that the treewidth was bounded above by the sum of the size of the separator plus the treewidth of disjoint components, and this was obtained by the heuristic of filling in all edges of the separator making it into a clique. In this paper, we present a new, tighter upper bound on the treewidth of a graph obtained by only partially filling in the edges of a separator. In particular, the method completes just those pairs of separator vertices that are adjacent to a common component, and indicates a more effective heuristic than filling in the entire separator. We discuss the relevance of this result for combinatorial algorithms and give an example of how the tighter bound can be exploited in the domain of constraint satisfaction problems.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Computing All-Pairs Shortest Paths by Leveraging Low Treewidth
We present two new and efficient algorithms for computing all-pairs shortest paths. The algorithms operate on directed graphs with real (possibly negative) weights. They make use of directed path consistency along a vert…
AllSchedulingThe Complexity of Optimizing Atomic Congestion
Atomic congestion games are a classic topic in network design, routing, and algorithmic game theory, and are capable of modeling congestion and flow optimization tasks in various application areas. While both the price o…
On the Complexity of Counterfactual Reasoning
We study the computational complexity of counterfactual reasoning in relation to the complexity of associational and interventional reasoning on structural causal models (SCMs). We show that counterfactual reasoning is n…
counterfactualCounterfactual ReasoningCan Separators Improve Chain-of-Thought Prompting?
Chain-of-thought (CoT) prompting is a simple and effective method for improving the reasoning capabilities of Large Language Models (LLMs). The basic idea of CoT is to let LLMs break down their thought processes step-by-…
8kGSM8KSeparator Injection Attack: Uncovering Dialogue Biases in Large Language Models Caused by Role Separators
Conversational large language models (LLMs) have gained widespread attention due to their instruction-following capabilities. To ensure conversational LLMs follow instructions, role separators are employed to distinguish…
Instruction Following