Complexity of Finding Embeddings in a k-Tree

DOI10.1137/0608024zbMath0611.05022OpenAlexW2085550081WikidataQ29013861 ScholiaQ29013861MaRDI QIDQ3751595

Stefan Arnborg, Andrzej Proskurowski, Derek Gordon Corneil

Publication date: 1987

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0608024

zbMATH Keywords

NP completeness algorithm complexity k-tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

Improving robustness of next-hop routing, Minimal triangulations of graphs: a survey, Safe separators for treewidth, Lex M versus MCS-M, Trees, grids, and MSO decidability: from graphs to matroids, Tractability in constraint satisfaction problems: a survey, A review of combinatorial problems arising in feedforward neural network design, Improved self-reduction algorithms for graphs with bounded treewidth, The nonexistence of reduction rules giving an embedding into a $k$-tree, Regularity and locality in $k$-terminal graphs, $k$-NLC graphs and polynomial algorithms, A polynomial time algorithm to compute the connected treewidth of a series-parallel graph, Treewidth of cocomparability graphs and a new order-theoretic parameter, Finding the maximum common subgraph of a partial $k$-tree and a graph with a polynomially bounded number of spanning trees, A comparison of graphical techniques for decision analysis, Approximate tree decompositions of planar graphs in linear time, Approximation algorithms for treewidth, Probability propagation, Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs, On embedding graphs in trees, Online promise problems with online width metrics, Symbolic techniques in satisfiability solving, Tree clustering for constraint networks, Linear time algorithms for NP-hard problems restricted to partial k- trees, Treewidth for graphs with small chordality, Characterizations and algorithmic applications of chordal graph embeddings, Algorithmic uses of the Feferman-Vaught theorem, Achievable sets, brambles, and sparse treewidth obstructions, An $\mathcal O(n^2)$-time algorithm for the minimal interval completion problem, On treewidth and minimum fill-in of asteroidal triple-free graphs, Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs, Courcelle's theorem -- a game-theoretic approach, A new probabilistic constraint logic programming language based on a generalised distribution semantics, Practical algorithms for branch-decompositions of planar graphs, Decomposition width of matroids, Creating non-minimal triangulations for use in inference in mixed stochastic/deterministic graphical models, Interval degree and bandwidth of a graph, Computing bond orders in molecule graphs, An efficient tree decomposition method for permanents and mixed discriminants, Approximating the treewidth of AT-free graphs., Splitting a graph into disjoint induced paths or cycles., Constant-degree graph expansions that preserve treewidth, Directed NLC-width, The dag-width of directed graphs, Forbidden minors characterization of partial 3-trees, Chordal embeddings of planar graphs, A comparison of boundary graph grammars and context-free hypergraph grammars, A logic-based analysis of Dempster-Shafer theory, Faster computation of the Robinson-Foulds distance between phylogenetic networks, On the extension of a partial metric to a tree metric, Treewidth governs the complexity of target set selection, PRM inference using Jaffray \& Faÿ's local conditioning, Treewidth lower bounds with brambles, Maximum $k$-splittable $s, t$-flows, Practical algorithms for MSO model-checking on tree-decomposable graphs, Monotonicity of non-deterministic graph searching, An annotated bibliography on guaranteed graph searching, Distributed chasing of network intruders, Approximation algorithms for digraph width parameters, Algorithms for recognition of regular properties and decomposition of recursive graph families, The complexity of minimum-length path decompositions, $k$-chordal graphs: from cops and robber to compact routing via treewidth, Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families, The complexity of subgraph isomorphism for classes of partial k-trees, Characterization and complexity of uniformly nonprimitive labeled 2-structures, The complexity of pursuit on a graph, Mixed searching and proper-path-width, Canonical representations of partial 2- and 3-trees, \textsc{ToTo}: an open database for computation, storage and retrieval of tree decompositions, Monadic second-order evaluations on tree-decomposable graphs, Precoloring extension. I: Interval graphs, On the SPANNING $k$-TREE problem, On the complexity of finding iso- and other morphisms for partial $k$- trees, Efficient computation of the characteristic polynomial of a tree and related tasks, Studies on hypergraphs. I: Hyperforests, Complexity of path-forming games, Minimum fill-in and treewidth of split $+ ke$ and split $+kv$ graphs, Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in $O(n^{1+\epsilon})$ time, Treewidth and minimum fill-in on permutation graphs in linear time, Exact and approximate bandwidth, Upper and lower bounds for finding connected motifs in vertex-colored graphs, Understanding the scalability of Bayesian network inference using clique tree growth curves, Complexity of secure sets, Perspectives on the theory and practice of belief functions, All structured programs have small tree width and good register allocation, Upper bounds on the size of obstructions and intertwines, Nondeterministic graph searching: from pathwidth to treewidth, A partial k-arboretum of graphs with bounded treewidth, Computational properties of argument systems satisfying graph-theoretic constraints, Triangulating graphs with few $P_4$'s, Conjunctive query containment revisited, Edge and node searching problems on trees, A faster tree-decomposition based algorithm for counting linear extensions, On hyperedge replacement and BNLC graph grammars, On the pathwidth of chordal graphs, On some optimization problems on $k$-trees and partial $k$-trees, Counting $H-$colorings of partial $k-$trees, Listing all potential maximal cliques of a graph, Minimal acyclic forbidden minors for the family of graphs with bounded path-width, Hybrid backtracking bounded by tree-decomposition of constraint networks, Seeing Arboretum for the (partial k-) Trees, As Time Goes By: Reflections on Treewidth for Temporal Graphs, Computing Tree Decompositions, Experimental Analysis of Treewidth, Efficient Problem Solving on Tree Decompositions Using Binary Decision Diagrams, An Improvement of Reed’s Treewidth Approximation, Learning Bounded Tree-Width Bayesian Networks via Sampling, Sequential and parallel algorithms for embedding problems on classes of partial k-trees, The pathwidth and treewidth of cographs, Canonical representations of partial 2-and 3-trees, Fixed-Parameter Tractability of Treewidth and Pathwidth, On the k-rainbow domination in graphs with bounded tree-width, Constructing Brambles, A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth, Graphical Models and Message-Passing Algorithms: Some Introductory Lectures, Unnamed Item, Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth, Graph decompositions and tree automata in reasoning with uncertainty, Theory of evidence ? A survey of its mathematical foundations, applications and computational aspects, Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth, Computing Bond Types in Molecule Graphs, Constructive linear time algorithms for branchwidth, Independent sets in asteroidal triple-free graphs, The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues, Decomposability helps for deciding logics of knowledge and belief, Efficient algorithms for solving systems of linear equations and path problems, Adapting the Directed Grid Theorem into an FPT Algorithm, Chordal Networks of Polynomial Ideals, Characterizations and directed path-width of sequence digraphs, Metropolized Knockoff Sampling, A forbidden pair for connected graphs to have spanning k‐trees, Treelength of series-parallel graphs, The power of non-ground rules in Answer Set Programming, Unnamed Item, Unnamed Item, Shape Measures of Random Increasing k-trees, Parameters Tied to Treewidth, Hardness of computing width parameters based on branch decompositions over the vertex set, Minimum size tree-decompositions, On the Maximum Weight Minimal Separator, The “Art of Trellis Decoding” Is NP-Hard, Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs, Weighted Treewidth Algorithmic Techniques and Results, Treewidth and pathwidth of permutation graphs, Hardness of computing width parameters based on branch decompositions over the vertex set, LP Formulations for Polynomial Optimization Problems, Decomposing SAT Instances with Pseudo Backbones, Fifty years of the spectrum problem: survey and new results, Graphs of Bounded Treewidth Can Be Canonized in $\mbox{{\sf AC}$^1$}$, An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents, A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions, Minimum size tree-decompositions, How to use the minimal separators of a graph for its chordal triangulation, Parallel algorithms with optimal speedup for bounded treewidth, Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization, Unnamed Item, An algorithm for simultaneous backbone threading and side-chain packing, Finding Low-rank Solutions of Sparse Linear Matrix Inequalities using Convex Optimization, To Approximate Treewidth, Use Treelength!, A sufficiently fast algorithm for finding close to optimal clique trees, Topological parameters for time-space tradeoff, Tree-decompositions of small pathwidth, Linear ordering based MIP formulations for the vertex separation or pathwidth problem, Unnamed Item, Faster and enhanced inclusion-minimal cograph completion, Using a hybrid of exact and genetic algorithms to design survivable networks, Tree-decompositions of small pathwidth, Two strikes against perfect phylogeny, Graph isomorphism restricted by lists, Parameterised complexity of model checking and satisfiability in propositional dependence logic, Postoptimal Analysis in Nonserial Dynamic Programming, Characterizing Marginalization and Incremental Operations on the Bayes Tree, Faster Computation of Path-Width, Exact algorithms for a discrete metric labeling problem, Encoding Treewidth into SAT, Power Indices in Spanning Connectivity Games, An Experimental Study of the Treewidth of Real-World Graph Data, The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs, Heuristic and metaheuristic methods for computing graph treewidth, FPT is characterized by useful obstruction sets, Exact or approximate inference in graphical models: why the choice is dictated by the treewidth, and how variable elimination can be exploited, Integrating and Sampling Cuts in Bounded Treewidth Graphs, A Polynomial Time Algorithm for Bounded Directed Pathwidth, Finding good tree decompositions by local search, Efficient Pattern Matching on Graph Patterns of Bounded Treewidth, Searching for a Visible, Lazy Fugitive, Positive-Instance Driven Dynamic Programming for Treewidth., Unnamed Item, Unnamed Item, Digraphs of Bounded Width, AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH, On the Tree-Width of Planar Graphs, A Logical Approach to Constraint Satisfaction, Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs, Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure, Unnamed Item, Unnamed Item, THE POINT-SET EMBEDDABILITY PROBLEM FOR PLANE GRAPHS, The Power of the Weisfeiler--Leman Algorithm to Decompose Graphs, Edge-treewidth: algorithmic and combinatorial properties, Approximating Pathwidth for Graphs of Small Treewidth, Tangle bases: Revisited, Approximating the bandwidth for asteroidal triple-free graphs, A new global algorithm for max-cut problem with chordal sparsity, Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks, Stability, vertex stability, and unfrozenness for special graph classes, Solving infinite-domain CSPs using the patchwork property, On integer linear programs for treewidth based on perfect elimination orderings, Treewidth of the $q$-Kneser graphs, Domino treewidth, A lower bound for treewidth and its consequences, Tree-width and path-width of comparability graphs of interval orders, Bounded tree-width and LOGCFL, Locating Eigenvalues of Symmetric Matrices - A Survey, Space efficient algorithm for solving reachability using tree decomposition and separators, NC-algorithms for graphs with small treewidth, The monadic second-order logic of graphs : Definable sets of finite graphs, Path cover problems with length cost, Treewidth of the generalized Kneser graphs, The parametrized complexity of knot polynomials, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, Degree-constrained decompositions of graphs: Bounded treewidth and planarity, Tree-decompositions with bags of small diameter, Efficient learning of Bayesian networks with bounded tree-width, Linear-time minimal cograph editing, Deleting edges to restrict the size of an epidemic: a new application for treewidth, Treewidth distance on phylogenetic trees, Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs, Finding all leftmost separators of size $\le k$, A parameterized view on the complexity of dependence logic, Path cover problems with length cost, Treewidth computation and extremal combinatorics, Unnamed Item, Triangulating graphs without asteroidal triples, The $k$-path coloring problem in graphs of bounded treewidth: an application in integrated circuit manufacturing, Deleting edges to restrict the size of an epidemic in temporal networks, Probabilistic reasoning with graphical security models, On quasi-planar graphs: clique-width and logical description, Lpopt: a rule optimization tool for answer set programming, Propositional semantics for disjunctive logic programs, Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all?, Treewidth and gonality of glued grid graphs, From tree-decompositions to clique-width terms, The connected critical node problem, Dependence modelling in ultra high dimensions with vine copulas and the graphical Lasso, Improved Steiner tree algorithms for bounded treewidth, Recoloring graphs via tree decompositions, Polynomial time algorithms for variants of graph matching on partial $k$-trees, Positive-instance driven dynamic programming for treewidth, Probabilistic and exact frequent subtree mining in graphs beyond forests, Computing partial hypergraphs of bounded width, On strict brambles, Chordal graphs in triangular decomposition in top-down style, Structural parameters for scheduling with assignment restrictions, Combining restarts, nogoods and bag-connected decompositions for solving csps, Digraphs of bounded elimination width, Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth, A polynomial-time algorithm to compute Turaev-Viro invariants $\mathrm{TV}_{4,q}$ of 3-manifolds with bounded first Betti number, Domination and total domination on asteroidal triple-free graphs, A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs, On the complexity of planning for agent teams and its implications for single agent planning, Equitable list tree-coloring of bounded treewidth graphs, How to compute digraph width measures on directed co-graphs, Turbocharging treewidth heuristics, Tractability of most probable explanations in multidimensional Bayesian network classifiers, On efficiently solvable cases of quantum $k$-SAT, On permuted super-secondary structures of transmembrane $\beta$-barrel proteins, Bounded-width QBF is PSPACE-complete, Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs, Controlled generation of hard and easy Bayesian networks: Impact on maximal clique size in tree clustering, An improvement of Reed's treewidth approximation, Line graphs of bounded clique-width, Node-searching problem on block graphs, Visualizing SAT instances and runs of the DPLL algorithm, Efficiently enumerating minimal triangulations, On the complexity of computing treebreadth, Counting truth assignments of formulas of bounded tree-width or clique-width, A branch-and-price-and-cut method for computing an optimal bramble, On tradeoffs between width- and fill-like graph parameters, Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem, Tree decomposition and discrete optimization problems: a survey, An extended tree-width notion for directed graphs related to the computation of permanents, Minimal separators in extended $P_4$-laden graphs, Two feedback problems for graphs with bounded tree-width, Tree decompositions with small cost, Computing the branchwidth of interval graphs, Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable, On some tractable and hard instances for partial incentives and target set selection, An exact method for graph coloring, Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial $k$-trees, The basic algorithm for pseudo-Boolean programming revisited, Linear layouts measuring neighbourhoods in graphs, The complexity of graph languages generated by hyperedge replacement, Treewidth, crushing and hyperbolic volume, A $c^k n$ 5-Approximation Algorithm for Treewidth, Variable neighborhood search for graphical model energy minimization, Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion, Tree-width, path-width, and cutwidth, Complete-subgraph-transversal-sets problem on bounded treewidth graphs, Inference in belief networks: A procedural guide, Binary join trees for computing marginals in the Shenoy-Shafer architecture, Parameterized complexity of vertex colouring, Exploiting Chordal Structure in Polynomial Ideals: A Gröbner Bases Approach, Minimum fill-in: inapproximability and almost tight lower bounds, On the Complexity of Computing Treebreadth, Algorithms and complexity for Turaev-Viro invariants, Learning tractable Bayesian networks in the space of elimination orders, Comparing linear width parameters for directed graphs, On the hardness of palletizing bins using FIFO queues, On the maximum weight minimal separator, Revising Johnson's table for the 21st century, Directed tree-width, Methods for solving reasoning problems in abstract argumentation -- a survey, On sparsification for computing treewidth, Constructing NP-intermediate problems by blowing holes with parameters of various properties, An implementation of the iterative proportional fitting procedure by propagation trees., On the impact of treewidth in the computational complexity of freezing dynamics, New limits of treewidth-based tractability in optimization

Cites Work