2022 Developer Survey is open! Take survey.

Questions tagged [graph-minor]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
9 votes
1 answer
208 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 ...
user avatar
  • 91
6 votes
0 answers
176 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 ...
user avatar
9 votes
1 answer
440 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$ ...
user avatar
  • 13.5k
12 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?
user avatar
5 votes
0 answers
81 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 ...
user avatar
  • 748
4 votes
1 answer
151 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$ , ...
user avatar
  • 1,006
4 votes
1 answer
162 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 $...
user avatar
  • 1,006
10 votes
2 answers
329 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 ...
user avatar
  • 7,350
6 votes
0 answers
147 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 ...
user avatar
  • 1,006
4 votes
1 answer
132 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 ...
user avatar
  • 305
9 votes
2 answers
280 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{...
user avatar
19 votes
1 answer
427 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'...
user avatar
13 votes
1 answer
352 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$ ...
user avatar
  • 3,160
5 votes
1 answer
316 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 ...
user avatar
  • 2,267
9 votes
2 answers
269 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 ...
user avatar
  • 7,643
19 votes
1 answer
440 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 ...
user avatar
8 votes
2 answers
202 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$...
user avatar
18 votes
1 answer
281 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?
user avatar
  • 289
13 votes
2 answers
275 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 $|...
user avatar
4 votes
1 answer
186 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 ...
user avatar
  • 1,006
6 votes
1 answer
315 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 ...
user avatar
8 votes
2 answers
581 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 ...
user avatar
  • 3,420
11 votes
1 answer
407 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 ...
user avatar
6 votes
0 answers
329 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$?...
user avatar
  • 343
15 votes
1 answer
502 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 ...
user avatar
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, ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 343
3 votes
0 answers
204 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 ...
user avatar
  • 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 ...
user avatar