Search Results

Documents authored by McFarland, Caleb

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.38
Almost All Graphs Are Vertex-Minor Universal

Authors: Ruben Ascoli, Bryce Frederickson, Sarah Frederickson, Caleb McFarland, and Logan Post

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract
Answering a question of Claudet, we prove that the uniformly random graph G∼ 𝔾(n, 1/2) is Ω(√n)-vertex-minor universal with high probability. That is, for some constant α≈ 0.911, any graph on any α√ n specified vertices of G can be obtained as a vertex-minor of G. This has direct implications for quantum communications networks: an n-vertex k-vertex-minor universal graph corresponds to an n-qubit k-stabilizer universal graph state, which has the property that one can induce any stabilizer state on any k qubits using only local operations and classical communications. We further employ our methods in two other contexts. We obtain a bipartite pivot-minor version of our main result, and we use it to derive a universality statement for minors in random binary matroids. We also introduce the vertex-minor Ramsey number R_{vm}(k) to be the smallest value n such that every n-vertex graph contains an independent set of size k as a vertex-minor. Supported by our main result, we conjecture that R_{vm}(k) is polynomial in k. We prove Ω(k²) ≤ R_{vm}(k) ≤ 2^k - 1.
Cite as

Ruben Ascoli, Bryce Frederickson, Sarah Frederickson, Caleb McFarland, and Logan Post. Almost All Graphs Are Vertex-Minor Universal. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 38:1-38:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ascoli_et_al:LIPIcs.APPROX/RANDOM.2026.38,
  author =	{Ascoli, Ruben and Frederickson, Bryce and Frederickson, Sarah and McFarland, Caleb and Post, Logan},
  title =	{{Almost All Graphs Are Vertex-Minor Universal}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{38:1--38:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.38},
  URN =		{urn:nbn:de:0030-drops-277559},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.38},
  annote =	{Keywords: vertex-minors, random graphs, quantum networks, graph states}
}
Document
DOI: 10.4230/LIPIcs.WG.2026.33
Totally Δ-Modular Tree Decompositions of Graphic Matrices for Integer Programming

Authors: Caleb McFarland

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

Abstract
We introduce the tree-decomposition-based parameter totally Δ-modular treewidth (TDM-treewidth) for matrices with two nonzero entries per row. We show how to solve integer programs whose matrices have bounded TDM-treewidth in polynomial time when variables have bounded domain. This extends previous graph-based decomposition parameters for matrices with at most two nonzero entries per row to include matrices with entries outside of {-1,0,1}. We also give an analogue of the Grid Theorem of Robertson and Seymour for matrices of bounded TDM-treewidth in the language of rooted signed graphs.
Cite as

Caleb McFarland. Totally Δ-Modular Tree Decompositions of Graphic Matrices for Integer Programming. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 33:1-33:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{mcfarland:LIPIcs.WG.2026.33,
  author =	{McFarland, Caleb},
  title =	{{Totally \Delta-Modular Tree Decompositions of Graphic Matrices for Integer Programming}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{33:1--33:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.33},
  URN =		{urn:nbn:de:0030-drops-261992},
  doi =		{10.4230/LIPIcs.WG.2026.33},
  annote =	{Keywords: Integer programming, subdeterminants, independent set, rooted graphs, signed graphs, odd cycle packing number}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.64
Odd-Cycle-Packing-Treewidth: On the Maximum Independent Set Problem in Odd-Minor-Free Graph Classes

Authors: Mujin Choi, Maximilian Gorsky, Gunwoo Kim, Caleb McFarland, and Sebastian Wiederrecht

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
We introduce the tree-decomposition-based graph parameter Odd-Cycle-Packing-treewidth (OCP-tw) as a width parameter that asks to decompose a given graph into pieces of bounded odd cycle packing number. The parameter OCP-tw is monotone under the odd-minor-relation and we provide an analogue to the celebrated Grid Theorem of Robertson and Seymour for OCP-tw. That is, we identify two infinite families of grid-like graphs whose presence as odd-minors implies large OCP-tw and prove that their absence implies bounded OCP-tw. This structural result is constructive and implies a 2^poly(k) poly(n)-time parameterized poly(k)-approximation algorithm for OCP-tw. Moreover, we show that the (weighted) Maximum Independent Set problem (MIS) can be solved in polynomial time on graphs of bounded OCP-tw. Finally, we lift the concept of OCP-tw to a parameter for matrices of integer programs. To this end, we show that our strategy can be applied to efficiently solve integer programs whose matrices have entries in {-1,0,1} and can be "tree-decomposed" into totally Δ-modular matrices with at most two non-zero entries per row.
Cite as

Mujin Choi, Maximilian Gorsky, Gunwoo Kim, Caleb McFarland, and Sebastian Wiederrecht. Odd-Cycle-Packing-Treewidth: On the Maximum Independent Set Problem in Odd-Minor-Free Graph Classes. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 64:1-64:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{choi_et_al:LIPIcs.ICALP.2026.64,
  author =	{Choi, Mujin and Gorsky, Maximilian and Kim, Gunwoo and McFarland, Caleb and Wiederrecht, Sebastian},
  title =	{{Odd-Cycle-Packing-Treewidth: On the Maximum Independent Set Problem in Odd-Minor-Free Graph Classes}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{64:1--64:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.64},
  URN =		{urn:nbn:de:0030-drops-264533},
  doi =		{10.4230/LIPIcs.ICALP.2026.64},
  annote =	{Keywords: Odd-minor, treewidth, parameterized algorithm, graph minor, structural graph theory, Odd-Cycle-Packing-treewidth, Maximum Independent Set problem}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact