Algorithm Design 5

发表于 分类于 ， 阅读次数： 本文字数： 1.2k 阅读时长 ≈ 4 分钟
[2023 秋] 算法设计 第五课课堂笔记 / [2023 Fall] Algorithm Design Lecture 5 Notes

Chapter 3 Dynamic Programming

3.4.2 Treewidth cond.

Extension : [ Roberson , Seymour ] [ Graph Minor THM ]

1983 - 2004 , 20 papers , 500 pages

  1. Def [ Minor ] : a minor of \(G\) can be obtained by contracting edges and deletion of nodes/edges from \(G\)

    contract edge : \(e=\{u,v\}\) , contract it : then merge \({u,v}\) as a new vertex .

  2. Def [ Minor-closed ] : A graph family \(\mathcal F\) of graph is minor-closed if \(\forall G\in \mathcal F\) , the minor of \(G\in \mathcal F\)

    E.g. : \(\mathcal F=\{\text{forests}\}\) , \(\mathcal F=\{\text{planar graph}\}\) , \(\mathcal F=\{\text{graphs with }tw\le k\}\) are all minor-closed

  3. Thm [ Wagner-Kuratowski THM ] : planar graph \(\Leftrightarrow\) no \(K_{3,3} , K_5\) as minors

    Likewise : forests \(\Leftrightarrow\) no \(K_3\) as minors

  4. Thm [ Graph Minor THM ] : a minor-closed family \(\Leftrightarrow\) no \(H\) as minors , \(H\) is a finite graph set

  5. Application : Fixed Parameter Tractable

3.5 Shortest Path (Bellman-Ford)

  1. Description

    directed graph \(G=(V,E)\) , \(w_e\in \mathbb R\) , \(G\) has no negative cycle . ( not necessarily \(w_e\ge 0\) )

    Find shortest path for all vertices to \(t\) .

  2. Algorithm

    \(opt(i,v)\) : using at most \(i\) edges , the shortest path from \(v\) to \(t\) . \[ opt(i,v)=\min\begin{cases} opt(i-1,v)\\ \min_u\{opt(i-1,u)+w_{v\to u}\} \end{cases} \] Time Complexity : \(\mathcal O(nm)\) .

    Memory Complexity : \(\mathcal O(n^2)\) . ( at most using \(n-1\) edges )

  3. Optimize Memory Complexity \[ opt(v)=\min\begin{cases} opt(v)\\ \min_{(v,u)\in E}\{opt(u)+w_{v\to u}\} \end{cases} \] Iterate the update \(n\) times .

    Note : may using \(opt(i,u)\) , but we do not care about the really number of edges in the shortest path .

    Observation : After \(i\) iterations , \(opt(v)\) is not larger than \(opt(i,v)\)

  4. Find the Shortest Path

    Construct a pointer graph \(P=\{(v,first[v])|v\in V\backslash\{t\}\}\) :

    \(\forall v\in V\) , \(first[v]\) : the first node on the \(v\to t\) path after \(v\) .

    Compute \(first[v]\) : When \(opt(v)\) is updated by \(opt(u)+w_{v\to u}\) , let \(first[v]=u\) .

    Observation : After all iterations , \(\{(v,first[v])|v\in V\backslash \{t\}\}\) forms a shortest path tree .

  5. Lemma 1 : Suppose \(G\) has no negative cycle . At the termination of the algorithm , \(P\) is the a shortest path tree rooted at \(t\) .

    Proof : [ Induction like ]

    If \(first[v]=u\) , then \(opt(v)=opt(u)+w_{v\to u}\)

    \(opt(u)\) is the shortest \(u\to t\) path . Therefore , the cost of \(u\to t\) path on \(P\) is smallest . Therefore , the cost of \(v\to t\) path on \(P\) is smallest .

  6. Lemma 2 : If \(P\) contains a cycle \(C\) at any stage , then \(cost(C)<0\)

    Proof : Let \(C=\{v_1,v_2,\cdots,v_k\}\) .

    If \(first[v]=u\) , then \(opt(v)\ge w_{v\to u} +opt(u)\) .

    If \(opt(v)<w_{v\to u}+opt(u)\) , then \(v\) is updated by other \(u'\) , so \(first[v]\neq u\) .

    Therefore , \(opt(v_1)\ge w_{v_1\to v_2}+opt(v_2)\) , \(opt(v_2)\ge w_{v_2\to v_3}+opt(v_3)\) , \(\cdots\) , \(opt(v_k)\ge w_{v_k \to v_1} +opt(v_1)\) .

    Therefore , \(cost(C)=\sum_{i=1}^k w_{v_i\to v_{i+1}}\le 0\) .

    Consider the time before we update the last cycle edge , suppose that it is \(v_k\to v_1\) .

    Therefore , exactly before the update , \(opt(v_k)>w_{v_k\to v_1}+opt(v_1)\) , so at this time the inequality is strict .

  7. Note : If exists negative cycle , there may still exist finite shortest-path vertices and \(+\infty\) shortest-path vertices .

Chapter 4 NP Completeness

  1. [ Cook , Karp ]

    \(NPC\subset NP\) , poly-time reduction

    \(P\neq NP\) conjecture

4.1 Polynomial Time Reduction

  1. using poly-time as measure ?

    different computation model can have different power constant ( \(\mathcal O(n^2,n^3,\cdots)\) )

  2. Def [ polynomial-time reduction ] : If a problem \(Y\) can be solved in poly-time plus an oracle that solves problem \(X\) , then \(Y\) is poly-time reducible to \(X\) , denote as \(Y\le_P X\) .

    1. Def [ oracle ] : an oracle for \(X\) is a "black-box" , input an instance of \(X\) and can output the answer in \(\mathcal O(1)\) time .

      Even if \(X\) itself cannot be solved in \(\mathcal O(1)\) .

    2. \(Y\le _P X\) : \(X\) is more powerful than \(Y\) ( i.e. \(Y\) is not harder than \(X\) )

  3. Properties

    1. If \(Y\le_P X\) , \(X\) is poly-solvable , then \(Y\) is poly-solvable
    2. If \(Y\le_P X\) , \(Y\) cannot be solved in poly-time , then \(X\) cannot be solved in poly-time

  4. [ Cook , Karp ] :

    Intuitive : If \(Y\le_P X\) , then connect a directed edge \(Y\to X\) . Then there exists a class of Problems \(\mathcal C\) . \(\forall C\in \mathcal C,\forall X\in \mathcal P\) , there exists a directed edge \(X\to C\) .

4.2 Examples of Poly-reduction

  1. Independent Set Problem

    \(IS=(G(V,E),k)\) .

    Independent set : \(I\subseteq V\) , s.t. \(\forall u,v\in I,(u,v)\notin E\) .

    Ask whether there exists an Independent Set of size at least \(k\) .

  2. Vertex Cover Problem

    \(VC=(G(V,E),h)\) .

    Vertex Cover : \(C\subseteq V\) , s.t. \(\forall (u,v)\in E\) , either \(u\in C\) or \(v\in C\) .

    Ask whether there exists a Vertex Cover of size at most \(h\) .

  3. \(IS\le_P VC\)

    Lemma : \(I\) is an Independent Set \(\Leftrightarrow\) \(V\backslash I\) is a Vertex Cover

  4. Set Cover Problem

    \(SC=(U,\{S_1,\cdots,S_m\},h)\) .

    \(U\) : universe . \(S_1,\cdots,S_m\subseteq U\) .

    Set Cover : \(I\subseteq [m]\) , s.t. \(\bigcup_{i\in I}S_i=U\) .

    Ask whether there exists a Set Cover of size at most \(h\) .

  5. \(VC\le_P SC\)

    Let \(S_i=\{e\in E|i\in e\}\) , \(U=E\) .

4.3 NP-Complete Problem

  1. Def [ NP ] : Only consider decision problems ( output Y/N )

    A decision problem \(X\) , we can consider \(X\) as a collection of YES instances.

    1. Def [ Efficient Verifier ] : \(V(x,\pi)\) is an efficient verifier for problem \(X\) if

      • \(V\) is a poly-time algorithm with \(x\) and \(\pi\)

      • \(x\in X\) \(\Leftrightarrow\) \(\exists \pi , |\pi|\le poly(|x|) , V(x,\pi)=1\)

      \(\pi\) : certificate / proof

    2. Def [ P ] : The class of all problems \(X\) , s.t. there exists a poly-time algorithm that solves \(X\) .

    3. Def [ NP ] : The class of all problems \(X\) , s.t. there exists an efficient verifier for \(X\) .

  2. Def [ NP-Complete ] : A problem \(X\) is NPC if

    • \(X\in NP\)
    • \(\forall Y\in NP\) , \(Y\le_P X\)

  3. Properties of NPC

    1. \(\forall X\in NPC\) , if \(X\in P\) , then \(P=NP\)
    2. \(\forall X,Y\in NPC\) , \(X\le_P Y\) and \(Y\le_P X\)

  4. Thm [ Cook-Levin 1971 , the first NPC problem ] : SAT is NPC

    1. Def [ SAT ] : a formula \(F\) of \(0/1\) variables \(\{x_n\}\) and \(\land,\lor,\lnot\) .

      Fix some variables , determine whether there exists an assignment of \(\{x_n\}\) s.t. \(F=true\) .

    2. Proof ( high-level sketch )

      SAT \(\in\) NP : given an assignment , can verify

      \(\forall X\in NP,X\le_P SAT\) :

      efficient verifier for \(X\) : can be write as logic-circuit form

      \(V(x,\pi)\) : \(x\) as fixed , \(\pi\) as assignment .