DSDP-THETA(1)

📦 version 5.8, in fedora 43, fedora 44

💜 DSDP-THETA — the Lovasz Theta number, but make it iconic 💜

okay bestie, listen. this is the manual page for dsdp-theta, a User Commands situation, and it's genuinely one of my faves. we're computing the Lovasz Theta number of a graph. that's it. that's the whole job. let's get into it 💅

✨ NAME ✨

dsdp-theta — compute the Lovasz Theta number of a graph 🦋

🌸 SYNOPSIS 🌸

dsdp-theta [OPTIONS] GRAPH_FILE

that's it. options, then a graph file. no cap. 🎀

👑 DESCRIPTION 👑

so here's the tea 🍓: the dsdp-theta program uses the DSDP library to compute the Lovasz Theta number of an input graph. and bestie, this number is not just some random number, it is doing SO much heavy lifting:

  • it's an upper bound for the maximum clique of a graph 🫶
  • it's a lower bound for the minimal graph coloring ✨
  • and it serves as a bound for several other combinatorial graph problems too 🌈

the number itself is the solution to a semidefinite program. main character math behavior, honestly. 💅

⚠️ okay this part matters, so pay attention: the input file should be the complement of the graph. not the graph. the complement. i know. i know. but that's the vibe. 🙈

also, fun fact: this file also demonstrates the use of customized data matrices in DSDP. so it's lowkey a teaching moment too. iconic. 👑

💖 OPTIONS 💖

  • -dloginfo N — sets the logging level (default 0). the higher the number, the more information gets printed. so if you want the whole gossip, crank that N up. 📈
  • -params FILE — reads DSDP parameters from FILE. give it a file, it'll read the params. simple as. 🎀
  • -help — prints a help message. bestie behavior when you're lost. 🫶

🌈 FILE FORMAT 🌈

the input file needs to be in exactly this format, okay? no improvising:

n m
r1 c1 [w1]
…
im jm [wm]

let me break it down for you 🧚:

  • n is the number of nodes
  • m is the number of edges
  • each r/c pair or r/c/w triple describes one edge, where:
    • r is the row
    • c is the column
    • w is the weight
  • and the weight? ignored, if present. so you can include it, you can skip it, the program literally does not care. 💀

🦋 SEE ALSO 🦋

go read these too, they're all in the family:

and that's the whole page bestie!! this one comes from DSDP, version 5.8, and it lives in section 1 as DSDP-THETA(1). slay, go compute some theta numbers, and remember: complement of the graph. always. periodt. 💜✨🎀

📦 where this page comes from