Questions tagged [graph-minor]
The graph-minor tag has no usage guidance.
33
questions
2
votes
1
answer
112
views
Embedding degree-3 planar graphs as topological minors in wall graphs in polynomial time
For a proof, I need the fact that we can efficiently embed an input planar graph into a representative of a specific family of high-treewidth graphs. Specifically, I need an embedding as a topological ...
- 8,816
0
votes
0
answers
65
views
Maintaining a $K_{3,3}$-minor-free graph
Suppose we are given that an undirected, connected graph $G$ is $K_{3,3}$-minor-free.
Let $a,b\in V(G)$ be non-adjacent vertices.
Under what conditions is the graph that results by adding the edge $(a,...
- 95
5
votes
0
answers
160
views
Complexity of a problem related to Friedman's TREE(k) function?
Background
Given two rooted, vertex-colored trees $T_1, T_2$, $T_1$ is color-preserving inf-embeddle in $T_2$, which we'll denote $T_1 \leq T_2$, if there is an injective $f \colon V(T_1) \to V(T_2)$ ...
- 36.7k
9
votes
1
answer
221
views
What is the best upper bound on the running time of the graph minor algorithm?
A cornerstone of the graph minor theory is an algorithm that, given undirected graphs $G, H$, runs in time $f(|H|)poly(|G|)$, and determines whether $H$ is a minor of $G$ or not. It has been obtained ...
- 91
6
votes
0
answers
287
views
Grid-Minor Theorem of Robertson and Seymour and its Algorithmic Applications
Graph-Minor Theorem of Robertson and Seymour [1] states that if graph G has large treewidth, then it contains a large grid as minor. Most approximation results on general classes of graphs with ...
user17918
9
votes
1
answer
496
views
Is there an algorithm that finds the forbidden minors?
The Robertson–Seymour theorem says that any minor-closed family $\mathcal G$ of graphs can be characterized by finitely many forbidden minors.
Is there an algorithm that for an input $\mathcal G$ ...
- 14k
13
votes
1
answer
1k
views
Number of 4 cycles
Let $C_4$ be a cycle with four vertices. For an arbitrary graph $G$ with $n$ vertices and m edges say $m>n\sqrt n$, how many $C_4$s exist? Is there a lower bound for this?
5
votes
0
answers
86
views
Complexity of bounded degree full contraction
This paper defines the problem $\mathrm{B{\scriptsize OUNDED} \ D{\scriptsize EGREE}\ C{\scriptsize ONTRACTION}}$ as follows:
Instance: A graph $G$ and two integers $d$ and $k$.
Question: Is there a ...
- 778
4
votes
1
answer
166
views
Properties of toroidal graph
I am interested in work pertaining to graphs that have genus 1 i.e. toroidal graphs. Specifically, i am trying to find answers to the questions below.
Since toroidal graphs can be recognized in $P$ , ...
- 1,006
4
votes
1
answer
231
views
Minor and subdivision
It is a well known fact that if $H$ is a graph of maximum degree 3, then $H$ is a minor of a graph $G$ if and only if $H$ is a topological minor of $G$.
Moreover, a graph $G$ has one of $K_{3,3}$ or $...
- 1,006
10
votes
2
answers
361
views
Finding subgraphs with high treewidth and constant degree
I am given a graph $G$ with treewidth $k$ and arbitrary degree, and I would like to find a subgraph $H$ of $G$ (not necessarily an induced subgraph) such that $H$ has constant degree and its treewidth ...
- 8,816
6
votes
0
answers
154
views
Book/ Monograph on graph minor theory [Reference request]
I want to learn graph minor theory. Now i have read the very basic things and the overview from the book of R.Diestel but proceeding further is getting difficult. Currently, I am also following the ...
- 1,006
4
votes
1
answer
133
views
Hadwiger number under matching contraction
Given a graph $G$ with Hadwiger number $h(G)$ and a matching $M$ of $G$. Let $G/M$ be the simple graph obtained by contracting $M$. I am looking for a lower bound on the Hadwiger number of $G/M$ as a ...
- 305
9
votes
2
answers
292
views
Something-Treewidth Property
Let $s$ be a graph parameter (ex. diameter, domination number, etc)
A family $\mathcal{F}$ of graphs has the $s$-treewidth property if there is a function $f$ such that for any graph
$G\in \mathcal{...
- 616
19
votes
1
answer
459
views
Minor closed properties that are explicitly MSO expressible
Below, MSO denotes the monadic second order logic of graphs with vertex-set and edge-set quantifications.
Let $\mathcal{F}$ be a minor closed family of graphs. It follows from Robertson and Seymour'...
13
votes
1
answer
360
views
Does treewidth $k$ imply the existence of a $K_{1,k}$ minor?
Let $k$ be fixed, and let $G$ be a (connected) graph. If I'm not mistaken, it follows from the work of Bodlaender [1, Theorem 3.11] that if the treewidth of $G$ is roughly at least $2k^3$, then $G$ ...
- 3,160
5
votes
1
answer
330
views
Sparser Bipartite graphs?
Maximal Planar Bipartite graphs are sparser than maximal planar graphs. For which other classes of graphs are maximal Bipartite members sparser than arbitrary maximal members.
Let $\mathcal{C}$ be a ...
- 2,299
9
votes
2
answers
283
views
Understanding graph minor theorem
This question is two-fold, and is mainly reference-oriented:
Is there somewhere where the main intuitions for proving graph minor theorem are given, without going too much into the details? I know ...
- 8,588
19
votes
1
answer
505
views
Algorithmic advantages of pathwidth over treewidth
Treewidth plays an important role in FPT algorithms, in part because many problems are FPT parameterized by treewidth. A related, more restricted, notion is that of pathwidth. If a graph has pathwidth ...
- 3,256
8
votes
2
answers
206
views
Do graphs with large number of paths contain large chain minor?
Definition: A "$k$-chain" is a multi-graph obtained from a path of length $k$ by duplicating every edge.
Note that the number of paths between two endpoints of a $k$-chain is $2^k.$
Question: Let $G$...
- 143
18
votes
1
answer
282
views
A good Library for testing whether a minors exists in a graph?
I would like to know if there are any free graph libraries for testing whether a specific set of minors exists in a given graph?
- 289
13
votes
2
answers
276
views
Complexity of computing a densest minor
Consider the following problem.
Input: An undirected graph $G=(V,E)$.
Output: A graph $H$ which is a minor of $G$ with the highest edge density among all minors of $G$, i.e., with the highest ratio $|...
- 1,096
4
votes
1
answer
188
views
H-induced Containment problem
In the paper "On Graph Contractions and Induced Minors" by Pim van't Hof et al. they showed that this problem is fi xed parameter tractable in |VH| if G belongs to any non-trivial minor-closed graph ...
- 1,006
6
votes
1
answer
340
views
Complexity of finding large grid minors
What is the complexity of finding the largest $k\times k$ grid graph that is a minor of a given graph $G$? It is FPT in $k$, and it seems likely to be NP-hard (or NP-complete in a decision version ...
- 50.8k
8
votes
2
answers
585
views
Grid minor in digraphs
Thor Johnson, et al, in their paper: Directed Tree Width, introduced a definition for directed grid $J_k$, and they conjectured:
$(5.1)$ For every integer $k$ there exists an integer $N$ such that ...
- 3,440
11
votes
1
answer
426
views
MSO properties, planar graphs and minor-free graphs
Courcelle's theorem states that every graph property definable in monadic second-order logic can be decided in linear time on graphs of bounded treewidth. This is one of the most well-known ...
- 10.6k
6
votes
0
answers
331
views
Citation request: Complexity of determining if a graph exists with a minor but no subgraph in set
I'm looking for a reference of the complexity of the following problem.
Let our input $C$ be a finite set of graphs. Is there a graph $G$ such that:
$G$ has a minor in $C$
$G$ has no subgraph in $C$?...
- 343
15
votes
1
answer
513
views
Decomposing graphs of genus one
Planar graphs are $K_{3,3}$-free. Such graphs can be decomposed into tri-connected components, which are known to be either planar or $K_5$ components.
Is there such a "nice" decomposition of ...
- 10.6k
17
votes
2
answers
1k
views
Forbidden minors for bounded treewidth graphs
This question is similar to one of my previous questions. It is known that $K_{t+2}$ is a forbidden minor for graphs of treewidth at most $t$.
Is there a nicely-constructed, parameterized, ...
- 10.6k
17
votes
1
answer
2k
views
Forbidden minors for bounded genus graphs
It is well known that $K_5$ and $K_{3,3}$ are forbidden minors for planar graphs. There are hundreds of forbidden minors for graphs embeddable on a torus. The number of forbidden minors for graphs ...
- 10.6k
12
votes
1
answer
2k
views
Citation showing minors are topological minors for subcubic graphs
If $G$ is a graph with maximum degree 3 and is a minor of $H$, then $G$ is a topological minor of $H$.
Wikipedia cites this result from Diestel's "Graph Theory". It's listed as Prop 1.7.4 in the ...
- 343
3
votes
0
answers
205
views
Name for relationship where one graph is a minor usually implies another is?
Let $G$ and $H$ be graphs with the following relationship: for some $k$, after you perform at least $k$ arbitrary subdivisions of the edges of $G$ (or the edges produced through subdivision), $H$ must ...
- 343
31
votes
5
answers
1k
views
what is easy for minor-excluded graphs?
Approximating number of colorings seems to be easy on minor-excluded graphs using algorithm by Jung/Shah. What are other examples of problems that are hard on general graphs but easy on minor-excluded ...
- 4,671