pith. sign in

arxiv: 1907.03863 · v1 · pith:PKXJBTYYnew · submitted 2019-07-08 · 💻 cs.DS

The Densest k Subgraph Problem in b-Outerplanar Graphs

Sean Gonzales , Theresa Migler This is my paper

Pith reviewed 2026-05-25 00:29 UTC · model grok-4.3

classification 💻 cs.DS
keywords densest k subgraphouterplanar graphsb-outerplanar graphsexact algorithmdynamic programming
0
0 comments X

The pith

Outerplanar graphs admit an exact O(n k squared) algorithm for the densest k-subgraph problem.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents an exact algorithm that solves the densest k-subgraph problem on outerplanar graphs in O(n k squared) time. It generalizes the approach to b-outerplanar graphs with running time O(n k squared times 8 to the b). A sympathetic reader would care because the problem is NP-hard on general graphs, making polynomial-time cases on restricted graph classes useful for mapping the boundary between easy and hard instances. The authors also put forward the hypothesis that Baker's technique for polynomial-time approximation schemes on planar graphs will not succeed here.

Core claim

We give an exact O(nk^2) algorithm for finding the densest k subgraph in outerplanar graphs. We extend this to an exact O(nk^2 8^b) algorithm for finding the densest k subgraph in b-outerplanar graphs. Finally, we hypothesize that Baker's PTAS technique will not work for the densest k subgraph problem in planar graphs.

What carries the argument

Dynamic programming that exploits the structure of outerplanar graphs and the layered structure of b-outerplanar graphs to track candidate subgraphs of size up to k.

Load-bearing premise

The structure of outerplanar graphs and the layered structure of b-outerplanar graphs permits a dynamic programming solution whose state space and transitions yield exactly the stated time bound without additional hidden factors or correctness gaps.

What would settle it

An outerplanar graph instance on which the algorithm either exceeds the claimed O(n k^2) running time on all inputs or returns a k-vertex subgraph whose density is strictly less than the true maximum.

Figures

Figures reproduced from arXiv: 1907.03863 by Sean Gonzales, Theresa Migler.

Figure 1
Figure 1. Figure 1: The left figure is an example outerplanar graph, [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: figure 3-outerplanar example [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 4
Figure 4. Figure 4: figure Trees for example graph 3.0.2 Slice Construction The dynamic programming solution follows a divide and conquer paradigm, where we divide the graph into so-called slices and calculate the tables for each slice before merging them together. Each vertex in each tree (and hence each interior face and exterior edge in each component of the graph) corresponds to a particular slice. We lay out the construc… view at source ↗
Figure 5
Figure 5. Figure 5: figure Trees with boundary numbers 8 [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: figure Trees with slice boundaries With the definition for boundaries in place, we can now formally define slices. Let v be a level i tree vertex for i ≥ 1 with label (x, y). We denote the slice of v as slice(v), which is defined as follows: (S1) If v represents a level i face f that does not enclose any level i+ 1 components, then slice(v) is the union of the slices of the children of v, together with (x,… view at source ↗
Figure 7
Figure 7. Figure 7: figure Slices for (a, b), (b, d), and (d, a). 3.0.3 Dynamic Program In this section, we detail the dynamic program that solves the densest k subgraph prob￾lem for b-outerplanar graphs. Note that adjust, merge, extend and contract are original whereas the table procedure is given by Baker [2]. The pseudocode for these procedures can be found in Appendix B. The program essentially follows the same recursive … view at source ↗
Figure 8
Figure 8. Figure 8: figure The slice for (c, d) is split into subslices for computing tables. c, E and d, E. We then merge the other subslices in a clockwise fashion, first merging the table for the subslice with subboundaries c, C and c, E, and then merging the table for the subslice with subboundaries c, C and c, B. The adjust procedure, given in [PITH_FULL_IMAGE:figures/full_fig_p012_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: The table procedure. 21 [PITH_FULL_IMAGE:figures/full_fig_p021_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: The adjust procedure. procedure merge(T1, T2) let T be an initially empty table; let L and M be the left and right boundaries of the slice that T1 represents; let M and R be the left and right boundaries of the slice that T2 represents; for each subset A of L ∪ R do for each k 0 = 0, . . . , maxT1 k 0 + maxT2 k 0 − |M| do let V be an initially empty list; for each subset B of M do let n = 0; let x and y b… view at source ↗
Figure 11
Figure 11. Figure 11: The merge procedure. procedure contract(T) let C be the level i + 1 component such that T represents the slice of C; let f be the level i face that contains C; let L and R be the left and right boundaries of the slice of f; let (z, z) be the label of the tree root such that T is a table for slice((z, z)); let T 0 be an initially empty table; for each subset A of L ∪ R do for each k 0 = 0, . . . , maxT k 0… view at source ↗
Figure 12
Figure 12. Figure 12: The contract procedure. 22 [PITH_FULL_IMAGE:figures/full_fig_p022_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: The extend procedure. 23 [PITH_FULL_IMAGE:figures/full_fig_p023_13.png] view at source ↗
read the original abstract

We give an exact $O(nk^2)$ algorithm for finding the densest k subgraph in outerplanar graphs. We extend this to an exact $O(nk^2 8^b)$ algorithm for finding the densest k subgraph in b-outerplanar graphs. Finally, we hypothesize that Baker's PTAS technique will not work for the densest k subgraph problem in planar graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The manuscript presents dynamic programming algorithms for the densest k-subgraph problem. It claims an exact O(n k^2) algorithm for outerplanar graphs and an O(n k^2 8^b) algorithm for b-outerplanar graphs. It also states a hypothesis that Baker's PTAS technique will not work for this problem on planar graphs.

Significance. If the claimed algorithms hold, the results supply the first polynomial-time exact solutions for densest k-subgraph on outerplanar graphs and a singly exponential dependence on the outerplanarity parameter b. The manuscript supplies explicit recurrences realizing the stated time bounds with no hidden polynomial or exponential factors, which strengthens verifiability.

minor comments (1)
  1. [Abstract] Abstract: the hypothesis that Baker's PTAS technique will not work for planar graphs is stated without any supporting argument, counter-example sketch, or reference; if retained, it should be expanded in a dedicated paragraph or section.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their thorough review and positive recommendation to accept the manuscript. We are pleased that the explicit recurrences and time bounds were found to strengthen verifiability.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The manuscript constructs an explicit dynamic program whose states track selected vertices and induced edges over the outerplanar embedding (or b-layered decomposition). The O(nk²) and O(nk² 8^b) bounds follow directly from the per-bag transition sizes stated in the recurrences; these sizes are obtained by enumerating the O(k) or O(1) choices per layer rather than by fitting parameters or invoking prior self-citations. No load-bearing step reduces to a definition of the target quantity, a fitted input renamed as prediction, or an ansatz imported via self-citation. The derivation is therefore self-contained against the graph class and the problem definition.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on domain assumptions about the decomposability of outerplanar graphs; no free parameters or invented entities are introduced.

axioms (1)
  • domain assumption Outerplanar graphs admit an efficient dynamic programming decomposition for the densest k-subgraph problem.
    The O(nk^2) bound depends on this structural property of the graph class.

pith-pipeline@v0.9.0 · 5578 in / 1147 out tokens · 30533 ms · 2026-05-25T00:29:29.283704+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages · 1 internal anchor

  1. [1]

    Dense subgraph maintenance under streaming edge weight updates for real-time story identification

    Albert Angel, Nikos Sarkas, Nick Koudas, and Divesh Srivastava. Dense subgraph maintenance under streaming edge weight updates for real-time story identification. Proc. VLDB Endow., 5(6):574–585, February 2012

    work page 2012

  2. [2]

    Brenda S. Baker. Approximation algorithms for NP-complete problems on planar graphs. Journal of The ACM , 41:153–180, 1994. 16

    work page 1994

  3. [3]

    Approx- imation schemes for steiner forest on planar graphs and graphs of bounded treewidth

    MohammadHossein Bateni, MohammadTaghi Hajiaghayi, and D´ aniel Marx. Approx- imation schemes for steiner forest on planar graphs and graphs of bounded treewidth. CoRR, 2009

    work page 2009

  4. [4]

    Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph

    Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vi- jayaraghavan. Detecting high log-densities – an o(n1/4) approximation for densest k-subgraph. CoRR, abs/1001.2891, 2010

    work page internal anchor Pith review Pith/arXiv arXiv 2010

  5. [5]

    An o(n log n) approximation scheme for steiner tree in planar graphs

    Glencora Borradaile, Philip Klein, and Claire Mathieu. An o(n log n) approximation scheme for steiner tree in planar graphs. ACM Trans. Algorithms, 5:31:1–31:31, July 2009

    work page 2009

  6. [6]

    A scalable pattern mining approach to web graph compression with communities

    Gregory Buehrer and Kumar Chellapilla. A scalable pattern mining approach to web graph compression with communities. In Proceedings of the 2008 International Conference on Web Search and Data Mining , WSDM ’08, pages 95–106, New York, NY, USA, 2008. ACM

    work page 2008

  7. [7]

    Chen and Y

    J. Chen and Y. Saad. Dense subgraph extraction with application to community detection. Knowledge and Data Engineering, IEEE Transactions on , PP(99):1, 2010

    work page 2010

  8. [8]

    Reachability and dis- tance queries via 2-hop labels

    Edith Cohen, Eran Halperin, Haim Kaplan, and Uri Zwick. Reachability and dis- tance queries via 2-hop labels. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms , SODA ’02, pages 937–946, Philadelphia, PA, USA, 2002. Society for Industrial and Applied Mathematics

    work page 2002

  9. [9]

    Corneil and Y

    D.G. Corneil and Y. Perl. Clustering and domination in perfect graphs. Discrete Applied Mathematics, 9(1):27 – 39, 1984

    work page 1984

  10. [10]

    Lee, and John H

    Xiaoxi Du, Ruoming Jin, Liang Ding, Victor E. Lee, and John H. Thornton, Jr. Migration motif: A spatial - temporal pattern mining approach for financial markets. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , KDD ’09, pages 1135–1144, New York, NY, USA, 2009. ACM

    work page 2009

  11. [11]

    Goodrich

    David Eppstein and Michael T. Goodrich. Studying (non-planar) road networks through an algorithmic lens. In Proceedings of the 16th ACM SIGSPATIAL Interna- tional Conference on Advances in Geographic Information Systems , GIS ’08, pages 16:1–16:10, New York, NY, USA, 2008. ACM

    work page 2008

  12. [12]

    Crossing patterns in nonplanar road networks

    David Eppstein and Siddharth Gupta. Crossing patterns in nonplanar road networks. In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems , SIGSPATIAL ’17, pages 40:1–40:9, New York, NY, USA, 2017. ACM

    work page 2017

  13. [13]

    The dense k-subgraph problem

    Uriel Feige, Guy Kortsarz, and David Peleg. The dense k-subgraph problem. Algo- rithmica, 29:2001, 1999

    work page 2001

  14. [14]

    Fratkin, B

    E. Fratkin, B. T. Naughton, D. L. Brutlag, and S. Batzoglou. Motifcut: regulatory motifs finding with maximum density subgraphs. In Bioinformatics, pages 150–157, 2006. 17

    work page 2006

  15. [15]

    Inferring web communities from link topology

    David Gibson, Jon Kleinberg, and Prabhakar Raghavan. Inferring web communities from link topology. In Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space—structure in hypermedia systems: links, objects, time and space—structure in hypermedia systems , HYPERTEXT ’98, pages 225–234, New York, NY, USA, 1998. ACM

    work page 1998

  16. [16]

    Discovering large dense subgraphs in massive graphs

    David Gibson, Ravi Kumar, and Andrew Tomkins. Discovering large dense subgraphs in massive graphs. In Proceedings of the 31st international conference on Very large data bases, VLDB ’05, pages 721–732. VLDB Endowment, 2005

    work page 2005

  17. [17]

    Dense subgraph recovery

    Aristides Gionis and Charalampos Tsourakakis. Dense subgraph recovery. In KDD, 2015

    work page 2015

  18. [18]

    A. V. Goldberg. Finding a maximum density subgraph. Technical report, University of California at Berkeley, Berkeley, CA, USA, 1984

    work page 1984

  19. [19]

    Mark Keil and Timothy B

    J. Mark Keil and Timothy B. Brecht. The complexity of clustering in planar graphs. The Journal of Combinatorial Mathematics and Combinatorial Computing , 9:155– 159, 1991

    work page 1991

  20. [20]

    Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique

    Subhash Khot. Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput. , 36:1025–1071, December 2006

    work page 2006

  21. [21]

    Philip N. Klein. A linear-time approximation scheme for tsp in undirected planar graphs with edge-weights. SIAM J. Comput. , 37:1926–1952, 2008

    work page 1926

  22. [22]

    Langston, Lan Lin, Xinxia Peng, Nicole E

    Michael A. Langston, Lan Lin, Xinxia Peng, Nicole E. Baldwin, Christopher T. Symons, Bing Zhang, and Jay R. Snoddy. A combinatorial approach to the analysis of differential gene expression data: The use of graph algorithms for disease prediction and screening. In Methods of Microarray Data Analysis IV , pages 223–238. Springer Verlag, 2005

    work page 2005

  23. [23]

    M. E. J. Newman. Fast algorithm for detecting community structure in networks. Phys. Rev. E , 69:066133, Jun 2004

    work page 2004

  24. [24]

    Event detection in activity networks

    Polina Rozenshtein, Aris Anagnostopoulos, Aristides Gionis, and Nikolaj Tatti. Event detection in activity networks. In Proceedings of the 20th ACM SIGKDD Interna- tional Conference on Knowledge Discovery and Data Mining , KDD ’14, pages 1176– 1185, New York, NY, USA, 2014. ACM. A A Complete Set of Tables for the Example in Figure 1 As mentioned in Sectio...

    work page 2014