Jump to content

Bidimensionality: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
No edit summary
Citation bot (talk | contribs)
Added isbn. | Use this bot. Report bugs. | Suggested by Abductive | Category:Analysis of algorithms | #UCB_Category 11/47
 
(21 intermediate revisions by 13 users not shown)
Line 1: Line 1:
'''Bidimensionality''' theory characterizes a broad range of graph problems ('''bidimensional''') that admit efficient approximate, fixed-parameter or kernel solutions in a broad range of graphs. These graph classes include [[planar graph]]s, map graphs, [[Graph embedding|bounded-genus]] graphs and graphs excluding any fixed minor. In particular, bidimensionality theory builds on the [[Minor (graph theory)|Graph Minor Theory]] of [[Neil Robertson (mathematician)|Robertson]] and [[Paul Seymour (mathematician)|Seymour]] by extending the mathematical results and building new algorithmic tools. The theory was introduced in the work of [[Erik Demaine|Demaine]], Fomin, Hajiaghayi, and Thilikos.<ref name="dfht05">{{harvtxt|Demaine|Fomin|Hajiaghayi|Thilikos|2005}}</ref>
'''Bidimensionality''' theory characterizes a broad range of graph problems ('''bidimensional''') that admit efficient approximate, fixed-parameter or kernel solutions in a broad range of graphs. These graph classes include [[planar graph]]s, map graphs, [[Graph embedding|bounded-genus]] graphs and graphs excluding any fixed minor. In particular, bidimensionality theory builds on the [[graph minor]] theory of [[Neil Robertson (mathematician)|Robertson]] and [[Paul Seymour (mathematician)|Seymour]] by extending the mathematical results and building new algorithmic tools. The theory was introduced in the work of [[Erik Demaine|Demaine]], [[Fedor_Fomin|Fomin]], [[Mohammad Hajiaghayi| Hajiaghayi]], and Thilikos,<ref name="dfht05">{{harvtxt|Demaine|Fomin|Hajiaghayi|Thilikos|2005}}</ref> for which the authors received the [[Nerode Prize]] in 2015.


==Definition==
==Definition==
Line 8: Line 8:
# there is <math>\delta > 0</math> such that for every <math>(r \times r)</math>-grid <math>R</math>, <math>(R, k)\not \in \Pi</math> for every <math>k\leq \delta r^2</math>. In other words, the value of the solution on <math>R</math> should be at least <math>\delta r^2</math>.
# there is <math>\delta > 0</math> such that for every <math>(r \times r)</math>-grid <math>R</math>, <math>(R, k)\not \in \Pi</math> for every <math>k\leq \delta r^2</math>. In other words, the value of the solution on <math>R</math> should be at least <math>\delta r^2</math>.


Examples of minor-bidimensional problems are the parameterized versions of [[Vertex cover|Vertex Cover]], [[Feedback vertex set|Feedback Vertex Set]], Minimum Maximal Matching, and [[Longest path problem|Longest Path]].
Examples of minor-bidimensional problems are the parameterized versions of [[vertex cover]], [[feedback vertex set]], minimum maximal matching, and [[longest path]].


[[Image:Gamma graph.jpg|thumb|180px|frameless|right| Graph <math>\Gamma_6</math>]]
[[Image:Gamma graph.jpg|thumb|180px|right| Graph <math>\Gamma_6</math>]]


Let <math>\Gamma_{r}</math> be the graph obtained from the <math>(r\times r)</math>-grid by
Let <math>\Gamma_{r}</math> be the graph obtained from the <math>(r\times r)</math>-grid by
Line 20: Line 20:
# there is <math>\delta > 0</math> such that <math>(\Gamma_r, k)\not \in \Pi</math> for every <math>k\leq \delta r^2</math>.
# there is <math>\delta > 0</math> such that <math>(\Gamma_r, k)\not \in \Pi</math> for every <math>k\leq \delta r^2</math>.


Examples of contraction-bidimensional problems are [[Dominating set|Dominating Set]], [[Connected dominating set|Connected Dominating Set]], Max-Leaf Spanning Tree, and [[Edge dominating set|Edge Dominating Set]].
Examples of contraction-bidimensional problems are [[dominating set]], [[connected dominating set]], max-leaf spanning tree, and [[edge dominating set]].


==Excluding Grid Theorems==
==Excluded grid theorems==
All algorithmic applications of bidimensionality are based on the following combinatorial property: either the [[treewidth]] of a graph is small, or the graph contains a large grid as a minor or contraction. More precisely,
All algorithmic applications of bidimensionality are based on the following combinatorial property: either the [[treewidth]] of a graph is small, or the graph contains a large grid as a minor or contraction. More precisely,


# There is a function ''f'' such that every graph ''G'' excluding a fixed ''h''-vertex graph as a [[Minor (graph theory)|minor]] and of treewidth at least ''f(h)r'' contains '' (r x r)''-grid as a minor.<ref name="dh06">{{harvtxt|Demaine|Hajiaghayi|2008}}</ref>
# There is a function ''f'' such that every graph ''G'' excluding a fixed ''h''-vertex graph as a [[Minor (graph theory)|minor]] and of treewidth at least ''f(h)r'' contains '' (r x r)''-grid as a minor.<ref name="dh06">{{harvtxt|Demaine|Hajiaghayi|2008a}} &nbsp;{{clarify|date=November 2021|reason=Which journal article, If the 101-page article, page should be added.}}</ref>
# There is a function ''g'' such that every graph ''G'' excluding a fixed ''h''-vertex [[apex graph]] as a minor and of treewidth at least ''g(h) r'' can be edge-contracted to <math>\Gamma_r</math>.<ref name="fgt09">{{harvtxt|Fomin|Golovach|Thilikos|2009}}</ref>
# There is a function ''g'' such that every graph ''G'' excluding a fixed ''h''-vertex [[apex graph]] as a minor and of treewidth at least ''g(h) r'' can be edge-contracted to <math>\Gamma_r</math>.<ref name="fgt09">{{harvtxt|Fomin|Golovach|Thilikos|2009}}</ref>

[[Halin's grid theorem]] is an analogous excluded grid theorem for infinite graphs.<ref>{{harvtxt|Diestel|2004}}</ref>


==Subexponential parameterized algorithms==
==Subexponential parameterized algorithms==


Let <math> \Pi </math> be a minor-bidimensional problem such that for any graph ''G'' excluding some fixed graph as a minor and of treewidth at most ''t'', deciding whether <math> (G,k) \in \Pi </math> can be done in time <math> 2^{O(t)}\cdot |G|^{O(1)}</math>. Then for every graph ''G'' excluding some fixed graph as a minor, deciding whether <math> (G,k) \in \Pi </math> can be done in time <math> 2^{O(\sqrt{k})}\cdot |G|^{O(1)}</math>. Similarly, for contraction-bidimensional problems, for graph ''G'' excluding some fixed [[apex graph]] as a minor, inclusion <math> (G,k) \in \Pi </math> can be decided in time <math> 2^{O(\sqrt{k})}\cdot |G|^{O(1)}</math>.
Let <math> \Pi </math> be a minor-bidimensional problem such that for any graph ''G'' excluding some fixed graph as a minor and of treewidth at most ''t'', deciding whether <math> (G,k) \in \Pi </math> can be done in time <math> 2^{O(t)}\cdot |G|^{O(1)}</math>. Then for every graph ''G'' excluding some fixed graph as a minor, deciding whether <math> (G,k) \in \Pi </math> can be done in time <math> 2^{O(\sqrt{k})}\cdot |G|^{O(1)}</math>. Similarly, for contraction-bidimensional problems, for graph ''G'' excluding some fixed [[apex graph]] as a minor, inclusion <math> (G,k) \in \Pi </math> can be decided in time <math> 2^{O(\sqrt{k})}\cdot |G|^{O(1)}</math>.


Thus many bidimensional problems like Vertex Cover, Dominating Set, k-Path, are solvable in time <math> 2^{O(\sqrt{k})}\cdot |G|^{O(1)}</math> on graphs excluding some fixed graph as a minor.
Thus many bidimensional problems like Vertex Cover, Dominating Set, k-Path, are solvable in time <math> 2^{O(\sqrt{k})}\cdot |G|^{O(1)}</math> on graphs excluding some fixed graph as a minor.


==Polynomial Time Approximation Schemes (PTAS)==
==Polynomial time approximation schemes==


Bidimensionality theory has been used to obtain Polynomial Time Approximation Schemes ([[Polynomial-time approximation scheme|PTAS]]) for many bidimensional problems.
Bidimensionality theory has been used to obtain [[polynomial-time approximation scheme]]s for many bidimensional problems.
If a minor (contraction) bidimensional problem has several additional properties <ref name="flrs10">{{harvtxt|Fomin|Lokshtanov|Raman|Saurabh|2010}}</ref><ref name="dh05">{{harvtxt|Demaine|Hajiaghayi|2005}}</ref> then the problem poses Efficient Polynomial Time Approximation Scheme (EPTAS) on (apex) minor-free graphs.
If a minor (contraction) bidimensional problem has several additional properties <ref name="flrs10">{{harvtxt|Fomin|Lokshtanov|Raman|Saurabh|2011}}</ref><ref name="dh05">{{harvtxt|Demaine|Hajiaghayi|2005}}</ref> then the problem poses efficient polynomial-time approximation schemes on (apex) minor-free graphs.


In particular, by making use of Bidimensionality, it was shown that Feedback Vertex Set, Vertex Cover, Connected Vertex Cover, Cycle Packing, Diamond Hitting Set, Maximum Induced Forest, Maximum Induced Bipartite Subgraph and Maximum Induced Planar Subgraph admit an EPTAS on H-minor-free graphs. Edge Dominating Set, Dominating Set, r-Dominating Set, Connected Dominating Set, r-Scattered Set, Minimum Maximal Matching, Independent Set, Maximum Full-Degree Spanning Tree, Max Induced at most d-Degree Subgraph, Max Internal Spanning Tree, Induced Matching, Triangle Packing, Partial r-Dominating Set and Partial Vertex Cover admit an EPTAS on apex-minor-free graphs.
In particular, by making use of bidimensionality, it was shown that [[feedback vertex set]], [[vertex cover]], connected vertex cover, cycle packing, diamond hitting set, maximum induced forest, maximum induced bipartite subgraph and maximum induced planar subgraph admit an EPTAS on H-minor-free graphs. Edge dominating set, [[dominating set]], r-dominating set, connected dominating set, r-scattered set, minimum maximal matching, [[independent set (graph theory)|independent set]], maximum full-degree spanning tree, maximum induced at most d-degree subgraph, [[maximum internal spanning tree]], [[induced matching]], triangle packing, partial r-dominating set and partial vertex cover admit an EPTAS on apex-minor-free graphs.


==Kernelization==
==Kernelization==
Line 48: Line 50:


==Notes==
==Notes==
{{reflist|2}}
{{reflist|colwidth=20em}}


==References==
==References==
{{refbegin}}

*{{citation
*{{citation
| last1 = Demaine| first1 = Erik D.
| last1 = Demaine| first1 = Erik D.
Line 63: Line 65:
| title = Subexponential parameterized algorithms on bounded-genus graphs and ''H''-minor-free graphs
| title = Subexponential parameterized algorithms on bounded-genus graphs and ''H''-minor-free graphs
| volume = 52
| volume = 52
| year = 2005}}.
| year = 2005| arxiv = 1104.2230| s2cid = 6238832
}}.
*{{citation
*{{citation
| last1 = Demaine| first1 = Erik D.
| last1 = Demaine| first1 = Erik D.
Line 75: Line 78:
| title = Bidimensional parameters and local treewidth
| title = Bidimensional parameters and local treewidth
| volume = 18
| volume = 18
| year = 2004}}.
| year = 2004| citeseerx = 10.1.1.81.9021}}.
*{{citation
*{{citation
| last1 = Demaine| first1 = Erik D.
| last1 = Demaine| first1 = Erik D.
Line 92: Line 95:
| title = Linearity of grid minors in treewidth with applications through bidimensionality
| title = Linearity of grid minors in treewidth with applications through bidimensionality
| volume = 28
| volume = 28
| year = 2008}}.
| year = 2008a| s2cid = 16520181
}}.
*{{citation
*{{citation
| last1 = Demaine| first1 = Erik D.
| last1 = Demaine| first1 = Erik D.
Line 99: Line 103:
| issue = 3
| issue = 3
| journal = The Computer Journal
| journal = The Computer Journal
| pages = 332–337
| pages = 292–302
| title = The bidimensionality theory and its algorithmic applications
| title = The bidimensionality theory and its algorithmic applications
| volume = 51
| volume = 51
| year = 2008}}.
| year = 2008b| hdl = 1721.1/33090| hdl-access = free}}.
*{{citation
| last = Diestel | first = R.
| doi = 10.1007/BF02941538
| journal = Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg
| mr = 2112834
| pages = 237–242
| title = A short proof of Halin's grid theorem
| volume = 74
| year = 2004| s2cid = 124603912
}}.
*{{citation
*{{citation
| last1 = Fomin| first1 = Fedor V.
| last1 = Fomin| first1 = Fedor V.
Line 109: Line 123:
| doi = 10.1007/978-3-642-04128-0_63
| doi = 10.1007/978-3-642-04128-0_63
| series = Lecture Notes in Computer Science
| series = Lecture Notes in Computer Science
| title = 17th Annual European Symposium on Algorithms (ESA 2009)
| title = 17th Annual European Symposium on Algorithms (ESA 2009)
| volume = 5757
| volume = 5757
| pages = 706–717
| pages = 706–717
| contribution = Contraction Bidimensionality: The Accurate Picture
| contribution = Contraction Bidimensionality: The Accurate Picture
| year = 2009}}.
| year = 2009| isbn = 978-3-642-04127-3
| url = https://drops.dagstuhl.de/opus/volltexte/2010/2500/
}}.
*{{citation
*{{citation
| last1 = Fomin| first1 = Fedor V.
| last1 = Fomin| first1 = Fedor V.
Line 120: Line 136:
| last4 = Saurabh| first4 = Saket
| last4 = Saurabh| first4 = Saket
| arxiv = 1005.5449 | contribution = Bidimensionality and EPTAS
| arxiv = 1005.5449 | contribution = Bidimensionality and EPTAS
| year = 2010}}.''Proc. 22nd ACM/SIAM Symposium on Discrete Algorithms (SODA 2011), pp. 748-759.''
| year = 2011
| title = Proc. 22nd ACM/SIAM Symposium on Discrete Algorithms (SODA 2011)
| pages = 748–759| bibcode = 2010arXiv1005.5449F}}.
*{{citation
*{{citation
| last1 = Fomin| first1 = Fedor V.
| last1 = Fomin| first1 = Fedor V.
Line 130: Line 148:
| contribution = Bidimensionality and Kernels
| contribution = Bidimensionality and Kernels
| year = 2010}}.
| year = 2010}}.
{{refend}}

==Further reading==
*{{citation
|last1=Cygan|first1=Marek
|last2=Fomin|first2=Fedor V.
|last3=Kowalik|first3=Lukasz
|last4=Lokshtanov|first4=Daniel
|last5=Marx|first5=Daniel
|last6=Pilipczuk|first6=Marcin
|last7=Pilipczuk|first7=Michal
|last8=Saurabh|first8=Saket
|year=2015
|chapter=Chapter 7
|title=Parameterized Algorithms
|publisher=Springer
|isbn=978-3-319-21274-6
|page=612}}
*{{citation
|last1=Fomin|first1=Fedor V.
|last2=Lokshtanov|first2=Daniel
|last3=Saurabh|first3=Saket
|last4=Zehavi|first4=Meirav
|year=2019
|chapter=Chapter 15
|title=Kernelization: Theory of Parameterized Preprocessing
|publisher=Cambridge University Press
|isbn=978-1107057760
|doi=10.1017/9781107415157
|page=528}}


[[Category:Analysis of algorithms]]
[[Category:Analysis of algorithms]]
[[Category:Approximation algorithms]]
[[Category:Graph minor theory]]
[[Category:Graph minor theory]]
[[Category:Parameterized complexity]]
[[Category:Parameterized complexity]]

Latest revision as of 03:09, 18 March 2024

Bidimensionality theory characterizes a broad range of graph problems (bidimensional) that admit efficient approximate, fixed-parameter or kernel solutions in a broad range of graphs. These graph classes include planar graphs, map graphs, bounded-genus graphs and graphs excluding any fixed minor. In particular, bidimensionality theory builds on the graph minor theory of Robertson and Seymour by extending the mathematical results and building new algorithmic tools. The theory was introduced in the work of Demaine, Fomin, Hajiaghayi, and Thilikos,[1] for which the authors received the Nerode Prize in 2015.

Definition

[edit]

A parameterized problem is a subset of for some finite alphabet . An instance of a parameterized problem consists of (x,k), where k is called the parameter.

A parameterized problem is minor-bidimensional if

  1. For any pair of graphs , such that is a minor of and integer , yields that . In other words, contracting or deleting an edge in a graph cannot increase the parameter; and
  2. there is such that for every -grid , for every . In other words, the value of the solution on should be at least .

Examples of minor-bidimensional problems are the parameterized versions of vertex cover, feedback vertex set, minimum maximal matching, and longest path.

Graph

Let be the graph obtained from the -grid by triangulating internal faces such that all internal vertices become of degree 6, and then one corner of degree two joined by edges with all vertices of the external face. A parameterized problem is contraction-bidimensional if

  1. For any pair of graphs , such that is a contraction of and integer , yields that . In other words, contracting an edge in a graph cannot increase the parameter; and
  2. there is such that for every .

Examples of contraction-bidimensional problems are dominating set, connected dominating set, max-leaf spanning tree, and edge dominating set.

Excluded grid theorems

[edit]

All algorithmic applications of bidimensionality are based on the following combinatorial property: either the treewidth of a graph is small, or the graph contains a large grid as a minor or contraction. More precisely,

  1. There is a function f such that every graph G excluding a fixed h-vertex graph as a minor and of treewidth at least f(h)r contains (r x r)-grid as a minor.[2]
  2. There is a function g such that every graph G excluding a fixed h-vertex apex graph as a minor and of treewidth at least g(h) r can be edge-contracted to .[3]

Halin's grid theorem is an analogous excluded grid theorem for infinite graphs.[4]

Subexponential parameterized algorithms

[edit]

Let be a minor-bidimensional problem such that for any graph G excluding some fixed graph as a minor and of treewidth at most t, deciding whether can be done in time . Then for every graph G excluding some fixed graph as a minor, deciding whether can be done in time . Similarly, for contraction-bidimensional problems, for graph G excluding some fixed apex graph as a minor, inclusion can be decided in time .

Thus many bidimensional problems like Vertex Cover, Dominating Set, k-Path, are solvable in time on graphs excluding some fixed graph as a minor.

Polynomial time approximation schemes

[edit]

Bidimensionality theory has been used to obtain polynomial-time approximation schemes for many bidimensional problems. If a minor (contraction) bidimensional problem has several additional properties [5][6] then the problem poses efficient polynomial-time approximation schemes on (apex) minor-free graphs.

In particular, by making use of bidimensionality, it was shown that feedback vertex set, vertex cover, connected vertex cover, cycle packing, diamond hitting set, maximum induced forest, maximum induced bipartite subgraph and maximum induced planar subgraph admit an EPTAS on H-minor-free graphs. Edge dominating set, dominating set, r-dominating set, connected dominating set, r-scattered set, minimum maximal matching, independent set, maximum full-degree spanning tree, maximum induced at most d-degree subgraph, maximum internal spanning tree, induced matching, triangle packing, partial r-dominating set and partial vertex cover admit an EPTAS on apex-minor-free graphs.

Kernelization

[edit]

A parameterized problem with a parameter k is said to admit a linear vertex kernel if there is a polynomial time reduction, called a kernelization algorithm, that maps the input instance to an equivalent instance with at most O(k) vertices.

Every minor-bidimensional problem with additional properties, namely, with the separation property and with finite integer index, has a linear vertex kernel on graphs excluding some fixed graph as a minor. Similarly, every contraction-bidimensional problem with the separation property and with finite integer index has a linear vertex kernel on graphs excluding some fixed apex graph as a minor.[7]

Notes

[edit]

References

[edit]
  • Demaine, Erik D.; Fomin, Fedor V.; Hajiaghayi, MohammadTaghi; Thilikos, Dimitrios M. (2005), "Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs", J. ACM, 52 (6): 866–893, arXiv:1104.2230, doi:10.1145/1101821.1101823, S2CID 6238832.
  • Demaine, Erik D.; Fomin, Fedor V.; Hajiaghayi, MohammadTaghi; Thilikos, Dimitrios M. (2004), "Bidimensional parameters and local treewidth", SIAM Journal on Discrete Mathematics, 18 (3): 501–511, CiteSeerX 10.1.1.81.9021, doi:10.1137/S0895480103433410.
  • Demaine, Erik D.; Hajiaghayi, MohammadTaghi (2005), "Bidimensionality: new connections between FPT algorithms and PTASs", 16th ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 590–601.
  • Demaine, Erik D.; Hajiaghayi, MohammadTaghi (2008a), "Linearity of grid minors in treewidth with applications through bidimensionality", Combinatorica, 28 (1): 19–36, doi:10.1007/s00493-008-2140-4, S2CID 16520181.
  • Demaine, Erik D.; Hajiaghayi, MohammadTaghi (2008b), "The bidimensionality theory and its algorithmic applications", The Computer Journal, 51 (3): 292–302, doi:10.1093/comjnl/bxm033, hdl:1721.1/33090.
  • Diestel, R. (2004), "A short proof of Halin's grid theorem", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 74: 237–242, doi:10.1007/BF02941538, MR 2112834, S2CID 124603912.
  • Fomin, Fedor V.; Golovach, Petr A.; Thilikos, Dimitrios M. (2009), "Contraction Bidimensionality: The Accurate Picture", 17th Annual European Symposium on Algorithms (ESA 2009), Lecture Notes in Computer Science, vol. 5757, pp. 706–717, doi:10.1007/978-3-642-04128-0_63, ISBN 978-3-642-04127-3.
  • Fomin, Fedor V.; Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket (2011), "Bidimensionality and EPTAS", Proc. 22nd ACM/SIAM Symposium on Discrete Algorithms (SODA 2011), pp. 748–759, arXiv:1005.5449, Bibcode:2010arXiv1005.5449F.
  • Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Thilikos, Dimitrios M. (2010), "Bidimensionality and Kernels", 21st ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pp. 503–510.

Further reading

[edit]
  • Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket (2015), "Chapter 7", Parameterized Algorithms, Springer, p. 612, ISBN 978-3-319-21274-6
  • Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav (2019), "Chapter 15", Kernelization: Theory of Parameterized Preprocessing, Cambridge University Press, p. 528, doi:10.1017/9781107415157, ISBN 978-1107057760